Links und Funktionen


Inhaltsbereich
Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Übungen | Klausuren

Formale Sprachen und Komplexität (FSK)

Vorlesung, 3(+1)-std., Blanchette; Übungen 2-std., Limperg, Maio

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). Themen sind:

  • Automaten und Formale Sprachen:
    Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Kellerautomaten

  • Berechenbarkeit:
    Turing-Maschinen, Churchsche These, Unentscheidbarkeit, Halteproblem, Reduktionen

  • Komplexität:
    Die Klassen P und NP, NP-vollständige Probleme, Polynomialzeit-Reduktionen

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

Organisation

Zeit und Ort

Veranstaltung Zeit Ort Beginn
Vorlesung Di 14-17 GSP A 240 16.04.2024
Zentralübung Mi 12-14, ca. 2-wöchig GSP A 240 17.04.2024
Übungsgruppe A Do 08-10 GSP A 016 18.04.2024
Übungsgruppe B Do 12-14 GSP E 216 18.04.2024
Übungsgruppe C Do 16-18 GSP A 016 18.04.2024
Übungsgruppe D Do 18-20 GSP M 109 18.04.2024
Übungsgruppe E Fr 12-14 GSP M 109 19.04.2024
Übungsgruppe F Fr 14-16 GSP M 109 19.04.2024
Übungsgruppe G Fr 16-18 Online (Meeting-Link) 19.04.2024
Übungsgruppe H Mo 08-10 GSP M 109 22.04.2024
Übungsgruppe I Mo 10-12 GSP M 109 22.04.2024
Übungsgruppe J Mo 12-14 GSP M 109 22.04.2024
Übungsgruppe K Mo 14-16 GSP M 109 22.04.2024
Übungsgruppe L Mo 16-18 GSP M 109 22.04.2024

Chat

Für die Vorlesung gibt es einen Zulip-Chatraum, in dem Sie sowohl organisatorische als auch inhaltliche Fragen stellen können. Bitte verwenden Sie wenn möglich diesen Chatraum, anstatt uns Emails zu schreiben, damit Ihre Mitstudierenden auch von den Antworten profitieren können.

Zulip-Server: https://chat.ifi.lmu.de
Stream: TCS-24S-FSK-TIMI

Material

Literatur

  • Uwe Schöning: Theoretische Informatik – kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008

  • Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002

  • John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation, 3. Auflage, 2006

  • Ingo Wegener: Theoretische Informatik – eine algorithmenorientierte Einführung, 3. Auflage, Teubner Verlag, 2005

Nützliche Webseiten

Planung

Termin Inhalte
16.04. Vorlesung 1a: Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen
Vorlesung 1b: Grammatiken und die Chomsky-Hierarchie
Vorlesung 1c: Weitere Grammatikbegriffe sowie Eigenschaften von Sprachen
17.04. Zentralübung 1: Wörter, Beweise, Grammatiken, Chomsky Hierarchie
23.04. Vorlesung 2a: Grammatikbeispiele, Mehrdeutigkeit und Entfernen von Epsilon-Produktionen
Vorlesung 2b: Deterministische endliche Automaten
Vorlesung 2c: Minimierung von deterministischen endlichen Automaten
30.04. Vorlesung 3a: Regularität von deterministischen endlichen Automaten und nichtdeterministische endliche Automaten
Vorlesung 3b: Determinisierung von endlichen Automaten
Vorlesung 3c: Nichtdeterministische endliche Automaten mit Epsilon-Übergängen
07.05. Vorlesung 4a: Reguläre Ausdrücke
Vorlesung 4b: Das Pumping-Lemma für reguläre Sprachen
Vorlesung 4c: Eigenschaften von regulären Sprachen
08.05. Zentralübung 2: DFAs, NFAs, Äquivalenz
14.05. Vorlesung 5a: Der Satz von Myhill und Nerode
Vorlesung 5b: Die Chomsky-Normalform
Vorlesung 5c: Das Pumping-Lemma für kontextfreie Sprachen
15.05. Zentralübung 3: Reguläre Ausdrücke, Abschluss, Pumping-Lemmas
21.05. Pfingstdienstag: Vorlesungsfrei
28.05. Vorlesung 6a: Die Greibach-Normalform und Eigenschaften von kontextfreien Sprachen
Vorlesung 6b: Der CYK-Algorithmus
Vorlesung 6c: Kellerautomaten
04.06. Vorlesung 7a: Äquivalenz von kontextfreien Sprachen und von Kellerautomaten
Vorlesung 7b: Deterministische Kellerautomaten
Vorlesung 7c: Turingmaschinen
05.06. Zentralübung 4: Minimierung, PDAs, Turingmaschinen
11.06. Vorlesung 8a: Linear beschränkte Turingmaschinen (Fortsetzung)
Vorlesung 8b: Entscheiden des Wortproblems für Typ 1-Grammatiken
Vorlesung 8c: Intuitive und Turing-Berechenbarkeit
18.06. Vorlesung 9a: Konstruktionen von Turingmaschinen und LOOP-Programme
Vorlesung 9b: WHILE- und GOTO-Programme
Vorlesung 9c: Die Ackermannfunktion
19.06. Zentralübung 5: Berechenbarkeit, LOOP, WHILE, Myhill-Nerode
25.06. Vorlesung 10a: Primitiv und my-rekursive Funktionen
Vorlesung 10b: Unentscheidbarkeit und das Halteproblem
Vorlesung 10c: Reduktion und der Satz von Rice
02.07. Vorlesung 11a: Das Postsche Korrespondenzproblem
Vorlesung 11b: Laufzeitkomplexität und die Klassen P und NP
Vorlesung 11c: NP-Vollständigkeit
03.07. Zentralübung 6: Reduktionen, Rice, PCP, Rekursion
09.07. Vorlesung 12a: NP-Vollständigkeit von SAT
Vorlesung 12b: NP-Vollständigkeit von 3-CNF-SAT
Vorlesung 12c: NP-Vollständigkeit von CLIQUE, INDEPENDENT-SET und VERTEX-COVER
16.07. Vorlesung 13a: NP-Vollständigkeit von SET-COVER, SUBSET-SUM, KNAPSACK, PARTITION und BIN-PACKING
Vorlesung 13b: NP-Vollständigkeit von GRAPH-COLORING, (UN)DIRECTED-HAMILTON-CYCLE und TRAVELING-SALESPERSON
Vorlesung 13c: Wiederholung und Fragestunde
17.07. Zentralübung 7: CLIQUE, GRAPH-COLORING, KNAPSACK

