INF-Alg - Algorithmen, Programmierung und Komplexität — Informatik · Matura-Zusammenfassung

Kontrollstrukturen, Funktionen und Modularisierung#

BasisINF-Alg-1.1INF-Alg-1.2

Jeder Algorithmus, so komplex er auch sei, ist aus einem winzigen Wortschatz gebaut. Das Theorem von Böhm/Jacopini (1966) beweist, dass drei Kontrollstrukturen für jede berechenbare Funktion genügen: Sequenz (Anweisungen nacheinander), Selektion (if/else - eine Verzweigung anhand einer Bedingung wählen) und Iteration (while/for - wiederholen, solange eine Bedingung gilt). Ein GOTO ist nie nötig, und jedes Programm lässt sich als verschachtelte Kombination dieser drei lesen.

Eine Funktion bündelt ein Stück Verhalten hinter einem Namen, nimmt Parameter als Eingabe und liefert einen Rückgabewert. Das bringt drei Vorteile: Wiederverwendung (einmal schreiben, oft aufrufen), Abstraktion (der Aufrufer muss die Interna nicht kennen) und Testbarkeit (eine Funktion mit klarer Ein-/Ausgabe lässt sich isoliert prüfen). Der Vertrag lautet: gleiche Eingabe, gleiche Ausgabe.

Modularisierung führt das weiter und zerlegt ein Programm in unabhängige Bausteine mit je einer klaren Aufgabe (). Das senkt die kognitive Last, ermöglicht arbeitsteilige Entwicklung und lokalisiert Änderungen - eine Korrektur in einem Modul bricht selten ein anderes. Eine typische Zerlegung trennt etwa `einlesen()`, `berechnen()` und `ausgeben()` als eigene Funktionen unter einem schlanken Hauptprogramm.

Modularisierung - Aufrufgraph

Abb. 1Ein kleines Hauptprogramm ruft spezialisierte Funktionen auf; jede Funktion hat genau eine Aufgabe.

Variablen haben eine Sichtbarkeit (Scope): Eine lokale Variable lebt nur innerhalb ihrer Funktion und verschwindet beim Rücksprung; eine globale Variable ist überall sichtbar, koppelt Module aber unsichtbar aneinander und ist eine häufige Fehlerquelle. Daten besser über Parameter übergeben, als auf Globale zuzugreifen.

Ein Seiteneffekt ist jede Wirkung über den Rückgabewert hinaus (eine globale Variable ändern, Datei- oder Bildschirm-I/O). Reine Funktionen - ohne Seiteneffekte, Ausgabe hängt nur von der Eingabe ab - sind deutlich leichter zu testen, zu parallelisieren und zu verstehen. Vorhandene Seiteneffekte einer Funktion sollten dokumentiert sein.

Codeausschnitt Python: ```python def bmi(masse_kg, größe_m): return masse_kg / (größe_m ** 2) for person in personen: print(person["name"], bmi(person["masse"], person["größe"])) ```

Musterbeispiel

Pseudocode -> Python

Übersetze den Pseudocode in Python: "Solange n > 1 wiederhole: wenn n gerade, n := n/2; sonst n := 3n+1. Zähle Schritte."

Funktionssignatur
`def collatz_schritte(n: int) -> int:`
Schleife & Verzweigung
```python schritte = 0 while n > 1: n = n // 2 if n % 2 == 0 else 3 * n + 1 schritte += 1 return schritte ```
Testfall
`collatz_schritte(6)` ergibt 8 (6,3,10,5,16,8,4,2,1).

Ergebnis: Die Funktion liefert die Länge der Collatz-Folge ab Startwert $n$ . Sie terminiert empirisch für alle bisher getesteten Werte - mathematisch unbewiesen!

Schritt-für-Schritt Erklärung3 Schritte

1
Jedes Programm lässt sich aus Sequenz, Selektion und Iteration aufbauen - das ist das Theorem von Böhm/Jacopini.
2
Funktionen sind die wichtigste Abstraktionsstufe: gleiche Eingabe ergibt gleiche Ausgabe, ohne Seiteneffekte ist Testen einfach.
3
Modularisiere frühzeitig, damit jede Funktion einen einzigen klaren Zweck erfüllt.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre am Beispiel einer selbst gewählten Aufgabe die Bedeutung der drei elementaren Kontrollstrukturen Sequenz, Selektion und Iteration. Schreibe die Lösung in Pseudocode oder einer Programmiersprache deiner Wahl.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

