Algorithmen, Programmierung und Kontrollstrukturen — Informatik · DE-Abitur Notizen

Algorithmusbegriff, Spezifikation und Korrektheit#

BasisKMK-EPA-Inf-ModellierenNRW-IF1BY-Inf-1

Der Begriff Algorithmus geht auf den persischen Gelehrten al-Chwarizmi (9. Jahrhundert) zurück und bezeichnet ein eindeutig beschriebenes, schrittweises Lösungsverfahren für eine ganze Problemklasse. Entscheidend ist die Trennung dreier Ebenen, die in Klausuren oft durcheinandergeraten: das Problem (was soll gelöst werden), der Algorithmus (das sprachunabhängige Lösungsverfahren) und die Implementation (seine Umsetzung in einer konkreten Sprache wie Java oder Python). Derselbe Algorithmus — etwa die binäre Suche — lässt sich in beliebig vielen Sprachen implementieren, ohne sein Wesen zu ändern; deshalb prüft das Abitur fast immer zuerst das Verfahren und erst danach den Code.

Ein Verfahren ist nur dann ein Algorithmus im strengen Sinn, wenn es vier konstituierende Eigenschaften erfüllt. Die Endlichkeit verlangt sowohl einen endlichen Beschreibungstext (statische Endlichkeit) als auch eine endliche Zahl tatsächlich ausgeführter Schritte (dynamische Endlichkeit, d. h. Terminierung). Die Eindeutigkeit (Determinismus) fordert, dass der jeweils nächste Schritt eindeutig festliegt. Die Ausführbarkeit (Effektivität) verlangt, dass jeder einzelne Schritt mit den verfügbaren Mitteln tatsächlich durchführbar ist. Die Allgemeinheit fordert, dass das Verfahren eine ganze Klasse von Eingaben löst, nicht nur einen Einzelfall.

Donald Knuth (The Art of Computer Programming, 1968) nennt eine eng verwandte Liste von fünf Merkmalen — Finiteness, Definiteness, Input, Output, Effectiveness — und führt Ein- und Ausgabe gesondert auf, wo der deutsche Schulkanon die Allgemeinheit betont. Beide Kataloge meinen dasselbe: ein endliches, eindeutiges, durchführbares, allgemeines Rezept. Wer die vier (bzw. fünf) Merkmale an einem konkreten Verfahren prüft (z. B. der schriftlichen Division), zeigt das geforderte Verständnis statt bloßer Begriffswiedergabe.

Bevor man ein Verfahren beweist oder beurteilt, muss man präzise sagen, was es leisten soll — das leistet die Spezifikation aus Vorbedingung (Precondition: was über die Eingabe vorausgesetzt werden darf) und Nachbedingung (Postcondition: was über die Ausgabe garantiert wird). Für „Maximum eines Arrays" etwa lautet die Vorbedingung „a ist ein nichtleeres Array", die Nachbedingung „der Rückgabewert m erfüllt m ≥ a[i] für alle i und kommt in a vor". Ohne Vorbedingung sind viele Verfahren gar nicht spezifizierbar (das Maximum eines leeren Arrays existiert nicht); ein „Beweis", der die Vorbedingung übergeht, bleibt deshalb unvollständig.

