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

Was ist Memoisation?

  1. ADas Schreiben von Kommentaren neben jede Codezeile
  2. BDas automatische Umwandeln einer Rekursion in eine gleichwertige Schleife, sodass kein Aufrufstack nötig ist
  3. CDas Speichern der Ergebnisse von Funktionsaufrufen, sodass wiederholte Aufrufe aus dem Speicher beantwortet werden
  4. DDas Freigeben von Speicher, nachdem eine Funktion zurückkehrt
2.Leicht

Welche Zeitkomplexität hat das Finden des größten Werts in einem unsortierten Array mit n Zahlen?

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

Was ist ein Brute-Force-Algorithmus?

  1. AEiner, der immer Rekursion verwendet
  2. BEiner, der eine Antwort zufällig rät
  3. CEiner, der alle möglichen Lösungskandidaten ausprobiert
  4. DEiner, der auf vielen Prozessoren läuft
4.Mittel

Welche Zeitkomplexität hat die Multiplikation zweier n × n-Matrizen mit der üblichen dreifachen Schleife?

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

Was berechnet der Floyd-Warshall-Algorithmus, und wie schnell?

  1. AKürzeste Wege zwischen allen Knotenpaaren in O(V³)
  2. BEinen minimalen Spannbaum in O(E log V)
  3. CKürzeste Wege von einem Startknoten zu allen anderen in O(V + E)
  4. DEine topologische Sortierung in O(V²)
6.Mittel

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

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

Was würde folgen, wenn jemand einen Polynomialzeitalgorithmus für ein NP-vollständiges Problem fände?

  1. ADas Halteproblem würde entscheidbar
  2. BAlle Algorithmen mit exponentieller Laufzeit würden sofort in linearer Zeit laufen
  3. CJedes Problem in NP wäre in polynomieller Zeit lösbar, also P = NP
  4. DNur dieses eine Problem würde nach P wandern
8.Schwer

Der Held-Karp-Algorithmus der dynamischen Programmierung löst das Problem des Handlungsreisenden exakt. Welche Laufzeit hat er für n Städte?

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

Lösungsschlüssel

  1. 1. C · Das Speichern der Ergebnisse von Funktionsaufrufen, sodass wiederholte Aufrufe aus dem Speicher beantwortet werden
  2. 2. D · O(n)
  3. 3. C · Einer, der alle möglichen Lösungskandidaten ausprobiert
  4. 4. A · O(n³)
  5. 5. A · Kürzeste Wege zwischen allen Knotenpaaren in O(V³)
  6. 6. A · O(n²)
  7. 7. C · Jedes Problem in NP wäre in polynomieller Zeit lösbar, also P = NP
  8. 8. C · O(n² 2ⁿ)

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