Folien
V0.pdf
V1-0.pdf
V2-0.pdf
V3-0.pdf
V4-0.pdf
V5-0.pdf
V6-0.pdf
V7-0.pdf
V8-0.pdf
V9-0.pdf
V10-0.pdf
V11-0.pdf
Notizen
Die Chomsky-Hierarchy
Turingmaschinen zu Grammatik
WHILE-Programme
Entscheidungsproblem ⇒ Wortproblem
Wortproblem für Turing Maschinen
semi-entscheidbar ⇒ Halteproblem
spezielles Halteproblem (Diagonalisierung)
Orakel-Turingmaschinen
Turing-Reduktionen
Reduktionen
Satz von Rice
Äquivalenzproblem
Leerheitsproblem
Church-Turing These
Erweiterte Church-Turing These
Laufzeit und Platz-komplexitätsklasen
Polynomialzeitreduktionen
SAT
3-SAT
Vertex Cover
Clique
Independent Set
Hamilton Kreis
Travelling Salesperson Problem
3-Color
Die Exponential Time Hypothesis
Strong Exponential Time Hypothesis
Blätter
blatt01.pdf THI2 UE01
blatt02.pdf THI2 UE02
blatt03.pdf
blatt04.pdf
blatt05.pdf THI2 UE 05
blatt06-1-0.pdf THI2 UE 06
blatt07.pdf
blatt08.pdf
blatt09.pdf Vertex Cover zu Feedback Vertex Set
blatt10.pdf
blatt11-0.pdf
Probeklausur
probeklausur2024-1-0.pdf
THI2 Probeklausur
THI2 Probeklausur Liam
THI2 Probeklausur 2
probeklausur2024-2-0.pdf