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 Notation beschreibt eine untere Schranke für das Wachstum?

  1. Ao (Klein-o)
  2. BΩ (Groß-Omega)
  3. CO (Groß-O)
  4. DΘ (Groß-Theta)
2.Leicht

Welche Zeitkomplexität hat Insertionsort im Worst Case?

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

Wie viel zusätzlichen Speicher braucht ein üblicher arraybasierter Mergesort?

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

Warum wechseln viele Sortierroutinen in Bibliotheken bei sehr kleinen Teilarrays zu Insertionsort?

  1. AInsertionsort ist im Worst Case O(n log n)
  2. BRekursive Algorithmen können Arrays mit weniger als 10 Elementen nicht verarbeiten
  3. CInsertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  4. DInsertionsort braucht bei großen Eingaben weniger Speicher als jeder andere Sortieralgorithmus
5.Mittel

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

  1. ADer Compiler wandelt sie immer in eine Schleife um, die sicher endet
  2. BSie läuft in O(1) Zeit
  3. CSie gibt automatisch 0 zurück
  4. DSie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
6.Mittel

Die Zeitkomplexität des naiven rekursiven Fibonacci (fib(n) = fib(n−1) + fib(n−2)) ist:

  1. ALinear
  2. BKonstant
  3. CExponentiell
  4. DLogarithmisch
7.Schwer

Worin unterscheidet sich ein unentscheidbares Problem von einem praktisch unlösbaren (intractable)?

  1. APraktisch unlösbare Probleme können von keinem Algorithmus gelöst werden, unentscheidbare brauchen nur exponentielle Zeit
  2. BBeides bedeutet, dass es für das Problem überhaupt keinen Algorithmus gibt
  3. CEin unentscheidbares Problem hat keinen Algorithmus für alle Eingaben; ein praktisch unlösbares hat einen, der aber zu langsam ist
  4. DUnentscheidbare Probleme liegen in NP, praktisch unlösbare in P
8.Schwer

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

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

Lösungsschlüssel

  1. 1. B · Ω (Groß-Omega)
  2. 2. A · O(n²)
  3. 3. C · O(n)
  4. 4. C · Insertionsort hat wenig Overhead und ist bei kleinen oder fast sortierten Eingaben schnell
  5. 5. D · Sie ruft sich immer weiter selbst auf, bis der Aufrufstack überläuft
  6. 6. C · Exponentiell
  7. 7. C · Ein unentscheidbares Problem hat keinen Algorithmus für alle Eingaben; ein praktisch unlösbares hat einen, der aber zu langsam ist
  8. 8. A · Jedes Problem in NP wäre in polynomieller Zeit lösbar, also P = NP

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