zurück zum Inhaltsverzeichnis dieser Seite
Angenommen Sie arbeiten in einer Firma, in der es um die Annahme eines
Grossauftrags geht.
Dabei würde jeden Tag eine feste Zahl verschiedener Rechenaufträge
festgelegter Dauer anfallen, die alle bis zum jeweils nächsten Tag
abgewickelt werden müssten.
Sie sollen die einzelnen Rechenaufträge so auf die freien
Kapazitäten der Firmenrechner aufteilen, dass die Abwicklung an
einem Tag gelingt.
Wie gehen Sie vor?
Und was wenn Sie keine Lösung finden?
Wie überzeugen Sie Ihre Vorgesetzten, dass es nicht an Ihrer
Unfähigkeit liegt, sondern die Firmenrechner tatsächlich nicht
ausreichen?
Nach dieser Vorlesung werden Sie für Probleme dieser Art gut
gerüstet sein.
In der Vorlesung werden zentrale Themen der Komplexitätstheorie
behandelt.
Nach der Präsentation und dem Vergleich abstrakter Berechnungsmodelle wie
Turing- und Registermaschinen, werden die grundlegenden Begriffe
für die Berechnungsresourcen Zeit und Platz vorgestellt.
Anhand konkreter Probleme und der Analyse ihrer inhärenten
"`Schwierigkeit"'
führen wir die wichtigsten Komplexitätsklassen wie P, NP, PSPACE und
zahlreiche Verfeinerungen ein.
Zur Klassifikation von Problemen wurden eine Reihe von Begriffen und
Techniken wie die Reduzierbarkeit zwischen Problemen oder die
Vollständigkeit von Problemen entwickelt, die
ausführlich behandelt werden.
Mit diesen Methoden werden eine Reihe konkreter Probleme wie z.B.
das Rucksackproblem oder die Boolesche Erfüllbarkeit und entsprechende
Lösungsverfahren verglichen.
Schwerpunkte der Vorlesung sind die Behandlung von Hierarchiesätzen und
die Präsentation von Vollständigkeitsresultaten.
Weitere Themen sind die Boolesche und die Polynomielle
Hierarchie, Orakel- und alternierenden Maschinen, Boolesche Schaltkreise sowie
probabilistische Komplexitätsklassen.
zurück zum Inhaltsverzeichnis dieser Seite
Blatt1 Blatt2 Blatt3 Blatt4 Blatt5 Blatt6 Blatt7 Blatt8 Blatt9 Blatt10