Werkblad Algoritmen & complexiteit met antwoorden

Gratis printbaar werkblad Algoritmen & complexiteit: 8 opgaven van makkelijk tot tentamenniveau, met antwoordenblad. Print het of sla het op als pdf.

Nieuw werkbladOnline oefenen met hints

Voor docenten: gratis te printen, kopiëren en in de les te gebruiken. Elk nieuw werkblad heeft nieuwe waarden en een eigen antwoordblad. Een link naar ExamProblems op je cursuspagina wordt gewaardeerd.

Naam: ____________________   Datum: ____________

1.Makkelijk

Welke notatie beschrijft een bovengrens voor de groei?

  1. AGrote Theta (Big Theta)
  2. BKleine omega (little omega)
  3. CGrote Omega (Big Omega)
  4. DGrote O (Big O)
2.Makkelijk

Een algoritme met twee geneste lussen die elk n keer worden doorlopen, heeft doorgaans welke complexiteit?

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

Wat is memoisatie?

  1. AResultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
  2. BGeheugen vrijgeven nadat een functie is teruggekeerd
  3. CRecursie automatisch omzetten in een equivalente lus, zodat geen call stack nodig is
  4. DCommentaar schrijven naast elke regel code
4.Gemiddeld

Wat is de tijdcomplexiteit van het standaardalgoritme voor dynamisch programmeren voor de langste gemeenschappelijke deelrij van strings met lengte m en n?

  1. AO(mn)
  2. BO(m + n)
  3. CO(mn log n)
  4. DO(2m+n)
5.Gemiddeld

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

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

Welk algoritme vindt de kortste paden vanuit één bron in een graaf met niet-negatieve kantgewichten?

  1. ABellman-Ford is in alle gevallen vereist
  2. BHet algoritme van Dijkstra
  3. CDiepte-eerst zoeken (DFS)
  4. DHet algoritme van Kruskal
7.Moeilijk

Welke definitie van de klasse NP is juist?

  1. AProblemen die niet in polynomiale tijd kunnen worden opgelost
  2. BBeslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
  3. CProblemen die geen enkel algoritme kan oplossen
  4. DProblemen die niet polynomiaal zijn
8.Moeilijk

Welke bewering over P en NP is juist?

  1. AEr is bewezen dat P ≠ NP
  2. BOplossingen van NP-problemen kunnen niet snel worden geverifieerd
  3. CNP betekent "niet polynomiaal"
  4. DElk probleem in P zit ook in NP

Antwoordenblad

  1. 1. D · Grote O (Big O)
  2. 2. C · O(n²)
  3. 3. A · Resultaten van functieaanroepen opslaan, zodat herhaalde aanroepen uit het geheugen worden beantwoord
  4. 4. A · O(mn)
  5. 5. D · O(log n)
  6. 6. B · Het algoritme van Dijkstra
  7. 7. B · Beslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd
  8. 8. D · Elk probleem in P zit ook in NP

Volledige stapsgewijze oplossingen: oefen dit onderwerp op examproblems.com.