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

• Zur Vorlesung gibt es ein Skript.
• Für Übungszettel 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, und 13 ist der Zug schon abgefahren.
• Blatt 14 ist abzugeben bis zum 10.2.2001 13:00.
• Zur Vorbereitung auf eine mündliche Püfung empfehle ich Blatt 15.
• Bei Springer kann man nachlesen, was die Komplexitätstheorie für die Praxis leistet
  (geht allerdings nur beim Surfen von der Domäne uni-paderborn.de)
• Nächstes Semester wird diese Veranstaltung fortgeführt als Komplexitätstheorie II
• Bereits in diesem Semester gibt es als nützliche Parallelveranstaltung das Seminar Perlen der Theoretischen Informatik
• Sprechstunde: Mittwochs 13:30-14:30 im F1.301 sowie nach Vereinbarung

Literatur

• C. H. Papadimitriou: «Computational complexity», Addison-Wesley, 1994
• Bernard M. Moret: «The Theory of Computation», Addison-Wesley 1998
• John E. Savage: «Models of Computation -- Exploring the Power of Computing», Addison-Wesley 1998
• J. E. Hopcroft, J.D. Ullmann: «Introduction to Automata Theory, Languages and Computation» Addison-Wesley 1979
• M. Sipser: «Introduction to the Theory of Computation» PWS Publishing Company, 1997
• H.R. Lewis, C.H. Papadimitriou: «Elements of the Theory of Computation» Prentice-Hall
• U.Schöning «Perlen der Theoretischen Informatik» BI-Wissenschaftsverlag, 1995
• U. Schöning «Theoretische Informatik kurz gefaßt» Spektrum Akademischer Verlag 1997
• K. W. Wagner «Einführung in die theoretische Informatik, Grundlagen der Modelle» Springer Verlag
• I. Wegener «Theoretische Informatik» Teubner-Verlag
• M. R. Garey, D.S. Johnson «Computers and Intractability - A Guide to the Theory of NP-Completness» W. H. Freeman and Company
• R.Motwani, P.Raghavan «Randomized Algorithms» Cambridge University Press, 1995
• Rüdiger Reischuk: «Einführung in die Komplexitätstheorie» Band 1, Teubner 1990

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

---

Martin Ziegler