DE-Abitur · InformatikT·011 / 8

Algorithmen, Programmierung und Kontrollstrukturen

Vom Algorithmusbegriff über Kontrollstrukturen bis hin zur Implementation in Java und Python. Schwerpunkte sind Spezifikation, Korrektheit, Iteration, Rekursion sowie modulare Zerlegung — die KMK EPA verortet diesen Kompetenzbereich an der Schnittstelle von „Modellieren/Implementieren" und „Strukturieren/Darstellen".

7Abschnitteca. 13Min Lesezeit3Kompetenzen

KB-MI · Modellieren und Implementieren — Algorithmen entwerfen, kodieren und testen.KB-SD · Strukturieren und Darstellen — Programme dokumentieren und in Sprachen formulieren.KB-BB · Begründen und Bewerten — Effizienz und Korrektheit von Algorithmen analysieren.

Operatoren:analysieren · erläutern · implementieren · beurteilen · darstellen

grundlegendes Niveau

gA: Algorithmus als endliche Folge wohldefinierter Schritte erklären, Sequenz/Selektion/Iteration in Java oder Python implementieren, einfache Schleifeninvarianten benennen.

erhöhtes Niveau

eA: Rekursion vs. Iteration vergleichen, Schleifeninvarianten formal nachweisen, Komplexität in O-Notation angeben und nicht-triviale Algorithmen (Euklid, Ackermann qualitativ) analysieren.

Inhalt · 7 Abschnitte

Algorithmen, Programmierung und Kontrollstrukturen

Algorithmusbegriff, Spezifikation und Korrektheit#

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

Kernpunkte

Ein Algorithmus ist eine endliche Folge von eindeutig ausführbaren Anweisungen zur Lösung einer Problemklasse (Knuth 1968).
Algorithmen sind sprachunabhängig; eine Implementation ist ihre Umsetzung in einer konkreten Programmiersprache.
Eigenschaften nach dem üblichen deutschen Kanon: Endlichkeit (statisch + dynamisch), Eindeutigkeit (Determinismus), Ausführbarkeit (jeder Schritt durchführbar), Allgemeinheit (Klasse von Eingaben). Knuth (1968) nennt fünf etwas andere Punkte (Finiteness, Definiteness, Input, Output, Effectiveness) — er führt Ein-/Ausgabe gesondert auf statt der Allgemeinheit.
Eine Spezifikation beschreibt Vorbedingung (was darf erwartet werden), Nachbedingung (was wird garantiert) und ggf. Invarianten.
Korrektheit zerfällt in partielle Korrektheit (Nachbedingung gilt, falls Programm terminiert) und totale Korrektheit (Programm terminiert zudem).
Hoare-Tripel {P} S {Q} dokumentieren Beweise; gA-Niveau: informell, eA: Hoare-Kalkül.

HOARE-TRIPEL

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

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

Typische Fehler

Algorithmus wird mit Programm gleichgesetzt; sprachliche und logische Ebene werden vermischt.
Determinismus mit Determiniertheit verwechselt: deterministisch (eindeutiger nächster Schritt) ≠ determiniert (gleiches Ergebnis bei gleicher Eingabe).
Nachbedingung ohne Vorbedingung; resultierende „Beweise" decken nicht alle Eingaben ab.

LK-Vertiefung

eA-Vertiefung: Formulieren Sie ein Hoare-Tripel für eine while-Schleife, die das Maximum eines Arrays bestimmt, und beweisen Sie die Schleifeninvariante.

Sequenz, Selektion, Iteration und Funktionen#

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

Kernpunkte

Drei strukturierte Grundbausteine nach Böhm-Jacopini: Sequenz, Selektion (if/else, switch), Iteration (while, for, do-while).
Jeder Algorithmus lässt sich strukturiert (ohne goto) formulieren — Theorem von Böhm und Jacopini, 1966.
Funktionen kapseln wiederverwendbaren Code; Parameter werden in Java per Wert (Primitive) bzw. per Referenz (Objekte) übergeben.
Lokale Variablen leben nur innerhalb des Blocks; echte globale Variablen gibt es in Java nicht — das nächste Äquivalent sind klassenweite statische Felder, deren weiträumige Nutzung jedoch als schlechter Stil gilt.
Schleifenbedingung wird vor jedem Durchlauf (while) oder nach jedem Durchlauf (do-while) ausgewertet; for-Schleife ist Spezialfall mit Init/Test/Update.
Code-Beispiel: ```java int summe(int[] werte) { int s = 0; for (int x : werte) s += x; return s; } ```

