Wichtige Ankündigungen

Eine weitere Prüfungseinsicht für die Prüfungen

  • Theoretische Informatik I
  • Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung
  • Automaten und Formale Sprachen
  • Automaten und Formale Sprachen (für Mathematiker)
  • Logik und Diskrete Strukturen
  • Theoretische Grundlagen der Informatik

wird am Montag, den 8. April ab 15 Uhr in Raum 1.140 für Studierende, die an der ersten Prüfungseinsicht nicht teilnehmen konnten, angeboten.

Beachten Sie, dass sich die Ergebnisse seit der letzten Einsicht zum Teil geändert haben. Die neuen Ergebnisse hängen am schwarzen Brett des FMI aus (neben Raum 1.101).

Prüfungsräume & Hilfsmittel

Theoretische Informatik I

Hilfsmittel: Ein beidseitig beschriebenes DIN A4 Blatt

Die Räume teilen sich nach Anfangsbuchstaben der Nachnamen wie folgt auf:

A-L: 53.01
M-P: 7.03
R-V: 7.02
W-Z: 38.01

Formale Sprachen und Automatentheorie für die Maschinelle Sprachverarbeitung

Hilfsmittel: Ein beidseitig beschriebenes DIN A4 Blatt
Raum: 38.01

Automaten und Formale Sprachen

Hilfsmittel: ein beidseitig beschriebenes DIN A4-Blatt
Raum: 47.02 (Bitte beachten Sie die Sitzordnung)

Automaten und Formale Sprachen (für Mathematiker)

Hilfsmittel: ein beidseitig beschriebenes DIN A4-Blatt
Raum: 47.02 (Bitte beachten Sie die Sitzordnung)

Logik und Diskrete Strukturen

Hilfsmittel: ein beidseitig beschriebenes DIN A4-Blatt
Raum: 47.02 (Bitte beachten Sie die Sitzordnung)

Theoretische Grundlagen der Informatik

Hilfsmittel: 2 beidseitig beschriebene DIN A4 Blätter
Raum: 47.01

Vorlesung

Prof. Dr. Ulrich Hertrampf

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.

F
Einheit Datum Inhalt Folien
018.10.Vorstellung, Arbeitsweise --
118.10. Sprachen und Grammatiken pdf
224.10. Chomsky-Hierarchie pdf
324.10. Einschub: Wie führt man Beweise? (Teil 1) pdf
425.10. Einschub: Wie führt man Beweise? (Teil 2) pdf
525.10. Das Wort-Problem pdf
631.10. Syntaxbäume, Linksableitungen pdf
731.10. Mehrdeutige Grammatiken, (E)BNF, Zusammenfassung pdf
807.11. Endliche Automaten und Typ-3 Sprachen pdf
907.11. Nichtdeterministische Automaten pdf
1008.11.Satz von Rabin und Scott, Beispiele pdf
1108.11. Exponentieller Blow-Up, DEA=NEA=Typ-3 pdf
1215.11. Reguläre Ausdrücke, Satz von Kleene pdf
1315.11. Pumping Lemma (mit Beweis) pdf
1422.11. Pumping Lemma: Drei Anwendungen, Myhill/Nerode-Äquivalenz pdf
1522.11. Der Satz von Myhill und Nerode, Minimalität des Automaten pdf
1628.11. Minimalautomaten, Erkennung durch Monoide (Einschub) pdf
1728.11. Erkennung durch Monoide (Einschub, Teil 2), Abschlusseigenschaften pdf
1829.11. Entscheidbarkeitsresultate, kontextfreie Sprachen pdf
1929.11. Kontextfreie Sprachen: Normalformen pdf
2005.12. Chomsky-Normalform: Beispiele pdf
2105.12. Greibach-Normalform: Beweis und Beispiele pdf
2206.12. Pumping Lemma für Typ-2 pdf
2306.12. Beispiele und Anwendungen, Einelementiges Alphabet pdf
2412.12. Abschlusseigenschaften pdf
2512.12. Zusammenfassung pdf
2613.12. Wortproblem für Typ-2: CYK-Algorithmus pdf
2713.12. CYK: Beispiele, Vorschau: Kellerautomat pdf
2820.12. Kellerautomaten (PDA): Definition und Funktion pdf
2920.12. Kellerautomaten: Beispiele pdf
3009.01. Von der Typ-2 Grammatik zum PDA pdf
3109.01. Vom PDA zur Typ-2 Grammatik pdf
3210.01. DPDA und DCFL pdf
3310.01. Abschlusseigenschaften von DCFL pdf
3416.01. Typ-1 Sprachen, Kuroda-Normalform pdf
3516.01. Der LBA als Maschinenmodell für Typ-1 pdf
3617.01. Satz von Kuroda, Beweis des Satzes pdf
3717.01. Fortsetzung des Beweises (Satz von Kuroda) pdf
3824.01. Determinismus/Nichtdetermismus, Satz von Immerman und Szelepcsenyi pdf
3924.01. Beweis des Satzes von Immerman und Szelepcsenyi pdf
4006.02. Tabellen pdf
4106.02. Entscheidbarkeiten pdf

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.

Webseite der Ergänzungen

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

Daniel Bahrdt

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.

News

[June 19] The paper “The power word problem” by Markus Lohrey and Armin Weiß has been accepted at MFCS 2019.

[May 19] The paper “On the Average Case of MergeInsertion” by Florian Stober and Armin Weiß has been accepted at IWOCA 2019.

[Oct’18] The paper “Worst-Case Efficient Sorting with QuickMergesort” by Stefan Edelkamp and Armin Weiß has been accepted at ALENEX 2019.

[Jun’18] At CCC 2018, Lukas Fleischer received a Best Student Paper Award for his submission “On the Complexity of the Cayley Semigroup Membership Problem”.

[Jun’18] The paper “Testing Simon’s congruence” by Lukas Fleischer and Manfred Kufleitner was accepted at MFCS 2018.

[Jun’18] The paper “The Intersection Problem for Finite Semigroups” by Lukas Fleischer was accepted at DLT 2018.

[Apr’18] The paper “The isomorphism problem for finite extensions of free groups is in PSPACE” by Géraud Sénizergues and Armin Weiß was accepted at ICALP 2018.

[Apr’18] The paper “On the Complexity of the Cayley Semigroup Membership Problem” by Lukas Fleischer was accepted at CCC 2018.

[Jan’18] On March 24-29, 2019 Volker Diekert, Markus Lohrey, Olga Kharlampovich and Alexei Miasnikov will organize the Schloss Dagstuhl Seminar “Algorithmic Problems in Group Theory”.

[Dec’17] The paper “The Intersection Problem for Finite Monoids” by Lukas Fleischer and Manfred Kufleitner was accepted at STACS 2018.

[Jun’17] At the 12th International Computer Science Symposium in Russia (CSR), Lukas Fleischer and Manfred Kufleitner received a Best Paper Award for their publication “Green’s Relations in Finite Transformation Semigroups”, and Armin Weiss received a Best Paper Award for “The conjugacy problem in free solvable groups and wreath product of abelian groups is in $\text{TC}^0$ \text{TC}^0 “ which is joint work with Alexei Miasnikov and Svetla Vassileva.