Theoretische Informatik II
Sommersemester 2020
Vorlesung: Theoretische Informatik II
Hinweise zu Theoretische Informatik II
Die Vorlesung wird sich sehr stark an dem Buch "Theoretische Informatik - kurz gefasst" von Uwe Schöning orientieren. Wir empfehlen Ihnen daher, sich dieses Buch zu besorgen.
Wenn Sie fragen haben, können Sie gerne eine Mail an Julian Pape-Lange ( julian.pape-lange@…) schreiben.
|
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 |
|