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 Zeitkomplexität hat Insertionsort im Worst Case?

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

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

  1. AO(2ⁿ)
  2. BO(n³)
  3. CO(n log n)
  4. DO(n²)
3.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)
4.Mittel

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

  1. ANur zufällige Eingaben
  2. BÜberlappende Teilprobleme und optimale Teilstruktur
  3. CÜberhaupt keine Teilprobleme, sodass es in einem Schritt lösbar ist
  4. DEine einzige Schleife
5.Mittel

Welche Zeitkomplexität hat: for i = 1 to n: for j = 1 to i: O(1)-Arbeit?

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

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

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

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

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

Was musst du tun, um zu zeigen, dass ein neues Problem X NP-schwer ist?

  1. AX in polynomieller Zeit auf ein bekanntes NP-schweres Problem reduzieren
  2. BZeigen, dass X für kleine Eingaben keinen polynomiellen Algorithmus hat
  3. CEin bekanntes NP-schweres Problem in polynomieller Zeit auf X reduzieren
  4. DZeigen, dass X in polynomieller Zeit überprüft werden kann

Lösungsschlüssel

  1. 1. C · O(n²)
  2. 2. A · O(2ⁿ)
  3. 3. C · O(n²)
  4. 4. B · Überlappende Teilprobleme und optimale Teilstruktur
  5. 5. D · O(n²)
  6. 6. B · O(2ⁿ)
  7. 7. B · n = o(n²), aber n ist nicht o(n)
  8. 8. C · Ein bekanntes NP-schweres Problem in polynomieller Zeit auf X reduzieren

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