Komplexitätstheorie im SS2008

Modulinformationen

Für weiterführende Informationen siehe auch den Eintrag im Modulhandbuch.

Inhalt

Die Komplexitätstheorie ist ein wichtiges Komplement zur Theorie der Algorithmen. Ihr Ziel ist es zu verstehen, warum gewisse Berechnungsprobleme schwierig sind, und diese anhand ihrer Schwierigkeit zu klassifizieren. Durch Einordnung eines konkreten Problems in so eine Schwierigkeitsklasse kann man feststellen, ob ein gegebener Algorithmus zu seiner Lösung (vermutlich) optimal ist oder nicht. Das bekannteste und wichtigste Beispiel ist die Theorie der NP-Vollständigkeit.

Inhaltliche Gliederung:

  1. Komplexitätsklassen, P vs. NP
  2. Reduktionen und Vollständigkeit
  3. Platzkomplexität
  4. Hierarchiesätze
  5. Relativierung
  6. Polynomialzeit-Hierarchie
  7. Probabilistische Komplexitätsklassen

Koala

E-Learning

Termine

Kalender

Predigt

Es kann nicht genügend betont werden, wie wichtig das selbstständige Nacharbeiten der Vorlesungsinhalte für einen Studienerfolg ist. Die o.g. Aufgaben bieten dazu einen unterstützenden Service und die Möglichkeit zur Selbstkontrolle. Rein statistisch hat sich in der Vergangenheit eine enge Korrelation gezeigt zwischen Prüfungsabschluß und Übungsbearbeitung. Dies in kleinen Gruppen (2-3 Personen) zu tun, bietet zusätzlich soziale Vorteile.
Merke: Lernen ist ein langer und oftmals mühsamer Prozess; er findet nicht am Computer, sondern im Gehirn statt!

Skript

Die Vorlesung orientiert sich inhaltlich an der von Prof. Johannes Blömer im SS2006 gehaltenen und deren Skript.

Prüfung

Eine Klausur (75 Minuten, am 14.7.2008 ab 11:15 im D1.338) und eine mündliche Prüfung in Gruppen a 30 Minuten zu je 5-6 Studierenden (21.7.2008 im D3.230) bestimmen gleichberechtigt die Endnote. Dabei wird Mitarbeit in den Übungen wohlwollend berücksichtigt. Außer Kopf und Stift sind keine Hilfsmittel zugelassen! Zeitplan für die mündlichen Prüfungen:
UhrzeitMatrikelnummern
09h306255249, 6402022, 6259154
10h306381419, 6070647, 3978227, 6223393
11h306245998, 6381530, 6382728, 6180010, 6258296
14h006054917, 6197433, 6299766, 6189931
15h006382024, 6384092, 6279394, 6437893
16h006383058, 6382772, 6365755, 6254787

vorläufige Gesamtnoten ohne Gewähr:
MatrNrNote
62552485,0
64020224,0
62591545,0
63814191,7
60706472,0
62233931,0
62459981,7
61800103,0
62582962,7
60549173,3
61974332,7
62997662,7
61899314,0
63820241,0
63840921,0
62793941,7
64378935,0
63830582,0
63827721,3
63657552,3
62547871,3
61837382,7
3978277NT
6381530NT
6382728NT

Durchschnitt: 2,60. Klausureinsicht: Freitag 1. August 2008 14h00 bis 15h00 im D3.230.

Literatur