Vorlesung
"Informatik III (Theoretische Informatik)"
Wintersemester 2002/03
Prof. Dr. Susanne Albers

Ergebnisse der Nachklausur
Inzwischen liegen die Ergebnisse der Nachklausur vor. Die Grenze zum Bestehen der Klausur wurde auf 18 Punkte gesenkt. Von denen, die in den Übungen schon gut mitgearbeitet haben und mehr als 50 Prozent der Übungspunkte erreicht haben, haben 82 Prozent auch einen Schein erreicht.
Eine Klausureinsicht wird es geben am 28.04.2003 um 10-12 Uhr im Kinohörsaal.
Die Klausurergebnisse sind nicht abrufbar.

Inhalte

Die Vorlesung gibt eine Einführung in die theoretische Informatik. Zunächst erarbeiten wir eine präzise Fassung des Berechenbarkeitsbegriffs. Insbesondere studieren wir das fundamentale Halteproblem, das sich mit der Frage beschäftigt, ob ein Computerprogramm auf einer Eingabe hält. Danach behandeln wir Grundlagen der Komplexitätstheorie, speziell der Theorie der NP-Vollständigkeit. Wir untersuchen die Frage, welche Probleme effizient gelöst werden können und welche Probleme schwer sind. Es folgt eine Untersuchung von endlichen Automaten und Grammatiken. Insbesondere stellen wir eine Verbindung zwischen Grammatikklassen und verschiedenen abstrakten Maschinenmodellen her.

Literatur:

1. Ingo Wegener . Theoretische Informatik -- eine algorithmische  Einführung .
Teubner Verlag, 1999. ISBN 3-519-12123-9.


2. Uwe Schöning. Theoretische Informatik - kurzgefasst
Spektrum Akademischer Verlag 4. Auflage, Dezember  2000 ISBN: 382741099.


3. Michael F. Sipser. Introduction to the Theory of Computation.
WS Publishing, 1997


4. K. Erk, L. Priese. Theoretische Informatik.
Springer Verlag, 1999, 410 S. ISBN 3-540-66192-1


5. M.R. Garey and D.S. Johnson. Computers and intractability.
W.H. Freeman Co. New York, 1979.

Übungen:

Ein Schein kann durch Bestehen der Abschlußklausur am Ende des Semesters erlangt werden. Dabei besteht die Möglichkeit, durch regelmäßige Teilnahme und richtiges Bearbeiten der Übungen die Note der Abschlußklausur aufzubessern. Durch 50% der Übungspunkte kann man seine Abschlußnote um eine Notenstufe (z.B. von 2 auf 2+ oder von 2+ auf 1-) verbessern. Mit 80% der Übungspunkte verbessert man seine Abschlußnote um eine weitere Notenstufe. Nur eine bestandene Klausur kann so allerdings verbessert werden!

Die Aufgaben dürfen alleine oder in Teams von 2 Personen bearbeitet werden. Dafür muß jeder Student in der Lage sein, die von ihm abgegebene Lösung in der Übung zu präsentieren. Weiterhin muß jeder innerhalb des Semesters mindestens zwei mal in den Übungen eine Lösung präsentiert haben, um seine Note verbessern zu können.

Übungsblätter

Hier gibt es die Übungsblätter zum Download.

• Blatt 00 (Präsenzübung, wird in erster Übung zusammen bearbeitet) (PostScript) (PDF)
• Blatt 01 (abzugeben bis 24.Oktober 2002) (PostScript) (PDF)
• Blatt 02 (abzugeben bis 31.Oktober 2002) (PostScript) (PDF)
• Blatt 03 (abzugeben bis 7.November 2002) (PostScript) (PDF)
• Blatt 04 (abzugeben bis 14.November 2002) (PostScript) (PDF)
• Blatt 05 (abzugeben bis 21.November 2002) (PostScript) (PDF)
• Blatt 06 (abzugeben bis 28.November 2002) (PostScript) (PDF)
• Blatt 07 (abzugeben bis 5.Dezember 2002) (PostScript) (PDF)
• Blatt 08 (abzugeben bis 12.Dezember 2002) (PostScript) (PDF)
• Blatt 09 (abzugeben bis 19.Dezember 2002) (PostScript) (PDF)
• Blatt 10 (abzugeben bis 9.Januar 2003) (PostScript) (PDF)
• Blatt 11 (abzugeben bis 16.Januar 2003) (PostScript) (PDF)
• Blatt 12 (abzugeben bis 23.Januar 2003) (PostScript) (PDF)
• Blatt 13 (abzugeben bis 30.Januar 2003) (PostScript) (PDF)
• Blatt 14 (abzugeben bis 6.Februar 2003) (PostScript) (PDF)
• Blatt 15 (abzugeben bis 13.Februar 2003) (PostScript) (PDF)     Hinweis: Blatt 15 wird in keiner Übung mehr besprochen. Dafür stellen wir dann eine Musterlösung ins Netz. Die Punkte gehen natürlich wie sonst auch in die Bewertung ein.
• Musterlösung zu Blatt 15 (PostScript) (PDF)

• Folien zum Satz von Cook (PostScript) (PDF)