Links und Funktionen
Sprachumschaltung
Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2019 / Formale Sprachen und Komplexität
Inhaltsbereich

Formale Sprachen und Komplexität

Vorlesung, 3+1-std., Sabel; Übungen 2-std., Barth
Aktuelles | Inhalt | Organisation | Zeit und Ort | Planung | Materialien | Übungen | Klausur

Aktuelles

  • Raumverlegung am Mittwoch in der letzten Vorlesungswoche:
    Am 24.07. findet die Vorlesung nicht in S 002 (Schellingstr. 3, EG), sondern in R 051 (Schellingstr. 3, EG) statt    .
    Der  Raum ist im gleichen Gebäude auf der gleichen Ebene, aber vom Eingang her gesehen weiter hinten
    (siehe LMU Raumfinder)
  • Klausuranmeldung zu beiden Klausuren: Die Anmeldung ist ab sofort im Uni2work möglich. Beachten Sie die Anmeldefristen!
  • Pfingsmontag (10.6.) und Dienstag der 11.6. sind vorlesungsfrei. Es finden daher keine Übungen statt. Im Uni2Work finden Sie klausurähnliche Aufgaben (zum ersten Teil der Vorlesung), die sie stattdessen bearbeiten können. DIese Aufgaben werden nicht abgegeben und nicht besprochen.
  • Update Skript und Foliensatz 02: Die Definition der epsilon-Hülle war nicht richtig. Diese ist nun verbessert.
  • Montagsübung, 18-20, beginnt auf Wunsch der Teilnehmenden ab sofort um 18 s.t.
  • Bitte melden Sie sich bei Uni2work zur Vorlesung an.

Inhalt

Die Vorlesung behandelt Grundlagen der theoretischen Informatik: Sie gibt Einführungen in die Theorie der formalen Sprachen und Automaten sowie in die Berechenbarkeits- und Komplexitätstheorie. Die Veranstaltung orientiert sich inhaltlich und strukturell am Lehrbuch von Schöning (Theoretische Informatik - kurz gefasst).

Organisation

Zeit und Ort

Veranstaltung Zeit OrtBeginn
Vorlesung Mi 12-14 Uhr Schellingstr. 3 (S), S 002 24.04.2019
Vorlesung / Zentralübung Do 16-18 Uhr Schellingstr. 3 (S), S 002 25.04.2019
Übung (Stephan Barth) Mo 10-12 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (Sebastian Sturm) Mo 16-18 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (Elisabeth Lempa) Mo 18:00 - 19:30 Uhr Geschw.-Scholl-Pl. 1 (A), A 022 29.04.2019
Übung (David Sabel) Di 16-18 Uhr Geschw.-Scholl-Pl. 1 (M), M 203 30.04.2019
Übung (David Tellenbach) Di 18-20 Uhr Geschw.-Scholl-Pl. 1 (M), M 203 30.04.2019

Material

Folien

Skript

Das Skript zur Vorlesung wird ständig erweitert. Die aktuelle Version ist hier verfügbar.

Zentralübung

Literatur

  • [AB02] Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002.
  • [HMU06] John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006
  • [IW05] Ingo Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 3.Auflage, Teubner Verlag, 2005.
  • [US08] Uwe Schöning: Theoretische Informatik - kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008.
  • ...

Nützliche Webseiten

Protokoll und Planung

