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. A4 Sekunden
  2. B2 Sekunden
  3. C1 Sekunde
  4. D8 Sekunden
2.Leicht

Wie nennt man ein Wachstum von O(2ⁿ)?

  1. ALinear
  2. BLogarithmisch
  3. CExponentiell
  4. DPolynomiell
3.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²)
4.Mittel

Welcher Sortieralgorithmus ist stabil?

  1. AMergesort
  2. BSelectionsort (typische Variante)
  3. CQuicksort (typische In-place-Variante)
  4. DHeapsort
5.Mittel

Die untere Schranke für vergleichsbasiertes Sortieren im Worst Case ist:

  1. AΩ(n²)
  2. BΩ(n log n)
  3. CΩ(log n)
  4. DΩ(n)
6.Mittel

Welche Laufzeit hat LSD-Radixsort für n ganze Zahlen mit d Ziffern zur Basis k?

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

Welche Definition der Klasse NP ist richtig?

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

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

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

Lösungsschlüssel

  1. 1. A · 4 Sekunden
  2. 2. C · Exponentiell
  3. 3. B · O(1)
  4. 4. A · Mergesort
  5. 5. B · Ω(n log n)
  6. 6. C · O(d(n + k))
  7. 7. D · Entscheidungsprobleme, deren Ja-Antworten mithilfe eines Zertifikats in polynomieller Zeit überprüft werden können
  8. 8. A · X liegt in NP, und ein bekanntes NP-vollständiges Problem lässt sich in polynomieller Zeit auf X reduzieren

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