| Inhalt | Organisation | Zeit und Ort | Chat | Material | Planung | Übungen | Klausuren |
Theoretische Informatik für Studierende der Medieninformatik (TIMI)
Vorlesung, 2(+1)-std., Blanchette; Übungen 1-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 (2V) und den Übungen (1Ü) 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: 2(+1)+1 Semesterwochenstunden
-
Vorlesung: Prof. Dr. Jasmin Blanchette
-
Übung: Jannis Limperg, Luca Maio
Zeit und Ort
Die Vorlesung findet integriert in der größeren Veranstaltung Formale Sprachen und Komplexität (FSK) statt. Daher ist für die 2-stündige Vorlesung ein dreistündiger Zeitslot reserviert, von dem nicht alle Stunden für die Theoretische Informatik für Studierende der Medieninformatik verwendet werden. Welche Vorlesungsteile relevant sind, sind der Planung zu entnehmen.
| 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 14-15 s.t. | Leopoldstr. 13, Haus 1, 1503 | 18.04.2024 |
| Übungsgruppe B | Do 15:30-16:30 s.t. | Leopoldstr. 13, Haus 1, 1503 | 18.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
-
Die ersten 11 Übungsblätter als ZIP:
Übung 0, Übung 1, Übung 2, Übung 3, Übung 4, Übung 5, Übung 6, Übung 7, Übung 8, Übung 9, Übung 10
(siehe Übungen unten für die Lösungen) -
Die Klausuren von 2023:
Hauptklausur (Lösungen), Nachholklausur (Lösungen) -
Die Hauptklausur von 2022:
Hauptklausur (Lösungen) -
Die FSK-Klausuren von 2019:
Hauptklausur, (Lösungen), Nachholklausur (Lösungen) -
Die LMU-Cast-Playlist aus den SoSe 2021/2022 für FSK ist hier verfügbar. Die Nutzung dieser Videos erfolgt auf eigene Verantwortung der Studierenden. Der Inhalt der Vorlesung im SoSe 2024 kann von den Inhalten in den vorherigen Jahren abweichen. Insbesondere werden die Themen DFA-Minimierung und linear beschränkte Turingmaschinen anders behandelt. Allein der Inhalt der Vorlesung im SoSe 2024 ist für die Prüfung im SoSe 2024 verbindlich.
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
-
Automata Tutor: ein Online-Werkzeug zum Lernen von Automatentheorie
-
Online Turing Machine Simulator: Online-Werzkeug zum Simulieren von Turingmaschinen
Planung
Durchgestrichene Vorlesungsteile sind nur für FSK relevant. Die TIMI-Vorlesungsteile beginnen entsprechend später, wobei jeder Vorlesungsteil ca. eine Stunde dauert.
Korrespondenz zwischen Vorlesungsteilen und Skript
| Vorlesungsteil | Abschnitte im Skript |
|---|---|
| 1a | 1, 2.1 (Hausaufgabe: 2.2–2.5) |
| 1b | 3.1, 3.2 bis Anfang 3.2.2 |
| 1c | 3.2.2, 3.3–3.6 |
| 2b | 4.1 |
| 2c | 4.11 |
| 3a | 4.2, 4.3 |
| 3b | 4.4, 4.5 |
| 3c | 4.6 |
| 4a | 4.7, 4.8 |
| 4b | 4.12, 4.13 |
| 4c | 4.9 |
| 6b | 5.2 bis Anfang 5.2.1, 5.6 |
| 6c | 5.7 bis Anfang 5.7.2, 5.7.2.2 |
| 7b | 5.8 |
| 7c | 6.2, 6.3 bis Anfang 6.3.1, 7 |
| 8c | 8, 9.1, 9.2 |
| 10b | 13.1, 13.2 bis Anfang 13.2.2 |
| 10c | 13.2.2–13.2.4, 13.3 |
| 11a | 13.4, 13.5 |
| 11b | 14 |
| 11c | 15 bis Anfang 15.2 |
| 12a | 15.2 |
| 12b | 16 bis Anfang 16.2 |
| 12c | 16.2–16.4 |
| 13b | 16.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
Klausuren
Bei den Klausuren sind Hilfsmittel nicht erlaubt. Die Klausuren werden sich strukturell und inhaltlich an denen von 2023 orientieren, aber wir behalten uns natürlich beliebige Änderungen vor.
Die Hauptklausur wird am 05.08.2024 ab 15:00 Uhr in Theresienstr. 41 C 123 stattfinden. Die Nachholklausur 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