»Komplexitätstheorie II«

Herzlich Willkommen auf den WWW-Seiten zur Vorlesung »Komplexitätstheorie II« im Wintersemester 2004/05

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.

In Fortsetzung zu Komplexitätstheorie I werden u.a. folgende Themen behandelt:

• Pebble Games on Graphs
• Time versus Space
• P-completeness
• Boolean Circuits
  • Asymptotics
  • Simulating Turing Machines
  • Eine untere Schranke für mod₃
• parallele Komplexitätsklassen

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 Termine werden wir am Ende der Vorlesungszeit ankündigen.

Ü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.

Übungsaufgaben

Es wird 2-wöchentlich Montags ein Übungsblatt mit jeweils 3-4 Aufgaben auf dieser Website herausgegeben (1. Termin 11.10.04), das von Ihnen zu bearbeiten ist. Ihre Lösung können Sie bis  zum übernächsten Montag, 9:00 Uhr in den Kästen auf Ebene D3 abgeben (1. Termin Mo. 25.10.04, 9 Uhr). Ihre Lösung wird von den Betreuern der Übungsgruppe korrigiert und bewertet.

Anmeldung

Die Anmeldung zu der Übung erfolgt über StudInfo{flex}. Sie können Ihre persönlichen Informationen, sowie Ihre Punkte aus den Übungsaufgaben einsehen. 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.