Theoretische Informatik II - SoSe 2025
Nachdem in der Theoretischen Informatik I Algorithmen für kombinatorische Probleme und ihre Effizienz behandelt wurden, geht es in der Vorlesung Theoretische Informatik II um prinzipiellere Fragen:
Welche Probleme sind überhaupt algorithmisch behandelbar? Kann man Probleme angeben, die sich prinzipiell nicht durch Computer behandeln lassen? Es stellt sich heraus, dass sich derartige Probleme relativ leicht angeben lassen.
Darüber hinaus geht es um die Frage, welche Probleme sich effizient behandeln lassen. Auch hier lassen sich Probleme angeben, bei denen das (vermutlich) nicht der Fall ist. Das sind die so genannten NP-vollständigen Probleme.
Die skizzierten Themenkreise lassen sich am günstigsten im Kontext der Automaten und formalen Sprachen behandeln. Dadurch ergibt sich, dass einige Grundlagen des Compilerbaus in der Vorlesung fast umsonst mitbehandelt werden.
Einige Stichwörter zur Vorlesung:
- 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.
Vorlesungen:
- Dienstag 13:30-15:00 Uhr (Prof. Dr. Dominik Scheder, A10.205)
- Mittwoch 11:30-13:00 Uhr (Prof. Dr. Dominik Scheder, A10.205)
Übungen: