Komplexitätstheorie und Effiziente Algorithmen
Wintersemester 2005/2006

Veranstalter: Martin Sauerhoff
Termin: Montag 12:15-13:45 Uhr HS 112 / GB IV
Mittwoch 08:30-10:00 Uhr HS 1, OH 14 (Informatik-Neubau)
Beginn: 17. Oktober 2005

Die Vorlesung ist beendet.

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.

Hinweise zu Prüfungen

Vorlesungsankündigung
Was wurde wann gemacht?
Informationen zu den Übungen
Begleitmaterial (Vorlesungsfolien, Übungsblätter, Testfragen)
Zusätzliche Literatur und nützliche Links


Begleitmaterial

Die Vorlesung wird sich in wesentlichen Teilen an folgendem Buch orientieren:
Ingo Wegener, "Komplexitätstheorie -- Grenzen der Effizienz von Algorithmen". Springer, 2003.
Geplant ist die Behandlung einer Auswahl aus den Kapiteln 7, 8, 10-12, 14, 15 und 16 sowie zusätzlich ein neues Kapitel mit dem Thema "Pseudozufall und Derandomisierung".

Vorlesungsfolien: Revised Edition

Inhaltliche Änderungen in der Revised Edition

Vorlesungsfolien: Online-Version aus der Vorlesung

Übungsblätter


Zusätzliche Literatur und nützliche Links

Nicht behandelt, nur ergänzend zum Stoff der Vorlesung.

Kapitel 8:

A compendium of NP optimization problems.
(Editoren: P. Crescenzi und V. Kann.)

Kapitel 10:

Kapitel 11:

Kapitel 12:

Kapitel 15:

Kapitel 16:

Kapitel 17:

P. Bro Miltersen, "Derandomizing Complexity Classes", 1999.


Informationen zu den Übungen:

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

Das erste Übungsblatt wird in der Vorlesung am 19.10. verteilt. Alle weiteren Übungsblätter werden NICHT in der Vorlesung verteilt, sondern sind jeweils mittwochs (Blatt 2 am 26.10.) ab 10.00 Uhr hier verfügbar und liegen im GB IV auf dem Flur im 2.Stock zwischen Raum 325 und Raum 326 aus (Lehrstuhl 2).

Jedes Übungsblatt enthält in der Regel 4 Aufgaben zu jeweils 5 Punkten. Eine Abgabe darf von maximal 2 Personen gemeinsam erstellt werden. Werden Lösungen von mehreren Gruppen gemeinsam erarbeitet, so muss jede Gruppe ihre Lösung eigenständig formulieren und aufschreiben. Bitte bei jeder Abgabe Name, Matrikelnummer und Übungsgruppennummer angeben! Einen Übungsschein erhält, wer

  1. insgesamt 50 % der auf den Blättern erreichbaren Punkte erreicht und
  2. regelmäßig an den Übungsgruppen teilnimmt und dort die eigenen Lösungen vorstellt.

Übungsgruppen:

Zeit: Ort: Veranstalter:
Gruppe 1: Dienstag 16-18 GB IV, Raum 318 Markus Strauch
Gruppe 2: Mittwoch 16-18 GB IV, Raum 318 Stefan Droste
Gruppe 3: Donnerstag 14-16 GB IV, Raum 318 Stefan Droste
Gruppe 4: Freitag 12-14 GB IV, Raum 318 Markus Strauch


M. Sauerhoff