Prüfungsrelevante Algorithmen
In Prüfungen für Fachinformatiker kommen häufig verschiedene Standard-Algorithmen vor. Hier sind einige der Algorithmen, die oft gefordert werden:
1. Sortieralgorithmen:
- Bubble Sort: Ein einfacher, aber ineffizienter Sortieralgorithmus.
- Insertion Sort: Ein weiterer einfacher Algorithmus, der für kleine Datenmengen gut geeignet ist.
- Merge Sort: Ein effizienter, stabiler Sortieralgorithmus mit einer Zeitkomplexität von \(O(n \log n)\).
- Quick Sort: Ein sehr effizienter Sortieralgorithmus, der jedoch im schlechtesten Fall \(O(n^2)\) Zeit benötigt.
2. Suchalgorithmen:
- Lineare Suche: Eine einfache Methode, um ein Element in einer Liste zu finden.
- Binäre Suche: Ein effizienter Algorithmus zum Finden eines Elements in einer sortierten Liste, mit einer Zeitkomplexität von \(O(\log n)\).
3. Rekursionsalgorithmen:
- Fakultät: Berechnung der Fakultät einer Zahl.
- Fibonacci-Folge: Berechnung der Fibonacci-Zahlen.
- Türme von Hanoi: Ein klassisches Beispiel für rekursive Problemlösung.
4. Kompressions- und Prüfalgorithmen
- RLL- IBAN
5. Datenstrukturen:
- Stacks und Queues: Implementierung und Anwendung dieser grundlegenden Datenstrukturen.
- Verkettete Listen: Implementierung und Operationen auf verketteten Listen.
- Binärbäume: Implementierung und Traversierung von binären Bäumen (Inorder, Preorder, Postorder).
6. Dynamische Programmierung:
- Rucksackproblem: Ein klassisches Optimierungsproblem.
- Longest Common Subsequence: Ein Algorithmus zur Bestimmung der längsten gemeinsamen Teilfolge zweier Sequenzen.
7. Backtracking:
- N-Damen-Problem: Platzierung von N Damen auf einem Schachbrett, so dass keine zwei Damen sich gegenseitig bedrohen.
Diese Algorithmen und Konzepte sind wesentliche Bestandteile der Informatik-Ausbildung und kommen daher häufig in Prüfungen für Fachinformatiker vor.