Vorlesung
Termine
Zeit | Raum | Termine |
---|---|---|
Di 11:30-13:00 | V47.02 | wöchentlich ab 9.04. bis 02.07. außer am 28.05. |
Do 14:00-15:30 | V47.02 | wöchentlich ab 11.04. bis 27.06. außer am 02.05. |
Bitte beachten:
Am Dienstag, dem 2. Juli findet die letzte Vorlesung statt.
Folien:
Vorl. | Datum | Folien | Inhalt |
---|---|---|---|
1 | 09.04. | (pdf) | Semesterplanung, Grammatiken: Definitionen und Beispiele |
2 | 11.04. | (pdf) | Chomsky-Hierarchie, Wortproblem |
3 | 16.04. | (pdf) | Syntaxbäume, Backus-Naur-Form |
4 | 18.04. | (pdf) | Reguläre Sprachen: Endliche Automaten, Nichtdeterministische Automaten (Teil 1) |
5 | 23.04. | (pdf) | Nichtdeterministische Automaten (Teil 2) |
6 | 25.04. | (pdf) | Reguläre Ausdrücke, das Pumping-Lemma |
7 | 30.04. | (pdf) | Äquivalenzrelationen und Minimalautomaten |
02.05. | (Keine Vorlesung) | ||
8 | 07.05. | (pdf) | Erkennung durch Monoide, Abschlusseigenschaften, Entscheidbarkeit |
09.05. | (Feiertag - keine Vorlesung) | ||
9 | 14.05. | (pdf) | Kontextfreie Sprachen: Normalformen (Teil 1) |
10 | 16.05. | (pdf) | Normalformen (Teil 2) |
28.05. | (Keine Vorlesung) | ||
30.05. | (Feiertag - keine Vorlesung) | ||
11 | 04.06. | (pdf) | Das Pumping-Lemma (bzw. uvwxy-Theorem) für kontextfreie Sprachen |
12 | 06.06. | (pdf) | Abschlusseigenschaften, der CYK-Algorithmus |
13 | 11.06. | (pdf) | Kellerautomaten (Teil 1) |
14 | 13.06. | (pdf) | Kellerautomaten (Teil 2) |
15 | 18.06. | (pdf) | Determin. kontextfreie Sprachen, Entscheidbarkeit bei kontextfr. Sprachen |
16 | 20.06. | (pdf) | Kontextsensitive und Typ-0 Sprachen, Turingmaschinen, LBA |
17 | 25.06. | (pdf) | Satz von Kuroda |
18 | 27.06. | (pdf) | Typ 0 und Turingmaschinen, Satz von Immerman und Szelepcsenyi |
19 | 02.07. | (pdf) | Tabellen und Zusammenfassung |
Ergänzungen
Übungen
Übungsgruppen
Gruppe | Tutor | Zeit | Beginn | Raum | Besprechung | |||||
---|---|---|---|---|---|---|---|---|---|---|
Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 | |||||
1 | M. Schneider | Di 17:30-19:00 | 23.04. | 0.363 | 23.04. | 07.05. | 28.05. | 11.06. | 25.06. | 09.07. |
2 | T. Walter | Mo 14:00-15:30 | 22.04. | 0.453 | 22.04. | 06.05. | 27.05. | 10.06. | 24.06. | 08.07. |
3 | V. Kalach | Di 9:45-11:15 | 23.04. | 0.124 | 23.04. | 07.05. | 28.05. | 11.06. | 25.06. | 09.07. |
4 | P. Wagner | Di 9:45-11:15 | 23.04. | 0.463 | 23.04. | 07.05. | 28.05. | 11.06. | 25.06. | 09.07. |
5 | M. Reingruber | Di 15:45-17:15 | 23.04. | 0.108 | 23.04. | 07.05. | 28.05. | 11.06. | 25.06. | 09.07. |
6 | C. Weisser | Di 15:45-17:15 |
23.04. | 0.124 | 23.04. | 07.05. | 28.05. | 11.06. | 25.06. | 09.07. |
7 | A. Bühler | Mi 15:45-17:15 | 24.04. | 0.124 | 24.04. | 08.05. | 29.05. | 12.06. | 26.06. | 10.07. |
8 | M. Schneider | Di 17:30-19:00 | 30.04. | 0.363 | 30.04. | 14.05. | 04.06. | 18.06. | 02.07. | 16.07. |
9 | M. Reingruber | Mo 14:00-15:30 | 29.04. | 0.453 | 29.04. | 13.05. | 03.06. | 17.06. | 01.07. | 15.07. |
10 | V. Kalach | Di 9:45-11:15 | 30.04. | 0.124 | 30.04. | 14.05. | 04.06. | 18.06. | 02.07. | 16.07. |
11 | P. Wagner | Di 9:45-11:15 | 30.04. | 0.463 | 30.04. | 14.05. | 04.06. | 18.06. | 02.07. | 16.07. |
12 | M. Reingruber | Di 15:45-17:15 | 30.04. | 0.108 | 30.04. | 14.05. | 04.06. | 18.06. | 02.07. | 16.07. |
13 | C. Weisser | Di 15:45-17:15 | 30.04. | 0.124 | 30.04. | 14.05. | 04.06. | 18.06. | 02.07. | 16.07. |
14 | A. Bühler | Mi 15:45-17:15 | 30.04.∗ | 0.124 | 30.04.∗ | 15.05. | 05.06. | 19.06. | 03.07. | 17.07. |
∗Dieser Termin findet wegen des Feiertags am Dienstag, den 30.04. um 8:00 statt.
Übungsblätter
- Blatt 1
- Blatt 2 Hinweis zur Notation in Aufgabe 2: w^R ist das gespiegelte Wort zu w
- Blatt 3
- Blatt 4
- Blatt 5
- Blatt 6
Scheinkriterien
- Sie müssen jeweils zwei der Aufgaben schriftlich abgeben. Wollen Sie mehr als zwei Aufgaben kontrolliert haben, so kennzeichnen Sie eindeutig die zwei Aufgaben, die bewertet werden sollen.
- Einen Schein erhält, wer mit den gewählten Hausübungen mindestens 50% der maximal zu erreichenden Punkte erhält und aktive Teilnahme in den Übungsgruppen zeigt. Die aktive Teilnahme beinhaltet das Votieren von mindestens einer zusätzlichen Aufgabe pro Übungsblatt (Ausnahmen bei Krankheit etc. sind mit Ihrem Tutor abzusprechen).
Hinweis: Um an der Modulprüfung “Theoretische Grundlagen der Informatik” teilzunehmen benötigen Sie einen Übungsschein in “Logik und Diskrete Strukturen” oder in “Formale Sprachen und Automatentheorie”.
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.