Realistische Probleme (Komplexitätstheorie / Theoretische Informatik)

Ein paar Probleme aus der Graphentheorie (z.B. Cliquenproblem und Stabilitätsproblem) sowie Überlegungen zu sinnvollen Codierungen und polynomialer Reduktion.
* Das GANZ NEUE Buch: weitz.de/GDM/
* Das NEUE Buch: weitz.de/PP/
* Skript: weitz.de/files/ti-skript.pdf
* Ausführliche Playlist zur Komplexitätstheorie (Sommersemester 2014): • Theoretische Informati...
* Das Stabilitätsproblem zum Ausprobieren: weitz.de/indset/
* Das Video im Playlist-Kontext: weitz.de/y/LguH9C9HrUk?list=PL...
* Liste aller Videos: weitz.de/haw-videos/
* Das etwas andere Mathe-Lehrbuch: weitz.de/KMFI/
* "FAQ": weitz.de/youtube.html
00:00 Sinnvolle Codierung von Entscheidungsproblemen
07:28 Grundbegriffe der Graphentheorie
12:40 Optimierungs-, Funktions- und Suchprobleme
19:01 Kürzester Weg durch einen Graphen
25:27 Das Cliquenproblem
32:55 Ein nichtdeterministischer Algorithmus
38:47 Das Stabilitätsproblem
42:42 Polynomiale Reduktion