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

Kontrollstrukturen, Funktionen und Modularisierung#

~4 Min LesezeitBasisINF-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.

Abb. 1 ↓

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"])) ```

Vokabeln

→ Kartei

KontrollstrukturSprachmittel für Verzweigung und Wiederholung.
ParameterBezeichner in der Funktionsdefinition; das Argument ist der übergebene Wert.
RückgabewertErgebnis, das die Funktion an die aufrufende Stelle liefert.
GültigkeitsbereichBereich, in dem ein Bezeichner sichtbar ist; lokal oder global.
ModularisierungZerlegung eines Programms in getrennt testbare Bausteine.
SeiteneffektÄnderung eines Zustands außerhalb der Funktion; erschwert das Testen.

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

Das `return` steht innerhalb der Schleife und beendet sie nach dem ersten Durchlauf.
Eine globale Variable wird in der Funktion überschrieben, statt sie als Parameter zu übergeben.
Pseudocode vermischt sprachspezifische Details wie Semikolons und Einrückungsregeln.
Die Randfälle bleiben ungetestet; leere Liste oder ein einzelnes Element decken die meisten Fehler auf.
Die Funktion gibt nichts zurück und schreibt stattdessen direkt auf die Ausgabe - damit ist sie nicht weiterverwendbar.

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema

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#

~4 Min LesezeitStandardINF-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.

Abb. 2 ↓

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.

Vokabeln

→ Kartei

BasisfallFall ohne weiteren rekursiven Aufruf; er beendet die Rekursion.
RekursionstiefeGrößte Zahl gleichzeitig offener Aufrufe.
AufrufstapelSpeicherbereich für die offenen Funktionsaufrufe.
MemoizationZwischenspeichern bereits berechneter Teilergebnisse.
EndrekursionRekursiver Aufruf als letzte Anweisung; in manchen Sprachen in eine Schleife übersetzbar.
TerminierungGarantie, dass das Verfahren nach endlich vielen Schritten endet.

Rekursive Definition der Fakultät

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

Die obere Zeile ist der Basisfall, die untere der Rekursionsfall. Ohne den Basisfall terminiert die Rekursion nicht; die Festlegung $0!=1$ hält die Formeln in den Randfällen gültig.

Fibonacci-Rekurrenz

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

Die naive Umsetzung dieser Rekurrenz berechnet dieselben Teilwerte immer wieder und läuft exponentiell. Mit Zwischenspeicherung oder iterativ sinkt der Aufwand auf $O(n)$ - das ist das Standardbeispiel für den Nutzen der Memoization.

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 große $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

Der Basisfall fehlt; die Rekursion terminiert nicht und der Aufrufstapel läuft über.
Das Ergebnis des rekursiven Aufrufs wird nicht zurückgegeben.
Naives Fibonacci wird als effizient bezeichnet; es rechnet dieselben Teilprobleme vielfach.
Rekursionstiefe und Anzahl der Aufrufe werden verwechselt.
Endrekursion wird als automatisch optimiert angenommen; nicht jede Sprache tut das.

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema

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#

~4 Min LesezeitStandardINF-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].

Abb. 3 ↓

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

Abb. 4 ↓

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.

Vokabeln

→ Kartei

StabilitätGleiche Schlüssel behalten ihre ursprüngliche Reihenfolge.
in-placeVerfahren mit nur konstantem zusätzlichem Speicherbedarf.
PivotTrennelement bei Quicksort; seine Wahl entscheidet über den Worst Case.
Divide and ConquerZerlegen, rekursiv lösen, zusammenfügen; Prinzip von Mergesort und Quicksort.
VergleichssortierungVerfahren, das nur Elementvergleiche nutzt; untere Schranke $\Omega(n\log n)$.
Worst CaseUngünstigste Eingabe; sie bestimmt die Garantie eines Verfahrens.

Mergesort-Rekurrenz und Lösung

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

Der Faktor 2 steht für die beiden Hälften, $n$ für das Verschmelzen. Die Lösung folgt aus dem Master-Theorem (zweiter Fall) und gilt für Best, Average und Worst Case gleichermaßen - das unterscheidet Mergesort von Quicksort.

Wiedergabe lädt Inhalte von YouTube (Google).Auf YouTube öffnen ↗

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

Der Worst Case von Quicksort wird mit $O(n\log n)$ angegeben; er ist $O(n^{2})$ .
Mergesort wird als in-place beschrieben; er braucht zusätzlich $O(n)$ Speicher.
Quicksort wird als stabil bezeichnet; in der üblichen Implementierung ist er es nicht.
Best und Worst Case werden vertauscht: Insertion Sort ist bei bereits sortierten Daten $O(n)$ , nicht $O(n^{2})$ .
Aus einer besseren Big-O-Klasse wird auf schnellere Ausführung bei kleinen $n$ geschlossen; dort schlagen die Konstanten durch.

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?

Passende Aufgaben üben50 Fragen zum Thema

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#

~4 Min LesezeitBasisINF-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.

Abb. 6 ↓

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)

.

Vokabeln

→ Kartei

