Theoretische Informatik II
Sommersemester 2022
Vorlesung: Theoretische Informatik II
Hinweis zu Theoretische Informatik II
Die Vorlesung vom 13.07.2022 und das Video der elften Übung sind online.
Hinweis zu Theoretische Informatik II
Anstatt der Übungen am Freitag, dem 15.07.2022, und am Montag, dem 18.07.2022, biete ich (Julian Pape-Lange) nochmal zwei (Präsenz-)Fragestunden an.
Die erste Fragestunde ist am Freitag, dem 15.07.2022 ab 09:15 Uhr und wir treffen uns in/vor dem Raum 1/375 (neu: A10.375)
Die zweite Fragestunde ist am Mittwoch, dem 20.07.2022 ab 11:30 Uhr und wir treffen uns in/vor dem Raum 1/368A (neu: A10.368.1)
|
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 |
Wenn Raum 1/205 besetzt ist, weichen wir auf 1/204 aus.
|
|||||||||||||||
|
Links |
|