Links und Funktionen
Sprachumschaltung

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


Inhaltsbereich

Formale Sprachen und Komplexität

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

Aktuelles

  • Aufgrund von uni2work-Problemen wird die Abgabefrist für Blatt 4 auf Donnerstag 26.05. 08 Uhr verlängert.
  • Räume für die Präsenzübungen würden hinzugefügt!
  • Raumänderung für die Zentralübung: Diese findet aufgrund des besseren Platzangebots nun in A 240, Geschw.-Scholl-Pl.1 statt (Ausnahme am 27.Juli findet sie in  A 140, Geschw.-Scholl-Pl.1 statt.
  • Vorlesung und Zentralübung finden als Präsenzveranstaltungen statt,
    als Digitale Alternative zur Vorlesung werden Screencasts (zum Großteil aus dem SoSe 2021) bereitgestellt.
  •  Übungen finden zum Teil in Präsenz und zum Teil online statt.
  • Weitere Informationen zur Veranstaltung werden nach und nach vervollständigt, sobald sie bekannt sind.

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).

Neben der Vorlesung (3V) und den Übungen (2Ü) wird eine optionale Zentralübung (ca alle 2 Wochen, 2-stündig) angeboten. Diese ist "freiwillig" und dient zum Wiederholen / Einüben des Stoffs, aber es wird kein neuer Stoff behandelt.


Organisation


Zeit und Ort

VeranstaltungZeitOrtBeginn
Vorlesung Di 14-17 Uhr M 018, Geschw.-Scholl-Pl.1 26.04.2022
Zentralübung Mi,12-14 Uhr, ca 2-wöchig A 240, Geschw.-Scholl-Pl.1 (am 27.07. in 023, Kaulbachstr. 37) 27.04.2022
Übung (Präsenz) Montag 10-12 B 106, Geschw.-Scholl-Pl.1 02.05.2022
Übung (Präsenz) Montag 12-14 M 014, Geschw.-Scholl-Pl.1 02.05.2022
Übung (Präsenz) Montag 14-16 E 216, Geschw.-Scholl-Pl.1 02.05.2022
Übung (Präsenz) Donnerstag 8-10 A 125, Geschw.-Scholl-Pl.1 28.04.2022
Übung (Präsenz) Donnerstag 16-18 M 018, Geschw.-Scholl-Pl.1 28.04.2022
Übung (Online) Montag 16-18 Link im uni2work 02.05.2022
Übung (Online) Montag 18-20 Link im uni2work 02.05.2022
Übung (Online) Donnerstag 10-12 Link im uni2work 28.04.2022
Übung (Online) Donnerstag 18-20 Link im uni2work 28.04.2022
Übung (Online) Freitag 10-12 Link im uni2work 29.04.2022
Übung (Online) Freitag 12-14 Link im uni2work 29.04.2022

Material

  • Das Vorlesungsskript, die Vorlesungsfolien, die Übungsblätter und die Videos sind im Materialbereich in Uni2Work zu finden.
  • Ein Backup des Materials (Folien,Skript,Aufgaben) (z.B. wenn uni2work ausfällt) ist hier.
  • Die LMU-Cast Playliste ist hier

Literatur (Auswahl)

  • [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
26.04. Begrüßung, Einführung, Inhaltsübersicht, Grundlagen
Chomsky-Grammatiken und die Chomsky-Hierarchie
Entfernen von Epsilon-Produktionen
27.04 Zentralübung
03.05. Grammatiken: Entscheidungsprobleme und Abschlusseigenschaften
Endliche Automaten: DFAs
Entscheidbarkeit des Wortproblems
10.05. DFAs, DFAs in Typ-3 Grammatiken umformen,NFAs
Typ-3-Grammatiken in NFAs umformen, Determinisierung (Potenzmengenkonstruktion)
Größe von DFAs und NFAs, NFAs mit Epsilon-Übergängen
11.05. Zentralübung
17.05. NFAs mit Epsilon-Übergängen, reguläre Ausdrücke
Satz von Kleene
Pumping-Lemma
18.05. Zentralübung
24.05. Nerode-Relation, Satz von Myhill-Nerode, Nerode-Automat
DFA-Minimierung
Abschlusseigenschaften Typ 3-Sprachen, Entscheidbarkeiten bei Typ-3-Sprachen
25.05. Zentralübung
31.05. CFLs: Normalformen und Abschlusseigenschaften
CFLs: Herstellen von Normalformen
Das Pumpinglemma für CFLs
07.06. Pfingstdienstag: Vorlesungsfrei (wird am 08.06. z.T. nachgeholt)
08.06. CFLs: Wortproblem lösen mit dem CYK-Algorithmus
Kellerautomaten: Definition, Verwendung, Varianten
14.06. Äquivalenz von PDAs und CFLs
Deterministisch kontextfreie Sprachen
Turingmaschinen und Typ 1- und Typ 0-Sprachen
15.06. Zentralübung
21.06. Entscheidbarkeiten bei CFLs und Kuroda-Normalform für CSLs
Beweis des Satz von Kuroda, LBA-Probleme
Intuitive Berechenbarkeit,  Mehrspuren- und Mehrbandmaschinen
28.06. TM-Konstruktionen und LOOP-Programme
WHILE- und GOTO-Berechenbarkeit
Ackermannfunktion
05.07. Primitive Rekursion und mu-Rekursion
entscheidbar, semi-entscheidbar, rekursiv aufzählbar, Halteproblem
Satz von Rice,
06.07. Zentralübung
12.07. Postsches Korrespondenzproblem
Laufzeitkomplexität, die Klassen P und NP
NP-Vollständigkeit
19.07. Der Satz von Cook
NP-Vollständigkeit von 3-CNF-SAT
NP-Vollständigkeit von CLIQUE, INDEPENDENT SET und VERTEX COVER
20.07. Zentralübung
26.07. NP-Vollständigkeit von SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING
NP-Vollständigkeit von HAMILTONCYCLE, TRAVELLINGSALESMAN und GRAPH-COLORING
Wiederholung und Fragestunde
27.07. Zentralübung (Reserve / bei Bedarf)

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

TBA

Artikelaktionen


Funktionsleiste