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

Wie lautet die Groß-O-Klasse von 3n² + 5n + 2?

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

Was beschreibt die Worst-Case-Laufzeit eines Algorithmus?

  1. ADie maximale Laufzeit über alle Eingaben der Größe n
  2. BDie Laufzeit bei der kleinsten Eingabe
  3. CDie Laufzeit auf einem langsamen Computer
  4. DDie erwartete Laufzeit bei einer zufälligen Eingabe der Größe n
3.Leicht

Welche Komplexitätsklasse wächst für große n am schnellsten?

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

Was bedeutet es, dass ein Problem optimale Teilstruktur hat?

  1. ADas Problem kann in konstanter Zeit gelöst werden
  2. BJedes Teilproblem hat dieselbe Größe
  3. CEine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
  4. DDas Problem hat genau eine optimale Lösung, die jedes Teilproblem teilt
5.Mittel

Ein Greedy-Algorithmus:

  1. ATrifft in jedem Schritt die lokal beste Wahl
  2. BLiefert immer die optimale Lösung
  3. CProbiert jede mögliche Lösung aus
  4. DVerwendet ausschließlich Rekursion
6.Mittel

Welcher Algorithmus findet die kürzesten Wege von einem Startknoten in einem Graphen mit nichtnegativen Kantengewichten?

  1. ADijkstra-Algorithmus
  2. BBellman-Ford ist in allen Fällen erforderlich
  3. CKruskal-Algorithmus
  4. DTiefensuche (DFS)
7.Schwer

Warum braucht jede vergleichsbasierte Suche in einem sortierten Array im Worst Case Ω(log n) Vergleiche?

  1. AEin Entscheidungsbaum mit n möglichen Ergebnissen muss mindestens die Tiefe log₂ n haben
  2. BJeder Vergleich braucht logarithmische Zeit
  3. CDie binäre Suche ist der einzig mögliche Algorithmus und braucht log₂ n Vergleiche
  4. DJedes Element muss mindestens einmal verglichen werden
8.Schwer

Welche Aussage über P und NP ist korrekt?

  1. AEs wurde bewiesen, dass P ≠ NP
  2. BLösungen von NP-Problemen lassen sich nicht schnell überprüfen
  3. CNP bedeutet „nicht polynomiell“
  4. DJedes Problem in P liegt auch in NP

Lösungsschlüssel

  1. 1. C · O(n²)
  2. 2. A · Die maximale Laufzeit über alle Eingaben der Größe n
  3. 3. D · O(2ⁿ)
  4. 4. C · Eine optimale Lösung lässt sich aus optimalen Lösungen seiner Teilprobleme zusammensetzen
  5. 5. A · Trifft in jedem Schritt die lokal beste Wahl
  6. 6. A · Dijkstra-Algorithmus
  7. 7. A · Ein Entscheidungsbaum mit n möglichen Ergebnissen muss mindestens die Tiefe log₂ n haben
  8. 8. D · Jedes Problem in P liegt auch in NP

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