Prüfungsergebnisse (SoSe 20)
Die Prüfungsergebnisse zu den unten aufgeführten Prüfungen wurden versandt.
Hinweise und Notenschlüssel
- Theoretische Informatik I (7862100000):
[Prüfung]
[Notenschlüssel & Hinweise] -
Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung (7281100000):
[Prüfung]
[Notenschlüssel & Hinweise] - Theoretische Grundlagen der Informatik (1094100000):
[Prüfung]
[Notenschlüssel & Hinweise] - Automaten und Formale Sprachen (2353100000) und
Automaten und Formale Sprachen (für Mathematiker) (1207100000):
[Prüfung]
[Notenschlüssel & Hinweise]
Prüfungsergebnisse (WiSe 19/20)
Die Prüfungsergebnisse zu den unten aufgeführten Prüfungen wurden versandt.
Hinweise und Notenschlüssel
- Theoretische Informatik I (7862100000):
[Prüfung]
[Notenschlüssel & Hinweise] -
Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung (7281100000):
[Prüfung]
[Notenschlüssel & Hinweise] - Theoretische Grundlagen der Informatik (1094100000):
[Prüfung]
[Notenschlüssel & Hinweise] - Automaten und Formale Sprachen (2353100000) und
Automaten und Formale Sprachen (für Mathematiker) (1207100000):
[Prüfung]
[Notenschlüssel & Hinweise] - Logik und Diskrete Strukturen (4569100000):
[Prüfung]
[Notenschlüssel & Hinweise]
Einsicht
Eine allgemeine Prüfungseinsicht wird nach aktueller Lage in diesem Semester wohl nicht stattfinden können.
Mündliche Fortsetzung
Alle Kandidaten, die nach unseren Daten eine mündliche Fortsetzungsprüfung ablegen müssen, wurden per E-Mail benachrichtigt.
Sollten Sie keine Nachricht bekommen haben, aber nach Ihren eigenen Informationen eine mündliche Fortsetzungsprüfung machen müssen, dann schreiben Sie bitte umgehend eine E-Mail an Prof. Hertrampf.
Prüfung
Für die Prüfungen am Dienstag, den 25. Februar 2020, gilt folgende Raumaufteilung:
Kandidaten für Theoretische Informatik I (7862100000):
| Nachname | Raum |
|---|---|
| A* → L* | V53.01 (Audimax) |
| M* → Z* | V47.01 |
Kandidaten für Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung (7281100000) oder Theoretische Grundlagen der Informatik (1094100000):
Raum V47.02 (unabhängig vom Nachnamen)
Kandidaten für Automaten und Formale Sprachen (2353100000), Automaten und Formale Sprachen (für Mathematiker) (1207100000) oder Logik und Diskrete Strukturen (4569100000):
Raum V47.03 (unabhängig vom Nachnamen)
Die Raumaufteilung sollte mittlerweile mit den Angaben im Campus übereinstimmen. Bei Unstimmigkeiten erscheinen sie bitte im hier angegebenen Raum.
Ankündigung
Mittlerweile hängt die Scheinliste neben Raum 1.101 aus. Bitte prüfen Sie, ob Ihre Matrikelnummer darauf aufgeführt ist, um einen reibungslosen Ablauf bei der Prüfung sicherzustellen. Bitte tun Sie dies auch dann, wenn Sie davon ausgehen, die Scheinbedingungen nicht zu erfüllen. Andernfalls könnten Sie irrtümlicherweise eine Verwaltungsfünf erhalten, wenn Sie davon ausgehen keine Zulassung zu besitzen und zur Prüfung nicht erscheinen.
Vorlesung
Termine
| Zeit | Raum | Termine |
|---|---|---|
| Do 15:45-17:15 | V47.02 | wöchentlich vom 17.10. bis 6.2. (außer 24.10., 7.11., 12.12., 30.1.) |
| Mi 14:00-15:30 | V47.02 | wöchentlich vom 23.10. bis 5.2. (außer 13.11., 20.11., 18.12., 22.1.) |
Insgesamt 21 Termine - genaue Termine sind der Tabelle unten zu entnehmen.
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 - die Einheiten sind mit den Nummern 0 bis 41 durchnummeriert.
Anmerkung: Es gibt in den Folien den einen oder anderen nicht angepassten Verweis. Hierfür bitten wir um Entschuldigung. Sie sollten in der Regel aber in der Lage sein, die Verweise selbst zu korrigieren.
| Einheit | Datum | Inhalt | Folien |
|---|---|---|---|
| 0 | 17.10. | Vorstellung, Arbeitsweise | --- |
| 1 | 17.10. | Sprachen und Grammatiken | |
| 2 | 23.10. | Chomsky-Hierarchie | |
| 3 | 23.10. | Einschub: Wie führt man Beweise? (Teil 1) | |
| 4 | 30.10. | Einschub: Wie führt man Beweise? (Teil 2) | |
| 5 | 30.10. | Das Wort-Problem | |
| 6 | 31.10. | Syntaxbäume, Linksableitungen | |
| 7 | 31.10. | Mehrdeutige Grammatiken, (E)BNF, Zusammenfassung | |
| 8 | 06.11. | Endliche Automaten und Typ-3 Sprachen | |
| 9 | 06.11. | Nichtdeterministische Automaten | |
| 10 | 14.11. | Satz von Rabin und Scott, Beispiele | |
| 11 | 14.11. | Exponentieller Blow-Up, DEA=NEA=Typ-3 | |
| 12 | 21.11. | Reguläre Ausdrücke, Satz von Kleene | |
| 13 | 21.11. | Pumping Lemma (mit Beweis) | |
| 14 | 27.11. | Pumping Lemma: Anwendungen | |
| 15 | 27.11. | Der Satz von Myhill und Nerode | |
| 16 | 28.11. | Minimalautomaten (mit Konstruktion) | |
| 17 | 28.11. | Einschub: Erkennung durch Monoide | |
| 18 | 04.12. | Abschlusseigenschaften, Entscheidbarkeitsresultate | |
| 19 | 04.12. | Kontextfreie Sprachen, Normalformen | |
| 20 | 05.12. | Chomsky-Normalform | |
| 21 | 05.12. | CNF: Beispiele, Greibach-Normalform | |
| 22 | 11.12. | Das Pumping Lemma für Typ-2 | |
| 23 | 11.12. | Pumping Lemma: Beispiele | |
| 24 | 19.12. | Einelementiges Alphabet | |
| 25 | 19.12. | Abschlusseigenschaften | |
| 26 | 08.01. | Zusammenfassung | |
| 27 | 08.01. | Das Wortproblem für Typ-2 | |
| 28 | 09.01. | Der CYK-Algorithmus: Beweis und Beispiele | |
| 29 | 09.01. | Kellerautomaten (PDA): Definition und Funktion | |
| 30 | 15.01. | Kellerautomaten: Beispiele | |
| 31 | 15.01. | Von der Typ-2 Grammatik zum PDA | |
| 32 | 16.01. | Vom PDA zur Typ-2 Grammatik | |
| 33 | 16.01. | DPDA und DCFL | |
| 34 | 23.01. | DCFL, Abschlusseigenschaften und Entscheidbarkeiten | |
| 35 | 23.01. | Typ-1 Sprachen, Kuroda-Normalform | |
| 36 | 29.01. | Turingmaschinen | |
| 37 | 29.01. | LBA, Satz von Kuroda | |
| 38 | 05.02. | Beweis des Satzes von Kuroda | |
| 39 | 05.02. | Der Satz von Immerman und Szelepcsenyi | |
| 40 | 06.02. | Beweis des Satzes, Tabellen | |
| 41 | 06.02. | Abschlusseigenschaften, Entscheidbarkeiten |
Ergänzungen
Carlos Camino bietet wöchentlich Ergänzungen an. Die Teilnahme ist freiwillig, aber sehr zu empfehlen.
Übungen
Übungsblätter
- Blatt 1 Änderung 30.10.: Bei Aufgabe 2 b) muss es “K, L ⊆ Σ*” heißen.
- Blatt 2 Änderung 13.11.: Tippfehler bei Aufgabe 4 korrigiert
- Blatt 3
- Blatt 4
- Blatt 5
- Blatt 6
Scheinkriterien
Zur Teilnahme an der Modulprüfung Theoretische Informatik I benötigen Sie einen Übungsschein. Einen Übungsschein erhält, wer mindestens 50% aller erreichbaren Punkte in den schriftlichen Abgaben erreicht. Mehr Informationen zum Ablauf der Übungen finden Sie am Ende von Blatt 1.
Gruppenwechsel
Wenn Sie möchten, können Sie von einer großen Gruppe (> 15 Teilnehmer) in eine kleine Gruppe wechseln. Schreiben Sie dazu eine E-Mail an den Übungsleiter. Die Anzahl der Teilnehmer einer Übungsgruppe finden Sie unter https://campus.uni-stuttgart.de/cusonline/sa.gruppen_einteilung?corg=182&clvnr=237444.
Übungsgruppen
| Gruppe | Tutor | Zeit | Raum | Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 | ||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 🤽 0x | 00 | P. Kischkat | Mo. | 09:45 – 11:15 | 0.124 | 04.11. | 18.11. | 02.12. | 16.12. | 13.01. | 27.01. |
| 🎱 0x | 01 | P. Strohbeck | Mo. | 11:30 – 13:00 | 0.118 | 04.11. | 18.11. | 02.12. | 16.12. | 13.01. | 27.01. |
| 🚴 0x | 02 | J. Bienias | Mo. | 14:00 – 15:30 | V55.01 | 04.11. | 18.11. | 02.12. | 16.12. | 13.01. | 27.01. |
| 🏓 0x | 03 | N. Schmid | Mo. | 14:00 – 15:30 | 0.118 | 04.11.* | 18.11. | 02.12. | 16.12. | 13.01. | 27.01. |
| 🏋 0x | 04 | D. Lieb | Di. | 08:00 – 09:30 | 0.124 | 05.11. | 19.11. | 03.12. | 17.12. | 14.01. | 28.01. |
| 🧗 0x | 05 | P. Mayer | Di. | 08:00 – 09:30 | 0.463 | 05.11. | 19.11. | 03.12. | 17.12. | 14.01. | 28.01. |
| ⛸ 0x | 06 | F. Mundinger | Di. | 11:30 – 13:00 | 0.457 | 05.11. | 19.11. | 03.12. | 17.12. | 14.01. | 28.01. |
| 🛀 0x | 07 | K. Bauer | Mi. | 09:45 – 11:15 | 0.124 | 06.11. | 20.11. | 04.12. | 18.12. | 15.01. | 29.01. |
| 🧘 0x | 08 | M. Flinspach | Mi. | 09:45 – 11:15 | 0.453 | 06.11. | 20.11. | 04.12. | 18.12. | 15.01. | 29.01. |
| 🎲 0x | 09 | J. Welker | Mi. | 11:30 – 13:00 | 0.118 | 06.11. | 20.11. | 04.12. | 18.12. | 15.01. | 29.01. |
| ⛹ 0x | 0A | S. Egger | Do. | 09:45 – 11:15 | 0.124 | 07.11. | 21.11. | 05.12. | 19.12. | 16.01. | 30.01. |
| 🤹♀️ 0x | 0B | B. Ariguib | Do. | 14:00 – 15:30 | 0.124 | 07.11. | 21.11. | 05.12. | 19.12. | 16.01. | 30.01. |
| 🎨 0x | 0C | M. Kurz | Fr. | 08:00 – 09:30 | 0.124 | 08.11. | 22.11. | 06.12. | 20.12. | 17.01. | 31.01. |
| 🤸 0x | 0D | P. Jungblut | Fr. | 09:45 – 11:15 | 0.124 | 08.11. | 22.11. | 06.12. | 20.12. | 17.01. | 31.01. |
| 🏌 0x | 0E | T. Abu El Komboz | Fr. | 14:00 – 15:30 | 0.124 | 08.11. | 22.11. | 06.12. | 20.12. | 17.01. | 31.01. |
| ♟ 0x | 0F | J.P. Wächter | Fr. | 15:45 – 17:15 | 0.124 | 08.11. | 22.11. | 13.12.* | 20.12. | 17.01. | 31.01. |
| Gruppe | Tutor | Zeit | Raum | Blatt 1 | Blatt 2 | Blatt 3 | Blatt 4 | Blatt 5 | Blatt 6 | ||
| 🥊 0x | 10 | P. Kischkat | Mo. | 09:45 – 11:15 | 0.124 | 11.11. | 25.11. | 09.12. | 08.01.* | 20.01. | 03.02. |
| 🏊 0x | 11 | P. Strohbeck | Mo. | 11:30 – 13:00 | 0.118 | 11.11. | 25.11. | 09.12. | 07.01.* | 20.01. | 03.02. |
| 🚣 0x | 12 | J. Bienias | Mo. | 14:00 – 15:30 | V55.01 | 11.11. | 25.11. | 09.12. | 07.01.* | 20.01. | 03.02. |
| 🤾 0x | 13 | N. Schmid | Mo. | 14:00 – 15:30 | 0.118 | 11.11. | 25.11. | 09.12. | 10.01.* | 20.01. | 03.02. |
| 🏐 0x | 14 | D. Lieb | Di. | 08:00 – 09:30 | 0.124 | 12.11. | 26.11. | 10.12. | 07.01. | 21.01. | 04.02. |
| ⛷ 0x | 15 | P. Mayer | Di. | 08:00 – 09:30 | 0.463 | 12.11. | 26.11. | 10.12. | 07.01. | 21.01. | 04.02. |
| 🛌 0x | 16 | F. Mundinger | Di. | 11:30 – 13:00 | 0.457 | 12.11. | 26.11. | 10.12. | 07.01. | 21.01. | 04.02. |
| 🏄 0x | 17 | K. Bauer | Mi. | 09:45 – 11:15 | 0.124 | 13.11. | 27.11. | 11.12. | 08.01. | 22.01. | 05.02. |
| 🎷 0x | 18 | M. Flinspach | Mi. | 09:45 – 11:15 | 0.453 | 13.11. | 27.11. | 11.12. | 08.01. | 22.01. | 05.02. |
| 💃 0x | 19 | J. Welker | Mi. | 11:30 – 13:00 | 0.118 | 13.11. | 27.11. | 11.12. | 08.01. | 22.01. | 05.02. |
| 🤼 0x | 1A | S. Egger | Do. | 09:45 – 11:15 | 0.124 | 14.11. | 28.11. | 12.12. | 09.01. | 23.01. | 06.02. |
| 🚶♀️ 0x | 1B | B. Ariguib | Do. | 14:00 – 15:30 | 0.124 | 14.11. | 28.11. | 12.12. | 09.01. | 23.01. | 06.02. |
| 🏹 0x | 1C | M. Kurz | Do. | 14:00 – 15:30 | 0.118 | 14.11. | 28.11. | 12.12. | 09.01. | 23.01. | 06.02. |
| 🏃 0x | 1D | P. Jungblut | Fr. | 09:45 – 11:15 | 0.124 | 15.11. | 29.11. | 13.12. | 10.01. | 24.01. | 07.02. |
| 🎮 0x | 1E | T. Abu El Komboz | Di. | 11:30 – 13:00 | 0.463 | 12.11. | 26.11. | 10.12. | 07.01. | 21.01. | 04.02. |
Änderungen *:
- Übungsgruppe 0x03 findet am 04.11. ausnahmsweise in Raum V 55.01 statt.
- Übungsgruppe 0x0F findet am 13.12. statt am 06.12. statt.
- Übungsgruppe 0x10 findet statt am 06.01. am 08.01. von 11:30 bis 13:00 Uhr in Raum 0.124 statt.
- Übungsgruppe 0x11 findet statt am 06.01. am 07.01. von 14:00 bis 15:30 Uhr in Raum 0.124 statt.
- Übungsgruppe 0x12 findet statt am 06.01. am 07.01. von 08:00 bis 09:30 Uhr in Raum 0.363 statt.
- Übungsgruppe 0x13 findet statt am 06.01. am 10.01. von 14:00 bis 15:30 Uhr in Raum 0.124 statt.
Hinweis: Wenn Sie einen Ausweichtermin Ihrer Übungsgruppe nicht wahrnehmen können, besuchen Sie bitte möglichst die entsprechende Übungsgruppe in der alternierenden Woche. Beachten Sie dabei, dass der alternierende Termin bereits vor Weihnachten stattfindet. Wenn Ihnen auch das nicht möglich ist, besuchen Sie bitte irgendeine andere Übungsgruppe und geben dem Tutor dort Bescheid.
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.