return innerhalb einer Schleife vergessen oder zu früh gesetzt.
Globale Variable wird in einer Funktion überschrieben, statt Parameter zu verwenden.
Pseudocode vermischt sprachspezifische Details (z.B. Semikolons aus C, Einrückungen aus Python).

Aktive Wiederholung

Schreibe eine Python-Funktion `vokale_zählen(text)`, die die Anzahl der Vokale (a, e, i, o, u; gross/klein) zurückliefert. Demonstriere den Aufruf mit "Informatik".

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Böhm/Jacopini: Flow diagrams, Turing machines and languages with only two formation rules (CACM) · Python Software Foundation - Tutorial (PSF)

Rekursion und Iteration#

StandardINF-Alg-2.1

Rekursion löst ein Problem, indem es auf eine kleinere Instanz desselben Problems zurückgeführt wird: Eine rekursive Funktion ruft sich selbst mit „kleineren" Argumenten auf. Das ist oft die natürlichste Beschreibung selbstähnlicher Strukturen - Bäume, Listen, Divide-and-Conquer - und entspricht mathematisch einer Rekurrenz wie

n! = n\cdot(n-1)!

.

Jede Rekursion braucht zwei Teile: einen Basisfall, der ohne weiteren Selbstaufruf terminiert (

0! = 1

), und einen Rekursionsfall, der das Problem verkleinert und sich selbst aufruft (

n! = n\cdot(n-1)!

). Fehlt der Basisfall - oder verkleinert der Rekursionsfall das Argument nicht -, läuft die Funktion endlos, bis der Speicher voll ist.

Der Mechanismus dahinter ist der Aufruf-Stack (Call-Stack): Bei jedem Aufruf legt das Laufzeitsystem einen Stack-Frame mit Parametern, lokalen Variablen und Rückkehradresse ab; ist der Basisfall erreicht, werden die Frames in umgekehrter Reihenfolge abgebaut. Die maximale Rekursionstiefe bestimmt damit den Speicherbedarf - zu tiefe Rekursion (etwa

n=10000

) löst in Python einen `RecursionError` bzw. einen Stack Overflow aus.

Wie teuer Rekursion werden kann, zeigt der Rekursionsbaum. Beim naiven Fibonacci

F(n)=F(n-1)+F(n-2)

verzweigt jeder Aufruf in zwei, der Baum hat

\approx \varphi^{n}

Knoten, und Teilprobleme werden mehrfach berechnet ( zeigt, wie

fib(2)

doppelt auftaucht). Daher ist die naive Laufzeit exponentiell, nicht linear.

Rekursionsbaum von fib(4)

Abb. 2Jeder Aufruf verzweigt in zwei; fib(2) wird zweimal berechnet (hervorgehoben) - die Redundanz motiviert Memoization.

Das Heilmittel ist Memoization: einmal berechnete Werte in einer Tabelle merken, sodass jeder Teilwert nur einmal entsteht - das senkt Fibonacci von

O(\varphi^{n})

auf

O(n)

. Allgemein sind iterative Lösungen meist speicherärmer (

O(1)

statt

O(n)

Stack), rekursive oft lesbarer. Endrekursion (Tail Recursion), bei der der Selbstaufruf die letzte Aktion ist, können viele Compiler in eine Schleife umwandeln - Python tut das allerdings nicht.

Klassische rekursive Verfahren sind Fakultät, Fibonacci, Türme von Hanoi, Quicksort, Mergesort und Baumtraversierungen. Typische Fehler: den Basisfall vergessen (Endlosrekursion), das `return` in der rekursiven Funktion weglassen, oder naives Fibonacci für effizient halten. In der Prüfung immer Basis- und Rekursionsfall explizit benennen und Tiefe bzw. Aufrufzahl an einem kleinen Beispiel begründen.

n! = \begin{cases} 1, & n = 0 \\ n \cdot (n-1)!, & n > 0 \end{cases}

