Algorithmen und Datenstrukturen
Der Bereich Algorithmen und Datenstrukturen prüft, ob du Algorithmen präzise beschreiben, ihre Korrektheit begründen und ihren Aufwand mit der O-Notation vergleichen kannst. Ebenso wichtig sind die operationellen Eigenschaften typischer Datenstrukturen: Liste, Stack, Queue, binärer Suchbaum, Graph und Hash-Tabelle. In der Abiturklausur werden diese Inhalte meist mit einer konkreten Operationsfolge oder einem Such- bzw. Sortierverfahren verbunden, das du schrittweise ausführen und analysieren musst.
Grundbegriffe und Gütekriterien
Ein Algorithmus ist eine endliche, eindeutige Vorschrift zur Lösung eines Problems. Zu den Gütekriterien gehören Ausführbarkeit, Finitheit, Determiniertheit (gleiche Eingabe liefert gleiche Ausgabe), Determinismus (gleicher Zustand und gleiche Eingabe erzwingen denselben nächsten Schritt), Eindeutigkeit und Allgemeingültigkeit. Verwechsle Determiniertheit nicht mit Determinismus: Ein Zufallsgenerator kann determiniert sein, ohne deterministisch im engeren Sinne zu sein.
Komplexität und Datenstrukturen
Die O-Notation beschreibt eine obere Schranke für das Wachstum der Laufzeit oder des Speicherbedarfs in Abhängigkeit von der Eingabegröße n; konstante Faktoren und kleinere Terme werden vernachlässigt. Typische Klassen sind O(1), O(log n), O(n), O(n log n), O(n²). Bubblesort und Insertionsort liegen im Worst Case in O(n²), Mergesort in O(n log n). Die binäre Suche benötigt ein sortiertes Feld und hat O(log n); die lineare Suche hat O(n). In einem binären Suchbaum ist die Suche O(h), wobei h die Höhe ist: balanciert gilt h ≈ log n, im entarteten Fall h = n. Für Graphen unterscheidet man Adjazenzmatrix (O(n²) Speicher) und Adjazenzliste (O(n+m) Speicher); Breiten- und Tiefensuche laufen mit Adjazenzliste in O(n+m).
Worked Example: Binäre Suche
Gegeben ist ein aufsteigend sortiertes Feld mit 15 Elementen; gesucht wird ein Wert x. Nach dem ersten Vergleich bleibt höchstens die Hälfte übrig: 15 → 7 → 3 → 1 → 0 Elemente. Also sind maximal ⌈log₂(15+1)⌉ = 4 Vergleiche nötig. Die Rechnung zeigt zugleich, warum die binäre Suche nur mit sortiertem Feld und wahlfreiem Zugriff funktioniert: Ohne Sortierung kann die Hälfte nicht sicher ausgeschlossen werden.
Typische Fallen
- O(log n) wird fälschlich auch für die Suche im unsortierten Feld angegeben.
- Die Höhe eines binären Suchbaums wird automatisch als log n angenommen; das gilt nur bei Balance.
- Average-Case und Worst-Case werden vermischt.
- Bei Sortierverfahren wird „stabil“ mit „in-place“ verwechselt.
- Bei Rekursion fehlt die Abbruchbedingung oder der Rekursionsschritt verkleinert das Problem nicht.