|
Dozent:
Prof. Dr. Ernst W. Mayr
Dr. Michal Mnuk
|
|
|
Bereich:
3+2 SWS Vorlesung im
Aufbaustudium Informatik
Pflichtvorlesung
|
|
|
Zeit und Ort:
Di 10h c.t. - 12:00, Hörsaal 1100
Mi 12h c.t. - 13:00, Hörsaal 2760
|
|
|
Übung:
2 SWS Übung zur Vorlesung
Mi 14h s.t. - 15:30, Hörsaal 1100
Übungsleitung: Ulrich Voll
Übungsschein: Einen Schein erhält, wer
(Kriterium wird noch bekanntgegeben)
|
|
|
Hörerkreis:
Studierende im Aufbaustudium Informatik
|
|
|
Voraussetzungen:
Elementare Grundkenntnisse in Informatik
|
|
|
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen
|
|
|
Inhalt:
- Sortieralgorithmen
Bubble-Sort, Merge-Sort, Heap-Sort, Quick-Sort, Radix-Sort,
Median-Algorithmen, untere Schranken für Sortierprobleme
- Suchen
Hashing, Suchbäume, Suchen in Texten
- Elementare Graphalgorithmen
Traversieren von Graphen, Transitive Hülle, kürzeste
Wege Algorithmen, minimale Spannbäume
- Algorithmen für arithmetische Probleme
Multiplikation ganzer Zahlen, Matrizenmultiplikation,
Optimale Klammerung von Matrizenprodukten
|
|
|
Skript:
Das Skript ist leider nicht mehr verfügbar, da es als
Buch erschienen ist.
|
|
|
Literatur:
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest:
-
Introduction to Algorithms
MIT Press, 1990
|
|
|
Sprechstunde:
siehe hier
|
|
|
- Overhead Folien:
- Sortieren
- Der Knuth-Morris-Pratt Algorithmus
- Balancierung bei AVL-Bäumen (Rotation)
- Graphen
- DFS und BFS
- Präorder- und Postorder-Nummerierung
- Baum- und Rückwärtskanten
|
