Theoretische Informatik I

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.

Schließlich einige Stichworte zum Thema:

• Automaten
• Grammatiken, Chomsky Hierarchie
• Turing Maschinen
• Nicht-Entscheidbarkeit
• NP-Vollständigkeit.

Schöning: Theoretische Informatik - kurz gefasst, Spektrum Verlag.

Aho, Hopcroft, Ullmann: Computabilitiy and formal languages.

• Übungsunterlagen
• Folien zum Satz von Cook