Theoretische Informatik II (Sommersemester 2012)

Lecturer: Prof. Dr. Christoph Kreitz

General Information

Weekly Hours: 4
Credits: 6
Graded: yes
Enrolment Deadline: 1.4.2012 - 25.4.2012
Teaching Form: VU
Enrolment Type: Compulsory Module

Programs, Module Groups & Modules

IT-Systems Engineering BA

Description

aktuelle Version der Angaben siehe:

http://www.cs.uni-potsdam.de/profs/ifi/theorie/lehre/ss11/ti-ii

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

1. Turingmaschinen,

2. Algorithmen, Church-Turing-These und Lambda-Kalkül,

3. Entscheidbarkeit: entscheidbare Sprachen, Halteproblem, nicht Turing-akzeptierbare Sprache

4. Reduzierbarkeit: unentscheidbare Probleme, Post'sches Korrespondenzproblem, Abbildungsreduzierbarkeit,

5. Rekusionssatz, Entscheidbarkeit logischer Theorien

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

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).
J. Hopcroft, R. Motwani, J. Ullmann: Einführung in die Autmatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson 2002. Dieses Buch bildet den Leittext für diese Veranstaltung. Manche Themen werden allerdings zu vereinfacht dargestellt. Es gibt eine ältere Version des Buches im Oldenbourg Verlag, in dem die Themen deutlich knapper, aus unserer Sicht aber noch klarer abgehandelt werden.Dafür fehlen einige modernere Ergebnisse.
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

Vorlesung immer freitags von 8.15 - 9.45 Uhr in HS 1

Tutorium donnerstags im Haus 6, 10.15 - 11.45 Uhr

Zurück