lineare SucheSequentielles Durchmustern; $O(n)$, ohne Sortierung möglich.
binäre SucheHalbierungssuche in sortierten Daten; $O(\log n)$.
SuchraumNoch nicht ausgeschlossener Bereich der Datenmenge.
InvarianteAussage, die vor und nach jedem Schleifendurchlauf gilt; Grundlage des Korrektheitsbeweises.
Off-by-oneFehler um eins bei Indexgrenzen; häufigste Fehlerquelle der binären Suche.
amortisierte BetrachtungKostenverteilung über viele Operationen statt Einzelbetrachtung.

Rekurrenz der binären Suche

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

Jeder Schritt halbiert den Suchraum und kostet einen Vergleich. Daraus folgt die logarithmische Laufzeit: In einer Million Elementen genügen rund 20 Schritte.

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

Die binäre Suche wird auf ein unsortiertes Feld angewandt.
Off-by-one-Fehler bei der Berechnung von $mid$ oder bei der Anpassung der Grenzen führen zu Endlosschleifen.
Logarithmisches Wachstum wird als langsamer als lineares beschrieben.
Der Aufwand des vorherigen Sortierens bleibt in der Gesamtbetrachtung unberücksichtigt.
Bei mehrfach vorkommendem Suchwert wird angenommen, die binäre Suche liefere den ersten Treffer.

Aktive Wiederholung

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

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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

Big-O, Master-Theorem und Grenzen#

~4 Min LesezeitVertiefungINF-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.

Abb. 7 ↓

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.

Vokabeln

→ Kartei

Big-OObere Schranke des Wachstums einer Funktion.
OmegaUntere Schranke des Wachstums.
ThetaScharfe Schranke; obere und untere Schranke fallen zusammen.
Master-TheoremLösungsschema für Rekurrenzen der Form $T(n)=a\,T(n/b)+f(n)$.
asymptotischFür sehr große Eingaben betrachtet; Konstanten spielen dort keine Rolle.
RekurrenzgleichungGleichung, die die Laufzeit über kleinere Teilprobleme ausdrückt.

Big-O Notation - obere asymptotische Schranke

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)

$c$ ist eine positive Konstante, $n_{0}$ die Stelle, ab der die Abschätzung gilt. Die Definition macht deutlich, warum konstante Faktoren wegfallen und die Aussage erst für große $n$ gilt.

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

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

$a$ ist die Zahl der Teilprobleme, $b$ der Verkleinerungsfaktor und $f(n)$ der Aufwand für Zerlegen und Zusammenfügen. Verglichen wird $f(n)$ mit $n^{\log_{b}a}$ ; welcher der beiden dominiert, entscheidet den Fall.

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 bleiben in der Big-O-Angabe stehen; $O(3n)$ ist $O(n)$ .
Das Master-Theorem wird auf Rekurrenzen angewandt, die nicht der Divide-and-Conquer-Form entsprechen.
Exponentielles Wachstum wird als praktisch beherrschbar eingestuft.
Big-O wird als exakte Laufzeit gelesen; es ist eine obere Schranke des Wachstums.
Speicherbedarf und Laufzeit werden vermengt; beide brauchen eigene Angaben.

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?

Passende Aufgaben üben50 Fragen zum Thema

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#

~4 Min LesezeitVertiefungINF-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.

Abb. 10 ↓

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

Vokabeln

→ Kartei

Greedy-VerfahrenTrifft in jedem Schritt die lokal beste Wahl.
optimale TeilstrukturDie optimale Gesamtlösung enthält optimale Teillösungen.
überlappende TeilproblemeDieselben Teilprobleme treten mehrfach auf; sie lohnen die Zwischenspeicherung.
dynamische ProgrammierungSystematisches Lösen und Speichern aller Teilprobleme.
RucksackproblemAuswahl von Gegenständen unter Gewichtsgrenze mit maximalem Wert.
pseudopolynomiellLaufzeit polynomiell im Zahlenwert der Eingabe, nicht in ihrer Länge.

DP-Rekurrenz für 0/1-Knapsack

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

$K(i,w)$ ist der beste Wert mit den ersten $i$ Gegenständen bei Restkapazität $w$ ; $w_{i}$ und $v_{i}$ sind Gewicht und Wert des $i$ -ten. Die beiden Argumente des Maximums sind die Entscheidungen weglassen und einpacken - der zweite Fall ist nur zulässig, wenn $w_{i}\le w$ gilt.

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 ein nicht kanonisches Münzsystem angewandt: Mit 1, 3 und 4 liefert Greedy für 6 die Zerlegung $4+1+1$ , optimal wären $3+3$ .
Die DP-Tabelle wird in falscher Reihenfolge gefüllt; benötigte Teilergebnisse fehlen dann noch.
Top-down-Rekursion ohne Memoization wird als dynamische Programmierung ausgegeben.
Nur der optimale Wert wird angegeben, obwohl nach der Zusammensetzung gefragt ist.
Pseudopolynomielle Laufzeit wird als polynomiell bezeichnet.

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.

Passende Aufgaben üben50 Fragen zum Thema

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

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