Theoretische Informatik II
Sommersemester 2023
Vorlesung: Theoretische Informatik II
Hinweis zu Theoretische Informatik II
In der 12. Übung habe ich behauptet, es wäre NP-schwer zu entscheiden, ob ein Graph planar ist. Diese Aussage war falsch. Es kann sogar sehr effizient auf planartät getestet werden.
Hinweis zu Theoretische Informatik II
Der vierzehnte Übungszettel ist online.
|
SWS (V/Ü/P) |
4/2/0 | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Voraussetzungen |
Theoretische Informatik I |
||||||||||||||||||||
|
Inhalt |
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:
|
||||||||||||||||||||
|
Literatur |
Schöning: "Theoretische Informatik - kurz gefasst", Spektrum Verlag. |
||||||||||||||||||||
|
Termine |
|
||||||||||||||||||||
|
Links |