Vorlesung

Prof. Dr. Ulrich Hertrampf

Termine

Zeit Raum Termine
Do 15:45-17:15 V47.02 wöchentlich vom 18.10. bis 24.1.
Mi 14:00-15:30 V47.02 wöchentlich vom 24.10. bis 6.2. (außer 14.11., 21.11., 19.12., 23.1., 30.1)

Insgesamt 21 Termine - genaue Liste in der folgenden Tabelle.

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

Die zugreifbaren Folien werden entsprechend in der Vorlesung erarbeitet, und zwar in jeder Vorlesung zwei Einheiten - daher gibt es die Einheiten mit den Nummern 0 bis 41.

Einheit Datum Inhalt Folien
018.10.Vorstellung, Arbeitsweise --
118.10. Sprachen und Grammatiken pdf
224.10. Chomsky-Hierarchie pdf
324.10. Einschub: Wie führt man Beweise? (Teil 1) pdf
425.10. Einschub: Wie führt man Beweise? (Teil 2) pdf
525.10. Das Wort-Problem pdf
631.10. Syntaxbäume, Linksableitungen pdf
731.10. Mehrdeutige Grammatiken, (E)BNF, Zusammenfassung pdf
807.11. Endliche Automaten und Typ-3 Sprachen pdf
907.11. Nichtdeterministische Automaten pdf
1008.11.Satz von Rabin und Scott, Beispiele pdf
1108.11. Exponentieller Blow-Up, DEA=NEA=Typ-3 pdf
1215.11. Reguläre Ausdrücke, Satz von Kleene pdf
1315.11. Pumping Lemma (mit Beweis) pdf
1422.11. Pumping Lemma: Drei Anwendungen, Myhill/Nerode-Äquivalenz pdf
1522.11. Der Satz von Myhill und Nerode, Minimalität des Automaten pdf
1628.11. Minimalautomaten, Erkennung durch Monoide (Einschub) pdf
1728.11. Erkennung durch Monoide (Einschub, Teil 2), Abschlusseigenschaften pdf
1829.11. Entscheidbarkeitsresultate, kontextfreie Sprachen pdf
1929.11. Kontextfreie Sprachen: Normalformen pdf
2005.12. Chomsky-Normalform: Beispiele pdf
2105.12. Greibach-Normalform: Beweis und Beispiele pdf
2206.12. Pumping Lemma für Typ-2 pdf
2306.12. Beispiele und Anwendungen, Einelementiges Alphabet pdf
2412.12. Abschlusseigenschaften pdf
2512.12. Zusammenfassung pdf
2613.12. Wortproblem für Typ-2: CYK-Algorithmus pdf
2713.12. CYK: Beispiele, Vorschau: Kellerautomat pdf
2820.12. Kellerautomaten (PDA): Definition und Funktion pdf
2920.12. Kellerautomaten: Beispiele pdf
3009.01. Von der Typ-2 Grammatik zum PDA pdf
3109.01. Vom PDA zur Typ-2 Grammatik pdf
3210.01. DPDA und DCFL pdf
3310.01. Abschlusseigenschaften von DCFL pdf
3416.01. Typ-1 Sprachen, Kuroda-Normalform pdf
3516.01. Der LBA als Maschinenmodell für Typ-1 pdf
3617.01. Satz von Kuroda, Beweis des Satzes pdf
3717.01. Fortsetzung des Beweises (Satz von Kuroda) pdf
3824.01. Determinismus/Nichtdetermismus, Satz von Immerman und Szelepcsenyi pdf
3924.01. Beweis des Satzes von Immerman und Szelepcsenyi pdf
4006.02. Tabellen pdf
4106.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 Kurztests
  • Bestehen der Scheinklausur

Ergänzungen

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

Webseite der Ergänzungen

Übungen

Daniel Bahrdt

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 19.10.18 16:00 bis Sonntag 21.10. 23:59 . Aus technischen Gründen ist eine Anmeldung leider nicht um 13:15 Uhr möglich. Wir haben die Anmeldung daher auf eine Uhrzeit gelegt zu der keine Veranstaltung statt finden sollte, sodass sie genug Zeit haben sich in eine passende Übungsgruppe einzutragen.
Falls Sie keine Möglichkeit haben sich in eine Übungsgruppe über das Campus System einzutragen schreiben sie Daniel Bahrdt eine E-Mail mit dem Betreff: “Theorie-I: Manuelle Übungsgruppenanmeldung”. Ihre E-Mail sollte enthalten:

  • Vorname+Nachname
  • präferierte Übungsgruppe
  • alternative Übungsgruppen
  • Matrikelnummer sofern vorhanden

Die aktuelle Auslastung der Übungsgruppen können Sie im Campus System einsehen (das sollte auch ohne Zugangsdaten funktionieren).

Übungsblätter

Die Abgabe der schriftlichen Aufgaben muss bis 14:00 Uhr des festgelegten Abgabetages in papierform erfolgen. Ihre Abgaben werfen Sie in den Abgabenschrank der sich in der Mitte des 1. Obergeschosses befindet. Abgabeblätter müssen geheftet sein und klar die Bearbeiter (Name und Matrikelnummer), die Übungsgruppe (Nummer und Tutorname) und Aufgabennummern nennen. Bitte geben Sie nach Möglichkeit Aufgabenblätter immer als Gruppe ab. Der Vorteil einer Lerngruppe ist nicht zu unterschätzen! Die schriftlichen Aufgaben werden von Ihrem Tutor korrigiert und in Ihrer Übungsgruppe besprochen. Eine Bewertung der schriftlichen Aufgaben findet nicht statt. Beachten Sie, dass die Besprechung der Aufgabenblätter zeitlich versetzt statt findet. So wird in der ersten Übungsstunde der Übungsgruppen der Besprechungsgruppe A lediglich Blatt 1 besprochen. In der ersten Übungsstunde der Übungsgruppen der Besprechungsgruppe B hingegen Blatt 1 und Blatt 2. Aufgabenblatt 0 dient der Übersicht über die mathematischen Grundlagen. Eine Abgabe ist weder nötig noch möglich. Die Inhalte werden zum Teil in den Übungsgruppen besprochen. Nutzen Sie diese um ihren Tutor kennenzulernen und eine Lerngruppe zu bilden.

