Prüfungseinsicht
Die Ergebnisse hängen am schwarzen Brett des FMI aus. Dieses befindet sich neben Raum 1.101. Bitte beachten Sie den Aushang mit Hinweisen zu Prüfungsergebnissen.
Am Dienstag, den 24. September 2019, finden folgende Prüfungseinsichten im Raum 0.124 statt:
| Nummer | Titel | Termin |
|---|---|---|
| 2353100000 | Automaten und Formale Sprachen | ab 11 Uhr |
| 1207100000 | Automaten und Formale Sprachen (für Mathematiker) | ab 11 Uhr |
| 7281100000 | Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung | ab 14 Uhr |
| 4569100000 | Logik und Diskrete Strukturen | ab 11 Uhr |
| 1094100000 | Theoretische Grundlagen der Informatik | ab 11 Uhr |
| 7862100000 | Theoretische Informatik I | ab 14 Uhr |
Bitte bringen Sie Ihren Studienausweis mit und beachten Sie den Leitfaden für Prüfungseinsichten der Universität.
Vorlesung
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.
Anmerkung 1: Auf Folie 7.1 gibt es einen Verweis auf Folie 5.4. Richtig müsste es hier heißen: Folie 6.5. (Dabei handelt es sich um die erste der Grammatiken auf 6.5)
Anmerkung 2: Es gibt noch mehr nicht angepasste Verweise. 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 | 18.10. | Vorstellung, Arbeitsweise | -- |
| 1 | 18.10. | Sprachen und Grammatiken | |
| 2 | 24.10. | Chomsky-Hierarchie | |
| 3 | 24.10. | Einschub: Wie führt man Beweise? (Teil 1) | |
| 4 | 25.10. | Einschub: Wie führt man Beweise? (Teil 2) | |
| 5 | 25.10. | Das Wort-Problem | |
| 6 | 31.10. | Syntaxbäume, Linksableitungen | |
| 7 | 31.10. | Mehrdeutige Grammatiken, (E)BNF, Zusammenfassung | |
| 8 | 07.11. | Endliche Automaten und Typ-3 Sprachen | |
| 9 | 07.11. | Nichtdeterministische Automaten | |
| 10 | 08.11. | Satz von Rabin und Scott, Beispiele | |
| 11 | 08.11. | Exponentieller Blow-Up, DEA=NEA=Typ-3 | |
| 12 | 15.11. | Reguläre Ausdrücke, Satz von Kleene | |
| 13 | 15.11. | Pumping Lemma (mit Beweis) | |
| 14 | 22.11. | Pumping Lemma: Drei Anwendungen, Myhill/Nerode-Äquivalenz | |
| 15 | 22.11. | Der Satz von Myhill und Nerode, Minimalität des Automaten | |
| 16 | 28.11. | Minimalautomaten, Erkennung durch Monoide (Einschub) | |
| 17 | 28.11. | Erkennung durch Monoide (Einschub, Teil 2), Abschlusseigenschaften | |
| 18 | 29.11. | Entscheidbarkeitsresultate, kontextfreie Sprachen | |
| 19 | 29.11. | Kontextfreie Sprachen: Normalformen | |
| 20 | 05.12. | Chomsky-Normalform: Beispiele | |
| 21 | 05.12. | Greibach-Normalform: Beweis und Beispiele | |
| 22 | 06.12. | Pumping Lemma für Typ-2 | |
| 23 | 06.12. | Beispiele und Anwendungen, Einelementiges Alphabet | |
| 24 | 12.12. | Abschlusseigenschaften | |
| 25 | 12.12. | Zusammenfassung | |
| 26 | 13.12. | Wortproblem für Typ-2: CYK-Algorithmus | |
| 27 | 13.12. | CYK: Beispiele, Vorschau: Kellerautomat | |
| 28 | 20.12. | Kellerautomaten (PDA): Definition und Funktion | |
| 29 | 20.12. | Kellerautomaten: Beispiele | |
| 30 | 09.01. | Von der Typ-2 Grammatik zum PDA | |
| 31 | 09.01. | Vom PDA zur Typ-2 Grammatik | |
| 32 | 10.01. | DPDA und DCFL | |
| 33 | 10.01. | Abschlusseigenschaften von DCFL | |
| 34 | 16.01. | Typ-1 Sprachen, Kuroda-Normalform | |
| 35 | 16.01. | Der LBA als Maschinenmodell für Typ-1 | |
| 36 | 17.01. | Satz von Kuroda, Beweis des Satzes | |
| 37 | 17.01. | Fortsetzung des Beweises (Satz von Kuroda) | |
| 38 | 24.01. | Determinismus/Nichtdetermismus, Satz von Immerman und Szelepcsenyi | |
| 39 | 24.01. | Beweis des Satzes von Immerman und Szelepcsenyi | |
| 40 | 06.02. | Tabellen | |
| 41 | 06.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:
- 40% 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.
Scheinklausur
Die Scheinklausur findet am Donnerstag den 31.1. ab 15:45 Uhr im Hörsaal 53.01 statt.
Erlaubte Hilfsmittel: KEINE
Zur Teilnahme werden der Studentenausweis (Lichtbild, Name und Matrikelnummer), Kugelschreiber und Tipp-Ex oder Bleistift und Radiergummi benötigt.
Die Bearbeitungszeit beträgt 60 Minuten wobei bis zu 60 Punkte erreicht werden können.
Die Scheinklausur gilt als bestanden, wenn Sie mehr als 40% der Gesamtpunktzahl erreichen.
Alle Punkte die Sie darüberhinaus erreichen werden Ihnen als Kurztestpunkte angerechnet.
Falls Sie noch nicht genügend Punkte in den Kurztests gesammelt haben, können Sie in der Scheinklausur noch genügend Punkte sammeln um dennoch einen Schein zu erhalten.
Hinweis zur Vorbereitung: Schauen Sie sich die Kurzteste noch einmal genau an!
Scheinklausuranmeldung
Eine Anmeldung zur Scheinklausur ist Voraussetzung zur Teilnahme.
Die Anmeldung ist nun noch bis zum 30.01 möglich.
Wir haben nun alle Kommentare gelöscht.
Wir werden sehen ob Sie es diesmal schaffen keine Kommentare abzugeben.
Falls Sie Interesse an einer Verbesserung dieser nextcloud-App haben können Sie dies gerne im Rahmen einer studentischen Arbeit bei dem Übungsleiter umsetzen.
Im folgenden die Anleitung zum Abstimmen:
Widerstehen Sie dem Drang einen Kommentar abzugeben.
Zählen Sie langsam bis zehn: Zehn, Neun, Acht, Sieben, Sechs, Fünf, Vier, Drei, Zwei, Eins. Sie haben kein Kommentar abgegeben. Sehr gut!
Scrollen Sie nun bis ganz nach unten.
Dann tragen Sie ihre Matrikelnummer als Namen ein und klicken auf das Feld neben Ihrer Matrikelnummer bis ein grüner Hacken erscheint.
Dann schicken Sie die Anmeldung ab.
Beachten Sie, dass sich die Anmeldezahl oben während der Änderung ihrer Auswahl anpasst!
Im Zweifel können Sie sich auch einfach nochmal anmelden!
Beachten Sie, dass sich die Anzahl an angemeldeten Personen nicht erhöht, falls die Anmeldung bereits geklappt hat. Die Nextcloud-Poll-App nutzt den Namen offenkundig als Identifier.
Beachten Sie, dass Ilias keine Alternative darstellt, da es Studenten gibt, die darauf keinen Zugriff haben.
Nutzen Sie nach Möglichkeit Chrome oder Chromium um die Seite zu laden. Mit ein bisschen Geduld funktioniert das schon noch.
Die eingesetzte Software wird im Übrigen in Zukunft das Rückgrat der Bundescloud bilden um den IT-Standort Deutschland ins 21. Jahrhundert zu katapultieren.
Bitte sehen Sie von Rückfragen bezüglich Ihres Anmeldestatus ab. Gehen Sie davon aus, dass alles geklappt hat. \
Kurzteste
Die Kurzteste können voraussichtlich Ende nächster Woche abgeholt werden.
Die genaue Uhrzeit sowie den Ort werden wir noch bekannt geben.
Konzentrieren Sie sich beim Lernen auf die Prüfung nicht nur auf die Kurzteste.
Viel relevanter sind die Übungsaufgaben!
Ü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 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.
22.02: Restliche Lösungen veröffentlicht.
| 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 | 9.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 | hier | hier | hier | hier | hier | hier | hier | hier | hier |
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 | - | - | 7 | 11 | 13 | 15 | 19 | 23 | 27 | 29 | 33 | 37 | 39 | 39 |
| Kurztestnummer | - | - | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Ü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.