Typische Fehler

Verwechslung von `=` (Zuweisung) und `==` (Vergleich) in Java/Python-Bedingungen.
Off-by-one-Fehler in for-Schleifen: `i <= n` statt `i < n` führt zu Out-of-Bounds.
do-while-Schleife durchläuft Rumpf immer mindestens einmal — wird übersehen, falls Eingabe schon valid ist.
Python-Einrückung wird nicht konsistent benutzt; Java-geschweifte Klammern werden vergessen.

Rekursion und Iteration im Vergleich#

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

Kernpunkte

Eine rekursive Funktion ruft sich selbst auf; jede Rekursion benötigt mindestens einen Basisfall und einen Reduktionsschritt, der das Problem verkleinert.
Beispiel Fakultät: ```java int fak(int n) { if (n <= 1) return 1; return n * fak(n - 1); } ```
Rekursion nutzt den Aufrufstapel: jeder Aufruf hat einen eigenen Stack Frame mit Parametern und lokalen Variablen.
Stack-Overflow tritt auf, wenn Rekursionstiefe den Stack erschöpft (Standard JVM: ca. 10⁴–10⁵ Frames).
Endrekursion (tail recursion) kann theoretisch in eine Schleife transformiert werden; Java optimiert dies nicht automatisch (Kotlin/Scheme schon).
Rekursion ist natürlich für rekursive Datenstrukturen (Bäume, Listen) und Divide-and-Conquer; Iteration ist meist effizienter und stackärmer.

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.

Musterlösung

BFS und DFS auf einem Beispielgraphen

Geben Sie die BFS- und DFS-Reihenfolge ausgehend von Knoten A im Graphen mit Kanten {A-B, A-C, B-D, B-E, C-F} an.

Schritt 1 — Datenstrukturen wählen
BFS verwendet eine FIFO-Queue, DFS einen LIFO-Stack (bzw. Rekursion).
Schritt 2 — BFS Ablauf
Queue: [A] → besuche A, Queue: [B,C] → besuche B, Queue: [C,D,E] → C → D → E → F. Reihenfolge: A, B, C, D, E, F.
Schritt 3 — DFS rekursiv ab A
A → B → D (zurück) → E (zurück, zurück) → C → F. Reihenfolge: A, B, D, E, C, F.
Schritt 4 — Komplexität
Beide Verfahren laufen in O(V + E) auf Adjazenzlisten. BFS findet kürzeste Pfade in ungewichteten Graphen, DFS eignet sich für Topologische Sortierung.

Ergebnis: BFS: A, B, C, D, E, F. DFS: A, B, D, E, C, F.

Typische Fehler

Basisfall vergessen — Endlosrekursion und Stack-Overflow.
Rekursive Fibonacci-Implementation ohne Memoisierung: exponentielle Laufzeit O(φⁿ).
Schleifenvariable wird in der Rekursion nicht reduziert — keine Termination.

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).

Sortierverfahren — Bubble, Insertion, Merge, Quick#

StandardNRW-IF1BY-Inf-2

Kernpunkte

