Arbeitsblatt Algorithmen & Komplexität mit Lösungen

Kostenloses Arbeitsblatt Algorithmen & Komplexität zum Ausdrucken: 8 Aufgaben von leicht bis Prüfungsniveau, mit Lösungsschlüssel. Drucke es aus oder speichere es als PDF.

Neues ArbeitsblattOnline mit Tipps üben

Für Lehrkräfte: kostenlos ausdrucken, kopieren und im Unterricht verwenden. Jedes neue Arbeitsblatt hat neue Werte und einen eigenen Lösungsschlüssel. Über einen Link zu ExamProblems auf Ihrer Kursseite freuen wir uns.

Name: ____________________   Datum: ____________

1.Leicht

Welche Laufzeit hat Countingsort für n ganze Zahlen im Bereich 0 bis k?

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

Welche Zeitkomplexität hat Insertionsort im Worst Case?

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

Was bedeutet es, wenn eine Operation in O(1) Zeit läuft?

  1. AIhre Laufzeit wächst nicht mit der Eingabegröße
  2. BSie kann nur einmal ausgeführt werden
  3. CSie verarbeitet genau ein Element pro Sekunde Laufzeit
  4. DSie dauert immer genau eine Sekunde
4.Mittel

Was ist die Lösung der Rekursionsgleichung T(n) = 2T(n − 1) + O(1)?

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

Warum bringt dynamische Programmierung bei Mergesort keine echte Beschleunigung?

  1. AMergesort hat keine rekursive Struktur
  2. BSeine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  3. CDynamische Programmierung funktioniert nur bei Graphenproblemen, nicht bei Arrays
  4. DMergesort ist bereits O(n)
6.Mittel

Dynamische Programmierung ist nützlich, wenn ein Problem Folgendes aufweist:

  1. AÜberhaupt keine Teilprobleme, sodass es in einem Schritt lösbar ist
  2. BNur zufällige Eingaben
  3. CEine einzige Schleife
  4. DÜberlappende Teilprobleme und optimale Teilstruktur
7.Schwer

Was ist die Lösung der Rekursionsgleichung T(n) = 2T(n/2) + n log n?

  1. AΘ(n log n)
  2. BΘ(n)
  3. CΘ(n log² n)
  4. DΘ(n²)
8.Schwer

Das Halteproblem zeigt, dass:

  1. ASchleifen vermieden werden sollten
  2. BJedes Programm irgendwann anhält
  3. CKein Algorithmus für jedes Programm und jede Eingabe entscheiden kann, ob es anhält
  4. DManche Programme auf schnelleren Computern schneller laufen, das Anhalten also von der Hardware abhängt

Lösungsschlüssel

  1. 1. B · O(n + k)
  2. 2. D · O(n²)
  3. 3. A · Ihre Laufzeit wächst nicht mit der Eingabegröße
  4. 4. A · O(2ⁿ)
  5. 5. B · Seine Teilprobleme überlappen sich nicht, also gibt es nichts wiederzuverwenden
  6. 6. D · Überlappende Teilprobleme und optimale Teilstruktur
  7. 7. C · Θ(n log² n)
  8. 8. C · Kein Algorithmus für jedes Programm und jede Eingabe entscheiden kann, ob es anhält

Vollständige Schritt-für-Schritt-Lösungen: Übe dieses Thema auf examproblems.com.