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 / Johannes Tantow | |
| Mittwoch | 15:30 - 17:00 |
Rasmus Eder / Johannes Tantow |
Hinweis: Schreiben Sie sich bitte in diesen OPAL-Kurs ein.
Vorlesungsskript
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
