HEINZ NIXDORF INSTITUT
Universität-GH Paderborn
Theoretische Informatik
AG Meyer auf der Heide


Komplexitätstheorie I

WS 00/01

 

Friedhelm Meyer auf der Heide

Termine

Vorlesung (V2)
Mo 11.15  - 12.45    E2.310        F. Meyer auf der Heide
Übung (Ü1)
Mo  8.15  -  9:00    E2.310  1     M. Ziegler
Mo 10.00  - 10:45    E2.310  2     M. Ziegler
Prüfung
Wer nach der DPO 4 oder der neuen Lehramtsstudienordnung studiert,
kann im Anschluß an »Komplexitätstheorie I«   benotete, mündliche, 
ca. 30-minütige Prüfungen bei Prof. Meyer auf der Heide ablegen:
entweder am 23.Februar oder am 3.April 2001. Anmeldungen per Email.

Für Studierende in anderen Prüfungsordnungen stehen nach dem Ende 
des SS2001 Termine für mündliche Prüfungen über »Komplexitätstheorie
I+II« zur Verfügung.
 

Inhalt der Vorlesung

Die Komplexitätstheorie versucht, algorithmische Problemstellungen nach ihrem Bedarf an Ressourcen wie z.B. Rechenzeit oder Speicherplatz zu klassifizieren. Der Idealfall ist, daß man (bzgl. eines festen Rechenmodells) einen Algorithmus angibt, der das Problem löst (obere Schranke: Entwurf effizienter Algorithmen) und zeigt, daß dieser Algorithmus optimal ist, d.h. daß kein (z.B.) schnellerer Algorithmus das Problem löst (untere Schranke). In mächtigen Modellen wie Turingmaschinen, Registermaschinen oder Schaltkreisen ist man bisher nicht in der Lage, solche »exakten Komplexitätsschranken« für Probleme anzugeben. Dennoch kann man wichtige, interessante Aussagen machen: Zum einen können in eingeschränkten Rechenmodellen untere Schranken nachgewiesen werden, zum anderen kann durch Vergleich von Komplexitätsklassen in vielen Fällen Evidenz für die Schwierigkeit von Problemen angegeben werden, siehe z.B. das Konzept der NP­Vollständigkeit.

Es werden u.a. folgende Themen behandelt:

  1. Einleitung
  2. Turingmaschinen
  3. Eine untere Schranke für 1-Band-Turingmaschinen
  4. Vergleiche zwischen Komplexitätsklassen, Hierarchiesätze
  5. Nichtdeterministische Turingmaschinen
  6. NP-Vollständigkeit (Erweiterung des Kapitels aus der Grundstudium-Vorlesung)
  7. Die Klasse PSPACE
  8. Unentscheidbarkeit der Arithmetik

Weitere Informationen

Literatur

Zur Vorlesung gibt es einen Semesterapparat in der Bibliothek, in dem einige der oben angegebenen Bücher zu finden sind.


Martin Ziegler