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
20 06.12.Chomsky-Normalform: Beispiele
21 07.12.Greibach-Normalform: Beweis und Beispiele
22 07.12.Pumping Lemma für Typ-2
23 13.12.Beispiele und Anwendungen
24 13.12.Einelementiges Alphabet
25 14.12.Abschlusseigenschaften, Zusammenfassung
26 14.12.
27 21.12.
28 21.12.
29 10.01.
30 10.01.
31 11.01.
32 11.01.
33 17.01.
34 17.01.
35 18.01.
36 18.01.
37 25.01.
38 25.01.
39 01.02.
40 01.02.

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 Scheinklausur findet in Kalenderwoche 6 von 2018 statt.

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. 18.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. 12.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

[Jun’17] Lukas’ paper “Green’s Relations in Finite Transformation Semigroups” and Armin’s paper “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ both have received a Best Paper Award at the 12th International Computer Science Symposium in Russia (CSR).