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/
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
- Boolesche Schaltkreise.
- Unendliche Mengen.
- Berechenbarkeitsbegriff auf natürlichen Zahlen: Primitive Rekursion.
- Formale Sprachen, insbesondere: reguläre Sprachen, endliche Automaten, reguläre Ausdrücke.
- Kontextfreie Sprachen. Parser.
- Turingmaschinen und Berechenbarkeit.
- Komplexitätstheorie: Laufzeit und Speicherbedarf.
Literatur
- Michael Sipser: Introduction to the Theory of Computing
- Uwe Schöning: Theoretische Informatik - kurz gefasst
