Vorlesung
Ergebnisse der Modulprüfungen
Die Ergebnisse der Modulprüfungen
- Theoretische Grundlagen der Informatik,
- Automaten und Formale Sprachen,
- Automaten und Formale Sprachen (für Mathematiker) und
- Logik und Diskrete Strukturen
- Theoretische Informatik I und
- Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung
hängen aus.
Raumverteilung für die Modulprüfungen
Die Modulprüfungen am Mittwoch, den 28.03.18, finden mit folgender Raumaufteilung statt:
| Theoretische Informatik I: 08:00 Uhr | |
|---|---|
| Nachname | Raum |
| A – G | V 7.02 |
| H – P | Sporthalle Keltenschanze |
| R – Z | V 47.02 |
Insbesondere findet in Raum V 57.01 keine Prüfung statt. Studenten des Studiengangs Maschinelle Sprachverarbeitung mit Prüfung „Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung“ (72811) schreiben ihre Prüfung nach derselben Buchstabenaufteilung und zu denselben Zeiten wie für „Theoretische Informatik I”.
| Theoretische Grundlagen der Informatik: 11:00 Uhr | |
|---|---|
| Nachname | Raum |
| A – M | V 53.01 |
| N – Z | Sporthalle Keltenschanze |
Die Modulprüfungen „Automaten und Formale Sprachen”, „Automaten und Formale Sprachen für Mathematiker” und „Logik und Diskrete Strukturen” finden gemeinsam in Raum V47.02 statt. Sie beginnen um 11:00 Uhr und enden (gegen) 12:00 Uhr, dauern also jeweils nur 60 Minuten.
| Prüfung | Erlaubte Hilfsmittel |
|---|---|
| 7862100000 Theoretische Informatik I | Ein beidseitig beschriebenes DIN A4 Blatt |
| 4569100000 Logik und Diskrete Strukturen | Ein beidseitig beschriebenes DIN A4-Blatt |
| 1207100000 Automaten und Formale Sprachen (für Mathematiker) | Ein beidseitig beschriebenes DIN A4-Blatt |
| 2353100000 Automaten und Formale Sprachen | Ein beidseitig beschriebenes DIN A4-Blatt |
| 1094100000 Theoretische Grundlagen der Informatik | 2 beidseitig beschriebene DIN A4 Blätter |
Hilfsmittel müssen dokumentenecht mit Name und Matrikelnummer gekennzeitnet sein.
Gedruckte Bögen werden akzeptiert, falls diese ohne optische Hilfen lesbar sind.
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 |
|---|---|---|---|
| 0 | 19.10. | Vorstellung, Arbeitsweise | -- |
| 1 | 25.10. | Sprachen und Grammatiken | |
| 2 | 25.10. | Chomsky-Hierarchie | |
| 3 | 26.10. | Einschub: Wie führt man Beweise? (Teil 1) | |
| 4 | 26.10. | Einschub: Wie führt man Beweise? (Teil 2) | |
| 5 | 02.11. | Das Wort-Problem, Syntaxbaum | |
| 6 | 02.11. | Beispiele für Syntaxbäume, Mehrdeutigkeit, (E)BNF | |
| 7 | 08.11. | Zusammenfassung, Endliche Automaten | |
| 8 | 08.11. | Automaten und Typ-3 Sprachen | |
| 9 | 09.11. | NEA, Satz von Rabin und Scott | |
| 10 | 09.11. | Beispiele, exponentieller Blow-Up, DEA=NEA=Typ-3 | |
| 11 | 16.11. | Reguläre Ausdrücke, Satz von Kleene | |
| 12 | 16.11. | Pumping Lemma (mit Beweis) | |
| 13 | 23.11. | Pumping Lemma: Drei Anwendungen | |
| 14 | 23.11. | Der Satz von Myhill und Nerode | |
| 15 | 29.11. | Minimalautomaten | |
| 16 | 29.11. | Erkennung durch Monoide (Einschub) | |
| 17 | 30.11. | Abschlusseigenschaften und Entscheidbarkeitsresultate | |
| 18 | 30.11. | Kontextfreie Sprachen, Normalformen | |
| 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. | Wortproblem für Typ-2: CYK-Algorithmus | |
| 27 | 21.12. | CYK: Beispiele, Einführung: Kellerautomaten | |
| 28 | 21.12. | Definition und Funktion des PDA | |
| 29 | 10.01. | Von der Typ-2 Grammatik zum PDA | |
| 30 | 10.01. | Vom PDA zur Typ-2 Grammatik | |
| 31 | 11.01. | DPDA und DCFL | |
| 32 | 11.01. | Abschlusseigenschaften von DCFL | |
| 33 | 17.01. | Typ-1 Sprachen, Kuroda-Normalform | |
| 34 | 17.01. | Der LBA als Maschinenmodell für Typ-1 | |
| 35 | 18.01. | Satz von Kuroda | |
| 36 | 18.01. | Beweis des Satzes von Kuroda | |
| 37 | 25.01. | Satz von Immerman und Szelepcsenyi | |
| 38 | 25.01. | Beweis des Satzes | |
| 39 | 01.02. | Tabellen | |
| 40 | 01.02. | Entscheidbarkeiten |
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 Scheinliste für das WS1718 kann ab dem 9. Februar am FMI Aushangbrett eingesehen werden.
Scheinklausur
Die Scheinklausur findet am Mittwoch, den 7.02., ab 14:00 statt.
Eine Anmeldung zur Scheinklausur (im Rahmen der schriftlichen Abgabe zu Blatt5) ist Voraussetzung zur Teilnahme.
Im Zweifel sollten Sie sich Anmelden.
Klausurräume: Namen A-M in V47.02 und Namen N-Z in V38.04
Erlaubte Hilfsmittel: KEINE
Zur Teilnamhe werden der Studentenausweis (Lichtbild, Name und Matrikelnummer), Kugelschreiber und Tipp-Ex oder Bleistift und Radiergummi benötigt.
Ergänzungen
Carlos Camino bietet wöchentlich Ergänzungen an. Teilnahme ist freiwillig, aber sehr zu empfehlen.
Übungen
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. | Fr. 19.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. | 19.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.