Zur Startseite der Abteilung Theoretische Informatik

Theoretische Grundlagen der Informatik: Formale Sprachen und Automatentheorie (WiSe 2016/17)

Prüfung im Sommersemester 2017

Die schriftliche Prüfung im Sommersemester 2017 findet am 05.09.2017 um 08:00 Uhr statt.

Bitte beachten Sie die folgenden Änderungen bei der Raumaufteilung:

  • Teilnehmer der Prüfung Theoretische Grundlagen der Informatik, deren erster Buchstabe des Nachnamens im Bereich A-L liegt, schreiben in Raum V47.01.
  • Teilnehmer der Prüfung Theoretische Grundlagen der Informatik, deren erster Buchstabe des Nachnamens im Bereich M-S liegt, schreiben in Raum V47.02.
  • Teilnehmer der Prüfung Theoretische Grundlagen der Informatik, deren erster Buchstabe des Nachnamens im Bereich T-Z liegt, schreiben in Raum V47.03.
  • Teilnehmer der Prüfungen Formale Sprachen und Automaten sowie Logik und diskrete Strukturen schreiben in Raum V57.03.

MINT-Kolleg

Im Sommersemester 2017 bietet das MINT-Kolleg die Möglichkeit an den FSuA-Stoff zu wiederholen und den Übungsschein nachzumachen. Mehr Informationen finden sich auf den Seiten des MINT-Kollegs.

Termine

Zeit Raum Termine
Do 15:45-17:00 V47.02 wöchentlich  ab 20.10.
Mi 14:15-15:30 V47.02 wöchentlich  ab 26.10.

Insgesamt ca. 23 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.

Insgesamt gibt es 45 Einheiten (ohne Einheit 0) - durchnummeriert von 1 bis 45.

Einheit Datum Inhalt alte Folien neue Folien
0 20.10. Vorstellung, Arbeitsweise  -  pdf
1 20.10. Sprachen und Grammatiken  -  pdf
2 26.10. Was ist die Chomsky-Hierarchie?  -  pdf
3 26.10. Chomsky-Hierarchie auf Sprachebene  -  pdf
4 27.10. Einschub: Wie führt man Beweise? (Teil 1)    pdf
5 27.10. Einschub: Wie führt man Beweise? (Teil 2)    pdf
6 02.11. Das Wort-Problem -  pdf
7 02.11. Syntaxbäume -  pdf
8 03.11. Mehrdeutigkeit, BNF, Zusammenfassung -  pdf
9 03.11. Endliche Automaten -  pdf
10 09.11. DFAs beschreiben Typ-3 Sprachen -  pdf
11 09.11. Nichtdeterministische Automaten -  pdf
12 10.11. Der Satz von Rabin und Scott -  pdf
13 10.11. Typ-3 Sprachen werden durch NFAs erkannt -  pdf
14 17.11. Reguläre Ausdrücke, Satz von Kleene -  pdf
15 17.11. Pumping Lemma und sein Beweis -  pdf
16 24.11. Pumping Lemma: Drei Anwendungen -  pdf
17 24.11. Der Satz von Myhill und Nerode -  pdf
18 30.11. Minimalautomaten -  pdf
19 30.11. Erkennung durch Monoide (Einschub) -  pdf
20 01.12. Abschlusseigenschaften, Entscheidbarkeitsresultate -  pdf
21 01.12. Kontextfreie Sprachen, Normalformen -  pdf
22 07.12. Chomsky-Normalform: Beweis -  pdf
23 07.12. Chomsky-Normalform: Beispiele -  pdf
24 08.12. Greibach-Normalform: Beweis und Beispiel -  pdf
25 08.12. Pumping Lemma für Typ-2, mit Beweis -  pdf
26 14.12. Beispiele, Anwendungen des Pumping Lemmas -  pdf
27 14.12. Typ-2 und einelementiges Alphabet -  pdf
28 15.12. Abschlusseigenschaften -  pdf
29 15.12. Zusammenfassung -  pdf
  21.12. Scheinklausur  (BEGINN: 14:00 Uhr pünktlich!!)    