Protokoll

  • Mittwoch 24. April: Begrüßung, Einführung, Inhaltsübersicht, Alphabete, Worte, Formale Sprachen
  • Donnerstag 25. April: Chomsky Grammatiken und die Chomsky-Hierarchie
  • Mittwoch 1.Mai: Feiertag (keine Vorlesung)
  • Donnerstag 2.Mai: Elimination von epsilon-Produktionen, Wortproblem, Typ-3 Sprachen, endliche Automaten (DFA)
  • Mittwoch 8.Mai:  DFA (Konstruktion DFA in Typ 3 Grammatik), NFAs, reguläre Grammatik in NFA überführen, NFA in DFA  mit Potenzmengenkonstruktion
  • Donnerstag 9.Mai: Grösse von DFA vs NFA, NFA mit Epsilon-Übergängen, Zentralübung (DFAs, NFAs)
  • Mittwoch 15.Mai: NFA mit Epsilon-Übergängen und mit eindeutigen Start- und Endzuständen, Reguläre Ausdrücke, Satz von Kleene
  • Donnerstag 16.Mai: Pumping-Lemma  und Zentralübung (Reguläre Ausdrücke und Anwenden des Pumping-Lemmas)
  • Mittwoch 22. Mai: Pumping-Lemma (Wdh),  Satz von Myhill-Nerode
  • Donnerstag 23. Mai: Konstruktion des Minimalautomaten, Abschlusseigenschaften Typ-3, Entscheidbarkeiten bei Typ-3 (keine Zentralübung, stattdessen Vorlesung, um die kommenden Feiertage auszugleichen)
  • Mittwoch 29. Mai:  Kontextfreie Sprachen: Operationen und Normalformen
  • Donnerstag 30.Mai: Feiertag (keine Vorlesung)
  • Mittwoch 05. Juni: Pumping-Lemma für kontextfreie Sprachen, CYK-Algorithmus
  • Donnerstag 06. Juni: Kellerautomaten Zentralübung: Pumping-Lemma für CFLs und Ogdens Lemma, Beispiel zum CYK-Algorithmus
  • Mittwoch 12.Juni: Kellerautomaten, deterministisch kontextfreie Sprachen, Abschlusseigenschaften Typ-2, Typ-1 Sprachen, Turingmaschinen
  • Donnerstag 13.Juni: Turingmaschinen und LBAs, Zentralübung: Kellerautomaten (Beispiele), Akzeptanz bei PDAs, Turingmaschinen (Beispiel)
  • Mittwoch 19.Juni: LBA-Probleme, Intuitive Berechenbarkeit, Mehrbandmaschinen
  • Donnerstag 20.Juni: Feiertag (keine Vorlesung)
  • Mittwoch 26. Juni: LOOP-Programme, WHILE-Programme, GOTO-Programme, Äquivalenz zur Turingberechenbarkeit
  • Donnerstag 27.Juni: Ackermannfunktion, Zentralübung: LOOP/WHILE/GOTO
  • Mittwoch 03.Juli: rekursive Funktionen,Halteproblem, Unentscheidbarkeit, rekursiv aufzählbar
  • Donnerstag 04.Juli: Fortsetzung Halteproblem, Unentscheidbarkeit, Reduktionen, Zentralübung: Beispiele zu primitiv und mu-rekursiven Funktionen, Reduktion
  • Mittwoch 10.Juli: Reduktionen, Satz von Rice, Postsches Korrespondenzproblem
  • Donnerstag 11.Juli: Zeitkomplexität, P, NP, Zentralübung: Reduktionen
  • Mittwoch 17.Juli: NP Vollständigkeit, Satz von Cook

Planung für die kommenden Vorlesungen

  • Donnerstag 18.Juli: Weitere NP vollständige Probleme
  • Mittwoch 24.Juli: Weitere NP vollständige Probleme
  • Donnerstag 25.Juli: Wiederholung/Fragen zur Klausur

Übungen

Die Übungsblätter werden über Uni2work verteilt. Die Abgabe und Korrektur wird ebenfalls über Uni2work abgewickelt, die Abgabefrist ist jeweils auf dem Übungsblatt angegeben.

Klausur

Klausur

Die Klausur findet am Dienstag, 30. Juli um 16:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Klausur ist erforderlich.
Die Anmeldung ist im Uni2work bereits freigeschaltet und bis zum 26. Juli um 12:00 Uhr nötig.

Nachklausur

Die Nachklausur findet am Dienstag, 24. September um 14:00 Uhr statt (Bearbeitungszeit 120 Minuten).
Eine Anmeldung ist zur Teilnahme an der Nachklausur ist erforderlich.
Die Anmeldung ist im Uni2work bereits freigeschaltet und bis zum 20. September um 12:00 Uhr nötig.

Artikelaktionen

Funktionsleiste