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

Ein O(n²)-Algorithmus braucht für n = 1000 eine Sekunde. Wie lange braucht er etwa für n = 2000?

  1. A1 Sekunde
  2. B8 Sekunden
  3. C4 Sekunden
  4. D2 Sekunden
2.Leicht

Welcher Sortieralgorithmus vertauscht wiederholt benachbarte Elemente, die in der falschen Reihenfolge stehen?

  1. AQuicksort
  2. BHeapsort
  3. CBubblesort
  4. DMergesort
3.Leicht

Ein Problem heißt in der Regel effizient lösbar (tractable), wenn:

  1. AEs in polynomieller Zeit gelöst werden kann
  2. BEs in konstanter Zeit gelöst werden kann
  3. CEs keine Lösung hat
  4. DEs nur durch Ausprobieren aller Möglichkeiten gelöst werden kann
4.Mittel

Welche Zeitkomplexität hat: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Was misst die amortisierte Analyse?

  1. ADie Kosten der einzelnen teuersten Operation irgendwo in der Folge
  2. BDie Kosten eines Algorithmus bei der besten Eingabe
  3. CDie erwarteten Kosten über zufällige Eingaben
  4. DDie durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
6.Mittel

Wie viele Münzen verwendet bei Münzen zu 1, 3 und 4 und einem Betrag von 6 die gierige Methode „größte Münze zuerst" im Vergleich zum Optimum?

  1. AGreedy braucht 3 Münzen; das Optimum ist 2
  2. BGreedy braucht 4 Münzen; das Optimum ist 3
  3. CGreedy braucht 3 Münzen; das Optimum ist 3
  4. DGreedy braucht 2 Münzen; das Optimum ist 2
7.Schwer

Welche zwei Dinge müssen gezeigt werden, um zu beweisen, dass ein Entscheidungsproblem X NP-vollständig ist?

  1. AX hat keinen polynomiellen Algorithmus, und X ist entscheidbar
  2. BX lässt sich auf ein Problem in P reduzieren, und X liegt in NP
  3. CX liegt in P, und X lässt sich auf SAT reduzieren
  4. DX liegt in NP, und ein bekanntes NP-vollständiges Problem lässt sich in polynomieller Zeit auf X reduzieren
8.Schwer

Welche Definition der Klasse NP ist richtig?

  1. AProbleme, die kein Algorithmus lösen kann
  2. BProbleme, die nicht in polynomieller Zeit gelöst werden können
  3. CProbleme, die nicht polynomiell sind
  4. DEntscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können

Lösungsschlüssel

  1. 1. C · 4 Sekunden
  2. 2. C · Bubblesort
  3. 3. A · Es in polynomieller Zeit gelöst werden kann
  4. 4. D · O(n log n)
  5. 5. D · Die durchschnittlichen Kosten pro Operation über eine Worst-Case-Folge von Operationen
  6. 6. A · Greedy braucht 3 Münzen; das Optimum ist 2
  7. 7. D · X liegt in NP, und ein bekanntes NP-vollständiges Problem lässt sich in polynomieller Zeit auf X reduzieren
  8. 8. D · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können

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