Rekursive Definition der Fakultät

F(n) = F(n-1) + F(n-2),\ F(0) = 0,\ F(1) = 1

Fibonacci-Rekurrenz

Musterbeispiel

Fibonacci - rekursiv vs. memoization

Implementiere `fib(n)` rekursiv und mit Memoization in Python.

Naive Rekursion
```python def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) ``` Laufzeit $T(n) = T(n-1)+T(n-2)+1 \in O(\varphi^{n})$ mit $\varphi=\tfrac{1+\sqrt 5}{2}$ .
Memoization
```python from functools import lru_cache @lru_cache def fib(n): return n if n < 2 else fib(n-1)+fib(n-2) ``` Laufzeit $O(n)$ , Speicher $O(n)$ .
Iterativ
```python def fib(n): a, b = 0, 1 for _ in range(n): a, b = b, a+b return a ``` Laufzeit $O(n)$ , Speicher $O(1)$ .

Ergebnis: Rekursion ist elegant, aber ohne Caching zu langsam; Memoization oder Iteration sind die richtigen Lösungen für grosse $n$ .

Schritt-für-Schritt Erklärung3 Schritte

1
Rekursion zerlegt ein Problem in eine kleinere Version desselben Problems plus einen Basisfall.
2
Der Call-Stack ist die Daten-struktur, die Rekursion überhaupt erst möglich macht.
3
Memoization speichert berechnete Werte und verwandelt exponentielle Rekursion in lineare Laufzeit.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Beschreibe das Prinzip der Rekursion und veranschauliche es am Beispiel der Fakultätsfunktion. Implementiere die Funktion in einer gewählten Programmiersprache und erläutere ihre Laufzeit sowie Speicherbedarf.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Basisfall vergessen -> Endlosrekursion.
Rekursive Funktion gibt nichts zurück (`return` fehlt).
Naives Fibonacci wird als effizient bezeichnet.

Aktive Wiederholung

Schreibe eine rekursive Python-Funktion `fakultät(n)`. Erläutere, warum sie bei $n=10000$ in Python einen `RecursionError` auslösen kann.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (CLRS) Kap. 2-4 (MIT Press)

Sortierverfahren - Bubble, Insertion, Merge, Quicksort#

StandardINF-Alg-3.1

Logarithmisches Wachstum O(log n) bei wachsendem n

Abb. 5Eine Verdopplung von n erhöht die Schrittzahl nur um eine Konstante - typisch für die binäre Suche. Markiert: n = 64 mit etwa 6 Schritten.

Sortieren ist das Standardproblem der Informatik - an ihm lassen sich alle Kernkonzepte zeigen: Verfahrensidee, Laufzeit, Speicher und Stabilität. Ein zentrales Ergebnis vorweg: Jedes vergleichsbasierte Verfahren braucht mindestens

\Omega(n\log n)

Vergleiche. Das folgt aus einem Entscheidungsbaum-Argument - es gibt

n!

mögliche Anordnungen, jeder Vergleich halbiert die Restmenge, und

\log_{2}(n!) \approx n\log n

.

Bubble Sort vergleicht benachbarte Elemente und tauscht sie, bis nichts mehr zu tauschen ist - sehr einfach, aber im Mittel und Worst Case

O(n^{2})

. Insertion Sort fügt jedes neue Element an die richtige Stelle des bereits sortierten Präfix ein; ebenfalls

O(n^{2})

, aber nur

O(n)

im Best Case (fast sortierte Daten) und mit geringem Overhead - daher ideal für kleine

n

.

Mergesort ist Divide-and-Conquer: Das Array wird halbiert, beide Hälften rekursiv sortiert und dann in Linearzeit verschmolzen (). Die Rekurrenz

T(n)=2T(n/2)+n

löst sich zu

O(n\log n)

, und zwar in allen Fällen. Der Preis ist

O(n)

Zusatzspeicher fürs Mischen; dafür ist Mergesort stabil.

Mergesort - Divide-and-Conquer Baum

Abb. 3Divide: das Array wird rekursiv halbiert bis zu Einzelelementen. Conquer (bottom-up): [27,38]+[3,43] ergibt [3,27,38,43], [9,82]+[10] ergibt [9,10,82], am Ende [3,9,10,27,38,43,82].

