Dozent: Hans Jürgen Prömel
Termine
| VL | Montag | 11:00 - 13:00 | (RUD 25, 3.101) |
|---|---|---|---|
| Mittwoch | 11:00 - 13:00 | (RUD 25, 3.101) | |
| UE | Mittwoch | 13:00 - 15:00 | (RUD 25, 3.101) Anusch Taraz |
| PR | n.V. |
Zuordnung
- Hauptstudium, 2. Teil eines Kurses
- Theoretische Informatik
Voraussetzungen
- Grundstudium
- Die Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Inhalte und Lernziele
Die Vorlesung setzt den im Wintersemester 1999/2000 abgehaltenen Teil I fort. Es werden anspruchsvollere Prinzipien der Graphenalgorithmen, insbesondere für NP-schwere Probleme betrachtet, u.a. Approximationsalgorithmen und randomisierte Verfahren. Die Vorlesung wird durch Übungen begleitet. Kenntnis des ersten Teils der Vorlesung ist wünschenswert, aber nicht notwendig.
Übungen
Leiter: Dr. Anusch Taraz- 1. Übung, Aufgaben 1 - 5
- 2. Übung, Aufgaben 6 - 9
- 3. Übung, Aufgaben 10 - 13
- 4. Übung, Aufgaben 14 - 17
- 5. Übung, Aufgaben 18 - 21
- 6. Übung, Aufgaben 22 - 25
- 7. Übung, Aufgaben 26 - 29
- 8. Übung, Aufgaben 30 - 33
- 9. Übung, Aufgaben 34 - 37
- 10. Übung, Aufgaben 38 - 40
- 11. Übung, Aufgaben 41 - 43
- 12. Übung, Aufgaben 44 - 47
Programmierpraktikum
Ziel des Praktikums soll es sein, einige Algorithmen auf Graphen zu implementieren, wie sie teilweise in der Vorlesung vorgestellt werden. Die Erfahrung zeigt, daß der Schritt von der Formulierung eines Algorithmus in einer informalen Notation hin zu einer Realisierung in einer existierenden Programmiersprache mit kleinen Problemen behaftet ist, die zu lösen hier geübt werden soll.
Die Programmiersprache kann individuell gewählt werden, solange sie nicht zu exotisch und auch am Institut lauffähig ist. Weiterhin ist jedem freigestellt, ob er eigene Datenstrukturen entwickelt, oder sich bereits vorhandener bedient (siehe Links am Ende der Seite.)
Weitere Links
- LEDA (MPI Saarbrücken)
- Stanford GraphBase
- Visualizing Graphs with Java (Auburn)
- Graph Template Library (Passau)
- Graph Drawing Toolkit (Rom)
- Graph Animation Toolbox (Köln)
Empfohlene Literatur
- , Modern Graph Theory, Springer
- , Graphentheorie, Springer
- , Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996
