Komplexitätstheorie und effiziente Algorithmen

im Wintersemester 2004/05

Prof. Dr. Ingo Wegener

Inhalt

1. Informationen zur Vorlesung
2. Informationen zu den Übungen
3. Begleitmaterial

Informationen zur Vorlesung

• Veranstalter

  Ingo Wegener

• Vorlesungstermine

  Wochentag	Uhrzeit	Hörsaal
  Montag	12-14 Uhr	HS 112 (GB IV)
  Mittwoch	08-10 Uhr	HS 112 (GB IV)

• Vorlesungsinhalt

  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.

• Literatur

  Geplant ist die Behandlung der Kapitel 7-12 und 15-16 aus dem Buch Ingo Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer. 2003.

Informationen zu den Übungen

• Veranstalter

  Ingo Wegener, Philipp Wölfel

• Modalitäten

  Für die Teilnahme an den Übungen ist keine Anmeldung erforderlich.

  Die ersten Übungen finden in der zweiten Vorlesungswoche (also ab dem 18.10.) statt.

  Das erste Übungsblatt wird in der ersten Vorlesung am 11.10. verteilt. Der Termin für die Abgabe ist Montag, der 18.10., 10.00 Uhr. Alle weiteren Übungsblätter werden NICHT in der Vorlesung verteilt, sondern sind jeweils mittwochs (Blatt 2 am 13.10.) ab 10.00 Uhr hier verfügbar und liegen im GB IV auf dem Flur des 2. OG (Lehrstuhl 2) zwischen Raum 325 und Raum 326 aus. Abgabetermin ist jeweils der auf die Ausgabe folgende Mittwoch um 18.00 Uhr.

  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.

• Übungstermine

  Übungen werde zu folgenden Terminen angeboten:

  Gruppe	Wochentag	Uhrzeit	Gebäude	Raum	Übungsgruppenleiter
  1	Montag	14-16 Uhr	GB IV	318	Ingo Wegener
  2	Mittwoch	10-12 Uhr	PAV 6	18	Philipp Wölfel
  3	Mittwoch	12-14 Uhr	GB IV	318	Philipp Wölfel

Begleitmaterial

• Übungsblätter
• Folien
• Handgeschriebene Folien aus der Vorlesung vom 10.01.2005 (JPEG)