Quicksort wählt ein Pivot und partitioniert das Array in „

<

Pivot" und „

\geq

Pivot" (), dann rekursiv weiter. Im Mittel

O(n\log n)

und in-place (wenig Speicher), im Worst Case aber

O(n^{2})

- etwa bei bereits sortiertem Array mit dem ersten Element als Pivot; randomisierte Pivots oder Median-of-three entschärfen das. Quicksort ist nicht stabil.

Quicksort - Partition mit Pivot

Abb. 4Das Pivot 5 trennt das Array in „kleiner Pivot" (links) und „größer/gleich Pivot" (rechts) und steht danach an seiner endgültigen Position (Index a4). Mittel O(n log n), Worst Case O(n^2).

Stabilität heißt: Elemente mit gleichem Schlüssel behalten ihre relative Reihenfolge. Das ist beim mehrstufigen Sortieren wichtig (erst nach Vorname, dann stabil nach Nachname - sonst zerfällt die erste Ordnung). Stabil sind Mergesort und Insertion Sort, nicht stabil Quicksort und Heapsort.

In der Praxis nutzen Standardbibliotheken Timsort (Python `sorted`, Java `Arrays.sort` für Objekte), eine Hybride aus Mergesort und Insertion Sort, die natürliche bereits sortierte Läufe ausnutzt. Häufige Fehler: den Quicksort-Worst-Case mit

O(n\log n)

angeben (richtig ist

O(n^{2})

), Mergesort als in-place bezeichnen (es braucht

O(n)

), oder Quicksort für stabil halten.

T(n) = 2T\!\left(\tfrac{n}{2}\right) + n \in O(n\log n)

Mergesort-Rekurrenz und Lösung

Musterbeispiel

Mergesort-Trace auf [38, 27, 43, 3, 9, 82, 10]

Sortiere [38, 27, 43, 3, 9, 82, 10] mit Mergesort und protokolliere die Merge-Schritte.

Teilen 1
Links [38,27,43,3] | Rechts [9,82,10].
Teilen 2 (links)
[38,27] und [43,3] werden zu je [27,38] und [3,43] gemergt.
Merge linker Halbteile
merge([27,38],[3,43]) = [3,27,38,43].
Teilen 2 (rechts)
[9,82] und [10]; merge ergibt [9,10,82].
Finaler Merge
merge([3,27,38,43],[9,10,82]) = [3,9,10,27,38,43,82].

Ergebnis: Sortiertes Array [3, 9, 10, 27, 38, 43, 82]. Laufzeit $T(n) = 2T(n/2)+n \in O(n \log n)$ .

Schritt-für-Schritt Erklärung3 Schritte

1
Sortieren ist das Standardbeispiel, an dem alle Konzepte zusammenkommen: Verfahren, Komplexität, Speicher und Stabilität.
Mergesort - Divide-and-Conquer Baum
Abb.Divide: das Array wird rekursiv halbiert bis zu Einzelelementen. Conquer (bottom-up): [27,38]+[3,43] ergibt [3,27,38,43], [9,82]+[10] ergibt [9,10,82], am Ende [3,9,10,27,38,43,82].
2
Mergesort teilt das Array bis auf Einzelelemente und fädelt sie sortiert zusammen - daher die garantiert logarithmische Tiefe.
3
Quicksort ist schnell, weil die Partition in-place arbeitet, aber er kann bei schlechter Pivotwahl quadratisch werden.
Quicksort - Partition mit Pivot
Abb.Das Pivot 5 trennt das Array in „kleiner Pivot" (links) und „größer/gleich Pivot" (rechts) und steht danach an seiner endgültigen Position (Index a4). Mittel O(n log n), Worst Case O(n^2).

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Vergleiche Insertion Sort und Mergesort hinsichtlich Idee, Laufzeit und Speicher. Wann würdest du Insertion Sort, wann Mergesort einsetzen?

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Quicksort-Worst-Case wird mit $O(n \log n)$ angegeben (richtig ist $O(n^{2})$ ).
Mergesort als in-place beschrieben (braucht aber $O(n)$ Speicher).
Stabilität wird ignoriert und Quicksort wird fälschlich als stabil bezeichnet.