Korrektheit zerfällt in zwei Stufen. Partielle Korrektheit bedeutet: Falls der Algorithmus terminiert, erfüllt das Ergebnis die Nachbedingung. Totale Korrektheit verlangt zusätzlich die Terminierung für jede zulässige Eingabe — kurz: totale = partielle Korrektheit + Termination. Der Unterschied ist real: Ein Programm mit einer Endlosschleife, das im Erfolgsfall stets das Richtige ausgäbe, kann partiell korrekt, aber nicht total korrekt sein. Terminierung weist man über eine Terminierungsfunktion nach — eine streng fallende, nach unten beschränkte ganzzahlige Größe (etwa „hi − lo" bei der binären Suche, die jeden Durchlauf kleiner wird und nicht unter null fällt).

Beweise werden mit Hoare-Tripeln {P} S {Q} notiert (C. A. R. Hoare, 1969): Gilt vor der Ausführung der Anweisung S die Vorbedingung P und terminiert S, so gilt danach die Nachbedingung Q. Der Kern eines Schleifenbeweises ist die Schleifeninvariante — eine Aussage, die vor der Schleife gilt, von jedem Durchlauf erhalten bleibt und zusammen mit der negierten Schleifenbedingung am Ende die Nachbedingung ergibt. Auf gA-Niveau argumentiert man informell („nach dem i-ten Durchlauf steht in m das Maximum der ersten i Elemente"); auf eA-Niveau formalisiert der Hoare-Kalkül dieselbe Argumentation mit Regeln für Zuweisung, Sequenz, Selektion und Iteration.

Sorgfältig zu trennen sind deterministisch und determiniert: deterministisch heißt, dass der nächste Schritt zu jedem Zeitpunkt eindeutig festliegt (kein „Raten"); determiniert heißt, dass bei gleicher Eingabe stets dasselbe Ergebnis herauskommt. Beides fällt oft zusammen, ist aber nicht dasselbe — ein randomisierter Quicksort mit zufälliger Pivotwahl ist nicht deterministisch (sein Ablauf hängt vom Zufall ab), aber dennoch determiniert (er gibt immer dieselbe sortierte Folge aus). Abzugrenzen ist der Algorithmus schließlich von der Heuristik, die oft schnell eine brauchbare, aber nicht garantiert korrekte oder optimale Lösung liefert. Dass nicht jedes Problem überhaupt algorithmisch lösbar ist, zeigt das unentscheidbare Halteproblem (Turing 1936) — vertieft im Topic Theoretische Informatik.

\{P\}\,S\,\{Q\}

Hoare-Tripel

Wenn die Vorbedingung P vor Ausführung von S gilt und S terminiert, dann gilt nach S die Nachbedingung Q.

Typische Fehler

Algorithmus, Programm und Implementation werden gleichgesetzt — die sprachunabhängige Verfahrensebene wird mit dem konkreten Code vermischt.
Determinismus mit Determiniertheit verwechselt (deterministisch ≠ determiniert; ein randomisierter Quicksort ist determiniert, aber nicht deterministisch).
Nachbedingung ohne Vorbedingung formuliert; der „Beweis" deckt dann nicht alle zulässigen Eingaben ab (z. B. das leere Array).
Partielle Korrektheit für totale gehalten — die Terminierung wird nicht eigens nachgewiesen.
Algorithmus und Heuristik gleichgesetzt — eine Heuristik garantiert die Nachbedingung gerade nicht.

LK-Vertiefung

eA-Vertiefung: Formulieren Sie ein Hoare-Tripel für eine while-Schleife, die das Maximum eines Arrays bestimmt, geben Sie die Schleifeninvariante an und beweisen Sie deren Erhalt (Induktion über die Durchläufe) sowie die Terminierung über eine geeignete Terminierungsfunktion.

Aktive Wiederholung

Erläutern Sie die vier konstituierenden Eigenschaften eines Algorithmus (Endlichkeit, Eindeutigkeit, Ausführbarkeit, Allgemeinheit) an einem Beispiel Ihrer Wahl und beurteilen Sie, ob das Verfahren der schriftlichen Division alle Eigenschaften erfüllt.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Sequenz, Selektion, Iteration und Funktionen#

BasisKMK-EPA-Inf-ImplementierenNRW-IF1BY-Inf-1

Das Strukturtheorem von Böhm und Jacopini (1966) besagt, dass sich jeder berechenbare Algorithmus allein aus drei Grundbausteinen — Sequenz, Selektion und Iteration — ohne wilde `goto`-Sprünge formulieren lässt. Diese Erkenntnis begründet die strukturierte Programmierung: Lesbarkeit, Testbarkeit und Beweisbarkeit folgen aus der klaren Schachtelung der drei Bausteine, weshalb moderne Hochsprachen praktisch ohne Sprunganweisungen auskommen.

Die Sequenz führt Anweisungen in fester Reihenfolge nacheinander aus. Die Selektion verzweigt abhängig von einem booleschen Ausdruck: `if`/`else` für die zweiwertige, `switch`/`case` für die mehrwertige Fallunterscheidung. Klausurrelevant ist die Vollständigkeit der Fälle — ein fehlender `else`-Zweig oder ein vergessenes `default` lässt Eingaben unbehandelt, und in `switch` führt ein vergessenes `break` zum unbeabsichtigten Durchfallen (fall-through).

Die Iteration (Schleife) wiederholt einen Rumpf. Bei der kopfgesteuerten `while`-Schleife wird die Bedingung vor jedem Durchlauf geprüft (der Rumpf läuft ggf. nullmal); bei der fußgesteuerten `do-while`-Schleife nach jedem Durchlauf (der Rumpf läuft mindestens einmal). Die `for`-Schleife bündelt Initialisierung, Test und Aktualisierung und eignet sich als Zählschleife, wenn die Zahl der Durchläufe vorab feststeht; die `for-each`-Variante durchläuft eine Sammlung ohne expliziten Index.

Wiederkehrender Code wird mit Funktionen/Methoden modular gekapselt: Sie erhalten Parameter, liefern ggf. einen Rückgabewert und machen Code wiederverwendbar, testbar und lesbar. In Java erfolgt die Parameterübergabe immer per Wert (call by value): Bei Primitiven wird der Wert kopiert, bei Objekten der Wert der Referenz. Die Methode arbeitet also auf demselben Objekt (Änderungen an einem übergebenen Array sind beim Aufrufer sichtbar), kann aber die Variable des Aufrufers nicht auf ein anderes Objekt umbiegen — eine Feinheit, die in Klausuren gern geprüft wird.

Der Gültigkeitsbereich (Scope) begrenzt die Lebensdauer von Variablen: Lokale Variablen existieren nur innerhalb ihres Blocks. Echte globale Variablen kennt Java nicht; das nächste Äquivalent sind klassenweite statische Felder, deren großflächige Nutzung jedoch als schlechter Stil gilt, weil sie verborgene Abhängigkeiten und schwer testbaren gemeinsamen Zustand erzeugt. Boolesche Bedingungen wertet Java kurzschließend (lazy) aus — in `a != null && a.length > 0` schützt der linke Operand vor einem Zugriff auf `null`.

Code-Beispiel: ```java int summe(int[] werte) { int s = 0; for (int x : werte) s += x; return s; } ```

Typische Fehler

Zuweisung `=` und Vergleich `==` in Bedingungen verwechselt (in Java Tippfehler, in Python SyntaxError-Schutz).
Off-by-one in for-Schleifen: `i <= n` statt `i < n` über ein Array der Länge n führt zu ArrayIndexOutOfBounds.
do-while läuft den Rumpf immer mindestens einmal — übersehen, wenn die Eingabe bereits gültig ist.
„Per Referenz" pauschal behauptet — Java übergibt stets per Wert (bei Objekten den Referenzwert); ein neu zugewiesener Parameter ist beim Aufrufer nicht sichtbar.
Inkonsistente Python-Einrückung bzw. vergessene geschweifte Klammern in Java verändern unbeabsichtigt den Block.

LK-Vertiefung

eA-Vertiefung: Begründen Sie mit dem Satz von Böhm-Jacopini, dass die `goto`-Anweisung theoretisch entbehrlich ist, und wandeln Sie eine mit Sprüngen formulierte Schleife in eine äquivalente strukturierte `while`-Form um.

Aktive Wiederholung

Implementieren Sie in Java eine Methode `int maximum(int[] a)`, die das Maximum eines Integer-Arrays liefert, und erläutern Sie die Schleifeninvariante.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Rekursion und Iteration im Vergleich#

StandardNRW-IF1BY-Inf-2BW-Inf-2

Eine Funktion heißt rekursiv, wenn sie sich (direkt oder indirekt) selbst aufruft. Jede korrekte Rekursion braucht zwingend zwei Bestandteile: mindestens einen Basisfall (Rekursionsanker), der ohne weiteren Selbstaufruf ein Ergebnis liefert, und einen Reduktionsschritt, der das Problem auf eine echt kleinere Instanz zurückführt und sich so dem Basisfall nähert. Fehlt der Basisfall oder verkleinert der Schritt das Problem nicht, entsteht eine Endlosrekursion.

Beispiel Fakultät: ```java int fak(int n) { if (n <= 1) return 1; // Basisfall return n * fak(n - 1); // Reduktionsschritt } ```

Rekursion ist eng an den Aufrufstapel (Call Stack) gebunden: Jeder noch nicht beendete Aufruf belegt einen eigenen Stapelrahmen (Stack Frame) mit seinen Parametern und lokalen Variablen. Die Rahmen werden beim Abstieg aufgebaut und beim Erreichen der Basisfälle in umgekehrter Reihenfolge wieder abgebaut (LIFO) — genau diese Stapelstruktur macht Rekursion und die Datenstruktur Stack zu zwei Seiten derselben Medaille (Querverweis Datenstrukturen).

Übersteigt die Rekursionstiefe die Stapelgröße, bricht das Programm mit einem StackOverflowError ab (Standard-JVM: grob 10⁴–10⁵ Rahmen). Endrekursion (tail recursion), bei der der Selbstaufruf die allerletzte Aktion ist, ließe sich prinzipiell in eine Schleife mit konstantem Stapelbedarf übersetzen; Java führt diese Optimierung jedoch nicht automatisch durch (anders als etwa Scheme oder Kotlin mit `tailrec`).

Im Vergleich zur Iteration ist Rekursion oft die natürlichere und kürzere Formulierung — besonders für rekursiv definierte Strukturen (Bäume, Listen) und Divide-and-Conquer-Verfahren (Mergesort, Türme von Hanoi). Iteration ist dagegen meist speicher- und laufzeiteffizienter, weil sie den Stapel-Overhead vermeidet. Jede Rekursion lässt sich grundsätzlich in eine Iteration überführen (notfalls mit einem expliziten Stack) und umgekehrt.

Ein klassisches Warnbeispiel ist die naive rekursive Fibonacci-Berechnung fib(n) = fib(n−1) + fib(n−2): Sie berechnet dieselben Teilergebnisse exponentiell oft und läuft in O(φⁿ) (φ ≈ 1,618, der Goldene Schnitt). Durch Memoisierung (Zwischenspeichern bereits berechneter Werte) oder eine iterative Bottom-up-Tabelle sinkt der Aufwand auf O(n) — derselbe Algorithmus, dramatisch andere Laufzeit (siehe Abschnitt Algorithmenstrategien, dynamische Programmierung).

Divide-and-Conquer-Rekursionen analysiert man über eine Rekursionsgleichung, etwa Mergesort mit T(n) = 2·T(n/2) + Θ(n). Das Master-Theorem liefert dafür geschlossen T(n) ∈ Θ(n log n) (siehe das nebenstehende Rechenbeispiel) — die formale Brücke von der rekursiven Struktur zur Komplexitätsklasse.

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)

Rekursionsgleichung (Master-Theorem)

Für Divide-and-Conquer-Verfahren; Lösung hängt vom Verhältnis zwischen f(n) und n^(log_b a) ab.

Musterlösung

Mergesort über die Rekursionsgleichung analysieren

Stellen Sie für Mergesort die Rekursionsgleichung auf und bestimmen Sie die Laufzeit mit dem Master-Theorem sowie über den Rekursionsbaum.

Schritt 1 — Reduktionsschritt
Mergesort teilt ein Array der Länge n in zwei Hälften der Länge n/2, sortiert beide rekursiv und mischt sie (merge) in linearer Zeit Θ(n) wieder zusammen.
Schritt 2 — Rekursionsgleichung aufstellen
Daraus folgt T(n) = 2·T(n/2) + c·n mit Basisfall T(1) = Θ(1). Der Term 2·T(n/2) erfasst die beiden rekursiven Aufrufe, c·n den linearen Mischaufwand.
Rekursionsgleichung (Master-Theorem)
$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)$
Für Divide-and-Conquer-Verfahren; Lösung hängt vom Verhältnis zwischen f(n) und n^(log_b a) ab.
Schritt 3 — Master-Theorem anwenden
Mit a = 2 und b = 2 ist n^(log_b a) = n^(log_2 2) = n^1 = n. Da f(n) = Θ(n) genau der Vergleichsgröße n^(log_b a) entspricht, greift Fall 2: T(n) = Θ(n^(log_b a) · log n) = Θ(n log n).
Schritt 4 — Probe über den Rekursionsbaum
Der Rekursionsbaum hat log_2 n Ebenen; auf jeder Ebene summiert sich die Mischarbeit aller Teilprobleme zu c·n. Gesamtaufwand: c·n · log_2 n = Θ(n log n). Beide Wege liefern dasselbe Ergebnis.

Ergebnis: T(n) = 2·T(n/2) + Θ(n) ∈ Θ(n log n) — garantiert, unabhängig von der Eingabe (Best, Average und Worst Case).

Typische Fehler

Basisfall vergessen oder unerreichbar — Endlosrekursion und StackOverflowError.
Naive rekursive Fibonacci ohne Memoisierung verwendet — exponentielle Laufzeit O(φⁿ) statt O(n).
Reduktionsschritt verkleinert das Problem nicht (Argument bleibt gleich) — keine Terminierung.
Endrekursion für „in Java automatisch optimiert" gehalten — die JVM ersetzt sie nicht durch eine Schleife.

LK-Vertiefung

eA-Vertiefung: Zeigen Sie, dass Mergesort mit T(n) = 2T(n/2) + O(n) die Komplexität T(n) ∈ O(n log n) hat (Master-Theorem, Fall 2).

Aktive Wiederholung

Implementieren Sie die Türme-von-Hanoi-Lösung rekursiv und beurteilen Sie, warum eine iterative Variante deutlich komplexer wäre.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Sortierverfahren — Bubble, Insertion, Merge, Quick#

StandardNRW-IF1BY-Inf-2

Insertion Sort — Trace über [5, 2, 4, 6, 1, 3]

Abb. 1Pro Durchgang wird das nächste Element in die sortierte Teilfolge eingefügt (Spalten 0–5 = Array-Positionen); Worst-/Average-Case O(n²), Best Case O(n) bei vorsortierten Daten, in-place und stabil.

Sortieren ist eines der am gründlichsten untersuchten Probleme der Informatik, weil zahlreiche andere Verfahren (binäre Suche, Mengenoperationen, Median, Duplikaterkennung) sortierte Daten voraussetzen. Verfahren klassifiziert man entlang dreier Achsen, die in Klausuren gegenübergestellt werden müssen: vergleichsbasiert vs. nicht-vergleichsbasiert, stabil vs. instabil und in-place (konstanter Zusatzspeicher) vs. nicht in-place. Erst diese Eigenschaften — nicht allein die O-Klasse — entscheiden über die Eignung im konkreten Einsatz.

Der Bubble Sort vertauscht wiederholt benachbarte Elemente, die in falscher Reihenfolge stehen, bis kein Tausch mehr nötig ist; mit O(n²) Vergleichen ist er langsam und dient vor allem der Veranschaulichung (mit Abbruch-Flag erreicht er im Best Case O(n)). Der Insertion Sort fügt jedes neue Element in den bereits sortierten Präfix ein; er ist stabil und in-place, im Worst Case O(n²), im Best Case (vorsortiert) aber O(n) und damit für kleine oder fast sortierte Arrays praktisch sehr schnell.

Der Merge Sort ist ein Divide-and-Conquer-Verfahren: Er halbiert das Array rekursiv bis zu einelementigen Teilen und mischt anschließend sortierte Teilfolgen in linearer Zeit zusammen. Seine Laufzeit T(n) = 2·T(n/2) + Θ(n) ergibt Θ(n log n) garantiert — auch im Worst Case —, und er ist stabil; er benötigt jedoch O(n) Zusatzspeicher für das Mischen und ist daher nicht in-place.

Der Quick Sort wählt ein Pivot-Element, partitioniert das Array in „≤ Pivot" und „≥ Pivot" und sortiert beide Teile rekursiv (siehe die Lomuto-Partition im Rechenbeispiel). Im Average und Best Case läuft er in O(n log n), ist dabei in-place und hat sehr kleine, cache-freundliche Konstanten; im Worst Case aber O(n²) — etwa bei bereits sortierter Eingabe mit Pivot = erstes/letztes Element. Eine zufällige oder Median-of-Three-Pivotwahl macht diesen Fall unwahrscheinlich; Quick Sort ist nicht stabil.

Ein Verfahren heißt stabil, wenn Elemente mit gleichem Schlüssel ihre relative Reihenfolge behalten. Das ist entscheidend für mehrstufiges Sortieren: Sortiert man eine Tabelle erst nach Vorname und dann stabil nach Nachname, bleibt die Vorname-Ordnung innerhalb gleicher Nachnamen erhalten. Insertion und Merge Sort sind stabil; Quick und Heap Sort sind es in der Standardform nicht.

Im Vergleichsmodell (Elemente werden nur paarweise verglichen) gilt die bewiesene untere Schranke Ω(n log n): Jeder vergleichsbasierte Sortieralgorithmus braucht im Worst Case mindestens proportional n log n Vergleiche, weil ein Entscheidungsbaum mit n! Blättern die Tiefe ⌈log₂(n!)⌉ ∈ Ω(n log n) hat. Nicht-vergleichsbasierte Verfahren wie Counting Sort oder Radix Sort unterliegen dieser Schranke nicht und erreichen unter Zusatzannahmen (kleiner, bekannter Wertebereich) sogar O(n).

In der Praxis nutzt Java TimSort — einen stabilen, auf reale (teils vorsortierte) Daten optimierten Merge Sort — für `Arrays.sort` auf Objekten und einen Dual-Pivot-Quicksort für Primitive; ein bewusster Kompromiss zwischen Stabilität, Speicher und Konstanten.

Code Insertion Sort: ```java void insertionSort(int[] a) { for (int i = 1; i < a.length; i++) { int key = a[i], j = i - 1; while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } a[j+1] = key; } } ```

Vergleichszahl: n²/2 gegen n·log₂n

Abb. 2Konkrete Vergleichsanzahl quadratischer O(n²)-Verfahren (Bubble/Insertion, ~n²/2) gegenüber O(n log n)-Verfahren (Merge/Quick) und der linearen Referenz n für n bis 32. Schon ab kleinem n läuft die quadratische Kurve allen davon.

Musterlösung

Big-O-Analyse einer geschachtelten Schleife

Bestimmen Sie die Zeitkomplexität in O-Notation für folgenden Java-Code: zwei verschachtelte Schleifen über n Elemente mit einer inneren O(log n)-Operation.

Schritt 1 — Codestruktur
```java for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { binarySearch(arr, key); // O(log n) } } ```
Schritt 2 — Iterationen zählen
Äußere Schleife n Iterationen, innere im Mittel n/2; insgesamt T(n) = n·(n+1)/2 ≈ n²/2 innere Aufrufe.
Schritt 3 — Kosten pro Iteration
Jeder innere Schritt kostet O(log n). Gesamtkosten: O(n²/2 · log n).
Schritt 4 — Asymptotische Vereinfachung
Konstanter Faktor 1/2 entfällt; Ergebnis ist O(n² log n).

Ergebnis: Zeitkomplexität: O(n² log n); dominanter Term ist die quadratische äußere Verschachtelung.

Musterlösung

Quicksort — eine Lomuto-Partition Schritt für Schritt

Führen Sie auf dem Array [3, 7, 8, 5, 2, 1, 9, 5, 4] eine Lomuto-Partition mit dem Pivot a[hi] = 4 (letztes Element) durch und geben Sie die Endposition des Pivots an.

Schritt 1 — Pivot und Grenze festlegen
Pivot p = a[hi] = 4. Der Index i (Grenze des „≤-Bereichs") startet auf i = lo − 1 = −1; j durchläuft die Positionen lo … hi−1, also 0 … 7.
Schritt 2 — Durchlauf mit Tausch bei a[j] ≤ Pivot
j=0: 3 ≤ 4 → i=0, Tausch a[0]↔a[0] → [3,7,8,5,2,1,9,5,4]. j=1,2,3: 7,8,5 > 4 → kein Tausch. j=4: 2 ≤ 4 → i=1, Tausch a[1]↔a[4] → [3,2,8,5,7,1,9,5,4]. j=5: 1 ≤ 4 → i=2, Tausch a[2]↔a[5] → [3,2,1,5,7,8,9,5,4]. j=6,7: 9,5 > 4 → kein Tausch.
Schritt 3 — Pivot an die Trennstelle setzen
Nach der Schleife ist i = 2. Pivot kommt auf i+1 = 3: Tausch a[3]↔a[hi]=a[8] → [3,2,1,4,7,8,9,5,5]. Der Pivot 4 steht jetzt am Index 3.
Schritt 4 — Invariante prüfen
Linker Teil [3,2,1] enthält nur Werte ≤ 4, rechter Teil [7,8,9,5,5] nur Werte ≥ 4. Der Pivot ist an seiner endgültigen Sortierposition; Quicksort sortiert beide Teile rekursiv weiter.

Ergebnis: Nach der Partition: [3,2,1,4,7,8,9,5,5]; der Pivot 4 liegt endgültig auf Index 3 (3 Elemente links, 5 rechts).

Typische Fehler

Merge Sort als „in-place" bezeichnet — falsch, er braucht O(n) Hilfsspeicher.
Quick-Sort-Worst-Case mit O(n log n) angegeben — tatsächlich O(n²) bei schlechter Pivotwahl.
Bubble Sort und Selection Sort verwechselt: Bubble tauscht benachbart, Selection sucht je Runde das Minimum.
Stabilität mit Laufzeit vermengt — Stabilität ist eine separate, von der O-Klasse unabhängige Eigenschaft.

LK-Vertiefung

eA-Vertiefung: Übersicht der Vergleichszahlen (worst/average/best) — Bubble Sort O(n²)/O(n²)/O(n) (mit Abbruch-Flag), Insertion Sort O(n²)/O(n²)/O(n), Selection Sort O(n²) in allen Fällen (~n²/2 Vergleiche, aber nur O(n) Tausche), Merge Sort O(n log n) garantiert (stabil, O(n) Zusatzspeicher), Quick Sort O(n²)/O(n log n)/O(n log n) (in-place, nicht stabil). Begründen Sie, warum nur die vergleichsbasierten Verfahren der unteren Schranke Ω(n log n) unterliegen, Zählsortierung dagegen nicht.

Aktive Wiederholung

Vergleichen Sie Insertion Sort, Merge Sort und Quick Sort hinsichtlich Zeit-/Speicherkomplexität, Stabilität und Eignung für eingebettete Systeme.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Such-Algorithmen — linear und binär#

BasisNRW-IF1BY-Inf-2

Die lineare (sequentielle) Suche durchläuft das Array Element für Element und vergleicht jeweils mit dem Suchschlüssel. Sie funktioniert auf unsortierten Daten, braucht keinerlei Vorbereitung und kostet im Worst Case O(n) Vergleiche (Best Case O(1), wenn schon das erste Element passt). Liegt keine Ordnung vor, ist sie die einzige Option.

Die binäre Suche setzt ein sortiertes Array voraus und nutzt diese Ordnung aus: Sie prüft wiederholt das mittlere Element und halbiert den Suchbereich — ist der Schlüssel kleiner, sucht sie links weiter, sonst rechts. Da pro Schritt die Hälfte der Kandidaten wegfällt, braucht sie nur O(log n) Vergleiche; für eine Million Elemente genügen rund 20. Ihre tragende Schleifeninvariante lautet: „Falls der Schlüssel im Array vorkommt, dann im aktuellen Intervall [lo, hi]".

Code binäre Suche: ```java int binSuche(int[] a, int key) { int lo = 0, hi = a.length - 1; while (lo <= hi) { int m = (lo + hi) >>> 1; // overflow-safe if (a[m] == key) return m; if (a[m] < key) lo = m + 1; else hi = m - 1; } return -1; } ```

Drei Implementierungsdetails entscheiden über die Korrektheit: Die Mittenberechnung `(lo + hi) / 2` kann bei großen Indizes überlaufen; man schreibt deshalb `lo + (hi − lo) / 2` oder den vorzeichenlosen Shift `(lo + hi) >>> 1`. Die Abbruchbedingung muss `lo <= hi` lauten (nicht `lo < hi`, sonst wird ein Randelement übersehen). Und das Verschieben `lo = m + 1` bzw. `hi = m − 1` (nicht `m`) sichert die Terminierung, weil das Intervall echt schrumpft.

Die Wahl des Suchverfahrens folgt dem Zugriffsmuster und dem Vorbereitungsaufwand. Bei kleinen n (grob n < 20) ist die lineare Suche praktisch oft schneller, weil sie cache-freundlich und ohne Sprung-Overhead arbeitet. Die binäre Suche lohnt nur, wenn die Daten bereits sortiert sind oder mehrfach durchsucht werden — einmaliges Sortieren kostet selbst O(n log n) und würde eine einzelne Suche nicht aufwiegen. Typische Einsatzfelder sind Wörterbuch- und Telefonbuchsuche sowie Datenbank-Indizes.

Geht es nicht um eine geordnete Suche, sondern nur um Existenz oder Zuordnung eines Schlüssels, liefern Hashtabellen im Durchschnitt O(1) (Querverweis Datenstrukturen). Der Preis ist der Verlust der Sortierung und ein möglicher O(n)-Worst-Case bei vielen Kollisionen — die Entscheidung zwischen sortiertem Array mit binärer Suche und Hashtabelle ist eine klassische Abwägung zwischen geordneter Iteration und schnellstem Punktzugriff.

Typische Fehler

Binäre Suche auf unsortierten Daten angewandt — das Ergebnis ist dann falsch.
Endlosschleife durch `lo < hi` statt `lo <= hi` oder durch Verschieben auf `m` statt `m ± 1`.
Mittenüberlauf bei `(lo + hi) / 2` für große Arrays unterschätzt.
Aufwand fürs vorherige Sortieren ignoriert — bei einmaliger Suche ist lineare Suche insgesamt billiger.

LK-Vertiefung

eA-Vertiefung: Beweisen Sie die Schleifeninvariante der iterativen binären Suche per Induktion über die Durchläufe (Erhalt der Invariante und Terminierung über die echt fallende Intervalllänge hi − lo + 1) und leiten Sie die obere Schranke ⌈log₂(n+1)⌉ für die Vergleichsanzahl her.

Aktive Wiederholung

Implementieren Sie die binäre Suche iterativ und beweisen Sie, dass die Schleifeninvariante „falls key in a vorkommt, dann im Intervall [lo, hi]" gilt.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

O-Notation und Komplexitätsanalyse#

StandardNRW-IF1BY-Inf-2BW-Inf-3

Big-O-Wachstumsklassen im Vergleich

Abb. 3Asymptotisches Verhalten typischer Komplexitätsklassen für n = 1…20. Exponentielles 2ⁿ und n² dominieren ab kleiner Eingabe; logarithmische Verfahren bleiben praktisch konstant.

Die Komplexitätsanalyse schätzt, wie der Ressourcenbedarf (Zeit, Speicher) eines Algorithmus mit der Eingabegröße n wächst — unabhängig von Rechner, Sprache und Compiler. Maßgeblich ist das asymptotische Verhalten für große n, denn dort entscheidet sich die Praktikabilität. Statt absolute Sekunden zu messen, zählt man die dominierenden Elementaroperationen als Funktion von n.

Die O-Notation (nach Bachmann und Landau) beschreibt eine asymptotische obere Schranke: f ∈ O(g) bedeutet, dass Konstanten c > 0 und n₀ existieren mit f(n) ≤ c·g(n) für alle n ≥ n₀ — f wächst „höchstens so schnell wie" g, bis auf konstante Faktoren und kleine n. Ergänzt wird sie durch die untere Schranke Ω(g) („mindestens so schnell") und die exakte Schranke Θ(g) (oben und unten zugleich, also „genau so schnell wie").

Die zentrale Wachstumshierarchie lautet O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ) ⊂ O(n!). Anschaulich: Indexzugriff ist O(1), binäre Suche O(log n), lineare Suche O(n), gute Sortierverfahren O(n log n), eine doppelte Schleife O(n²), das Durchprobieren aller Teilmengen O(2ⁿ). Der Unterschied ist gewaltig — für n = 10⁶ bedeutet O(log n) rund 20 Schritte, O(n) eine Million, O(n²) bereits 10¹², und O(2ⁿ) sprengt schon ab n ≈ 60 jede Rechenzeit (siehe nebenstehende Wachstumskurven).

Die Herleitung aus dem Code folgt festen Regeln: Aufeinanderfolgende Blöcke werden addiert, wobei der dominante Term die Klasse bestimmt; geschachtelte Schleifen werden multipliziert; und nur der höchste Term zählt, da niedrigere Terme und konstante Faktoren wegfallen (O(3n² + 5n + 7) = O(n²)). Eine Schleife, die den Bereich pro Durchlauf halbiert, trägt einen log-n-Faktor bei — das ist der Ursprung jedes „log n" in der Analyse.

Für Divide-and-Conquer-Rekurrenzen der Form T(n) = a·T(n/b) + f(n) liefert das Master-Theorem die Lösung über den Vergleich von f(n) mit n^(log_b a): Je nachdem, ob die Rekursion oder das Zusammenfügen dominiert (oder beide ausgeglichen sind), greift einer von drei Fällen. Mergesort (a = 2, b = 2, f = Θ(n)) fällt in den ausgeglichenen Fall 2 und ergibt Θ(n log n).

Zu unterscheiden sind Best-, Average- und Worst-Case; Klausuren verlangen meist den Worst Case (die Garantie) und oft den Average Case (das typische Verhalten). Die amortisierte Analyse mittelt die Kosten über eine Operationsfolge: Das Anhängen an ein dynamisches Array (ArrayList) kostet einzeln gelegentlich O(n) wegen der Verdopplung, über viele Operationen hinweg aber O(1) amortisiert.

Die O-Notation bleibt eine obere Schranke, keine exakte Laufzeit; konstante Faktoren werden bewusst ignoriert, können in der Praxis aber durch Cache-Verhalten, Pipelining und Speicherzugriffsmuster dominieren. Deshalb schlägt ein O(n²)-Verfahren für kleine n mitunter einen O(n log n)-Algorithmus — die Asymptotik gilt erst „ab hinreichend großem n".

f(n) \in \mathcal{O}(g(n)) \iff \exists c>0,\;n_0\in\mathbb{N}:\; \forall n\ge n_0\; f(n) \le c\cdot g(n)

Definition der O-Notation

Asymptotische obere Schranke; konstante Faktoren und niedrigere Terme werden ignoriert.

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)

