Theoretische Informatik II - Sommersemester 2026
| Dozent: | Dominik Scheder vorname.nachname@@informatik.tu-chemnitz.de |
| Termine: | Vorlesung | Dienstag | 13:45 - 15:15 | A10.205 | Dominik Scheder |
| Mittwoch | 11:30 - 13:00 | A10.205 | Dominik Scheder | ||
| Übung | Montag | 09:15 - 10:45 | A10.205 | Rasmus Eder | |
| Mittwoch | 15:30 - 17:00 | A10.375 | Johannes Tantow |
Prüfung:
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
Übung
Bitte melden Sie sich in diesem Opal-Kurs an und schreiben sich in eine der beiden Übungen ein (Montag oder Mittwoch). Im Opal werden wir auch die jeweiligen Übungsblätter veröffentlichen.
Sprechstunden
Machen Sie einfach persönlich oder per Email einen Termin mit mir aus!
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
