Termine
Beginn der Vorlesung:
17.4.2002
Beginn der Übung:
24.4.2002
| VL |
Montag |
11:00 - 13:00 |
(RUD 25, 3.101) |
| Wittwoch |
11:00 - 13:00 |
(RUD 25, 3.101) |
| UE |
Mittwoch |
13:00 - 15:00 |
(RUD 25, 3.101) Dr. C. Gröpl |
| 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
Der Kurs setzt die Vorlesung Graphen und Algorithmen 1 aus dem Wintersemester 2001/2002 fort.
Es werden die folgenden vier Themengebiete vertiefend behandelt:
- Steinerbäume
- zufällige Graphen
- Approximationsalgorithmen und Nichtapproximierbarkeit
- extremale Graphentheorie
Übungen
Leiter: Dr. C. Gröpl
- Übungsblatt 1, ps, pdf
- Übungsblatt 2, ps, pdf
- Übungsblatt 3, ps, pdf
- Übungsblatt 4 und 5, ps, pdf
- Übungsblatt 6, ps, pdf
- Übungsblatt 7, ps, pdf
- Übungsblatt 8, ps, pdf
- Übungsblatt 9, ps, pdf
- Übungsblatt 10, ps, pdf
- Übungsblatt 11, ps, pdf
- Übungsblatt 12, ps, pdf
Programmierpraktikum
Alle (teilweise verbesserten) Aufgaben(stellungen) zusammen auf 4 Seiten:
zall.ps,
zall.pdf
Empfohlene Literatur
-
Hougardy, Prömel,
Graphen und Algorithmen 1
-
Hougardy, Prömel,
Graphen und Algorithmen 2
-
Hougardy,
Proof Checking and Non-Approximability
-
Hougardy, Prömel, Steger,
Probabilistically checkable proofs and their consequences for approximation algorithms
-
Prömel, Steger,
The Steiner Tree Problem. A Tour Through Graphs, Algorithms and Complexity
-
Emden-Weinert, Hougardy, Kreuter, Prömel, Steger,
Einführung in Graphen und Algorithmen
-
Diestel,
Graphentheorie,
Springer Verlag, 2000
-
West,
Introduction to Graph Theory,
Prentice Hall, 1996
English