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 Algorithmus mit zwei verschachtelten Schleifen, die jeweils n-mal durchlaufen werden, hat typischerweise welche Komplexität?

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

Welche dieser Laufzeiten ist polynomiell?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
3.Leicht

Was ist ein Algorithmus?

  1. AEine endliche Folge eindeutig definierter Schritte, die ein Problem löst
  2. BJedes Computerprogramm mit grafischer Oberfläche
  3. CEine Programmiersprache zum Schreiben mathematischer Formeln
  4. DEine Datenstruktur, die Zahlen speichert
4.Mittel

Die Breitensuche (BFS) auf einem ungewichteten Graphen findet:

  1. ADen minimalen Spannbaum
  2. BKürzeste Wege in Graphen mit negativen Kantengewichten
  3. CEine topologische Sortierung in allen Graphen
  4. DKürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
5.Mittel

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

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

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

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

Insertionsort läuft bei sortierter Eingabe in O(n). Widerspricht das der unteren Schranke Ω(n log n) für vergleichsbasiertes Sortieren?

  1. ANein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe
  2. BNein, weil Insertionsort kein vergleichsbasiertes Sortierverfahren ist
  3. CJa, die untere Schranke ist also falsch
  4. DJa, aber nur für Arrays mit weniger als 100 Elementen
8.Schwer

Welche Aussage über die Klein-o-Notation ist richtig?

  1. An = o(n²), aber n ist nicht o(n)
  2. Bn² = o(n)
  3. C2n = o(n), weil 2n langsam wächst
  4. Dn = o(n), da jede Funktion Klein-o von sich selbst ist

Lösungsschlüssel

  1. 1. B · O(n²)
  2. 2. C · O(n³)
  3. 3. A · Eine endliche Folge eindeutig definierter Schritte, die ein Problem löst
  4. 4. D · Kürzeste Wege, gemessen in der Anzahl der Kanten vom Startknoten
  5. 5. D · O(n²)
  6. 6. A · O(n)
  7. 7. A · Nein, die untere Schranke gilt für den Worst Case über alle Eingaben, nicht für jede Eingabe
  8. 8. A · n = o(n²), aber n ist nicht o(n)

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