Table of Contents
Modul Graphenalgorithmen (WiSe 2017/18)
| Veranstalterin | Prof. Dr. Petra Mutzel |
| Modul | Diplom, Master INF-MSc-608 (Informatik, Angewandte Informatik) |
| Veranstaltungsart | VO 2 + UE 2 |
| Veranstaltungsnummer | 042615 |
| Forschungsbereich | Algorithmen und Komplexität (4,6,7 bzw. D) |
| Moodle | Moodle Anmeldung (Passwort s. VO) |
Inhalt und Themen
Diese Veranstaltung baut auf die Inhalte des Basismoduls „Algorithmen und Datenstrukturen“ auf. Während dort grundlegende Graphalgorithmen, wie z.B. einfache Flussprobleme und bipartites Matching behandelt wurden, werden wir hier vertieft Graphenalgorithmen studieren. Wir studieren sowohl polynomielle Algorithmen wie z.B. allgemeines gewichtetes Matching, als auch NP-schwierige Graphenprobleme wie z.B. Netzwerkdesignprobleme, Färbungsprobleme und Wegeprobleme. Wir betrachten spezielle Algorithmen aber auch allgemeinere Methoden, wie z.B. Fest- Parameteralgorithmen und Methoden für Graphen mit kleiner Baumweite.
In einigen Kapiteln werden Kenntnisse der Linearen Programmierung sowie der Dualität linearer Programme, wie sie in dem Basismodul „Algorithmen und Datenstrukturen“ behandelt wurden, vorausgesetzt. Deswegen ist es nicht sinnvoll, an der VO Graphenalgorithmen teilzunehmen, ohne bereits diese Basisvorlesung besucht zu haben. Auch eine gleichzeitige Teilnahme ist nicht sinnvoll.
Ort und Zeit
- Vorlesung:
- Dienstag, 12:00-13:30 Uhr, Seminarraumgebäude 1 R. 1.001
- Beginn der Vorlesungen: Dienstag, 10. Oktober 2017
- Übungen: ungefähr jede 2. Woche
- Termine: zwei Übungsgruppen je Dienstags 15:00-18:00 Uhr und Donnerstags 15:00-18:00 Uhr in OH 14 R.202
- Zur Einteilung in die Übungsgruppen tragen sich die Teilnehmer in Listen ein (in der ersten Vorlesung)
- Die Einteilungen Übungsgruppen werden den Teilnehmer/inne/n via Email gesendet, sofern sie im EWS angemeldet sind. Für die anderen gilt: bitte anmelden (aber erst nach der ersten VO, denn dort gibt es dass Passwort), sonst kommen Sie weder an die Vorlesungsfolien noch an die Übungsblätter!
- Termine der Übungen: 24./26.10.2017, 7./9.11.2017, 28./30.11.2017, 19./21.12.2017, 16./18.1.2018, 30.1./1.2.2018.
Prüfungen
- Prüfungen: mündlich (s. Modulbeschreibung sowie Folien der ersten Vorlesung)
Materialien
- Vorlesungsfolien sowie Originalartikel (englisch) (s. Moodle)
- Cook, Cunningham, Pulleyblank, Schrijver,Combinatorial Optimization, John Wiley and Sons, New York, 1998
Ansprechpartner
Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.