Einführung in die Theoretische Informatik

Prof. Tobias Nipkow -- Sommersemester 2008

Modul:

IN0011

Zeit und Ort:

Mo. 10:15 - 11:45, Fr. 8:00 - 9:30, Raum: MI HS 1

Beginn:

14. 04. 2008

Klausur:

Midterm: 3. Juni, 17:30 - 19:45
Endterm: 18. Juli, 16:30 - 18:45
Wiederholung: 10. Oktober, 15:30 - 19:00, Raum: MW 0001

Übungsleitung:

Dr. Werner Meixner, Alexander Krauss

Website zur Übung:

http://www14.in.tum.de/lehre/2008SS/theo/uebung/

News:

• Die Klausureinsicht für die Wiederholungsklausur findet am Donnerstag, den 23.10. von 14 - 15 Uhr in Raum MI 01.09.014 (Alonzo Church) statt.

• Hinweis zur Wiederholungsklausur: Die Klausur ist für 3 Stunden konzipiert und umfasst 8 Aufgaben. Da wir vermeiden wollen, dass die Zeit der entscheidende Faktor wird, haben wir uns entschlossen, die Klausurdauer um 30 Minuten zu verlängern. Damit ist die Klausurzeit von 15:30 - 19:00 Uhr. Die Klausur findet im Hörsaal MW 0001 statt.

• Die Klausureinsicht fand am Do. 31.7. von 14 - 16 Uhr statt (siehe auch Übungsseite)

• Aus noch ungeklärter Ursache war am 9.6. HS1 zentral belegt worden, ohne mich auch nur zu informieren. Wir bekamen spontan MW1250 zugewiesen, wo wir zu 100 gerade reinpassten, wo aber keine Aufzeichnugsmöglichkeit besteht. Behandelter Stoff: Primitiv rekursive Funktionen bis einschließlich Folie 289.

• Für die Abgabe der Hausübungen gibt es jetzt Briefkästen, die im Untergeschoss der Magistrale angebracht sind. Ab Übung 5 läuft die Abgabe nur noch über die Briefkästen (Leerung: 10h15). In der Vorlesung werden keine Hausübungen mehr angenommen.

• Aus gegebenem Anlass weisen wir darauf hin, dass eine Gruppenabgabe der Hausübungen nicht vorgesehen ist.

  Noch stärker als in anderen Vorlesungen ist in der Theoretischen Informatik das formale Aufschreiben ein primäres Lernziel. Da Sie auch in der Klausur alles allein aufschreiben müssen, ist es uns wichtig, dass Sie darin auch genug Übung haben. Das geht nur, wenn Sie die gemeinsam erarbeiteten Lösungsideen am Ende selbst zu Papier bringen. Die investierte Zeit lohnt sich.

  In Fällen, in denen offensichtlich Lösungen abgeschrieben wurden behalten wir uns vor, die Punkte gleichmäßig auf die uns bekannten Teilnehmer der "Äquivalenzklasse" zu verteilen.

• Die Anmeldung zu den Übungen erfolgt über das Grundstudiumstool (Zertifikat benötigt) und ist ab sofort möglich. Die Übungen beginnen in der 2. Vorlesungswoche.

Knobelaufgaben:

• Till Berger hat bewiesen, welche sehr einfache Funktion die "Ackermann-Funktion" mit Basisfall a(0,n) = n berechnet.

• Henning Femmer hat den regulären Ausdruck gefunden, der die Sprache der CFG A -> aⁱA^j | a^k beschreibt.

• Harald Kümmerle hat gezeigt, dass "F(X) = G(X) u B" einen eindeutigen Fixpunkt hat, falls jedes Wort in G(X) länger ist als das kürzeste Wort in X.

• Ein Beispiel für zwei minimale NFAs, die strukturell verschieden sind, wurde innerhalb von etwa 5 Minuten von ??? (bitte melden!) gefunden. Hinweis: a*a und aa*.

• Bisher kürzeste reguläre Ausdrücke für die Menge der durch 3 teilbaren Binärzahlen: 18 Zeichen (Jan Finis, 21.4.), 14 Zeichen (Martin Warmulla, 22.4.), inkl. Klammern. Vermutung: das ist optimal.

Folien und Aufzeichnungen:

Alle Folien

Die Vorlesung wird mit dem TeleTeachingTool aufgezeichnet. Hier geht es zu den Aufzeichnungen.

Übungsgruppen:

Tutorensprechstunden:

Literatur:

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation
• Dexter Kozen. Automata and Computability
• Katrin Erk, Lutz Priese. Theoretische Informatik. Eine umfassende Einführung.
• Uwe Schöning. Theoretische Informatik kurzgefasst.