Rekursionsgleichung (Master-Theorem)

Für Divide-and-Conquer-Verfahren; Lösung hängt vom Verhältnis zwischen f(n) und n^(log_b a) ab.

Musterlösung

Big-O-Analyse einer geschachtelten Schleife

Bestimmen Sie die Zeitkomplexität in O-Notation für folgenden Java-Code: zwei verschachtelte Schleifen über n Elemente mit einer inneren O(log n)-Operation.

Schritt 1 — Codestruktur
```java for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { binarySearch(arr, key); // O(log n) } } ```
Schritt 2 — Iterationen zählen
Äußere Schleife n Iterationen, innere im Mittel n/2; insgesamt T(n) = n·(n+1)/2 ≈ n²/2 innere Aufrufe.
Schritt 3 — Kosten pro Iteration
Jeder innere Schritt kostet O(log n). Gesamtkosten: O(n²/2 · log n).
Schritt 4 — Asymptotische Vereinfachung
Konstanter Faktor 1/2 entfällt; Ergebnis ist O(n² log n).

Ergebnis: Zeitkomplexität: O(n² log n); dominanter Term ist die quadratische äußere Verschachtelung.

Typische Fehler

O-Notation als exakte Laufzeit gelesen — sie ist nur eine obere Schranke.
Konstante Faktoren mitgeschleppt: O(2n) statt O(n), O(n²/2) statt O(n²).
Geschachtelte Schleifen additiv statt multiplikativ gerechnet (O(n) + O(n) statt O(n·n)).
log n und n log n vermischt; O und Ω gleichgesetzt.

