»Komplexitätstheorie I«

Herzlich Willkommen auf den WWW-Seiten zur Vorlesung »Komplexitätstheorie I« im Sommersemester 2004

Informationen zur Vorlesung

Inhalt

Im Zentrum der Vorlesungen über Komplexitätstheorie stehen die Frage nach den Grenzen der Berechenbarkeit und die Klassifizierung von Problemen bezüglich ihrer algorithmischen Komplexität. Als Maße für Komplexität werden insbesondere Laufzeit und Speicherbedarf, aber auch z.B. Parallelisierbarkeit herangezogen. Es beinhaltet den Nachweis sowohl der Nichtentscheidbarkeit z.B. der Arithmetik als auch die Untersuchung der Problem-inhärenten Komplexität, d.h. den Beweis unterer Komplexitätsschranken und den Komplexitätsvergleich von Problemen. Im ersten Teil, Komplexitätstheorie I, werden unter anderem folgende Themen behandelt:

• Eine untere Schranke für 1-Band-Turingmaschinen
• Vergleiche zwischen Komplexitätsklassen
• PSPACE-Vollständigkeit
• Nichtentscheidbarkeit

Im WS 04/05 wird im Teil II der Vorlesung u.a. auf parallele Komplexitätsklassen und P-Vollständigkeit eingegangen, und es werden einige weitere untere Schranken vorgestellt.

Termine

Vorlesung

von: Friedhelm Meyer auf der Heide

Übungen

von: Jens Krokowski

Prüfungen

Die Prüfungen sind 30-minütige, mündliche Einzelprüfungen. Die Uhrzeit erfahren Sie hier.
Änderungen werden auf dieser Webseite und/oder per Email mitgeteilt.

Übungen

Gruppenarbeit

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (3-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg (und den Spaß am Studieren) ist das sehr förderlich. Sie dürfen Ihre Übungen (Hausaufgaben) auch in solchen Gruppen abgeben.

Hausaufgaben

Es wird 2-wöchentlich Freitags ein Übungsblatt mit jeweils 3-4 Aufgaben auf dieser Website herausgegeben (1. Termin 16.04.04), das von Ihnen zu bearbeiten ist. Die Lösung wird bis Freitag, 9:00 Uhr in den Kästen auf Ebene D3 abgegeben (1. Termin Fr. 30.04.04, 9 Uhr) und von den Betreuern der Übungsgruppe korrigiert und bewertet.

Anmeldung

Die Anmeldung zu den Übungen erfolgt über StudInfo{flex}. Jede Gruppe ist auf 20 Teilnehmer begrenzt. Sie können Ihre persönlichen Informationen, sowie die Zugehörigkeit zu einer Übungsgruppe und Ihre Punkte aus den Hausaufgaben einsehen. Später finden Sie hier die Klausuranmeldung und erfahren Ihr Klausurergebnis. Bitte beachten Sie: Für jede Veranstaltung, die Sie besuchen und die zur Anmeldung StudInfo{flex} verwendet, müssen Sie sich erneut anmelden, jedes Teilnehmerkonto ist für genau eine Vorlesung gültig. Passwörter werden verschlüsselt gespeichert, d.h. als Administrator können wir nur ein neues Passwort setzen, falls Sie Ihr Passwort vergessen haben. Hier geht es zu Ihrem Teilnehmerkonto:

Prüfung

Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Note wie folgt verbessern (Bonus):

• Erreichen Sie mindestens 50% der Punkte der Hausaufgaben, so verbessert sich die Note um 1/3.

• Erreichen Sie mindestens 75% der Punkte der Hausaufgaben, so verbessert sich die Note um 2/3.

Als Bonusleistung zählen die Hausaufgaben von dieser Veranstaltung. Übungsleistungen aus früheren Veranstaltungen werden nicht anerkannt. Eine Verbesserung der Note 5 (nicht bestanden) ist nicht möglich.

Skript

Literatur

Lehrbücher

• Komplexitätstheorie, Ingo Wegener. Springer, 2003.
  
• Komplexitätstheorie, Band 1. Rüdiger Reischuk. Teubner, 1999. (WWW)
• Computational Complexity. Christos Papadimitriou. Addison-Wesley, 1994.
• Computers and Intractability - A Guide to the Theory of NP-Completeness. M.R. Garey, David S. Johnson. W.H. Freeman and Company, 1979.
• An Introduction to Kolmogorov Complexity and Its Applications. Ming Li, Paul Vitanyi. Springer, 1997. (WWW)
• Elements of the Theory of Computation. Harry R. Lewis, Christos Papadimitriou. Prentice-Hall, 2. Auflage 1997. (WWW)
• The Theory of Computation. Bernard M. Moret. Addison-Wesley, 1998. (WWW) (Fehlerliste)
• Komplexitätstheorie. Wolfgang Paul. Teubner, 1979.
• Einführung in die Komplexitätstheorie. Rüdiger Reischuk. Teubner, 1990.

Die obigen Bücher finden Sie auch im Semesterapparat.

Grundlagen

• Introduction to Automata Theory, Languages, and Computation. John Hopcroft, Jeffrey Ullman. Addsion Wesley, 1979.
• Theoretische Informatk - kurzgefaßt. Uwe Schöning. Spektrum, akad. Verlag, Heidelberg, 3. Auflage 1997.
• Theoretische Informatik - Eine algorithmenorientierte Einführung. Ingo Wegener. Teubner, 1993.
• Introduction to the Theory of Computation. Michael Sipser. PWS, 1997. (Fehlerliste)
  
• Einführung in die Theoretische Informatik. Klaus Wagner. Springer, 1993.
• Perlen der Theoretischen Informatik. Uwe Schöning. BI-Wiss. Verlag, 1995.