Seminar: Automatentheorie
WiSe12/13

Organisatorisches

Dozentin: Wiebke Petersen
Sitzung: Mo. 16.30-18.00; 25.22.HS 5G
Sprechstunde: Di. 16:30-17:30; 23.21.04.45;
Telefon: 81-15295


Kurslektüre

Literaturempfehlung

hilfreiche Software

Klausur, Probeklausur und Pencasts

Sitzungen

Datum Thema Material
08.10.2012 Vorbesprechung
15.10.2012 offiziell vorlesungsfrei: Eröffnung des akademischen Jahres Einführungsfolien
22.10.2012 Deterministische endliche Automaten Socher, Kapitel 2 (bitte lesen Sie dieses Kapitel vor der Sitzung)
29.10.2012 Nichtdeterministische endliche Automaten
  • Socher, Kapitel 2
  • Schöning S.24 und 25
  • bitte lesen Sie für die kommende Sitzung Kapitel 3
  • erarbeiten Sie einen endlichen Automaten für das Ziege-Wolf-Kohlkopf-Problem vom Handout(schicken Sie mir bitte ihren Automaten bis nächsten Montag 12 Uhr, Abgabe freiwillig)
05.11.2012 Reguläre Ausdrücke Socher, Kapitel 3 (bitte lesen Sie dieses Kapitel vor der Sitzung)
12.11.2012 Pumpinglemma für reguläre Sprachen, Satz von Myhill-Nerode Socher, Kapitel 3
19.11.2012 Grammatiken, CYK-Parser Socher, Kapitel 4
26.11.2012 Kellerautomaten Socher, Kapitel 4
03.12.2012 Typ1- und Typ0-Grammatiken, Chomsky-Hierarchie, Überabzählbarkeit Socher, Kapitel 5 (bitte lesen Sie dieses Kapitel vor der Sitzung)
10.12.2012 Turing-Maschinen, LBA, Turing-Berechenbarkeit Socher, Kapitel 5
17.12.2012 universelle Turingmaschine, Churchsche These Socher, Kapitel 5
07.01.2013 Entscheidbarkeit Socher, Kapitel 6
14.01.2013 Entscheidbarkeit, Reduktionsbeweise Socher, Kapitel 6
21.01.2013 Reduktionsbeweise, Satz von Rice Socher, Kapitel 6
28.01.2013 Socher, Kapitel 7 Komplexitätstheorie, NP-Vollständigkeit
05.04.2013 Klausur, 10:30 Uhr.
Ort: 23.21. Hörsaal 3H
Probeklausur für Übungszwecke mit Lösungen (weitere Lösungen werden nachgereicht)

zusätzliche Materialien

Übungsaufgaben

Weitere Materialien (von Gruppen aus vergangenen Semestern erstellt)