Aktive Wiederholung

Sortiere [5, 2, 9, 1, 5, 6] mit Insertion Sort und protokolliere die ersten drei Iterationen. Wie oft wird vergleichen und wie oft getauscht?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching (Addison-Wesley) · OpenDSA - Sorting Algorithms (Virginia Tech)

Suchverfahren - linear und binaer#

BasisINF-Alg-3.2

Suchen heißt: in einer Datenmenge ein Element mit gegebenem Schlüssel finden. Welche Methode richtig ist, hängt entscheidend davon ab, ob die Daten geordnet sind - das ist der rote Faden dieses Abschnitts ( vergleicht das Wachstum beider Verfahren).

Lineare vs. binäre Suche - Vergleichsschritte

Abb. 6Die lineare Suche wächst mit

n

, die binäre nur mit

\log_{2} n

: bei

n=64

genügen 6 statt 64 Vergleiche.

Die lineare Suche prüft der Reihe nach jedes Element; sie stellt keine Voraussetzung an die Reihenfolge und braucht im Worst Case

n

Vergleiche, also

O(n)

. Für unsortierte oder als Stream eintreffende Daten bleibt sie der Standard.

Die binäre Suche setzt ein sortiertes Array voraus und halbiert in jedem Schritt das Suchintervall: Man vergleicht mit dem mittleren Element und verwirft die Hälfte, in der der Wert nicht liegen kann. So sinkt das Restproblem

n \to n/2 \to n/4 \to \dots \to 1

; die Rekurrenz

T(n)=T(n/2)+1

ergibt

O(\log n)

. Konkret genügen bei

n=1\,000\,000

nur

\lceil \log_{2}(n+1) \rceil = 20

Vergleiche statt bis zu einer Million.

Die Tücke liegt im Detail:

mid=(low+high)/2

(besser

low+(high-low)/2

gegen Überlauf), und die Grenzen müssen je nach Treffer korrekt verschoben werden (

low=mid+1

bzw.

high=mid-1

), sonst entsteht eine Endlosschleife oder ein Off-by-one. Auf einem unsortierten Array liefert die binäre Suche schlicht falsche Ergebnisse.

Für gleichverteilte, sortierte Daten schätzt die Interpolationssuche die Position (wie beim Aufschlagen eines Telefonbuchs) und erreicht im Mittel

O(\log \log n)

. Hashtabellen suchen sogar in erwartetem

O(1)

- asymptotisch besser als binäre Suche -, kosten aber zusätzlichen Speicher und brauchen eine gute Hashfunktion.

Faustregel: lineare Suche für kleine, unsortierte oder streamende Daten; binäre Suche für große, sortierte, statische Bestände; Hashtabelle für sehr häufige Zugriffe bei vorhandenem Speicher. Häufige Fehler: binäre Suche auf unsortierte Daten anwenden, oder „logarithmisch ist langsamer als linear" - tatsächlich ist

O(\log n)

dramatisch schneller als

O(n)

.

T_{\text{bin}}(n) = T(n/2) + 1 \in O(\log n)

Rekurrenz der binären Suche

Musterbeispiel

Binäre Suche im sortierten Array

Finde mit binärer Suche den Wert 23 im Array [3, 7, 12, 18, 23, 31, 47, 55].

Initial
low = 0, high = 7. Pivot mid = (0+7)/2 = 3 -> a[3] = 18 < 23 -> rechts weitersuchen.
Iteration 2
low = 4, high = 7. mid = 5 -> a[5] = 31 > 23 -> links weitersuchen.
Iteration 3
low = 4, high = 4. mid = 4 -> a[4] = 23 == Suchwert. Index 4 zurückgeben.

Ergebnis: Index 4 nach 3 Vergleichen; allgemein $O(\log n)$ Schritte für $n$ Elemente.

Schritt-für-Schritt Erklärung3 Schritte

