Dozent: T. Nierhoff
Termine
Beginn der Vorlesung: 15.04.2003Beginn der Übung: 15.04.2003
| VL | Dienstag | 09:00 - 11:00 | (RUD 26, 3.001) |
|---|---|---|---|
| UE | Dienstag | 11:00 - 13:00 | 14tgl./1. (RUD 26, 1.305) T. Nierhoff |
| Dienstag | 11:00 - 13:00 | 14tgl./2. (RUD 26, 1.305) T. Nierhoff | |
| Dienstag | 11:00 - 13:00 | 14tgl./2. (RUD 25, 1.011) M. Füssel | |
| Donnerstag | 9:00 - 11:00 | 14tgl./1. (RUD 26, 0.311) D. Osthus | |
| Donnerstag | 9:00 - 11:00 | 14tgl./2. (RUD 26, 0.311) D. Osthus | |
| Donnerstag | 11:00 - 13:00 | 14tgl./1. (RUD 26, 0.311) D. Osthus | |
| Donnerstag | 11:00 - 13:00 | 14tgl./2. (RUD 26, 0.311) D. Osthus |
Zuordnung
- Grundstudium, 4. Semester
Voraussetzungen
- Theoretische Informatik 1
- Theoretische Informatik 2
Inhalte und Lernziele
Teil I: NP-Vollständigkeit- Random Access Machines und Polynomialzeitalgorithmen
- Selbstreduzierbarkeit
- Polynomialzeitreduktionen
- NP, NP-schwer, NP-vollständig, coNP
- NPO
- 2-Approximationsalgorithmen für VertexCover und TSP
- PTAS für Knapsack
- ln n-Approximationsalgorithmus für SetCover
- Ausblick: randomisierte Algorithmen
Lernziele: Selbständige Lösungsfindung, schlüssige Argumentation, saubere Dokumentation
Folien
Disclaimer: Es gilt das gesprochene Wort- 15. April (pdf)
- 22. April (pdf)
- 29. April (pdf)
- 6. Mai (pdf)
- 13. Mai (pdf)
- 20. Mai (pdf)
- 27. Mai (pdf)
- 3. Juni (pdf)
- 10. Juni (pdf)
- 17. Juni (pdf)
- 08. Juli (pdf)
- 15. Juli (pdf)
Übungen
Leiter: Dr. Till Nierhoff, M. Füssel und D. Osthus- Serie 1 (ps/pdf)
- Serie 2 (ps/pdf)
- Serie 3 (ps/pdf)
- Serie 4 (ps/pdf)
- Serie 5 (ps/pdf)
- Serie 6 (ps/pdf)
- Serie 7 (ps/pdf)
- Serie 8 (ps/ps.gz/pdf)
- Serie 9 (ps/ps.gz/pdf)
- Serie 10 (ps/ps.gz/pdf)
Empfohlene Literatur
- , Theoretische Informatik, Pearson Studium, 2002.
- , Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
- , Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
- , Approximation Algorithms for NP-hard problems, PWS Publishing, 1995.
- , Graphen und Algorithmen 1, Vorlesungsskript, Berlin 2000.
- , Theoretische Informatik II, Vorlesungsskript, Berlin 2000.
- , Computational Complexity, Addison Wesley, 1994.
- , Diskrete Strukturen 1, Springer Verlag, 2001.
- , Approximation Algorithms, Springer Verlag, 2001.
- , Theoretische Informatik, Teubner Verlag, 1993.
Prüfung
- Klausur
- Die Nachklausur findet am 15. Oktober 2003 von 9 bis 13 Uhr im großen Hörsaal 3.001 (RUD 25) statt.
- Einsicht in die Klausur bis zum 1. Dezember in Raum 3.320, RUD 25.
- Die erste Klausur war am 12.7.03.
English