Abitur Informatik: Algorithmen und Datenstrukturen
Sortierverfahren, Suchalgorithmen, Listen und Bäume — das komplette Informatik-Abitur-Wissen zu Algorithmen und Datenstrukturen.
Abitur Informatik: Algorithmen und Datenstrukturen
Informatik ist als Schulfach im Aufwind. Im Abitur werden vor allem algorithmisches Denken und Datenstrukturen geprüft.
Komplexität von Algorithmen — O-Notation
Die O-Notation beschreibt, wie der Aufwand eines Algorithmus mit der Eingabegröße wächst.
| O-Klasse | Wachstum | Beispiel |
|----------|----------|---------|
| O(1) | Konstant | Array-Zugriff |
| O(log n) | Logarithmisch | Binäre Suche |
| O(n) | Linear | Lineare Suche |
| O(n log n) | Linearithmisch | Merge Sort, Quick Sort |
| O(n²) | Quadratisch | Bubble Sort, Selection Sort |
| O(2ⁿ) | Exponentiell | Naive Fibonacci |
Sortierverfahren
**Bubblesort (O(n²)):**
Vergleicht benachbarte Elemente und tauscht sie bei Bedarf. Wiederholt bis alles sortiert.
Pseudocode: for i = 0 to n-1 → for j = 0 to n-i-2 → if arr[j] > arr[j+1]: swap(arr[j], arr[j+1])
**Selectionsort (O(n²)):**
Sucht das kleinste Element und setzt es an den Anfang. Wiederholt für den Rest.
**Mergesort (O(n log n)):**
Teile-und-Herrsche: Array halbieren, beide Hälften sortieren, zusammenführen.
**Quicksort (O(n log n) avg, O(n²) worst):**
Pivotelement wählen, Array partitionieren (kleiner/größer als Pivot), rekursiv sortieren.
Suchverfahren
**Lineare Suche (O(n)):**
Geht jedes Element durch und vergleicht.
**Binäre Suche (O(log n)):**
Nur in sortierten Arrays! Vergleicht mit dem mittleren Element und eliminiert die Hälfte.
Pseudocode: left=0, right=n-1 → while left ≤ right → mid=(left+right)/2 → if arr[mid]==target: return mid → elif arr[mid]<target: left=mid+1 → else: right=mid-1
Datenstrukturen
**Array:**
**Verkettete Liste:**
**Stack (Stapelspeicher):**
**Queue (Warteschlange):**
**Baum (insbesondere Binärbaum/BST):**
**Hash-Tabelle:**
Graphen
**Darstellung:**
**Tiefensuche (DFS):**
**Breitensuche (BFS):**
Rekursion
**Fibonacci-Zahlen:**
Pseudocode: function fib(n) → if n ≤ 1: return n → return fib(n-1) + fib(n-2)
Problem: O(2ⁿ) — extrem langsam für große n. Besser: dynamische Programmierung mit O(n).
Dynamische Programmierung
**Prinzip:** Teilprobleme lösen und Ergebnisse speichern (Memoization).
Beispiel: Rucksackproblem (Knapsack)
Objektorientierung (OOP)
Die vier Prinzipien:
1. **Kapselung:** Daten und Methoden in einer Klasse, private/ public
2. **Vererbung:** Kind-Klassen übernehmen Eigenschaften der Eltern-Klasse
3. **Polymorphie:** Gleiche Methode verhält sich je nach Typ unterschiedlich
4. **Abstraktion:** Komplexität verbergen, nur Relevantes zeigen
Fazit
Das Informatik-Abitur erfordert sowohl Theorie (Komplexität, Datenstrukturen) als auch Praxis (Programmieren). Wer die wichtigsten Algorithmen und Datenstrukturen kennt und deren Eigenschaften (Laufzeit, Speicher) sicher angeben kann, ist gut vorbereitet.