Vorlesung

Prof. Dr. Ulrich Hertrampf

Termine

Zeit Raum Termine
Do 15:45-17:15 V47.02 wöchentlich vom 19.10. bis 1.2.
Mi 14:00-15:30 V47.02 wöchentlich vom 25.10. bis 17.1., außer am 15.11., 22.11., 20.12.

Insgesamt ca. 21 Termine - genaue Liste folgt.

Folien und voraussichtliche Termine:
Die Einheiten der nächsten Vorlesung sind stets grün unterlegt.

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet.

Einheit Datum Inhalt Folien
019.10. Vorstellung, Arbeitsweise --
125.10. Sprachen und Grammatiken pdf
225.10. Chomsky-Hierarchie pdf
326.10. Einschub: Wie führt man Beweise? (Teil 1) pdf
4 26.10. Einschub: Wie führt man Beweise? (Teil 2) pdf
5 02.11. Das Wort-Problem, Syntaxbaum pdf
6 02.11. Beispiele für Syntaxbäume, Mehrdeutigkeit, (E)BNF pdf
7 08.11. Zusammenfassung, Endliche Automaten pdf
8 08.11. Automaten und Typ-3 Sprachen pdf
9 09.11. NEA, Satz von Rabin und Scott pdf
10 09.11. Beispiele, exponentieller Blow-Up, DEA=NEA=Typ-3 pdf
11 16.11. Reguläre Ausdrücke, Satz von Kleene pdf
12 16.11. Pumping Lemma (mit Beweis) pdf
13 23.11. Pumping Lemma: Drei Anwendungen pdf
14 23.11. Der Satz von Myhill und Nerode pdf
15 29.11.Minimalautomaten pdf
16 29.11.Erkennung durch Monoide (Einschub) pdf
17 30.11.Abschlusseigenschaften und Entscheidbarkeitsresultate pdf
18 30.11.Kontextfreie Sprachen, Normalformen pdf
19 06.12.Chomsky-Normalform: Beweis pdf
20 06.12.Chomsky-Normalform: Beispiele pdf
21 07.12.Greibach-Normalform: Beweis und Beispiele pdf
22 07.12.Pumping Lemma für Typ-2 pdf
23 13.12.Beispiele und Anwendungen pdf
24 13.12.Einelementiges Alphabet pdf
25 14.12.Abschlusseigenschaften, Zusammenfassung pdf
26 14.12.Wortproblem für Typ-2: CYK-Algorithmus pdf
27 21.12.CYK: Beispiele, Einführung: Kellerautomaten pdf
28 21.12.Definition und Funktion des PDA pdf
29 10.01.Von der Typ-2 Grammatik zum PDA pdf
30 10.01.Vom PDA zur Typ-2 Grammatik pdf
31 11.01.DPDA und DCFL pdf
32 11.01.Abschlusseigenschaften von DCFL pdf
33 17.01.Typ-1 Sprachen, Kuroda-Normalform pdf
34 17.01.Der LBA als Maschinenmodell für Typ-1 pdf
35 18.01.Satz von Kuroda pdf
36 18.01.Beweis des Satzes von Kuroda pdf
37 25.01.Satz von Immerman und Szelepcsenyi pdf
38 25.01.Beweis des Satzes pdf
39 01.02.Tabellen pdf
40 01.02.Entscheidbarkeiten pdf

Scheinkriterien

Zur Teilnahme an der Modulprüfung Theoretische Informatik I benötigen Sie einen Übungsschein.
Wer alle der folgenden Bedingungen erfüllt, erhält einen Übungsschein:

  • 50% der maximal erreichbaren Punkte der schriftlich abzugebenden Übungsaufgaben
  • 50% der maximal erreichbaren Punkte der Votieraufgaben
  • mindestens zweimal Vorrechnen im Besprechumgstermin
  • Bestehen der Scheinklausur

Die Scheinliste für das WS1718 kann ab dem 9. Februar am FMI Aushangbrett eingesehen werden.

Scheinklausur

Die Scheinklausur findet am Mittwoch, den 7.02., ab 14:00 statt. Eine Anmeldung zur Scheinklausur (im Rahmen der schriftlichen Abgabe zu Blatt5) ist Voraussetzung zur Teilnahme. Im Zweifel sollten Sie sich Anmelden.
Klausurräume: Namen A-M in V47.02 und Namen N-Z in V38.04
Erlaubte Hilfsmittel: KEINE
Zur Teilnamhe werden der Studentenausweis (Lichtbild, Name und Matrikelnummer), Kugelschreiber und Tipp-Ex oder Bleistift und Radiergummi benötigt.

Ergänzungen

Carlos Camino bietet wöchentlich Ergänzungen an. Teilnahme ist freiwillig, aber sehr zu empfehlen.

Webseite der Ergänzungen

Übungen

Martin Seybold

Die Anmeldung zu den Übungen erfolgt über das Campus System.
Diese sind dort als LV 020800105 Theoretische Informatik I (Formale Sprachen und Automatentheorie) hinterlegt.
Der Anmeldezeitraum ist Freitag 27.10. 08:00 bis Montag 30.10. 23:59 .

