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 die binäre Suche in einem sortierten Array?

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

Der Zugriff auf ein Array-Element über seinen Index benötigt:

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

Die Laufzeit eines Algorithmus ist O(n). Wie nennt man dieses Wachstum?

  1. ALogarithmisch
  2. BLinear
  3. CQuadratisch
  4. DKonstant
4.Mittel

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

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

Welche Zeitkomplexität hat die Berechnung der n-ten Fibonacci-Zahl mit einer Bottom-up-Tabelle?

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

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

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

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

  1. AZeigen, dass X in polynomieller Zeit überprüft werden kann
  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. DX in polynomieller Zeit auf ein bekanntes NP-schweres Problem reduzieren
8.Schwer

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

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

Lösungsschlüssel

  1. 1. A · O(log n)
  2. 2. B · O(1)
  3. 3. B · Linear
  4. 4. C · Überlappende Teilprobleme und optimale Teilstruktur
  5. 5. B · O(n)
  6. 6. D · O(n)
  7. 7. C · Ein bekanntes NP-schweres Problem in polynomieller Zeit auf X reduzieren
  8. 8. B · Ein Entscheidungsbaum mit n möglichen Ergebnissen muss mindestens die Tiefe log₂ n haben

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