Program Overview

Theoretische Informatik für Medieninformatiker (TIMI)

Overview

Theoretische Informatik für Medieninformatiker (TIMI) is a university program that focuses on the theoretical foundations of computer science, particularly in the context of media informatics.

Content

The program covers the following topics:

• 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

Organization

• Umfang: 2+1 Semesterwochenstunden
• Vorlesung: Prof. Dr. Jasmin Blanchette
• Übung: Lydia Kondylidou, Jannis Limperg

Schedule

The lecture takes place integrated into the larger event Formale Sprachen und Komplexität. Therefore, a three-hour time slot is reserved for the 2-hour lecture, not all of which is used for Theoretische Informatik für die Medieninformatik. Which (partial) lectures are relevant can be found in the planning.

For the exercise groups, you must register via Moodle.

Material

• Skript
• Vorlesungsfolien und Übungsblätter
• LMU-Cast-Playlist from SoSe 2021/2022
• Klausur von 2022: Klausur, Klausur mit Lösungen
• FSK-Klausuren von 2019: Klausur, Klausur mit Lösungen, Nachholklausur, Nachholklausur mit Lösungen

Literature

• 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

Planning

The planning for the program is as follows:

• 18.04. 1416 Uhr: 01. Begrüßung, Organisatorisches, Inhaltsübersicht und Grundlagen, 02. Grammatiken und die Chomsky-Hierarchie
• 25.04. 1416 Uhr: 04. Grammatiken: Abschlusseigenschaften und Entscheidungsprobleme, 05. Deterministische endliche Automaten
• 02.05. 1416 Uhr: 07. DFAs akzeptieren reguläre Sprachen, Nichtdeterministische endliche Automaten, 08. Determinisierung von endlichen Automaten
• 09.05.: 10. Reguläre Ausdrücke, 11. Der Satz von Kleene, 12. Das Pumping-Lemma für reguläre Sprachen
• 16.05. 1517 Uhr: 14. Minimierung von deterministischen endlichen Automaten, 15. Reguläre Sprachen: Abschlusseigenschaften und Entscheidbarkeitsresultate
• 23.05.: Keine Vorlesung
• 30.05.: Pfingstdienstag: Vorlesungsfrei (wird am 31.05. z. T. nachgeholt)
• 31.05. 1214 Uhr (A 240): 19. Der CYK-Algorithmus zum effizienten Entscheiden des Wortproblems für kontextfreie Sprachen, 20. Kontextfreie Sprachen: Kellerautomaten
• 06.06. 1517 Uhr: 22. Deterministisch kontextfreie Sprachen und Eigenschaften, 23. Turingmaschinen und Typ 1- und Typ 0-Sprachen
• 13.06. 1617 Uhr: 26. Intuitive und Turing-Berechenbarkeit
• 20.06.: Keine Vorlesung
• 27.06. 1517 Uhr: 31. Entscheidbarkeit, Unentscheidbarkeit und das Halteproblem, 32. Reduktion und der Satz von Rice
• 04.07. 1417 Uhr: 33. Das Postsche Korrespondenzproblem, 34. Laufzeitkomplexität und die Klassen P und NP, 35. NP-Vollständigkeit
• 11.07. 1417 Uhr: 36. Der Satz von Cook, 37. NP-Vollständigkeit von 3-CNF-SAT, 38. NP-Vollständigkeit von CLIQUE, INDEPENDENT-SET und VERTEX-COVER
• 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

Exercises

The exercise sheets must be submitted by 10:00 a.m. on the specified day via Moodle. Late submissions are not possible.

• Blatt 0: keine Abgabe, timi_blatt00.pdf, timiblatt00.pdf
• Blatt 1: 26.04., timi_blatt01.pdf, timiblatt01.pdf
• Blatt 2: 03.05., timi_blatt02.pdf, timiblatt02.pdf
• Blatt 3: 10.05., timi_blatt03.pdf, timiblatt03.pdf
• Blatt 4: 17.05., timi_blatt04.pdf, timiblatt04.pdf
• Blatt 5: 24.05., timi_blatt05.pdf, timiblatt05.pdf
• Blatt 6: 31.05., timi_blatt06.pdf, timiblatt06.pdf
• Blatt 7: 07.06., timi_blatt07.pdf, timiblatt07.pdf
• Blatt 8: 14.06., timi_blatt08.pdf, timiblatt08.pdf
• Blatt 9: 21.06., timi_blatt09.pdf, timiblatt09.pdf
• Blatt 10: 28.06., timi_blatt10.pdf, timiblatt10.pdf
• Blatt 11: 05.07., timi_blatt11.pdf, timiblatt11.pdf
• Blatt 12: 12.07., timi_blatt12.pdf, timiblatt12.pdf
• Blatt 13: keine Abgabe, timi_blatt13.pdf, timiblatt13.pdf

Exam

The repeat exam takes place on Monday, 25 September 2023. The room allocation will be announced via Moodle before the exam. No aids are allowed.

You can register for the repeat exam via Moodle until 13 September 2023. You can only take the repeat exam if you have registered in time. If you have registered and change your mind, you can deregister until 21 September 2023.

The regular exam took place on 02 August 2023.