30 22.12. Der CYK-Algorithmus, Entwurf -  pdf
31 22.12. CYK: Programm und Beispiele -  pdf
32 11.01. Kellerautomaten: Skizze, formale Definition -  pdf
33 11.01. Konfigurationen und akzeptierte Sprache -  pdf
34 12.01. Von der Typ-2 Grammatik zum PDA -  pdf
35 12.01. Vom PDA zur Grammatik -  pdf
36 18.01. DPDA und DCFL -  pdf
37 18.01. Abschlusseig. von DCFL, Entscheidbark. bei CFL, DCFL -  pdf
38 19.01. Typ-1: Kuroda-Normalform, Turingmaschinen -  pdf
39 19.01. Turingmaschine mit Beschränkung: LBA -  pdf
40 26.01. Kuroda: Satz und Beweis -  pdf
41 26.01. Beweis, 2. Richtung -  pdf
42 02.02. Typ-0 und Typ-1, Satz von Immerman und Scelepcsenyi -  pdf
43 02.02. Beweis des Satzes -  pdf
  08.02. Scheinklausur    
44 09.02. Tabellen -  pdf
45 09.02. Entscheidbarkeiten -  pdf

Übungen

Tobias Walter

Die Anmeldung zu den Übungen erfolgt über https://uebungsgruppen.informatik.uni-stuttgart.de. Benutzername und Passwort werden in der ersten Vorlesung bekannt gegeben.

Weitere Informationen zum Übungsbetrieb finden sich auf den Hinweisen zur Übung.

Übungsgruppen

Gr. Tutor Zeit Raum Besprechung
Blatt 1 Blatt 2 Blatt 3 Blatt 4 Blatt 5 Blatt 6
1 Bühler Mo. 8:00-9:30 0.108 31.10. 14.11. 28.11. 12.12. 09.01. 23.01.
2 Mendel Mo. 9:45-11:15 0.124 31.10. 14.11. 28.11. 12.12. 09.01. 23.01.
3 Bühler Mi. 8:00-9:30 0.108 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
4 Klein Mi. 9:45-11:15 0.118 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
5 Welker Mi. 17:30-19:00 0.124 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
6 Hasler Mi. 17:30-19:00 0.363 02.11. 16.11. 30.11. 14.12. 11.01. 25.01.
7 Dönicke Do. 08:00-09:30 0.108 03.11. 17.11. 01.12. 15.12. 12.01. 26.01.
8 Gaißert Do. 08:00-09:30 0.124 03.11. 17.11. 01.12. 15.12. 12.01. 26.01.
9 Tschechlov Do. 9:45-11:15 0.124 03.11. 17.11. 01.12. 15.12. 12.01. 26.01.
10 Walter Do. 11:30-13:00 0.457 03.11. 17.11. 01.12. 15.12. 12.01. 26.01.
11 Tschechlov Do. 14:00-15:30 0.363 03.11. 17.11. 01.12. 15.12. 12.01. 26.01.
12 Gaißert Fr. 8:00-9:30 0.124 04.11. 18.11. 02.12. 16.12. 13.01. 27.01.
13 Mendel Fr. 9:45-11:15 0.108 04.11. 18.11. 02.12. 16.12. 13.01. 27.01.
14 Bühler Mo. 8:00-9:30 0.108 07.11. 21.11. 05.12. 19.12. 16.01. 30.01.
15 Mendel Mo. 9:45-11:15 0.124 07.11. 21.11. 05.12. 19.12. 16.01. 30.01.
16 Bühler Mi. 8:00-9:30 0.108 09.11. 23.11. 07.12. 21.12. 18.01. 01.02.
17 Klein Mi. 9:45-11:15 0.118 09.11. 23.11. 07.12. 21.12. 18.01. 01.02.
18 Hasler Mi. 17:30-19:00 0.363 09.11. 23.11. 07.12. 21.12. 18.01. 01.02.
19 Dönicke Do. 08:00-09:30 0.108 10.11. 24.11. 08.12. 22.12. 19.01. 02.02.
20 Gaißert Do. 08:00-09:30 0.124 10.11. 24.11. 08.12. 22.12. 19.01. 02.02.
21 Tschechlov Do. 9:45-11:15 0.124 10.11. 24.11. 08.12. 22.12. 19.01. 26.01.
22 Tschechlov Do. 14:00-15:30 0.363 10.11. 24.11. 08.12. 22.12. 19.01. 26.01.
23 Gaißert Fr. 8:00-9:30 0.124 11.11. 25.11. 09.12. 16.12. 20.01. 03.02.

Übungsblätter

Beachten Sie auch die Hinweise zu den Übungen.

Scheinkriterien

Wer alle der folgenden Bedingungen erfüllt, erhält einen Übungsschein:

  • 50% der maximal erreichbaren Punkte aus jeder Kategorie der schriftlichen Abgaben
  • mindestens zweimal Vorrechnen
  • Bestehen der Scheinklausur (d.h. die Summe der Punktzahlen aus beiden Scheinklausuren ist mindestens 50% der erreichbaren Punkte.)

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.