LK-Vertiefung

eA-Vertiefung: Beweisen Sie mit dem Vergleichsmodell die untere Schranke Ω(n log n) für vergleichsbasierte Sortieralgorithmen über die Entscheidungsbaumtiefe.

Aktive Wiederholung

Analysieren Sie die Komplexität des Algorithmus „für jedes Element eines Arrays der Länge n eine binäre Suche im selben Array" und begründen Sie das Ergebnis.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Algorithmenstrategien — Greedy, Divide-and-Conquer, Backtracking#

VertiefungBY-Inf-2NRW-IF6BW-Inf-3

Die Greedy-Strategie trifft in jedem Schritt die lokal beste Entscheidung und revidiert sie nie. Sie ist einfach und schnell, liefert aber nur dann das globale Optimum, wenn sich dies beweisen lässt — etwa über die Matroid-Eigenschaft (Kruskals minimaler Spannbaum) oder ein Austausch-/Vertauschungsargument (Huffman-Codierung, Aktivitätenauswahl). Wo dieser Nachweis fehlt, ist Greedy bloß eine Heuristik, die das Optimum verfehlen kann.

Die Teile-und-herrsche-Strategie (Divide-and-Conquer) zerlegt ein Problem rekursiv in kleinere, gleichartige Teilprobleme, löst diese und kombiniert ihre Lösungen — Mergesort, Quicksort und die schnelle Multiplikation (Karatsuba) sind Beispiele. Ihre Laufzeit wird über eine Rekursionsgleichung und das Master-Theorem bestimmt; strukturell baut sie auf rekursiven Datenstrukturen (Bäume) auf (Querverweis Datenstrukturen).

