Proseminar: Effiziente Algorithmen
» This course is given in German.
Proseminar im Wintersemester 2002/2003
| Art | Termine/Ort | Beginn | Veranstalter |
|---|---|---|---|
| Ü2 | Do 10:00 - 11:30 5052 | 17.10.2002 | Thomas, Penner, Mitarbeiter |
Inhalt
In diesem Proseminar erarbeiten wir einige Perlen der Algorithmik, die sich an die Vorlesung "Datenstrukturen und Algorithmen" anschließen und die für viele Anwendungen von zentraler Bedeutung sind. Dabei werden auch interessante Methoden der Algorithmenkonzeption vorgestellt. Es werden augewählte Kapitel aus folgendem Lehrbuch behandelt:
Cormen, Leiserson, Rivest: Introduction to Algorithms
Einige der behandelten Themen sind:- Minimale spannende Bäume und die Matroidmethode der Optimierung
- Tiefensuche vertieft: Zusammenhangskomponenten in Graphen und weitere Anwendungen
- Extraktion einer ganzen Klasse von Optimierungsverfahren aus dem Floyd-Warshall-Algorithmus
- Zusammenfassen von Knoten in Graphen mit dem Union-Find-Algorithmus und sein fast linearer Zeitaufwand
- Paralleles Sortieren in sublinearer Zeit
- Effizientes Pattern Matching
- Einstieg in die algorithmische Geometrie