1
Die binaere Suche ist das Schulbuchbeispiel für logarithmische Laufzeit.
2
Bei jeder Halbierung sinkt das Restproblem auf $n/2$ , $n/4$ , ... bis $1$ .
3
Auf unsortierten Daten musst du linear suchen oder zuerst sortieren - das kostet $O(n\log n)$ .

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erkläre die binaere Suche im Vergleich zur linearen Suche. Implementiere sie iterativ und nenne Voraussetzungen und Laufzeit.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Binäre Suche wird auf unsortiertes Array angewendet.
Off-by-one Fehler bei `mid = (low+high)/2` - bei `high-low+1` an Bedingung denken.
Verwechslung von linearer und binärer Komplexität ("logarithmisch ist langsamer als linear").

Aktive Wiederholung

Schreibe eine iterative binaere Suche in JavaScript. Wie viele Iterationen sind im Worst Case bei einer Million Elementen nötig?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: Sedgewick & Wayne: Algorithms, 4. Auflage (Addison-Wesley)

Big-O, Master-Theorem und Grenzen#

VertiefungINF-Alg-4.1INF-Alg-4.2

Mergesort - Divide-and-Conquer Baum

Abb. 8Divide: das Array wird rekursiv halbiert bis zu Einzelelementen. Conquer (bottom-up): [27,38]+[3,43] ergibt [3,27,38,43], [9,82]+[10] ergibt [9,10,82], am Ende [3,9,10,27,38,43,82].

Will man Algorithmen vergleichen, ohne Hardware und Programmiersprache zu vermischen, zählt man nicht Sekunden, sondern wie die Schrittzahl mit der Eingabegröße

n

wächst. Die Big-O-Notation macht das präzise und ist damit die gemeinsame Sprache der Laufzeitanalyse ( zeigt die wichtigsten Klassen im Vergleich).

Wachstum der Komplexitätsklassen

Abb. 7Logarithmisch, linear, quadratisch und exponentiell im Vergleich - das exponentielle

2^{n}

enteilt allen anderen.

Formal ist

f \in O(g)

, wenn es Konstanten

c>0

und

n_{0}

gibt mit

f(n) \leq c\,g(n)

für alle

n \geq n_{0}

. Big-O ist also eine obere asymptotische Schranke: Konstante Faktoren und Terme niedrigerer Ordnung fallen weg,

O(3n+5)=O(n)

. Daneben stehen

\Omega(g)

(untere Schranke),

\Theta(g)

(gleiches Wachstum, obere und untere zugleich) und

o(g)

(strikt langsamer wachsend).

Die geläufige Hierarchie lautet

O(1) \subset O(\log n) \subset O(n) \subset O(n\log n) \subset O(n^{2}) \subset O(2^{n}) \subset O(n!)

. Anschaulich (): konstante und logarithmische Verfahren bleiben selbst bei Milliarden Elementen schnell, quadratische schaffen höchstens Hunderttausende, exponentielle nur Dutzende - das

2^{n}

enteilt allen anderen.

Für Divide-and-Conquer-Rekurrenzen

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}

: Dominiert

n^{\log_{b}a}

(Fall 1), ist

T \in \Theta(n^{\log_{b}a})

; sind beide gleich groß (Fall 2),

\Theta(n^{\log_{b}a}\log n)

; dominiert

f

(Fall 3),

\Theta(f(n))

. Für Mergesort (

a=2,\,b=2,\,f=n

) ist

n^{\log_{2}2}=n=f

, also Fall 2 und

\Theta(n\log n)

(siehe Beispiel).

Komplexität fragt „wie teuer?", die Berechenbarkeit fragt „überhaupt lösbar?". Nicht jedes Problem ist algorithmisch entscheidbar - das Halteproblem ist das berühmte Gegenbeispiel. Big-O sagt nichts über die Lösbarkeit, nur über den Aufwand lösbarer Probleme.

Häufige Fehler: Konstanten in Big-O behalten; das Master-Theorem auf Rekurrenzen ohne Divide-and-Conquer-Form anwenden; oder exponentielle Verfahren für „in der Praxis lösbar" halten. Und stets bedenken: Big-O gilt asymptotisch - für kleine

n

kann ein

O(n^{2})

-Verfahren ein

O(n\log n)

-Verfahren wegen kleinerer Konstanten schlagen.

f(n) \in O(g(n)) \iff \exists\, c>0,\, n_{0}\geq 0 : \forall\, n \geq n_{0} : f(n) \leq c\cdot g(n)

