Komplexität von Algorithmen, Optimierungsprobleme
Channel: ThI Videos
Date: 16/03/2020

In diesem Video erklären wir die Definition von Optimierungsproblemen an Hand des Beispiel MinTSP, betrachten die Klasse NPO und PO,
sprechen über Optimalität von Lösungen, definieren ein zu einem Optimierungsproblem zugehöriges Entscheidungsproblem sowie zeigen Zusammenhänge zu den Klassen NP und P.


0:00 Definition: Optimierungsproblem
2:11 Problem: MinTSP

4:55 Definition: NPO
5:48 MinTSP in NPO

8:13 Effizienzanforderungen
8:50 Definition: optimale Lösung
9:37 Definition: PO
10:22 Definition: Entscheidungsproblem zu Optimierungsproblem

11:17 Lemma 1+2
11:43 Beweis Lemma 1