Theoretische Informatik II (Sommersemester 2013)

Lecturer: Prof. Dr. Christoph Kreitz

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 10.2.2013 - 30.4.2013
• Teaching Form: VU
• Enrolment Type: Compulsory Module

Programs, Module Groups & Modules

Description

aktuelle Version der Angaben siehe:

 http://cs.uni-potsdam.de/ti2-ss13

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 der Theoretischen Informatik II:    

• Berechenbarkeitstheorie
  • Turingmaschinen, Turing-Akzeptierbarkeit vs. Berechenbarkeit
  • Äquivalenz von Berechenbarkeitsmodellen: Rekursive Funktionen, funktionale und logische Programme, Church-Turing-These
  • Berechenbarkeitstheorie: Grundgesetze, Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit; Abschlusseigenschaften
  • Beweismethoden für die Unlösbarkeit von Problemen: Diagonalisierung, Monotonieargumente, funktionale Reduktion, Satz von Rice
  • Post'sches Korrespondenzproblem, Unentscheidbarkeit von Eigenschaften kontextfreier Grammatiken
• Komplexitätstheorie
  • Zeitkomplexität von Algorithmen und Problemen
  • Komplexitätsklassen P und NP
  • NP-Vollständigkeit und die Nichthandhabbarkeit algorithmischer Probleme
  • Platzkomplexität, PSPACE-Vollständigkeit
  • Probabilistische Algorithmen zur Behandlung nichthandhabbarer Probleme

Literature

• J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen- und Komplexitätstheorie, Pearson 2002. Dieses Buch bildet den Leittext für diese Veranstaltung. Manche Themen werden allerdings etwas zu vereinfacht dargestellt. Es gibt eine ältere Version des Buches im Oldenbourg Verlag, in dem die Themen deutlich knapper, aus unserer Sicht aber auch klarer abgehandelt werden. Dafür fehlen einige moderndere Ergebnisse.
• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage, PWS 2005. Aus Sicht eines Theoretikers eine der besten Einführungen in die theoretische Informatik. Es verwendet in der abstrakten Berechenbarkeitstheorie allerdings eine Notation, die unserer Erfahrung nach nicht sehr intuitiv ist. Leider ist es in Deutschland recht teuer, aber vielleicht gebraucht zu bekommen (die erste Auflage von 1997 ist übrigens fast identisch).
• 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. 5. Auflage, Spektrum Akademischer Verlag 2008. Eine knappe, aber angenehm zu lesende Einführung in die theoretische Informatik.
• I. Wegener: Theoretische Informatik. 3. Auflage, Teubner Verlag 2005.
• H. Lewis, C. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall 1998
• K. Weihrauch: Computability. Springer Verlag 1987.

Learning

2 SWS Vorlesung; 2 SWS Übung; 2 SWS Tutorium/Hörsaalübung (optionales Angebot)

Examination

• Die Leistungsbewertung erfolgt durch eine abschließende Klausur. Es gibt keine Zulassungsbeschränkung.

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

Dates

Vorlesungen ab 12. April 2013 (an Freitagen Beginn jew. 8.30 Uhr (!))

Übungsgruppen ab der Folgewoche

Infos zum Tutorium in der ersten Vorlesungswoche

Zurück