Das Backtracking durchsucht den Lösungsraum systematisch als Tiefensuche und nimmt eine Teilentscheidung zurück, sobald sie nachweislich in keine gültige Lösung mehr führen kann. Klassiker sind das 8-Damen-Problem, Sudoku und das Erfüllbarkeitsproblem (SAT). Über die Laufzeit entscheidet das Beschneiden (Pruning) aussichtsloser Teilbäume — ohne Pruning entartet die Suche zur vollständigen, exponentiellen Aufzählung.

Die dynamische Programmierung (DP) löst Probleme, die zwei Bedingungen erfüllen: optimale Substruktur (die optimale Gesamtlösung setzt sich aus optimalen Teillösungen zusammen) und überlappende Teilprobleme (dieselben Teilprobleme treten mehrfach auf). Sie berechnet jedes Teilergebnis genau einmal — als Memoisierung (Top-Down, rekursiv mit Cache) oder als Tabelle (Bottom-Up, iterativ) — und ersetzt so exponentielle Mehrfachberechnung durch polynomiellen Aufwand.

Beispiel DP — Fibonacci O(n) statt O(2ⁿ): ```python def fib(n): dp = [0, 1] for i in range(2, n+1): dp.append(dp[i-1] + dp[i-2]) return dp[n] ```