Bubble Sort: paarweises Vertauschen benachbarter Elemente; einfach, aber O(n²) — nur für Lehrzwecke.
Insertion Sort: jedes neue Element wird in den sortierten Präfix eingefügt; O(n²) Worst, O(n) Best, stabil, in-place.
Merge Sort: Divide-and-Conquer; teilt rekursiv, mischt sortierte Teilfolgen; O(n log n) garantiert, aber O(n) Zusatzspeicher.
Quick Sort: Pivot-basiertes Partitionieren; Average O(n log n), Worst O(n²) bei schlechter Pivot-Wahl (z.B. vorsortiert + erstes Element).
Stabilität bedeutet: gleiche Schlüssel behalten ihre Reihenfolge — wichtig für mehrstufiges Sortieren.
Java verwendet TimSort (modifizierter Merge Sort) für `Arrays.sort` auf Objekten und Dual-Pivot-Quicksort für Primitive.
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; } } ```

INSERTION SORT — TRACE ÜBER [5, 2, 4, 6, 1, 3]

Welche drei Beschriftungen in "Insertion Sort — Trace über [5, 2, 4, 6, 1, 3]" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Pro Durchgang wird das nächste Element in die sortierte Teilfolge eingefügt; Worst-Case O(n²).

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" bezeichnen — falsch; O(n) Hilfsspeicher.
Quick Sort Worst-Case wird mit O(n log n) angegeben — tatsächlich O(n²).
Bubble Sort und Selection Sort werden verwechselt: ersteres tauscht benachbart, letzteres sucht Minimum.

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.

Such-Algorithmen — linear und binär#

BasisNRW-IF1BY-Inf-2

Kernpunkte

Lineare Suche: durchläuft Array sequenziell, O(n); funktioniert auf unsortierten Daten.
Binäre Suche: setzt sortiertes Array voraus; halbiert den Suchbereich rekursiv oder iterativ. O(log n).
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; } ```
Anwendungsfälle: Wörterbuchsuche, Telefonbuch, Datenbank-Indizes.
Bei kleinen n (n < ca. 20) ist lineare Suche praktisch schneller — Cache-Vorteil.
Hash-Tabellen liefern O(1) im Durchschnitt — wenn Eingaben nicht sortiert vorliegen müssen.

Typische Fehler

Binäre Suche auf unsortierten Daten anwenden — falsches Ergebnis.
Endlosschleife durch `lo < hi` statt `lo <= hi`.
Off-by-one bei `m + 1` vs. `m - 1` führt zu Endlosschleife oder Übersehen des Elements.

O-Notation und Komplexitätsanalyse#

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

Kernpunkte

O-Notation beschreibt asymptotische obere Schranke: f ∈ O(g) bedeutet, dass f höchstens proportional zu g wächst.
Hierarchie: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ) ⊂ O(n!).
Beispiele: Indexzugriff O(1), Suche in BST O(log n) im Mittel, Sortieren mind. Ω(n log n) im Vergleichsmodell.
Untere Schranke Ω(g) und exakte Schranke Θ(g) ergänzen die O-Notation.
Amortisierte Analyse: Folge von Operationen wird im Mittel gewichtet — z.B. dynamisches Array O(1) amortisiert für append.
Konstante Faktoren werden in der O-Notation ignoriert; in der Praxis können sie aber dominieren (Cache, Pipelining).

DEFINITION DER O-NOTATION

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)

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

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.

BIG-O-WACHSTUMSKLASSEN IM VERGLEICH

Welche drei Beschriftungen in "Big-O-Wachstumsklassen im Vergleich" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

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

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 interpretiert; tatsächlich nur obere Schranke.
Konstanten werden mitgenommen: O(2n) statt O(n).
Verschachtelte Schleifen werden additiv statt multiplikativ berechnet.
log n und n log n werden vermischt.

LK-Vertiefung

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

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

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

Kernpunkte

