| INHALT: |
- Grundlagen
- Algorithmen und Komplexität: Wiederholung
- Asymptotische Notation
- Rekurrenzen
- Graphen
- Grundbegriffe aus: elementare Kombinatorik
- Grundbegriffe aus: diskrete
Wahrscheinlichkeit
- Problemlösungsstrategien
- Divide and Conquer
- Technik des Balanzierens (optional)
- Greedy-Verfahren
- Dynamisches Programmieren
- Vollständiges Aufzählen (optional)
- Backtracking
- Branch and Bound (optional)
- Sortieren und Selektieren
- Resume elementarer Verfahren aus dem 1. Semester:
u.a. Sortieren durch Minimumsuche, durch Einfügen,
durch Mischen, Heapsort , Quicksort
- Alternativ : hier Heapsort/Quicksort falls im
1.Semester nicht beh.
- Untere Schranken für Sortieren
- Counting sort, Radix sort, Bucket sort
- Selektieren
- Externes Sortieren ( optional)
- Suchen und Mengenmanipulationen
- Union-find
- Suchbäume ( binäre Suchbäume, Mehrwege-Bäume,
B-Bäume, ...)
- Rot-schwarz Bäume
- Hashing
- Graphprobleme
- Durchlaufstrategien für Graphen
- Zusammenhang
- gewichtete Graphen: Single source shortest path
Probleme (z.B. Dijkstra, Bellman-Ford), Minimum Cost
Spanning tree,
- Färbeprobleme (optional)
- Algorithmen auf Zeichenfolgen
- Mustererkennung : allgemein mit Automaten z.B RK,
KMP, BM, Positionsbäume (optional)
- Datenkomprimierung
- Ausblick auf weitere Themen: (optional) Heuristische
Verfahren, probabilistische Verfahren , parallele
Algorithmen, genetische Algorithmen ,"Algorithmen in
Hardware"
|
