angeboten im WS 2008/2009
an der Lehr- und Forschungseinheit 5 (Theoretische Informatik)
des Instituts für Informatik der Universität München
Dr. Felix Brandt, Dr. Jan Johannsen, 2-stündig
Zeit und Ort: Donnerstag, 14.15-15.45 Uhr,
Oettingenstr. 67, Oe 1.39
Beginn: 16.10.2008
Markus Brill, Felix Fischer, 2-stündig
Zeit und Ort: Montag, 16.15-17.45 Uhr,
Oettingenstr. 67, Oe 0.43
Beginn: 27.10.2008
Graphen sind kombinatorische Strukturen, die bei der Modellierung zahlreicher Probleme (z.B. in der Routenplanung, im Mobilfunk oder in der künstlichen Intelligenz) hilfreich sind. Die Vorlesung beschäftigt sich mit den algorithmischen Aspekten grundlegender graphentheoretischer Konzepte wie Wegen, Kreisen, Färbungen, Überdeckungen oder Matchings. Neben der Konstruktion von effizienten Algorithmen werden auch Verbindungen zur Komplexitätstheorie hergestellt.
AnforderungenTeilnahmevorraussetzungen:
| Folien | Übungsblatt | |
|---|---|---|
| Einführung | --- | |
| Graphtraversierung | ||
| Euler- und Hamiltonkreise | ||
| Knotenüberdeckungen | ||
| Knotenfärbungen Teil 1 | ||
| Knotenfärbungen Teil 2 | ||
| Turniergraphen | ||
| Matchings | ||
| Planare Graphen | ||
Literatur
Die Vorlesung richtet sich nicht nach einem Lehrbuch. Die Vorlesungsfolien werden jede Woche auf dieser Webseite veröffentlicht.