Einführung in die Theoretische Informatik

Prof. Tobias Nipkow -- Sommersemester 2009

Modul:: IN0011
Zeit und Ort:: Mo. 10:15 - 11:45, MI HS 1
Do. 16:00 - 17:45, PH HS 1 - PH 2501
Beginn:: 20. 04. 2009
Klausurtermine:: Midterm: 12. Juni 2009, 15:00 - 17:00 Uhr
Endterm: 24. Juli 2009, 15:00 - 17:00 Uhr
Wiederholungsklausur: 9. Oktober 2009, 14:30 - 17:30 Uhr
Siehe auch: Zentraler Prüfungskalender
Übungsleitung:: Dr. Werner Meixner, Alexander Krauss
Website zur Übung (mit Aufgabenblättern):: http://www14.in.tum.de/lehre/2009SS/theo/uebung/

Die Ergebnisse der Wiederholungsklausur stehen auf der Übungsseite.
Die Klausureinsicht für die Wiederholungsklausur findet am Freitag, den 30.10. von 10 Uhr bis 11 Uhr im Raum 00.11.038 statt.
Alte Hausübungen können noch bis zum 30.10. bei Herrn Krauss (01.11.061) abgeholt werden. Bis dahin nicht abgeholte Übungen werden entsorgt.

Nikolaus Demmel und Dmitriy Traytel haben bewiesen, dass die modifizierte Ackermann-Funktion die Nachfolgerfunktion berechnet.
Pascal Minnerup hat gezeigt, dass zwei unterscheidbare Zustände eines endlichen Automaten mit n Zuständen immer durch ein Wort der Länge ≤ n² unterschieden werden können. Wer bietet weniger?
Nikolaus Demmel und Thomas Möllenhoff fanden folgenden regulären Ausdruck für den Automat aus der Vorlesung: (1(10)*(0|11)|0(01)*(1|00))*. Dmitriy Traytel benutzte JFLAP um den kürzeren Ausdruck (10|(0|11)(01)*(1|00))* zu erhalten. Vermutung: kürzer geht es nicht.
Dmitriy Traytel hat die Formel für die Übergansfunktion des mod3-Automaten gefunden und bewiesen: (q*2^{|w|} + #w) mod 3

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

Gruppe	Termin	Raum	Tutor
1	Mo. 12:15 - 13:45	MI 00.08.053	Jörg Blank
2	Mo. 14:00 - 15:30	MI 00.08.053	Jörg Blank
3	Di. 08:15 - 09:45	MI 00.08.036	Maximilian Schlund
4	Di. 10:15 - 11:45	MI 00.08.036	Dr. Werner Meixner
5	Di. 10:15 - 11:45	MI 01.09.014	Marin Zec
6	Di. 12:15 - 13:45	MI 00.08.036	Huan Zhao
7	Di. 12:15 - 13:45	MI 01.09.014	Alexander Krauss
8	Di. 16:15 - 17:45	MI 00.08.036	Marin Zec
9	Mi. 08:15 - 09:45	MI 00.08.036	Markus Dangl
10	Mi. 10:15 - 11:45	MI 00.08.036	Huan Zhao
11	Mi. 10:15 - 11:45	MI 00.08.059	Markus Dangl (Raum geändert)
12	Mi. 12:15 - 13:45	MI 00.08.036	André Dau
13	Do. 10:15 - 11:45	MI 00.08.059	Maximilian Schlund (Termin geändert)
14	Mi. 16:15 - 17:45	MI 00.08.036	Matej Svejda
15	Do. 10:15 - 11:45	MI 00.08.036	Lukas Bulwahn
16	Do. 12:15 - 13:45	MI 00.08.036	Andreas Mühling

Alle Termine als iCal-File für den elektronischen Kalender.

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.