Vorlesung Effiziente Algorithmen
Dozent:
Prof. Dr. R. Schrader
Zeit und Ort: Di und Mi 12-13.30
Hörsaal III (321c) Physikalische Institute
Vorlesungsbeginn am 13. Oktober 2009
Inhalt der Vorlesung
Die Vorlesung beschäftigt sich mit der Analyse und Implementierung von Verfahren zu folgenden Fragestellungen:
Zusammenhang in Graphen, Aufspannende Bäume, Matroide, Branchings und Aboreszenzen, maximale Flüsse, Matchings in bipartiten und allgemeinen
Graphen, Schnitte von Matroiden, Matrixmultiplikation und Fourier-Transformation. Vorausgesetzt werden Kenntnisse aus den Vorlesungen
"Informatik I und II". Kenntnisse der linearen Programmierung sind hilfreich.
Die Vorlesung wird 4-stündig mit Übungen
(2-stündig) angeboten. Ein Schein kann durch Teilnahme an den Übungen
und eine Abschlussklausur
erworben werden.
Literatur!
- W.J. Cook et al.: "Combinatorial Optimization" (John Wiley & Sons)
- J. Kleinberg, E. Tardos: "Algorithm Design" (Addison Wesley)
- S. O. Krumke, H. Noltemeier: "Graphentheoretische Konzepte und Algorithmen" (Teubner)
Übungen
In den Übungen wird der Inhalt der Vorlesung
vertieft und es besteht die Möglichkeit, den Vorlesungsstoff zu diskutieren. Zusätzlich
werden in den Übungen die Aufgaben besprochen und es wird eine intensive
Prüfungsvorbereitung stattfinden.