24.10: Änderungen an Blatt 0: Definition von Kleene-Star, Aufgabe 2b.(iv)
24.10: Änderungen an Blatt 1: Definition der Konkatenation von Sprachen, Aufgabe 2
26.10: Änderungen an Blatt 0: Definition der großen Vereinigung, Beispiel auf erster Seite; Aufgabe 2b.(iv)
29.10: Änderungen an Blatt 1: Die letzte Aufgabe ist jetzt eine Bonusaufgabe und wird nicht besprochen; Für einfache Aufgaben werden Lösungshinweise veröffentlicht. Diese Aufgaben werden nicht in der Übung besprochen
04.11: Blatt 2: Abgabebedingungen geändert
13.11: Blatt 3: Aufgabe 5(a): Fehlerzustand hinzugefügt

  Blatt 0 Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6 Blatt 7 Blatt 8 Blatt 9 Blatt 10 Blatt 11
Ausgabe 18.10 22.10 29.10 05.11 12.11 19.11 26.11 03.12 10.12 17.12 07.01 14.01
Abgabe bis 14:00 Uhr - 31.10 07.11 14.11 21.11 28.11 05.12 12.12 19.12 19.01 16.01 23.01
Besprechung A ab 22.10 05.11 19.11 19.11 03.12 03.12 17.12 17.12 14.01 14.01 28.01 28.01
Besprechung B ab 29.10 12.11 12.11 26.11 26.11 10.12 10.12 07.01 07.01 21.01 21.01 04.02
Lösungshinweise   keine hier keine keine keine keine keine keine keine keine keine

Besprechung der Übungsblätter und Kurztests

Im folgenden beziehen sich die Kurztestinhalte auf die obigen Foliensätze. Ein beispielhafter Kurztest findet sich hier. Die Kurztestinhalte beziehen sich im Regelfall auf die Inhalte der letzten 2 Wochen. Dies beinhaltet auch die Inhalte der vorangegangenen Übung!
Falls Sie aus gesundheitlichen oder anderen wichtigen Gründen verhindert sind melden Sie sich bitte beim Übungsleiter

  KW43 KW44 KW45 KW46 KW47 KW48 KW49 KW50 KW51 KW02 KW03 KW04 KW05 KW06
  22.10 29.10 05.11 12.11 19.11 26.11 03.12 10.12 17.12 07.01 14.01 21.01 28.01 04.02
Besprechungsgruppe A B A B A B A B A B A B A B
Aufgabenblätter 0 0 1 1,2 2,3 3,4 4,5 5,6 6,7 7,8 8,9 9,10 10,11 11
Kurztestinhalte bis Folie - - 7 11 13 17 19 23 27 29 33 37 39 39

Übungsgruppen

Die genauen Besprechungstermine finden sich im Campus System.

Auf Grund des Feiertags am 1.11 müssen die Gruppen 10B und 12B verlegt werden.
Die Übungsgruppe 10B beginnt am 29.10 um 9:45 Uhr in Raum 0.453.
Die Übungsgruppe 12B beginnt am 31.10 um 8:00 Uhr in Raum 0.118.

Gruppe Besprechungsgruppe Slot Raum Tutor Beginn
1 A Mo. 11:30-13:00 0.363 Spaney 22.10
2 B Mo. 11:30-13:00 0.363 Spaney 29.10
3 A Mi. 09:45-11:15 0.124 Gigliotti 24.10
4 B Mi. 09:45-11:15 0.124 Gigliotti 31.10
5 A Mi. 09:45-11:15 0.363 Kotowsky 24.10
6 B Mi. 09:45-11:15 0.363 Kotowsky 31.10
7 A Mi. 11:30-13:00 0.124 Bienias 24.10
8 B Mi. 11:30-13:00 0.124 Weitbrecht 31.10
9 A Do. 11:30-13:00 0.363 Lenk 25.10
10 B Do. 11:30-13:00 0.363 Lenk 29.10
11 A Do. 14:00-15:30 0.453 Kühn 25.10
12 B Do. 14:00-15:30 0.453 Kühn 31.10
13 A Fr. 08:00-09:30 0.124 Bienias 26.10
14 B Fr. 08:00-09:30 0.124 Bienias 02.11
15 A Fr. 09:45-11:15 0.108 Bredl 26.10
16 B Fr. 09:45-11:15 0.108 Bredl 02.11
17 A Fr. 09:45-11:15 0.124 Kässmann 26.10
18 B Fr. 09:45-11:15 0.124 Kässmann 02.11
19 A Fr. 09:45-11:15 0.363 Camino 26.10
20 B Fr. 09:45-11:15 0.363 Camino 02.11
21 A Fr. 15:45-17:15 0.108 Klein 26.10
22 B Fr. 15:45-17:15 0.108 Klein 02.11
23 A Fr. 15:45-17:15 0.447 Mayer 26.10
24 B Fr. 15:45-17:15 0.447 Mayer 02.11
25 A Fr. 15:45-17:15 0.457 Welker 26.10
26 B Fr. 15:45-17:15 0.457 Welker 02.11

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

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[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.