Korrespondenz zwischen Vorlesungsteilen und Skript

Vorlesungsteil Abschnitte im Skript
1a1, 2.1 (Hausaufgabe: 2.2–2.5)
1b3.1, 3.2 bis Anfang 3.2.2
1c3.2.2, 3.3–3.6
2a3.2.1, 3.5
2b4.1
2c4.11
3a4.2, 4.3
3b4.4, 4.5
3c4.6
4a4.7, 4.8
4b4.12, 4.13
4c4.9
5a4.10, 4.11
5b5.1, 5.2
5c5.4
6a5.3, 5.5, 5.9
6b5.2 bis Anfang 5.2.1, 5.6
6c5.7 bis Anfang 5.7.2, 5.7.2.2
7a5.7.2.1, 5.7.2.3, 5.7.2.4
7b5.8
7c6.2, 6.3 bis Anfang 6.3.1, 7
8a6.1, 6.3.1, 6.4, 6.5
8b3.3
8c8, 9.1, 9.2
9a9.3, 10.1
9b10.2, 10.3–10.5
9c12
10a11
10b13.1, 13.2 bis Anfang 13.2.2
10c13.2.2–13.2.4, 13.3
11a13.4, 13.5
11b14
11c15 bis Anfang 15.2
12a15.2
12b16 bis Anfang 16.2
12c16.2–16.4
13a16.5–16.9
13b16.10–16.13

Übungen

Die Übungsblätter müssen jeweils bis 10:00 Uhr am angegebenen Tag auf Moodle abgegeben werden. Verspätete Abgaben sind nicht möglich. Lösungsvorschläge werden jeweils nach Ende der Abgabefrist hier veröffentlicht.

Lösungsvorschlag zu Blatt 0
Lösungsvorschlag zu Blatt 1
Lösungsvorschlag zu Blatt 2
Lösungsvorschlag zu Blatt 3
Lösungsvorschlag zu Blatt 4
Lösungsvorschlag zu Blatt 5
Lösungsvorschlag zu Blatt 6
Lösungsvorschlag zu Blatt 7
Lösungsvorschlag zu Blatt 8
Lösungsvorschlag zu Blatt 9
Lösungsvorschlag zu Blatt 10
Lösungsvorschlag zu Blatt 11

Klausuren

Bei den Klausuren sind Hilfsmittel nicht erlaubt. Auch das Mitführen ausgeschalteter elektronischer Geräte wird als Betrug gewertet. Die Klausuren werden sich strukturell und inhaltlich an denen von 2023 orientieren, aber wir behalten uns natürlich beliebige Änderungen vor.

Die Erstklausur wird am 05.08.2024 ab 15:00 Uhr in Großhadern stattfinden. Die Zweitklausur wird voraussichtlich im September oder Oktober 2024 stattfinden. Die Bearbeitungszeit beträgt 120 Minuten.

Falls Sie einen Nachteilsausgleich in Anspruch nehmen möchten, melden Sie sich bitte rechtzeitig bei dem Dozenten.

Artikelaktionen


Funktionsleiste