| Wochentag | Uhrzeit | Hörsaal |
|---|---|---|
| Montag | 12-14 Uhr | HS 112 (GB IV) |
| Mittwoch | 08-10 Uhr | HS 112 (GB IV) |
Diese Vorlesung hat im Wintersemester den Schwerpunkt Komplexitätstheorie und im Sommersemester den Schwerpunkt Effiziente Algorithmen. Ein Besuch beider Vorlesungen ist sinnvoll und für eine Spezialisierung in diesen Bereichen sehr nützlich.
In den Grundvorlesungen wurde die NP-Vollständigkeitstheorie vorgestellt, die den Kern der Komplexitätstheorie darstellt. Schon dabei wurde deutlich, dass eine feinere Unterscheidung im Schwierigkeitsgrad von Problemen wünschenswert ist. So wird das Rucksackproblem effizient lösbar, wenn alle Gewichtswerte kleine Zahlen sind, während das TSP selbst bei Distanzwerten von 1 und 2 schwierig ist.
In dieser Vorlesung werden zunächst die Grundzüge der NP-Vollständigkeitstheorie wiederholt und es wird für Probleme untersucht, welche Teilprobleme effizient lösbar sind. Bei Optimierungsproblemen ist es oft ausreichend, an Stelle einer optimalen Lösung eine garantiert gute Lösung zu konstruieren. Die Untersuchung der Komplexität der zugehörigen Approximationsprobleme war in den letzten gut 10 Jahren Schwerpunkt der Forschung. Im ersten Teil der Vorlesung werden klassische Resultate aus diesem Gebiet vorgestellt, später wird das Thema wieder aufgegriffen, um die neuen Methoden und deren Auswirkungen zu diskutieren.
In den Anwendungen spielen randomisierte Suchheuristiken wie evolutionäre Algorithmen oder Simulated Annealing eine immer wichtigere Rolle. Diese Algorithmen nutzen nicht die volle Information über die Eingabe. Die Komplexitätstheorie reagiert auf alle neuen algorithmischen Entwicklungen und wir stellen eine Theorie vor, die Probleme darauf untersucht, ob sie mit randomisierten Suchheuristiken effizient lösbar sind.
Insgesamt hat die moderne Informatik die zentrale Rolle von Kommunikation bei der Lösung von Problemen erkannt. Das gilt auch für die Komplexitätstheorie. So basiert die oben genannte Komplexitätstheorie für Approximationsprobleme auf der Idee, Probleme interaktiv zu lösen. Ein Nebenprodukt hierzu sind kryptografische Systeme, um Passwörter zu benutzen, ohne Informationen über diese Passwörter preiszugeben. Dies klingt unglaublich - aber es funktioniert.
Darüber hinaus hat sich das Gebiet Kommunikationskomplexität etabliert. Wieviel Information müssen Alice und Bob austauschen, um f(a, b) zu berechnen, wenn Alice nur a und Bob nur b kennt? Dieses einfache Spiel hat überraschend viele Facetten und Anwendungen. Die Grundzüge dieser Theorie werden vorgestellt und die Anwendungen führen zu konkreten unteren Schranken für die Komplexität von Problemen in realistisch eingeschränkten Berechnungsmodellen.
Insgesamt ergibt sich ein Einblick in die moderne Komplexitätstheorie mit überraschend vielen konkreten Ergebnissen, die den Entwurf effizienter Algorithmen in die richtigen Bahnen lenken.
Für die Teilnahme an den Übungen ist eine Anmeldungen in der ersten Vorlesung (am 13.10.) erforderlich.
Die ersten Übungen finden in der zweiten Vorlesungswoche (also ab dem 20.10.) statt.
Das erste Übungsblatt wird in der ersten Vorlesung am 13.10. verteilt. Der Termin für die Abgabe ist Montag, der 20.10., 12.00 Uhr. Alle weiteren Übungsblätter werden NICHT in der Vorlesung verteilt, sondern sind jeweils montags hier verfügbar und liegen im GB IV auf dem Flur des 2. OG (Lehrstuhl 2) zwischen Raum 325 und Raum 326 aus.
Eine Abgabe darf von bis zu 2 Personen gemeinsam erstellt werden, wobei jede Person in der Lage sein muss, die Lösungen vorzurechnen. Bitte bei der Abgabe Name, Matrikelnummer und Übungsgruppennummer mit angeben.
Einen Übungsschein erhält, wer insgesamt 50% der Punkte erreicht und regelmäßig die eigenen Lösungen in der Übungsgruppe vorstellt.
Übungen werde zu folgenden Terminen angeboten:
| Gruppe | Wochentag | Uhrzeit | Gebäude | Raum | Übungsgruppenleiter |
|---|---|---|---|---|---|
| 1 | Dienstag | 08-10 Uhr | GB IV | 318 | Philipp Wölfel |
| 2 | Dienstag | 10-12 Uhr | GB IV | 318 | Philipp Wölfel |
| 3 | Dienstag | 16-18 Uhr | GB IV | 113 | Jens Jägersküpper |
| 4 | Mittwoch | 10-12 Uhr | Pav 6 | 18 | Stefan Droste |
| 5 | Mittwoch | 16-18 Uhr | GB IV | 318 | Stefan Droste |