Dozent: Dr. Till Nierhoff
Termine
Beginn der Vorlesung: 17.04.2002| VL | Donnerstag | 10:00 - 12:00 | (UL 6, 3038) |
|---|---|---|---|
| UE | Mittwoch | 14:00 - 16:00 | (DOR 24, 403) Dr. A. Taraz (ungerade Semesterwochen) |
| UE | Mittwoch | 14:00 - 16:00 | (DOR 24, 403) Dr. A. Taraz (gerade Semesterwochen) |
| UE | Donnerstag | 14:00 - 16:00 | (DOR 24, 403) Dr. T. Nierhoff (ungerade Semesterwochen) |
| UE | Donnerstag | 14:00 - 16:00 | (DOR 24, 403) Dr. T. Nierhoff (gerade Semesterwochen) |
| UE | Donnerstag | 16:00 - 18:00 | (DOR 24, 311) Dr. T. Nierhoff (ungerade Semesterwochen) |
| UE | Donnerstag | 16:00 - 18:00 | (DOR 24, 311) Dr. T. Nierhoff (gerade Semesterwochen) |
Zuordnung
- Grundstudium, 4. Semester
Voraussetzungen
- Theoretische Informatik 1
- Theoretische Informatik 2
Inhalte und Lernziele
Im Zentrum der Vorlesung steht die algorithmische Komplexität von Problemen, insbesondere die Begriffe der NP-Vollständigkeit und der Effizienz von Algorithmen und Datenstrukturen.
Basierend auf dem Rechnermodell Turingmaschine werden verschiedene Optimierungs- und Entscheidungsprobleme hinsichtlich ihrer algorithmischen Schwierigkeit analysiert. Probleme wie etwa das Traveling Salesman Problem und das Rucksackproblem kann man natürlich lösen, aber alle bekannten Algorithmen, die optimale Lösungen berechnen, haben eine exponentielle Rechenzeit. Die beiden Probleme sind NP-vollständig. Etwa 3000 weitere Probleme sind als NP-vollständig bekannt und entweder gibt es für alle diese polynomielle Verfahren oder für keines. Es wird allgemein vermutet, daß es für NP-vollständige Probleme keine polynomiellen Algorithmen gibt. Dieses ist die zentrale P!=NP-Vermutung.
Zur effizienten Behandlung NP-vollständiger Probleme erscheint es daher notwendig, sich mit Heuristiken oder Approximationsalgorithmen zufrieden zu geben. Hierzu werden erste algorithmische Prinzipien zur approximativen oder randomisierten `Lösung' NP-vollständiger Probleme vorgestellt.
Übungen
Leiter: Anusch Taraz, Dr. Till NierhoffIn den Übungen kann ein Übungsschein "Theoretische Informatik 3" erworben werden. Voraussetzung ist das Erreichen von mindestens 50% aller möglichen Punkte in den Übungsaufgaben.
Jeder Teilnehmer der Vorlesung muss sich über Goya in einer der Übungen anmelden.
Die Übungsaufgaben werden jede Woche am Ende der Vorlesung ausgeteilt. Sie sollen innerhalb von einer Woche in Arbeitsgruppen von bis zu drei Studierenden bearbeitet werden. Die Abgabe erfolgt zu Beginn der nächsten Vorlesung (bis 10.10 Uhr, spätere Abgaben werden nicht mehr angenommen).
| Woche | Thema in UE Mi | Thema in UE Do | Abgabe in VL Do |
|---|---|---|---|
| 1 | Anw.Aufg. | Anw.Aufg. | - |
| 2 | Anw.Aufg. | Anw.Aufg. | Serie 1 |
| 3 | Feiertag | Serie 1 | Serie 2 |
| 4 | Serie 1 | Feiertag | |
| 5 | Serie 1 | Tag der Informatik | |
| 6 | Serie 2 | Serien 1+2 | Serie 3 |
| 7 | Serien 2+3 | Serien 2+3 | Serie 4 |
| 8 | Serien 3+4 | Serien 3+4 | Serie 5 |
| 9 | Serien 4+5 | Serien 4+5 | Serie 6 |
| 10 | Serien 5+6 | Serien 5+6 | Serie 7 |
| 11 | Serien 6+7 | Serien 6+7 | Serie 8 |
| 12 | Serien 7+8 | Serien 7+8 | - |
| 13 | Serie 8 | Serie 8 | - |
| 14 | Klausurwoche (s.a. Prüfung) | ||
Prüfung
Die Vorlesung wird mit einer schriftlichen Prüfung (Klausur) abgeschlossen, die am 13.6. von 9-13 Uhr in den Hörsälen 9 und 10, Invalidenstr. 42 stattfindet. Die Nachklausur findet am 11.10. von 9-13 Uhr im großen Hörsaal 3.001, RUD 25 statt. Zur Vorbereitung/Einstellung auf die Klausur gibt es eine Übungsklausur.Mittlerweile stehen die Ergebnisse der Klausur und der Nachklausur fest. Die Klausuren können vom 24.9.02 bis zum 26.9.02 jeweils von 9:30 bis 16:00 in Raum 3.320, RUD 25, eingesehen werden.
Empfohlene Literatur
- , 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.
- , Theoretische Informatik, Teubner Verlag, 1993.
English