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

Een O(n²)-algoritme doet 1 seconde over n = 1000. Hoe lang doet het ongeveer over n = 2000?

  1. A4 seconden
  2. B2 seconden
  3. C1 seconde
  4. D8 seconden
2.Makkelijk

Wat is de grote O van 3n² + 5n + 2?

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

Een lus begint met i = 1 en verdubbelt i bij elke iteratie totdat i > n. Hoeveel iteraties voert hij uit?

  1. AOngeveer n
  2. BOngeveer n / 2
  3. COngeveer log₂ n
  4. DOngeveer n²
4.Gemiddeld

Een gretig (greedy) algoritme:

  1. AGeeft altijd de optimale oplossing
  2. BGebruikt alleen recursie
  3. CProbeert elke mogelijke oplossing
  4. DMaakt bij elke stap de lokaal beste keuze
5.Gemiddeld

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

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

Is het juist om te zeggen dat een O(n²)-algoritme ook O(n³) is?

  1. AJa, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  2. BNee, omdat n³ voor grote n kleiner is dan n²
  3. CNee, omdat grote O altijd de exacte groeisnelheid van de functie moet geven
  4. DJa, maar alleen als n kleiner is dan 100
7.Moeilijk

Welke definitie van de klasse P is juist?

  1. AProblemen die parallel kunnen worden opgelost
  2. BProblemen waarvan oplossingen wel kunnen worden gecontroleerd maar nooit in polynomiale tijd gevonden
  3. CProblemen die op elke computer exponentiële tijd nodig hebben
  4. DBeslissingsproblemen die door een deterministisch algoritme in polynomiale tijd kunnen worden opgelost
8.Moeilijk

Welke definitie van de klasse NP is juist?

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

Antwoordenblad

  1. 1. A · 4 seconden
  2. 2. D · O(n²)
  3. 3. C · Ongeveer log₂ n
  4. 4. D · Maakt bij elke stap de lokaal beste keuze
  5. 5. B · O(n)
  6. 6. A · Ja, omdat grote O een bovengrens is en n² niet sneller groeit dan n³
  7. 7. D · Beslissingsproblemen die door een deterministisch algoritme in polynomiale tijd kunnen worden opgelost
  8. 8. D · Beslissingsproblemen waarvan ja-antwoorden met een certificaat in polynomiale tijd kunnen worden geverifieerd

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