17 | 0:00:00 Starten0:01:45 Thema dieses Kapitels0:04:52 Material für Informationstheorie0:05:32 Information0:12:45 Wiederholung: Rechenregeln Logarithmus0:13:53 Definition Information0:14:52 Entropie0:19:16 Bemerkung zur Entropie0:19:31 Entropie einer Münze mit Wkt p für Zahl0:20:44 (Platzsparende) Codierungen0:22:12 Codierungsbäume0:26:49 Präfix-…
11 | 0:00:00 Starten0:02:50 Approximation mit relativer Gütegarantie0:03:31 Definition0:04:49 Approximierbarkeit von COLOR0:18:45 Approximierbarkeit von TSP0:28:12 Approximationsschemata0:38:45 Ein FPAS für KNAPSACK (1)0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK0:43:49 Ein FPAS für KNAPSACK (2)0:58:51 Ein allgemeineres Result…
09 | 0:00:00 Starten0:06:41 Das Problem SUBSET SUM0:07:46 NP-Vollständigkeit von SUBSET SUM0:24:03 Das Problem PARTITION0:31:06 Das Problem KNAPSACK0:37:32 Auswirkungen auf die Frage P=NP0:45:42 Zusammenfassung0:47:57 Die Klassen NPI, co-P und co-NP0:54:22 Das TSP-Komplement-Problem0:57:40 Lemma1:00:00 Bemerkung1:01:25 Das Problem Subgraphisomorphi…
08 | 0:00:00 Starten0:00:37 Wiederholung: NP-Vollständigkeit0:06:10 Wiederholung: Transitivität der poly. Transformation0:06:40 Wiederholung: Korollar0:07:37 Wiederholung: Das Problem SAT (satisfiability)0:12:17 Das Problem 3-SAT0:13:13 Beweis: NP-Vollständigkeit von 3-SAT0:30:07 Das Problem 2SAT0:34:40 Das Problem MAX2SAT0:38:02 Das Problem CLIQUE…
07 | 0:00:00 Starten0:01:06 Die Klasse P0:03:19 Die Klasse NP0:04:47 Die Nichtdeterministische Turingmaschine0:05:17 Zeitkomplexität für NTM0:08:55 Große Frage der Theoretischen Informatik0:11:38 NP-Vollständigkeit0:24:35 Transitivität der poly. Transformation0:25:46 Korollar0:28:28 Das Problem SAT (satisfiability)0:31:05 Weitere Beispiele für SAT-…
02 | 0:00:00 Starten0:00:24 Letzte Vorlesung0:09:53 Entfernen von e-Übergängen0:20:42 EA – Regulärität0:22:44 Beweis: EA – Regulärität0:44:02 Beispiel0:54:15 Satz von Kleene0:55:54 Frage: Was können endliche Automaten nicht?0:59:14 Pumping-Lemma für reguläre Sprachen1:10:10 Bemerkung1:11:49 Beispiel (1) zum PL1:14:18 Beispiel (2) zum PL1:18:31 Beis…
03 | 0:00:00 Starten0:00:25 Verallgemeinertes PL für reguläre Sprachen0:17:18 Kapitel Minimierung von Automaten und Äquivalenzklassenautomat0:20:14 Frage: Kann man konstruktiv die Anzahl der Zustände eines deterministischen endlichen Automatens erheblich verringern?0:22:04 Beispiel0:34:34 Äquivalenz0:37:22 Der Äquivalenzklassenautomat0:48:03 Frage:…