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 beschreibt die Average-Case-Laufzeit?

  1. ADie Laufzeit auf dem am weitesten verbreiteten Computer
  2. BDie Laufzeit für eine Eingabe durchschnittlicher Länge
  3. CDen Mittelwert zwischen den Laufzeiten im Best Case und im Worst Case
  4. DDie erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
2.Leicht

Welcher Sortieralgorithmus vertauscht wiederholt benachbarte Elemente, die in der falschen Reihenfolge stehen?

  1. AHeapsort
  2. BQuicksort
  3. CBubblesort
  4. DMergesort
3.Leicht

Welche dieser Funktionen wächst für große n am langsamsten?

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

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

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

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

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

Welche Aussage über eine rekursive Funktion ohne erreichbaren Basisfall ist richtig?

  1. ASie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  2. BSie gibt automatisch 0 zurück
  3. CSie läuft in O(1) Zeit
  4. DDer Compiler wandelt sie immer in eine Schleife um, die sicher endet
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. BEin bekanntes NP-schweres Problem in polynomieller Zeit auf X reduzieren
  3. CX in polynomieller Zeit auf ein bekanntes NP-schweres Problem reduzieren
  4. DZeigen, dass X für kleine Eingaben keinen polynomiellen Algorithmus hat
8.Schwer

Wie erkennt der Bellman-Ford-Algorithmus einen vom Startknoten erreichbaren Kreis mit negativem Gewicht?

  1. AEr zählt die Kreise mit einer Tiefensuche
  2. BEr führt den Dijkstra-Algorithmus zweimal aus und vergleicht die beiden Distanzergebnisse
  3. CNach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt
  4. DEr prüft, ob irgendeine Kante ein negatives Gewicht hat

Lösungsschlüssel

  1. 1. D · Die erwartete Laufzeit bezüglich einer gegebenen Verteilung der Eingaben der Größe n
  2. 2. C · Bubblesort
  3. 3. C · O(log n)
  4. 4. B · Überlappende Teilprobleme und optimale Teilstruktur
  5. 5. D · Ω(n log n)
  6. 6. A · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  7. 7. B · Ein bekanntes NP-schweres Problem in polynomieller Zeit auf X reduzieren
  8. 8. C · Nach V − 1 Runden prüft er, ob sich noch eine Kante relaxieren lässt

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