Werkblad Algoritmen & complexiteit met antwoorden

Welke notatie beschrijft een ondergrens voor de groei?

1. AΘ (grote theta)
2. BΩ (grote omega)
3. Co (kleine o)
4. DO (grote O)

Welke hiervan groeit het langzaamst als n groot wordt?

1. AO(log n)
2. BO(n)
3. CO(n log n)
4. DO(n²)

Wat is een algoritme?

1. AEen datastructuur die getallen opslaat
2. BEen eindige reeks goed gedefinieerde stappen die een probleem oplost
3. CEen programmeertaal die is ontworpen om wiskundige formules te schrijven
4. DElk computerprogramma met een grafische interface

Wat is de oplossing van de recurrente betrekking T(n) = 2T(n − 1) + O(1)?

1. AO(n²)
2. BO(n log n)
3. CO(n)
4. DO(2ⁿ)

Wat meet geamortiseerde analyse?

1. ADe kosten van de ene duurste bewerking ergens in de reeks
2. BDe verwachte kosten over willekeurige invoer
3. CDe kosten van een algoritme bij de beste invoer
4. DDe gemiddelde kosten per bewerking over een worst-casereeks van bewerkingen

Wat is de oplossing van de recurrente betrekking T(n) = T(n − 1) + O(n)?

1. AO(n)
2. BO(n log n)
3. CO(n²)
4. DO(2ⁿ)

Waarom kan het algoritme van Dijkstra verkeerde resultaten geven als sommige kantgewichten negatief zijn?

1. AHet werkt alleen op ongerichte grafen
2. BEen knoop is definitief zodra hij wordt uitgehaald, maar een latere negatieve kant kan hem nog een korter pad geven
3. CNegatieve getallen kunnen niet in een prioriteitswachtrij worden opgeslagen
4. DHet raakt bij elke negatieve kant in een oneindige lus

Wat is het verschil tussen een onbeslisbaar en een onhandelbaar probleem?

1. ABeide betekenen dat het probleem helemaal geen algoritme heeft
2. BOnhandelbare problemen kunnen door geen enkel algoritme worden opgelost, terwijl onbeslisbare alleen exponentiële tijd nodig hebben
3. CEen onbeslisbaar probleem heeft geen algoritme voor alle invoer; een onhandelbaar probleem wel, maar dat is te traag
4. DOnbeslisbare problemen zitten in NP, terwijl onhandelbare problemen in P zitten