18 | 0:00:00 Starten0:00:07 Fortsetzung Informationstheorie0:01:06 Wiederholung Quellkodierung0:01:46 Kanalkodierung0:02:24 Codierung zum Schutz gegen Übertragungsfehler0:04:17 Paritätscodes - Einfach Binär0:07:27 Kreuzsicherung0:12:20 Paritätscodes0:13:33 Beweis0:15:09 Paritätscodes gegen Vertauschungsfehler0:18:42 Bsp: ISBN-100:18:56 ISBN0:19:59 …

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-…

16 | 0:00:00 Starten0:00:37 Kellerautomaten0:03:49 Satz0:05:15 Satz (2)0:06:09 Beweis0:30:19 Korollar0:30:41 Übersicht Chomsky-20:32:46 Exkurs0:34:16 Zwischenfazit zu kontextfreien Grammatiken0:36:10 Satz (3)0:38:18 Das Post'sche Korrespondenzproblem0:39:47 Beweis (2)0:43:33 Beweisskizze0:44:07 Beweis (3)0:45:50 Sprache der korrekten Rechenwege0:51…

15 | 0:00:00 Starten0:00:07 Beweis0:03:26 Kellerautomaten0:09:17 Kellerautomaten - Visualisierung0:10:09 Kellerautomaten - Arbeitsweise0:18:33 Kellerautomaten - Beispiel0:27:20 Kellerautomaten - Beispiel 20:31:02 Satz (1)0:35:44 Satz (2)0:39:19 Satz (3)Von Prof. Dr. Dorothea Wagner

14 | 0:00:00 Starten0:00:07 Wiederholung0:12:03 Ogden´s Lemma für kontextfreie Sprachen0:14:31 Beweis0:29:20 Beweis - Teil 10:30:23 Beweis - Teil 20:39:23 Beweis - Teil 30:41:58 Nutzlose Variablen0:43:38 Schritt 10:47:24 Beispiel: Schritt 10:51:28 Schritt 20:53:16 Beispiel: Schritt 20:56:45 Korollar0:59:27 Beispielgraph…

13 | 0:00:00 Starten0:00:31 Wiederholung0:02:13 Die Chmosky Hierarchie0:08:16 Syntaxbäume0:10:28 Syntaxbäume - Beispiel0:15:54 Links/Rechtsabteilung, Eindeutigkeit0:17:31 Beispiel0:19:37 Chomsky-Normalform0:20:56 Die Chomsky Hierarchie0:21:21 Chomsky-Normalform0:31:01 Schritt 10:34:21 Schritt 20:38:20 Schritt 30:49:34 Schritt 40:53:36 Abhängigkeits…

12 | 0:00:00 Starten0:00:28 Grammatiken0:01:26 Beispiele0:05:33 Grammatiken0:07:12 Bemerkungen0:08:32 Beispiel0:09:22 Die Chomsky Hierarchie0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit0:24:58 Beweis - Beschreibung der Grammatik G0:28:28 Beweis - Zusammenfassung0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit0:32:04 Zwischenfazit0:34…

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…

10 | 0:00:00 Starten0:03:37 VerallgemeinerteNP-Schwere0:07:17 Das Problem INTEGER PROGRAMMING0:26:15 Pseudopolynomiale Algorithmen0:29:56 Beispiel: Problem KNAPSACK0:40:20 Starke NP-Vollständigkeit0:44:14 Absolute Approximationsalgorithmen0:46:31 Das allgemeine KNAPSACK-Suchproblem0:57:09 Approximation mit relativer Gütegarantie0:59:53 Beispiel: Gr…

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-…

06 | 0:00:00 Starten0:00:54 Definitionen zur TM0:05:21 Notation: Konfiguration0:07:49 Beispiel: Konfiguration0:20:00 Definition: berechenbar / totalrekursiv0:22:30 Beispiel0:26:57 Entscheidbarkeit und Berechenbarkeit0:30:18 Korollar0:33:13 Die Church´sche These0:36:20 Erweiterungen der Turing-Maschine0:39:17 Die universelle Turing-Maschine0:45:24 D…

05 | 0:00:00 Starten0:00:54 Definitionen zur TM0:05:56 Notation: Konfiguration0:07:50 Beispiel: Konfiguration0:20:37 Definition: berechenbar / totalrekursiv0:23:01 Beispiel0:27:27 Entscheidbarkeit und Berechenbarkeit0:30:19 Korollar0:33:21 Die Church´sche These0:36:38 Ertweiterungen der Turing-Maschine0:39:39 Die universelle Turing-Maschine0:44:35 …

04 | 0:00:00 Starten0:00:12 Endliche Automaten, reguläre Sprachen0:00:57 Frage0:01:40 Äquivalenz0:04:24 Der Äquivalenzklassenautomat0:06:29 Vorgehensweise0:08:44 Frage0:10:29 Antwort0:13:49 Definitionen: Rechtsinvarianz und Index0:17:08 Nerode-Relation0:20:55 Satz von Nerode0:24:06 Beweis zu Satz von Nerode: (1) – (2)0:28:54 Beweis zu Satz von Nero…

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:…

01 | 0:00:00 Starten0:00:30 Ziele der Vorlesung TGI0:13:46 Wiederholung aus Grundbegriffe der Informatik0:17:17 Wörter0:21:24 Formale Sprachen0:31:12 Reguläre Sprachen0:36:04 Reguläre Ausdrücke0:39:46 Reguläre Ausdrücke – Beispiele0:43:48 Endliche Automaten0:53:24 Kontextfreie Grammatiken0:58:07 Beispiel Kontextfreie Grammatiken…