Weet er nog iemand van 1ste lic wat de vragen waren?
greetz
[AlgEnComp] examen vragen algoritmen&complexiteit
Moderator: Praesidium
De eerste vraag ging over het relatieve startadres van een dynamische array in de P-machine. Wat dit is en hoe dit wordt gebruikt. En de bijvraag daar was waarom dat de d2,...,dk ook wordt opgeslagen vermits die kunnen berekend worden vanuit ui en oi. (Staat letterlijk in de copy's over de pmachine)
2e vraag werd er gevraagd om een attributengrammatica op te stellen die aan bepaalde voorwaarde voldeed. Niet zo moeilijk en een stukje vanzelfsprekend maar redelijk wat schrijfwerk.
3e vraag (en laatste) werd er gevraagd om de control flow graph op te stellen voor de repeat en while lus. En werd er gevraagd om symbolic interpretation in eigen woorden uit te leggen.
Het examen was open boek en duurde max 2 uur. Dus een raad: weet waar dat alles staat en zie dache snapt over wa dache bezig zijt en dan zal dat wel lukken.
Enjoy
2e vraag werd er gevraagd om een attributengrammatica op te stellen die aan bepaalde voorwaarde voldeed. Niet zo moeilijk en een stukje vanzelfsprekend maar redelijk wat schrijfwerk.
3e vraag (en laatste) werd er gevraagd om de control flow graph op te stellen voor de repeat en while lus. En werd er gevraagd om symbolic interpretation in eigen woorden uit te leggen.
Het examen was open boek en duurde max 2 uur. Dus een raad: weet waar dat alles staat en zie dache snapt over wa dache bezig zijt en dan zal dat wel lukken.
Enjoy
-
HyperQuantum
- Posts: 61
- Contact:
Inderdaad. Maar jij maakt hier dezelfde foutHmm, algoritmen en complexiteit is iets anders dan talen & compilers hé maarten
Ik heb het examen A&C ook gedaan dit jaar, en dat van die petri net zat er zeker niet bij. Die vraag komt waarschijnlijk van talen&correctheid, wat iets anders is dan algoritmen&complexiteitIk herinner mij alleen nog van A&C dat het een vrij makkelijk examen was, en dat er een vraag was over een petri net van verkeerslichten op een kruispunt...
Woeps,
Allesinds voor zij die dus nen tuyaux willen maken, ge hebt er nu al veel vragen, maar nog wel niet de juiste voor Algoritmen en Complexiteit.
Ik herriner me wel dat dat ook niet al te moeilijk was dat examen en dat de tijd dat ge er voor kreeg wel voldoende was om redelijk tot zeer veel op te kunnen zoeken.
Maakt nen index van alles met papierekes aan de zijkant of zo en dan zal da wel gaan.
Sorry dak de vragen niet meer heriner.
Allesinds voor zij die dus nen tuyaux willen maken, ge hebt er nu al veel vragen, maar nog wel niet de juiste voor Algoritmen en Complexiteit.
Ik herriner me wel dat dat ook niet al te moeilijk was dat examen en dat de tijd dat ge er voor kreeg wel voldoende was om redelijk tot zeer veel op te kunnen zoeken.
Maakt nen index van alles met papierekes aan de zijkant of zo en dan zal da wel gaan.
Sorry dak de vragen niet meer heriner.
-
Quintus Maximus
- Posts: 222
Tuyaux
Vragen die in de afgelopen jaren zijn gesteld:
Voor de algoritmes waarvan gevraagd wordt de complexiteiten te berkenen, moet je maar de Tuyaux zelf eens bestuderen.
In de Tuyaux staan andere pagina nummers dan hier, dat is omdat ik ze up to date heb gebracht met onze syllabus.
Januari 2001
Gegeven een algoritme bereken tijds/plaats complexiteit in uniform/logaritmisch kost criterium.
p29: Leg uitvoeriger uit waarom er O(T(n)*log(T(n))) komt voor het logaritmisch kost criterium. In het bijzonder : de opmerking over "het grootste getal".
p32: Waar faalt deze redenirong voor uniforme kost?
p66: Waarom kan een knoop geen hoofdknoop zijn van 2 verschillende i, Bewijs.
p102-104: Wat is precies het belang van het feit dat de lengte van de 8 delen O(p(n)), O(p^3(n)),... is?
Juni 2002:
p32: Leg uit waarom het bewijs niet geldig is voor het uniform kost criterium.
p40: Waarom is padding niet efficient?
p85: Verklaar de vergelijking: D(T) = i + D(Tl) + (n - i) + D(Tr)
Gegeven een algoritme bereken tijds/plaats complexiteit in uniform/logaritmisch kost criterium.
September 2002:
p32 Simulatie van RAM door DTM
- Verder uitwerken van MULT instructie zodat de logaritmische kost van de simulatie <= kwadraat van logaritmische kost van instructie die gesimuleerd wordt.
p65: Leg uit hoe je die stellen waarden concreet zou kiezen. Bewijs dat dat mogelijk is. (concreet uitleggen van keuze van stellen waarden)
p66: Waarom kan een knoop geen hoofdknoop zijn van meer dan 1 waarde i?.
Laat Sigma = {1,2,3}
Geef een algoritme dat het eerste deelwoord zoekt zodat de som van de waarden van de cijfers erin = 10 (zie oefeningenreeks 7)
p97: Bewijs de 2 stellingen bovenaan, en de stelling onderaan.
Voor de algoritmes waarvan gevraagd wordt de complexiteiten te berkenen, moet je maar de Tuyaux zelf eens bestuderen.
In de Tuyaux staan andere pagina nummers dan hier, dat is omdat ik ze up to date heb gebracht met onze syllabus.
Januari 2001
Gegeven een algoritme bereken tijds/plaats complexiteit in uniform/logaritmisch kost criterium.
p29: Leg uitvoeriger uit waarom er O(T(n)*log(T(n))) komt voor het logaritmisch kost criterium. In het bijzonder : de opmerking over "het grootste getal".
p32: Waar faalt deze redenirong voor uniforme kost?
p66: Waarom kan een knoop geen hoofdknoop zijn van 2 verschillende i, Bewijs.
p102-104: Wat is precies het belang van het feit dat de lengte van de 8 delen O(p(n)), O(p^3(n)),... is?
Juni 2002:
p32: Leg uit waarom het bewijs niet geldig is voor het uniform kost criterium.
p40: Waarom is padding niet efficient?
p85: Verklaar de vergelijking: D(T) = i + D(Tl) + (n - i) + D(Tr)
Gegeven een algoritme bereken tijds/plaats complexiteit in uniform/logaritmisch kost criterium.
September 2002:
p32 Simulatie van RAM door DTM
- Verder uitwerken van MULT instructie zodat de logaritmische kost van de simulatie <= kwadraat van logaritmische kost van instructie die gesimuleerd wordt.
p65: Leg uit hoe je die stellen waarden concreet zou kiezen. Bewijs dat dat mogelijk is. (concreet uitleggen van keuze van stellen waarden)
p66: Waarom kan een knoop geen hoofdknoop zijn van meer dan 1 waarde i?.
Laat Sigma = {1,2,3}
Geef een algoritme dat het eerste deelwoord zoekt zodat de som van de waarden van de cijfers erin = 10 (zie oefeningenreeks 7)
p97: Bewijs de 2 stellingen bovenaan, en de stelling onderaan.
[img]http://users.skynet.be/quintensoetens/sigG4.jpg[/img]
-
Quintus Maximus
- Posts: 222
Da zijn triviale bewijskes zeh.
Stelling Als L1 -p> L2 en L2 -p> L3 dan L1-p>L3
Bewijs er is dus een reductie die in polinomiale tijd p1(n) van L1 L2 maakt.
er is een reductie die in polinomiale tijd p2(n) van L2 L3 maakt.
dus om van L1 L3 te maken maken we eerst L2 in p1(n) en daarvan maken we dan L3.
dus om van L1 naar L3 te gaan is dit in tijd p2(p1(n)) wat ook een polynoom is.
Stelling Als L2 in P-Time zit en L1 -p> L2 dan is L1 in P-Time
Er bestaat dus een deterministische tering machine die in polynomiale tijd
L2 oplost.
Er is een polynomiaal algoritme dat van L1 L2 maakt.
Een polynomiaal algoritme is voorstelbaar op een deterministische wijze.
dus je kan een deterministische turing machine maken die eerst het polynomiaal reductie algoritme toepast en dan de machine van L2 toepast.
deze turing machine lost L1 op.
Stelling Als er een NP complete taal bestaat die behoort tot P-Time dan geldt P-Time = NP-Time
een taal is NP compleet als alle talen in NP-Time polynomiaal gereduceert kunnen worden naar die taal. Hier kunnen we dus de vorige stelling gebruiken. Een taal L zit in P-Time en is NP-Compleet dan is als een taal polynomiaal reduceert naar L die taal in P-Time, nu reduceren alle talen in NP-Time naar L dus alle talen in NP-Time zitten in P-Time.
Stelling Laat L1, L2 in NP-Time met L1 NP-Compleet en L1 -p> L2 Dan is L2 ook NP-Compleet.
Als alle talen in NP-Time polynomiaal reduceren naar L1 en L1 reduceert polynomiaal naar L2 dan reduceren alle talen in NP-Time polynomiaal naar L2 (wegens de eerste stelling) dus L2 is ook NP-Compleet
Mijn excuses als het nogal onoverzichtelijke bewijsjes zijn, maar het is maar gewoon een schets en ik had niet zo veel tijd ...
Stelling Als L1 -p> L2 en L2 -p> L3 dan L1-p>L3
Bewijs er is dus een reductie die in polinomiale tijd p1(n) van L1 L2 maakt.
er is een reductie die in polinomiale tijd p2(n) van L2 L3 maakt.
dus om van L1 L3 te maken maken we eerst L2 in p1(n) en daarvan maken we dan L3.
dus om van L1 naar L3 te gaan is dit in tijd p2(p1(n)) wat ook een polynoom is.
Stelling Als L2 in P-Time zit en L1 -p> L2 dan is L1 in P-Time
Er bestaat dus een deterministische tering machine die in polynomiale tijd
L2 oplost.
Er is een polynomiaal algoritme dat van L1 L2 maakt.
Een polynomiaal algoritme is voorstelbaar op een deterministische wijze.
dus je kan een deterministische turing machine maken die eerst het polynomiaal reductie algoritme toepast en dan de machine van L2 toepast.
deze turing machine lost L1 op.
Stelling Als er een NP complete taal bestaat die behoort tot P-Time dan geldt P-Time = NP-Time
een taal is NP compleet als alle talen in NP-Time polynomiaal gereduceert kunnen worden naar die taal. Hier kunnen we dus de vorige stelling gebruiken. Een taal L zit in P-Time en is NP-Compleet dan is als een taal polynomiaal reduceert naar L die taal in P-Time, nu reduceren alle talen in NP-Time naar L dus alle talen in NP-Time zitten in P-Time.
Stelling Laat L1, L2 in NP-Time met L1 NP-Compleet en L1 -p> L2 Dan is L2 ook NP-Compleet.
Als alle talen in NP-Time polynomiaal reduceren naar L1 en L1 reduceert polynomiaal naar L2 dan reduceren alle talen in NP-Time polynomiaal naar L2 (wegens de eerste stelling) dus L2 is ook NP-Compleet
Mijn excuses als het nogal onoverzichtelijke bewijsjes zijn, maar het is maar gewoon een schets en ik had niet zo veel tijd ...
[img]http://users.skynet.be/quintensoetens/sigG4.jpg[/img]
-
Guest
Who is online
Users browsing this forum: No registered users and 55 guests