Die Abgabe der schriftlichen Aufgaben muss bis zum festen Abgabetermin in papierform erfolgen. Abgabeblätter müssen geheftet sein und klar die (bis zu drei) Bearbeiter (Name und Matrikelnummer), die Übungsgruppe (Nummer und Tutorname) und Aufgabennummern nennen. Abgaben, die nicht frist- oder formgerecht erfolgen, werden nicht berücksichtigt. Zum Fristende finden Sie Kästen zum Einwurf ihrer Abgabe auf einem Tisch, Mitte 1.OG des Informatikgebäudes (V38). Lösungen müssen als vollständige Sätze oder Argumentationsketten ausformuliert sein. Bewertet wird der Schrieb Ihres Lösungswegs und nicht nur ein Endergebnis. Plagiate führen zur Bewertung von 0 Punkten aller schriftlichen Aufgaben des Blattes.

Durch votieren von Aufgaben zum Beginn des Besprechungstermins (gegenüber Ihrem Tutor) erklären Sie sich bereit, die jeweilige Aufgabe an der Tafel zu lösen.
Unvermögen, votierte Aufgaben im Besprechungstermin vorzurechnen, führt zur Bewertung von 0 Punkten aller Votieraufgaben des Blattes.
Insbesondere müssen Sie zum Votieren im Besprechungstermin ihrer Übungsgruppe anwesend sein.

Übungsblätter

Beachten Sie auch den Ablauf einer selbstständigen Arbeitsweise.

  Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5
Ausgabe KW44 KW46 KW48 KW50 KW2
Abgabe bis 13:00 Uhr 9.11. 23.11. 7.12. 21.12. Fr. 19.01.
Besprechung KW46/47 KW48/49 KW50/51 KW2/3 KW4/5

HINWEIS: Raumreservierungen im Campus System bedeuten nicht, dass zu diesen Zeiten Besprechungen stattfinden. Die Besprechungstermine sind:

Gruppe Slot Raum Tutor Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5
2 Mo. 09:45-11:15 0.124 Klein 13.11. 27.11. 11.12. 08.01. 22.01.
15 Mo. 09:45-11:15 0.124 Klein 20.11. 04.12. 18.12. 15.01. 29.01.
3 Di. 11:30-13:00 0.124 Ponomarenko 14.11. 28.11. 12.12. 09.01. 23.01.
16 Di. 11:30-13:00 0.124 Ponomarenko 21.11. 05.12 19.12. 16.01. 30.01.
4 Di. 14:00-15:30 0.124 Seybold 14.11. 28.11. 12.12. 09.01. 23.01.
17 Di. 14:00-15:30 0.124 Rupp 21.11. 05.12 19.12. 16.01. 30.01.
1 Di. 15:45-17:15 0.108 Klein 14.11. 28.11. 19.12. 09.01. 23.01.
14 Di. 15:45-17:15 0.108 Klein 21.11. 05.12 19.12. 16.01. 30.01.
5 Mi. 08:00-09:30 0.463 Krüger 15.11. 29.11. 13.12. 10.01. 24.01.
18 Mi. 08:00-09:30 0.463 Krüger 22.11. 06.12. 20.12. 17.01. 31.01.
6 Mi. 09:45-11:15 0.118 Ponomarenko 15.11. 29.11. 13.12. 10.01. 24.01.
19 Mi. 09:45-11:15 0.118 Ponomarenko 22.11. 06.12. 20.12. 17.01. 31.01.
7 Do. 08:00-09:30 0.118 Gaissert 16.11. 30.11. 14.12. 11.01. 25.01.
20 Do. 08:00-09:30 0.118 Gaissert 23.11. 07.12. 21.12. 18.01. 01.02.
8 Do. 08:00-09:30 0.124 Knecht 16.11. 30.11. 14.12. 11.01. 25.01.
21 Do. 08:00-09:30 0.124 Knecht 23.11. 07.12. 21.12. 18.01. 01.02.
9 Do. 11:30-13:00 0.124 Kreittner 16.11. 30.11. 14.12. 11.01. 25.01.
22 Do. 11:30-13:00 0.124 Kreittner 23.11. 07.12. 21.12. 18.01. 01.02.
10 Do. 11:30-13:00 0.457 Brösamle 16.11. 30.11. 14.12. 11.01. 25.01.
23 Do. 11:30-13:00 0.457 Brösamle 23.11. 07.12. 21.12. 18.01. 01.02.
11 Do. 14:00-15:30 0.363 Welker 16.11. 30.11. 14.12. 11.01. 25.01.
24 Do. 14:00-15:30 0.363 Welker 23.11. 07.12. 21.12. 18.01. 01.02.
12 Fr. 08:00-09:30 0.124 Kittelberger 17.11. 01.12. 15.12. 12.01. 26.01.
25 Fr. 08:00-09:30 0.124 Kittelberger 24.11. 08.12. 22.12. 19.01. 02.02.
13 Fr. 09:45-11:15 0.447 Kittelberger 17.11. 01.12. 15.12. 12.01. 26.01.
26 Fr. 09:45-11:15 0.447 Kittelberger 24.11. 08.12. 22.12. 19.01. 02.02.

Literatur

  • Uwe Schöning: Theoretische Informatik – kurzgefasst, 5. Auflage, Spektrum, 2008. (Die ältere Auflage von 2000 tut’s auch!)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, Addison-Wesley, 2002.

News

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.