Theoretische Informatik
Theoretische Informatik II
Theoretische Informatik 

Theoretische Informatik II - Sommersemester 2025

Dozent: Dominik Scheder vorname.nachname@@informatik.tu-chemnitz.de

 

Termine: Vorlesung Dienstag 13:30 - 15:00 A10.205 Dominik Scheder
    Mittwoch 11:30 - 13:00 A10.205 Dominik Scheder
           
  Übung Montag 09:15 - 10:45 A10.205 Simon Schulze
    Freitag 09:15 - 10:45 A10.367.1 Johannes Tantow

 

Einschreibung: Bitte schreiben Sie sich in diesen OPAL-Kurs ein.

Prüfung: Die mündlichen Prüfungen finden in der Woche vom 11. August 2025 statt (33. Kalenderwoche). Hier finden Sie den Link zu einem Google-Dokument, in dem Sie sich eintragen können: https://www.tu-chemnitz.de/informatik/theoretische-informatik/TI-2/2025-08-pruefung-registration-A(3,6)=XXX/

wobei Sie XXX durch den tatsächlichen Wert der Ackermann-Funktion $A(3,6)$ ersetzen.

Hinweis zur mündlichen Prüfung: Es wird einen Aufgabenzettel geben, anhand dessen wir uns durch den Stoff bewegen werden. Wichtig: Ich erwarte nicht, dass wir alle Fragen in den 20 Minuten schaffen. Die Fragen dienen als Gerüst für die mündliche Prüfung. Hier sehen Sie zwei solcher Zettel aus meiner Zeit an der Hochschule Zittau/Görlitz, die ähnliche Themen wie hier abgedeckt haben, damit Sie sich einen Eindruck machen können (Zettel 1 und Zettel 2). Die Themenauswahl auf diesen beiden Zetteln ist als Beispiel zu betrachten. Die Themen der Modulprüfung muss nicht auf die Themen beschränkt sein, die auf diesen Zetteln vorkommen!

Vorlesungsskript

Übungsblätter

Sprechstunden

Dienstag, 11:00 - 12:00 und Donnerstag, 10:00 - 11:00. An anderen Tagen gerne auch, dann aber nach Absprache!

Inhalt

  1. Boolesche Schaltkreise.
  2. Unendliche Mengen.
  3. Berechenbarkeitsbegriff auf natürlichen Zahlen: Primitive Rekursion.
  4. Formale Sprachen, insbesondere: reguläre Sprachen, endliche Automaten, reguläre Ausdrücke.
  5. Kontextfreie Sprachen. Parser.
  6. Turingmaschinen und Berechenbarkeit.
  7. Komplexitätstheorie: Laufzeit und Speicherbedarf.

Literatur

  • Michael Sipser: Introduction to the Theory of Computing
  • Uwe Schöning: Theoretische Informatik - kurz gefasst

TUCaktuell