Average effiziente Algorithmen und Average-Komplexitätstheorie

Vorlesung im Wintersemester 2003/04


Inhalt der Vorlesung

Im ersten Teil der Veranstaltung werden Grundbegriffe der Average-Komplexitätstheorie vorgestellt. Diese Spezialisierung der Komplexitätstheorie charakterisiert Probleme hinsichtlich der durchschnittlichen Laufzeit, die zur Lösung notwendig ist.  Hierfür ist es zusätzlich zur Problembeschreibung auch notwendig, eine Wahrscheinlichkeitsverteilung der Eingaben zu betrachten.
 
Wir untersuchen hier zunächst das Boolesche Erfüllbarkeitsproblem (Satisfiability) und wie ein Parameter in der Wahrscheinlichkeitsverteilung, diese Komplexität dieses Problems verändert. Danach führen wir den Begriff der Average-NP-Vollständigkeit ein, der die Menge aller NP-vollständigen Problem beschreibt, die auch im Durchschnitt schwierig sind bezüglich natürlicher Wahrscheinlichkeitsverteilungen.
 
Im zweiten Teil wenden wir uns der Average-Analyse von NP-schwieriegen Problemen zu und stellen Algorithmen vor, die diese in erwartet polynomieller Zeit lösen.

Einordnung

Diese Veranstaltung richtet sich hauptsächlich an Studierende der Informatik. Ein abgeschlossenes Vordiplom in Informatik wird hierbei vorausgesetzt.


Christian Schindelhauer (email: schindel@upb.de)
Erzeugt: 15.10.2003
Stand: 15.10.2003