Die Wahl der Strategie folgt der Problemstruktur: Ohne optimale Substruktur scheidet DP aus; ohne beweisbare Greedy-Optimalität liefert Greedy nur Näherungen. Am 0/1-Rucksackproblem wird der Unterschied scharf — die gierige Wahl nach bestem Wert-pro-Gewicht ist hier nicht optimal (jeder Gegenstand ist unteilbar), während DP über eine Tabelle (Kapazität × Gegenstände) das Optimum in O(n·W) findet.

Ein lehrreiches Greedy-Gegenbeispiel ist das Münzwechselproblem mit den Werten {1, 3, 4} und Betrag 6: Greedy nimmt erst die 4, dann zweimal die 1 (drei Münzen), optimal sind aber 3 + 3 (zwei Münzen). Für die Euro-Standardstückelung funktioniert Greedy zwar — gerade das zeigt, dass Greedy-Korrektheit stets bewiesen und nie unterstellt werden darf.

T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)

Rekursionsgleichung (Master-Theorem)

Für Divide-and-Conquer-Verfahren; Lösung hängt vom Verhältnis zwischen f(n) und n^(log_b a) ab.

Typische Fehler

Greedy ohne Beweis als optimal angenommen — die Optimalität muss über Matroid- oder Austauschargument gezeigt werden.
Backtracking ohne Beschneidung (Pruning) formuliert — die Laufzeit explodiert.
DP mit Memoisierung ohne Basisfall implementiert — Endlosrekursion.
Optimale Substruktur unterstellt, wo keine vorliegt — DP liefert dann ein falsches Optimum.

LK-Vertiefung

eA-Vertiefung: Skizzieren Sie eine DP-Tabelle für das 0/1-Rucksackproblem mit n Gegenständen und Kapazität W; Laufzeit O(nW), pseudopolynomial.

Aktive Wiederholung

Analysieren Sie das Rucksackproblem (0/1-Variante) hinsichtlich Greedy- und DP-Lösbarkeit und beurteilen Sie, warum Greedy hier nicht zum Optimum führt.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.