Theoretische Informatik II (Sommersemester 2009)

Dozent: Prof. Dr. Christoph Kreitz

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 11.05.2008
• Lehrform:
• Belegungsart: Pflichtmodul

Studiengänge

• IT-Systems Engineering BA

Beschreibung

aktuelle Version der Angaben siehe:

http://www.cs.uni-potsdam.de/ti/lehre/09-Theorie-II/inhalt.html

Die Lehrveranstaltung Theoretische Informatik II bietet eine Einführung die Berechenbarkeitstheorie und Komplexitätstheorie.

Während der ersten Hälfte des 20. Jahrhunderts entdeckten Mathematiker wie Kurt Gödel, Alan Turing und Alonzo Church, dass bestimmte grundlegende Probleme nicht mit Computern gelöst werden können. Ein Beispiel für dieses Phänomen ist das Problem, zu bestimmen, ob eine beliebige mathematische Aussage wahr oder falsch ist. Die Beschäftigung mit dieser Frage erforderte die Entwicklung eines präzisen Algorithmenbegriffs. Dieser Begriff ermöglicht es, in der Berechenbarkeitstheorie Fragen nach den prinzipiellen Grenzen von Computern zu untersuchen.

Wo die Berechenbarkeitstheorie nur nach der grundsätzlichen Lösbarkeit von Problemen fragt, ist es das Anliegen der Komplexitätstheorie, Probleme danach zu klassifizieren, ob sie einfach oder aufwändig zu lösen sind. Dazu werden Konzepte entwickelt, mit denen der Schwierigkeitsgrad eines Problems charakterisiert werden kann. Interessanterweise ist die zentrale Frage der Komplexitätstheorie, welche Eigenschaften eines Problems darüber entscheiden, ob das Problem algorithmisch handhabbar ist, bislang weitgehend ungeklärt.

Gliederung:    

• Berechenbarkeitstheorie
  • Turingmaschinen, Turing-Akzeptierbarkeit, Entscheidbarkeit, Aufzählbarkeit, Berechenbarkeit
  • Äquivalenz von Berechenbarkeitsmodellen, Church-Turing-These, formaler Algorithmenbegriff
  • Entscheidbare Probleme, Unentscheidbarkeit des Halteproblems
  • Beweis der Unentscheidbarkeit von Problemen durch funktionale Reduktion
  • Rekursionssatz und Unentscheidbarkeit logischer Theorien, Gödels Unvollständigkeitssatz
• Komplexitätstheorie
  • Zeitkomplexität von Algorithmen
  • Komplexitätsklassen P und NP
  • NP-Vollständigkeit
  • Platzkomplexität
  • Komplexitätsklasse PSPACE, PSPACE-Vollständigkeit
  • Probabilistische Algorithmen, Komplexitätsklassen ZPP, BPP und RP

Literatur

• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005 Auf diesem Buch basiert die Lehrveranstaltung. Es ist nach unserer Ansicht der beste Einführungstext in die theoretische Informatik. Leider ist es in Deutschlang recht teuer, aber vielleicht gebraucht zu bekommen (die erste Auflage von 1997 ist übrigens fast identisch). In der Bibliothek wird demnächst eine größere Anzahl von Exemplaren verfügbar sein.
• John E. Hopcroft und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 4. Auflage, Oldenbourg Verlag 2000 Dieses Buch basiert auf der 1979er Ausgabe des englischsprachigen Originals. Es ist etwas detaillierter als das Buch von Sipser, dafür fehlen einige modernere Ergebnisse. Im Handel ist es nicht mehr erhältlich, aber gebraucht günstig zu bekommen und in vielen Bibliotheken vorrätig.
  
  Achtung: Es gibt ein gleichnamiges Buch von Hopcroft, Ullman und Motwani, das 2002 bei Pearson erschienen ist. Dies ist jedoch ein völlig anderes Buch und aus unserer Sicht nur bedingt zu empfehlen. Dafür ist es recht günstig.
• John Martin: Introduction to Languages and the Theory of Computation. 3. Auflage, McGraw-Hill 2002 Ein gutes Buch, das alle Standardthemen abdeckt.
• Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage, Spektrum Akademischer Verlag 2001 Eine knappe, aber angenehm zu lesende Einführung in die theoretische Informatik.

Lern- und Lehrformen

2 SWS Vorlesung; 2 SWS Übung

Leistungserfassung

• Etwa in der Mitte des Semesters wird eine Probeklausur stattfinden. Die darin erreichten Punkte werden zu den Hausaufgabenpunkten addiert.

• Die Leistungsbewertung erfolgt durch eine abschließende Klausur. Um zur Klausur zugelassen zu werden, benötigen Sie mindestens 30% der Hausaufgaben- und Probeklausurpunkte.

• Die Übungsblätter werden wöchentlich als pdf-Dateien bereitgestellt. Jedes Übungsblatt enthält Präsenzaufgaben und Hausaufgaben. Die Präsenzaufgaben sollen während der wöchentlichen Übungen unter Anleitung durch die Tutoren bearbeitet werden.

• Die Hausaufgaben können Sie einzeln oder in Gruppen von bis zu vier Studierenden bearbeiten. Bitte werfen Sie Ihre Lösungen bis zum jeweiligen Abgabetermin in den gekennzeichneten Schrank im Foyer des ersten Stocks im Informatik-Gebäude. Die korrigierten Hausaufgaben erhalten Sie in einer der nächsten Übungen zurück. Einzelne Hausaufgaben werden in den Hörsaalübungen vorgerechnet.

• Falls Sie Fragen zu den Hausaufgaben oder zum Stoff der Vorlesung haben, nutzen Sie bitte rechtzeitig die Sprechstunden der Veranstalter oder sprechen Sie die Tutoren an.

Termine

Vorlesungen ab 24.04.2009

Übungsgruppen ab 27.04.2009

Tutorium ab 06.05.2009

Zurück