Aktuelles | Inhalt | Organisation | Zeit und Ort | Vorlesungs-Chat | Planung | Material | Übungen | Prüfung |
Formale Sprachen und Komplexität
Vorlesung, 3(+1)-std., Blanchette; Übungen 2-std., Kondylidou, Limperg
Aktuelles
-
Die Klausur wird am 02.08. ab 16 Uhr stattfinden und 120 Minuten dauern. Siehe die Seite der Studiengangskoordination für Details.
-
Die Klausuren von 2022 sind jetzt unter Material verfügbar.
-
Von Übungsblatt 5 haben wir die Teilaufgabe, die vorher FSK5-3d (“Chop-Operator”) war, entfernt. Das Übungsblatt, das Sie unten herunterladen können, enthält diese Teilaufgabe bereits nicht mehr.
-
Wichtig: Für die Übungen ab 27.04. haben sich die Räume der meisten Gruppen geändert. Die neuen Räume finden Sie unten.
-
Bitte melden Sie sich zum Vorlesungs-Chat an und stellen Sie Fragen bevorzugt dort, anstatt uns Emails zu schreiben.
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, Reduktion -
Komplexitätstheorie:
Die Klassen P und NP, NP-vollständige Probleme
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
-
Umfang: 3(+1)+2 Semesterwochenstunden
-
Vorlesung + Zentralübung: Prof. Dr. Jasmin Blanchette
-
Übung: Lydia Kondylidou, Jannis Limperg
Zeit und Ort
Für die Übungsgruppen müssen Sie sich über Moodle registrieren.
Veranstaltung | Zeit | Ort | Beginn |
---|---|---|---|
Vorlesung | Di 14-17 | M 018, Geschw.-Scholl-Pl. 1 | 18.04.2023 |
Zentralübung | Mi 12-14, ca. 2-wöchig | A 240, Geschw.-Scholl-Pl. 1 | 19.04.2023 |
Übungsgruppe 1 | Do 08-10 | M 109, Geschw.-Scholl-Pl. 1 | 20.04.2023 |
Übungsgruppe 2 | Do 12-14 | D Z005, Geschw.-Scholl-Pl. 1 | 20.04.2023 |
Übungsgruppe 3 | Do 16-18 | H2 - 2401, Leopoldstr. 13 | 20.04.2023 |
Übungsgruppe 4 | Fr 12-14 | A 213, Geschw.-Scholl-Pl. 1 | 21.04.2023 |
Übungsgruppe 5 | Fr 14-16 | A 021, Geschw.-Scholl-Pl. 1 | 21.04.2023 |
Übungsgruppe 6 | Mo 10-12 | M 109, Geschw.-Scholl-Pl. 1 | 24.04.2023 |
Übungsgruppe 7 | Mo 12-14 | H3 - 3232, Leopoldstr. 13 | 24.04.2023 |
Übungsgruppe 8 | Mo 14-16 | D Z005, Geschw.-Scholl-Pl. 1 | 24.04.2023 |
Übungsgruppe 9 | Mo 16-18 | H2 - 2401, Leopoldstr. 13 | 24.04.2023 |
Vorlesungs-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-23S-FSK-TIMI
Material
-
Skript (zuletzt aktualisiert am 10.04.2023)
-
Die Vorlesungsfolien und die Übungsblätter finden Sie unten.
-
Die LMU-Cast-Playlist aus den SoSe 2021/2022 ist hier verfügbar. Die Nutzung der Videos aus dem Vorjahr erfolgt auf eigene Verantwortung der Studierenden. Der Inhalt der Vorlesung im SoSe 2023 kann von den Inhalten in den vorherigen Jahren abweichen. Allein der Inhalt der Vorlesung im SoSe 2023 ist für die Prüfung im SoSe 2023 verbindlich.
-
Die Klausuren von 2022: Klausur, Klausur mit Lösungen, Nachholklausur, Nachholklausur mit Lösungen. Die Klausur dieses Jahr wird sich strukturell und inhaltlich an der von 2022 orientieren, aber wir behalten uns natürlich beliebige Änderungen vor. Außerdem wird die Klausur dieses Jahr 120 Minuten statt 90 Minuten dauern.
Literatur (Auswahl)
-
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
-
Automata Tutor: ein Online-Werkzeug zum Lernen von Automatentheorie
-
Online Turing Machine Simulator: Online-Werzkeug zum Simulieren von Turingmaschinen
Planung
Termin | Inhalte |
---|---|
18.04. | 01. Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen |
02. Grammatiken und die Chomsky-Hierarchie | |
03. Erzeugte Sprachen, Mehrdeutigkeit, Entfernen von Epsilon-Produktionen | |
19.04. | Zentralübung 1 |
25.04. | 04. Grammatiken: Abschlusseigenschaften und Entscheidungsprobleme |
05. Deterministische endliche Automaten | |
06. Entscheidbarkeit des Wortproblems für Typ 1-Sprachen | |
02.05. | 07. DFAs akzeptieren reguläre Sprachen, Nichtdeterministische endliche Automaten |
08. Determinisierung von endlichen Automaten | |
09. Nichtdeterministische endliche Automaten und Epsilon-Übergänge | |
03.05. | Zentralübung 2 |
09.05. | 10. Reguläre Ausdrücke |
11. Der Satz von Kleene | |
12. Das Pumping-Lemma für reguläre Sprachen | |
10.05. | Zentralübung 3 |
16.05. | 13. Der Satz von Myhill und Nerode |
14. Minimierung von deterministischen endlichen Automaten | |
15. Reguläre Sprachen: Abschlusseigenschaften und Entscheidbarkeitsresultate | |
17.05. | Zentralübung 4 |
23.05. | 16. Kontextfreie Sprachen: Chomsky-Normalform |
17. Kontextfreie Sprachen: Greibach-Normalform und Abschlusseigenschaften | |
18. Das Pumping-Lemma für kontextfreie Sprachen | |
30.05. | Pfingstdienstag: Vorlesungsfrei (wird am 31.05. z.T. nachgeholt) |
A 240 |
19. Der CYK-Algorithmus zum effizienten Entscheiden des Wortproblems für kontextfreie Sprachen |
20. Kontextfreie Sprachen: Kellerautomaten | |
06.06. | 21. Äquivalenz von kontextfreien Sprachen und von Kellerautomaten |
22. Deterministisch kontextfreie Sprachen und Eigenschaften | |
23. Turingmaschinen und Typ 1- und Typ 0-Sprachen | |
07.06. | Zentralübung 5 |
13.06. | 24. Entscheidbarkeiten bei kontextfreien Sprachen und Kuroda-Normalform für kontextsensitive Grammatiken |
25. Der Satz von Kuroda und LBA-Probleme | |
26. Intuitive und Turing-Berechenbarkeit | |
20.06. | 27. Konstruktionen von Turingmaschinen und LOOP-Programme |
28. WHILE- und GOTO-Programme | |
29. Die Ackermannfunktion | |
27.06. | 30. Primitiv und my-rekursive Funktionen |
31. Entscheidbarkeit, Unentscheidbarkeit und das Halteproblem | |
32. Reduktion und der Satz von Rice | |
28.06. | Zentralübung 6 |
04.07. | 33. Das Postsche Korrespondenzproblem |
34. Laufzeitkomplexität und die Klassen P und NP | |
35. NP-Vollständigkeit | |
11.07. | 36. Der Satz von Cook |
37. NP-Vollständigkeit von 3-CNF-SAT | |
38. NP-Vollständigkeit von CLIQUE, INDEPENDENT-SET und VERTEX-COVER | |
12.07. | Zentralübung 7 |
18.07. | 39. NP-Vollständigkeit von SETCOVER, SUBSETSUM, KNAPSACK, PARTITION und BINPACKING |
40. NP-Vollständigkeit von (UN-)DIRECTED-HAMILTON-CYCLE, TRAVELING-SALESPERSON und GRAPH-COLORING | |
41. Wiederholung und Fragestunde | |
19.07. | Zentralübung 8 |
Ü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.
Blatt | Abgabe am | Aufgaben | Lösungen |
---|---|---|---|
0 | keine Abgabe | fsk_blatt00.pdf | fsk_loesung_blatt00.pdf |
1 | 26.04. | fsk_blatt01.pdf | fsk_loesung_blatt01.pdf |
2 | 03.05. | fsk_blatt02.pdf | fsk_loesung_blatt02.pdf |
3 | 10.05. | fsk_blatt03.pdf | fsk_loesung_blatt03.pdf |
4 | 17.05. | fsk_blatt04.pdf | fsk_loesung_blatt04.pdf |
5 | 24.05. | fsk_blatt05.pdf | fsk_loesung_blatt05.pdf |
6 | 31.05. | fsk_blatt06.pdf | fsk_loesung_blatt06.pdf |
7 | 07.06. | fsk_blatt07.pdf | bald™ |
8 | 14.06. | bald™ | bald™ |
9 | 21.06. | bald™ | bald™ |
10 | 28.06. | bald™ | bald™ |
11 | 05.07. | bald™ | bald™ |
12 | 12.07. | bald™ | bald™ |
13 | keine Abgabe | bald™ | bald™ |
Klausur
Wird noch bekanntgegeben.
Artikelaktionen