Big-O Notation - obere asymptotische Schranke

T(n) = a\cdot T\!\left(\tfrac{n}{b}\right) + f(n),\quad a\geq 1,\, b>1

Master-Theorem - Rekurrenzform für Divide-and-Conquer

Logarithmisches Wachstum O(log n) bei wachsendem n

Abb. 9Eine Verdopplung von n erhöht die Schrittzahl nur um eine Konstante - typisch für die binäre Suche. Markiert: n = 64 mit etwa 6 Schritten.

Musterbeispiel

Master-Theorem auf Mergesort anwenden

Bestimme die Lösung der Rekurrenz $T(n) = 2T(n/2) + n$ mit dem Master-Theorem.

Parameter ablesen
$a=2$ , $b=2$ , $f(n)=n$ .
Vergleichsgröße
$\log_{b} a = \log_{2} 2 = 1$ ; also $n^{\log_{b}a} = n$ .
Fall prüfen
$f(n)=n=\Theta(n^{1})$ -> Fall 2 des Master-Theorems.
Lösung anwenden
$T(n) = \Theta(n^{\log_{b} a} \cdot \log n) = \Theta(n \log n)$ .

Ergebnis: Mergesort hat asymptotische Laufzeit $T(n) \in \Theta(n \log n)$ im Worst, Average und Best Case.

Schritt-für-Schritt Erklärung3 Schritte

1
Big-O sagt dir, wie sich eine Laufzeit verhält, wenn du die Eingabegröße verdoppelst.
Logarithmisches Wachstum O(log n) bei wachsendem n
Abb.Eine Verdopplung von n erhöht die Schrittzahl nur um eine Konstante - typisch für die binäre Suche. Markiert: n = 64 mit etwa 6 Schritten.
2
Das Master-Theorem ist die schnellste Methode, Divide-and-Conquer-Rekurrenzen zu lösen.
3
Achte darauf, dass Big-O nur asymptotisch gilt - für kleine Eingaben kann ein quadratischer Algorithmus schneller sein als ein log-linearer.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Erläutere die Big-O-Notation und vergleiche die Laufzeitklassen

O(1)

,

O(\log n)

,

O(n)

,

O(n \log n)

und

O(n^{2})

anhand konkreter Algorithmen. Diskutiere am Beispiel von Mergesort die Anwendung des Master-Theorems.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Konstanten in Big-O behalten ( $O(3n) = O(n)$ ).
Master-Theorem auf nicht-Divide-and-Conquer-Rekurrenzen anwenden.
Exponentielles Wachstum als "praktisch lösbar" einstufen.

Aktive Wiederholung

Bestimme mit dem Master-Theorem die Lösung der Rekurrenzen $T(n)=3T(n/2)+n^{2}$ und $T(n)=4T(n/2)+n$ . Wie lautet die Komplexität jeweils?

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: CLRS: Introduction to Algorithms, Kapitel 3 und 4 (MIT Press)

Greedy- und Dynamic-Programming-Verfahren#

VertiefungINF-Alg-5.1

Manche Optimierungsprobleme lassen sich nicht durch blindes Ausprobieren lösen, weil es zu viele Möglichkeiten gibt. Zwei mächtige Entwurfsstrategien helfen: Greedy und Dynamic Programming. Sie unterscheiden sich darin, ob eine lokal beste Entscheidung schon global optimal ist.

Greedy-Algorithmen treffen in jedem Schritt die lokal beste Wahl und revidieren sie nie. Das ist einfach und schnell, aber nur garantiert optimal, wenn das Problem die passende Struktur (ein Matroid) hat. Erfolgreiche Beispiele sind die Aktivitätenauswahl, Huffman-Codes, minimale Spannbäume (Prim, Kruskal) und Coin Change in kanonischen Münzsystemen.

Beim Coin Change sieht man die Grenze von Greedy: Münzen

\{1,\,3,\,4\}

, Ziel

6

- Greedy nimmt

4+1+1

(3 Münzen), optimal sind

3+3

(2 Münzen). Lokal optimal ist eben nicht immer global optimal; genau so ein Gegenbeispiel sollte man in der Prüfung parat haben.

