Post#7 » Sun Jun 11, 2006 5:05 pm
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.
[img]http://users.skynet.be/quintensoetens/sigG4.jpg[/img]