Greedy: trifft in jedem Schritt lokal optimale Entscheidung; global optimal nur bei nachweisbarer Optimalität — etwa über die Matroid-Eigenschaft (Kruskal) oder ein Austausch-/Vertauschungsargument (Huffman).
Divide-and-Conquer: zerlegt rekursiv, löst Teilprobleme, kombiniert Lösungen (Mergesort, Strassen-Multiplikation, Quickhull).
Backtracking: systematische Tiefensuche im Lösungsraum mit Rücknahme; Beispiele 8-Damen-Problem, Sudoku, SAT.
Dynamische Programmierung: optimale Substruktur + überlappende Teilprobleme; Memoisierung (Top-Down) oder Tabelle (Bottom-Up).
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] ```
Wahl der Strategie hängt von Problemstruktur ab: ohne optimale Substruktur kein DP; Greedy liefert nur dann global Optimales, wenn sich die Optimalität beweisen lässt (Matroid- bzw. Austauschargument).
Querverweis: Divide-and-Conquer baut auf den rekursiven Datenstrukturen (Bäume, Graphen) des Topics Datenstrukturen auf; Greedy-Verfahren wie Dijkstra werden dort vertieft.

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.

Typische Fehler

Greedy wird ohne Beweis als optimal angenommen.
Backtracking ohne Beschneidung (Pruning) — Laufzeit explodiert.
DP wird mit Memoisierung ohne Basisfall implementiert — Endlosrekursion.

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.

Wird geladen

EuraStudy

Dein Lernraum wird vorbereitet — Curriculum, Notizen und KI verbinden sich.

Algorithmen, Programmierung und Kontrollstrukturen

7Abschnitteca. 13Min Lesezeit3Kompetenzen

Operatoren:analysieren · erläutern · implementieren · beurteilen · darstellen

grundlegendes Niveau

gA: Algorithmus als endliche Folge wohldefinierter Schritte erklären, Sequenz/Selektion/Iteration in Java oder Python implementieren, einfache Schleifeninvarianten benennen.

erhöhtes Niveau

eA: Rekursion vs. Iteration vergleichen, Schleifeninvarianten formal nachweisen, Komplexität in O-Notation angeben und nicht-triviale Algorithmen (Euklid, Ackermann qualitativ) analysieren.

Algorithmusbegriff, Spezifikation und Korrektheit#

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

Kernpunkte

Ein Algorithmus ist eine endliche Folge von eindeutig ausführbaren Anweisungen zur Lösung einer Problemklasse (Knuth 1968).
Algorithmen sind sprachunabhängig; eine Implementation ist ihre Umsetzung in einer konkreten Programmiersprache.
Eigenschaften nach dem üblichen deutschen Kanon: Endlichkeit (statisch + dynamisch), Eindeutigkeit (Determinismus), Ausführbarkeit (jeder Schritt durchführbar), Allgemeinheit (Klasse von Eingaben). Knuth (1968) nennt fünf etwas andere Punkte (Finiteness, Definiteness, Input, Output, Effectiveness) — er führt Ein-/Ausgabe gesondert auf statt der Allgemeinheit.
Eine Spezifikation beschreibt Vorbedingung (was darf erwartet werden), Nachbedingung (was wird garantiert) und ggf. Invarianten.
Korrektheit zerfällt in partielle Korrektheit (Nachbedingung gilt, falls Programm terminiert) und totale Korrektheit (Programm terminiert zudem).
Hoare-Tripel {P} S {Q} dokumentieren Beweise; gA-Niveau: informell, eA: Hoare-Kalkül.

HOARE-TRIPEL

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

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

Typische Fehler

Algorithmus wird mit Programm gleichgesetzt; sprachliche und logische Ebene werden vermischt.
Determinismus mit Determiniertheit verwechselt: deterministisch (eindeutiger nächster Schritt) ≠ determiniert (gleiches Ergebnis bei gleicher Eingabe).
Nachbedingung ohne Vorbedingung; resultierende „Beweise" decken nicht alle Eingaben ab.

LK-Vertiefung

eA-Vertiefung: Formulieren Sie ein Hoare-Tripel für eine while-Schleife, die das Maximum eines Arrays bestimmt, und beweisen Sie die Schleifeninvariante.

Sequenz, Selektion, Iteration und Funktionen#

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

Kernpunkte

Drei strukturierte Grundbausteine nach Böhm-Jacopini: Sequenz, Selektion (if/else, switch), Iteration (while, for, do-while).
Jeder Algorithmus lässt sich strukturiert (ohne goto) formulieren — Theorem von Böhm und Jacopini, 1966.
Funktionen kapseln wiederverwendbaren Code; Parameter werden in Java per Wert (Primitive) bzw. per Referenz (Objekte) übergeben.
Lokale Variablen leben nur innerhalb des Blocks; echte globale Variablen gibt es in Java nicht — das nächste Äquivalent sind klassenweite statische Felder, deren weiträumige Nutzung jedoch als schlechter Stil gilt.
Schleifenbedingung wird vor jedem Durchlauf (while) oder nach jedem Durchlauf (do-while) ausgewertet; for-Schleife ist Spezialfall mit Init/Test/Update.
Code-Beispiel: ```java int summe(int[] werte) { int s = 0; for (int x : werte) s += x; return s; } ```

Typische Fehler

Verwechslung von `=` (Zuweisung) und `==` (Vergleich) in Java/Python-Bedingungen.
Off-by-one-Fehler in for-Schleifen: `i <= n` statt `i < n` führt zu Out-of-Bounds.
do-while-Schleife durchläuft Rumpf immer mindestens einmal — wird übersehen, falls Eingabe schon valid ist.
Python-Einrückung wird nicht konsistent benutzt; Java-geschweifte Klammern werden vergessen.

Rekursion und Iteration im Vergleich#

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

Kernpunkte

Eine rekursive Funktion ruft sich selbst auf; jede Rekursion benötigt mindestens einen Basisfall und einen Reduktionsschritt, der das Problem verkleinert.
Beispiel Fakultät: ```java int fak(int n) { if (n <= 1) return 1; return n * fak(n - 1); } ```
Rekursion nutzt den Aufrufstapel: jeder Aufruf hat einen eigenen Stack Frame mit Parametern und lokalen Variablen.
Stack-Overflow tritt auf, wenn Rekursionstiefe den Stack erschöpft (Standard JVM: ca. 10⁴–10⁵ Frames).
Endrekursion (tail recursion) kann theoretisch in eine Schleife transformiert werden; Java optimiert dies nicht automatisch (Kotlin/Scheme schon).
Rekursion ist natürlich für rekursive Datenstrukturen (Bäume, Listen) und Divide-and-Conquer; Iteration ist meist effizienter und stackärmer.

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.

Musterlösung

BFS und DFS auf einem Beispielgraphen

Geben Sie die BFS- und DFS-Reihenfolge ausgehend von Knoten A im Graphen mit Kanten {A-B, A-C, B-D, B-E, C-F} an.

Schritt 1 — Datenstrukturen wählen
BFS verwendet eine FIFO-Queue, DFS einen LIFO-Stack (bzw. Rekursion).
Schritt 2 — BFS Ablauf
Queue: [A] → besuche A, Queue: [B,C] → besuche B, Queue: [C,D,E] → C → D → E → F. Reihenfolge: A, B, C, D, E, F.
Schritt 3 — DFS rekursiv ab A
A → B → D (zurück) → E (zurück, zurück) → C → F. Reihenfolge: A, B, D, E, C, F.
Schritt 4 — Komplexität
Beide Verfahren laufen in O(V + E) auf Adjazenzlisten. BFS findet kürzeste Pfade in ungewichteten Graphen, DFS eignet sich für Topologische Sortierung.

Ergebnis: BFS: A, B, C, D, E, F. DFS: A, B, D, E, C, F.

Typische Fehler

Basisfall vergessen — Endlosrekursion und Stack-Overflow.
Rekursive Fibonacci-Implementation ohne Memoisierung: exponentielle Laufzeit O(φⁿ).
Schleifenvariable wird in der Rekursion nicht reduziert — keine Termination.

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).

Sortierverfahren — Bubble, Insertion, Merge, Quick#

StandardNRW-IF1BY-Inf-2

Kernpunkte

Bubble Sort: paarweises Vertauschen benachbarter Elemente; einfach, aber O(n²) — nur für Lehrzwecke.
Insertion Sort: jedes neue Element wird in den sortierten Präfix eingefügt; O(n²) Worst, O(n) Best, stabil, in-place.
Merge Sort: Divide-and-Conquer; teilt rekursiv, mischt sortierte Teilfolgen; O(n log n) garantiert, aber O(n) Zusatzspeicher.
Quick Sort: Pivot-basiertes Partitionieren; Average O(n log n), Worst O(n²) bei schlechter Pivot-Wahl (z.B. vorsortiert + erstes Element).
Stabilität bedeutet: gleiche Schlüssel behalten ihre Reihenfolge — wichtig für mehrstufiges Sortieren.
Java verwendet TimSort (modifizierter Merge Sort) für `Arrays.sort` auf Objekten und Dual-Pivot-Quicksort für Primitive.
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; } } ```