Dynamic Programming (DP) löst solche Fälle, indem es das Problem in überlappende Teilprobleme zerlegt und jedes nur einmal berechnet (die Ergebnisse werden gespeichert). Voraussetzung sind zwei Eigenschaften: optimale Substruktur (die Gesamtlösung setzt sich aus optimalen Teillösungen zusammen) und überlappende Teilprobleme (dieselben Teilprobleme treten mehrfach auf).

Es gibt zwei Bauweisen: Top-down (Memoization) - die rekursive Lösung mit Cache - und Bottom-up (Tabelle) - die Teilprobleme in passender Reihenfolge iterativ füllen. Beim 0/1-Rucksack mit der Rekurrenz

K(i,w)=\max\bigl(K(i-1,w),\,K(i-1,w-w_{i})+v_{i}\bigr)

füllt sich die DP-Tabelle zeilenweise (); das Ergebnis

K(3, 50)=220

steht unten rechts.

Knapsack-DP-Tabelle (W=50)

Abb. 10Bottom-up gefüllte DP-Tabelle für Werte [60,100,120] und Gewichte [10,20,30]; das Optimum 220 steht unten rechts.

Die Laufzeit von DP ergibt sich aus der Tabellengröße mal Aufwand pro Zelle:

O(n\cdot W)

für 0/1-Knapsack - pseudopolynomiell, weil

W

als Zahlwert und nicht als Eingabelänge zählt. Klassische DP-Probleme sind Fibonacci, das Rucksackproblem, kürzeste Pfade (Bellman-Ford) und die Edit Distance. Häufige Fehler: Greedy auf nicht-kanonische Systeme anwenden, die Tabelle in falscher Reihenfolge füllen, oder Top-down ohne Memoization als DP ausgeben (dann wieder exponentiell).

K(i, w) = \max\bigl(K(i-1, w),\, K(i-1, w - w_{i}) + v_{i}\bigr)

DP-Rekurrenz für 0/1-Knapsack

Musterbeispiel

0/1-Knapsack via DP

Werte $[60, 100, 120]$ , Gewichte $[10, 20, 30]$ , Kapazität $W=50$ .

DP-Tabelle initialisieren
Tabelle $K$ der Größe $4 \times 51$ ; erste Zeile/Spalte = 0.
Befüllen
Für jedes Item $i$ und jede Kapazität $w$ : $K(i,w) = \max(K(i-1,w), K(i-1, w-w_{i}) + v_{i})$ , falls $w \geq w_{i}$ .
Endergebnis ablesen
$K(3, 50) = 220$ (Items 2 und 3).

Ergebnis: Maximaler Wert 220 EUR. Mit Backtracking auf der Tabelle lässt sich die optimale Auswahl rekonstruieren. Laufzeit $O(n \cdot W)$ - pseudo-polynomiell.

Schritt-für-Schritt Erklärung3 Schritte

1
Greedy ist verführerisch einfach - aber nur bei matroidischen Problemen garantiert optimal.
2
DP ist die Klassiker-Antwort, wenn ein Problem optimale Teilstruktur und Überlappung hat.
3
Memoization spart Zeit, DP-Tabelle spart Stack - wähle nach Problem.

SRDP-Aufgaben

SelbsttestAus der Fragenbank7 Punkte

Aufgabenstellung

Vergleiche Greedy-Algorithmen und Dynamic Programming. Erkläre an einem konkreten Beispiel, warum Greedy nicht immer das Optimum liefert.

Deine Antwortwird nicht automatisch bewertet

Typische Fehler

Greedy wird auf nicht-kanonisches Münzsystem angewendet (z.B. Münzen 1, 3, 4 - Greedy liefert 6 = 4+1+1, optimal wäre 3+3).
DP-Tabelle wird in falscher Reihenfolge aufgebaut.
Top-down ohne Memoization wird als DP verkauft (-> exponentiell).

Aktive Wiederholung

Löse das 0/1-Knapsack-Problem mit Werten $[60, 100, 120]$ , Gewichten $[10, 20, 30]$ und Kapazität $50$ mittels DP-Tabelle.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Quellen: CLRS Kapitel 15 (DP) und 16 (Greedy) (MIT Press)