Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2021 / Formale Sprachen und Komplexität


Inhaltsbereich

Formale Sprachen und Komplexität

Vorlesung, 3+1-std., Sabel; Übungen 2-std., Barth

Aktuelles

 

  • Die Nachholprüfung ist für den 08.10.2021 von 8 bis 14 Uhr als Online-Prüfung (OpenBook-Exam) geplant. Anmeldung und weitere Informationen sind hier zu finden.
  • Backup-Variante des Materials verfügbar (hier)

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

VeranstaltungZeitOrtBeginn
Vorlesung und Zentralübung Di 14-18 Uhr online 13.04.2021
Übung Mi 8-10 online 14.04.2021
Übung Mi 12-14 online 14.04.2021
Übung Do 10-12 online 15.04.2021
Übung Do 16-18 online 15.04.2021
Übung Fr 10-12 online 16.04.2021
Übung Fr 12-14 online 16.04.2021

Material

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


TerminInhalte
13.04. Begrüßung, Einführung, Inhaltsübersicht, Grundlagen
Chomsky-Grammatiken und die Chomsky-Hierarchie
Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften
20.04. Entfernen von Epsilon-Produktionen
Entscheidbarkeit des Wortproblems
Endliche Automaten: DFAs
27.04 DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs
Typ-3-Grammatiken in NFAs, Determinisieriung (Potenzmengenkonstruktion)
Größe von DFAs und NFAs, NFAs mit Epsilon-Übergängen
04.05. NFAs mit Epsilon-Übergängen, reguläre Ausdrücke
Satz von Kleene
Pumping-Lemma
11.05. Nerode-Relation Satz von Myhill-Nerode, Nerode-Automat
DFA-Minimierung
Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen
18.05. CFLs: Normalformen und Abschlusseigenschaften
CFLs: Herstellen von Normalformen
Das Pumpinglemma für CFLs
25.05. CFLs: Wortproblem lösen mit dem CYK-Algorithmus
Kellerautomaten: Definition, Verwendung, Varianten
Äquivalenz von PDAs und CFLs
01.06. Deterministisch kontextfreie Sprachen
Turingmaschinen und Typ 1- und Typ 0-Sprachen
Entscheidbarkeiten bei CFLs und Kuroda-Normalform für CSLs
08.06. Beweise  des Satz von Kuroda, LBA-Probleme
Intuitive Berechenbarkeit,  Mehrspuren- und Mehrbandmaschinen
TM-Konstruktionen und LOOP-Programme
15.06. WHILE- und GOTO-Berechenbarkeit
Ackermannfunktion
Primitive Rekursion und mu-Rekursion
22.06. entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem
Satz von Rice,
Postsches Korrespondenzproblem
29.06. Laufzeitkomplexität, die Klassen P und NP,
NP-Vollständigkeit,
der Satz von Cook
06.07. NP-Vollständigkeit von 3-CNF-SAT,
NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER,
NP-Vollst.v. SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING
13.07. NP-Vollst. von HAMILTONCYCLE, TRAVELLINGSALESMAN und GRAPH-COLORING
Wiederholung und Fragestunde

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 / Prüfung

Ersttermin für die Prüfung ist der 21.07.21 von 8-14 Uhr als Online-Prüfung (OpenBook-Exam).
Die Anmeldung zur Prüfung ist hier möglich.

  • Bitte beachten Sie die Fristen und Termine:
    • Anmeldung bis Mi 14 Jul 2021 23:59
    • Abmeldung bis Di 20 Jul 2021 23:59
    • Prüfung: Mi 21 Jul 2021 08:00

 

Die Nachholprüfung ist für den 08.10.2021 von 8-14 Uhr als Online-Prüfung geplant.

https://www.tcs.ifi.lmu.de/lehre/ss-2021/fsk/material/material/view

Artikelaktionen


Funktionsleiste