INSERTION SORT — TRACE ÜBER [5, 2, 4, 6, 1, 3]

Welche drei Beschriftungen in "Insertion Sort — Trace über [5, 2, 4, 6, 1, 3]" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Pro Durchgang wird das nächste Element in die sortierte Teilfolge eingefügt; Worst-Case O(n²).

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" bezeichnen — falsch; O(n) Hilfsspeicher.
Quick Sort Worst-Case wird mit O(n log n) angegeben — tatsächlich O(n²).
Bubble Sort und Selection Sort werden verwechselt: ersteres tauscht benachbart, letzteres sucht Minimum.

LK-Vertiefung

Such-Algorithmen — linear und binär#

BasisNRW-IF1BY-Inf-2

Kernpunkte

Lineare Suche: durchläuft Array sequenziell, O(n); funktioniert auf unsortierten Daten.
Binäre Suche: setzt sortiertes Array voraus; halbiert den Suchbereich rekursiv oder iterativ. O(log n).
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; } ```
Anwendungsfälle: Wörterbuchsuche, Telefonbuch, Datenbank-Indizes.
Bei kleinen n (n < ca. 20) ist lineare Suche praktisch schneller — Cache-Vorteil.
Hash-Tabellen liefern O(1) im Durchschnitt — wenn Eingaben nicht sortiert vorliegen müssen.

Typische Fehler

Binäre Suche auf unsortierten Daten anwenden — falsches Ergebnis.
Endlosschleife durch `lo < hi` statt `lo <= hi`.
Off-by-one bei `m + 1` vs. `m - 1` führt zu Endlosschleife oder Übersehen des Elements.

O-Notation und Komplexitätsanalyse#

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

Kernpunkte

O-Notation beschreibt asymptotische obere Schranke: f ∈ O(g) bedeutet, dass f höchstens proportional zu g wächst.
Hierarchie: O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n log n) ⊂ O(n²) ⊂ O(2ⁿ) ⊂ O(n!).
Beispiele: Indexzugriff O(1), Suche in BST O(log n) im Mittel, Sortieren mind. Ω(n log n) im Vergleichsmodell.
Untere Schranke Ω(g) und exakte Schranke Θ(g) ergänzen die O-Notation.
Amortisierte Analyse: Folge von Operationen wird im Mittel gewichtet — z.B. dynamisches Array O(1) amortisiert für append.
Konstante Faktoren werden in der O-Notation ignoriert; in der Praxis können sie aber dominieren (Cache, Pipelining).

DEFINITION DER O-NOTATION

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)

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

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.

BIG-O-WACHSTUMSKLASSEN IM VERGLEICH

Welche drei Beschriftungen in "Big-O-Wachstumsklassen im Vergleich" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

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

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 interpretiert; tatsächlich nur obere Schranke.
Konstanten werden mitgenommen: O(2n) statt O(n).
Verschachtelte Schleifen werden additiv statt multiplikativ berechnet.
log n und n log n werden vermischt.

LK-Vertiefung

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

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

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

Kernpunkte

Greedy: trifft in jedem Schritt lokal optimale Entscheidung; global optimal nur bei nachweisbarer Optimalität — etwa über die Matroid-Eigenschaft (Kruskal) oder ein Austausch-/Vertauschungsargument (Huffman).
Divide-and-Conquer: zerlegt rekursiv, löst Teilprobleme, kombiniert Lösungen (Mergesort, Strassen-Multiplikation, Quickhull).
Backtracking: systematische Tiefensuche im Lösungsraum mit Rücknahme; Beispiele 8-Damen-Problem, Sudoku, SAT.
Dynamische Programmierung: optimale Substruktur + überlappende Teilprobleme; Memoisierung (Top-Down) oder Tabelle (Bottom-Up).
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] ```
Wahl der Strategie hängt von Problemstruktur ab: ohne optimale Substruktur kein DP; Greedy liefert nur dann global Optimales, wenn sich die Optimalität beweisen lässt (Matroid- bzw. Austauschargument).
Querverweis: Divide-and-Conquer baut auf den rekursiven Datenstrukturen (Bäume, Graphen) des Topics Datenstrukturen auf; Greedy-Verfahren wie Dijkstra werden dort vertieft.

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.

Typische Fehler

Greedy wird ohne Beweis als optimal angenommen.
Backtracking ohne Beschneidung (Pruning) — Laufzeit explodiert.
DP wird mit Memoisierung ohne Basisfall implementiert — Endlosrekursion.

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.