Claim OwnershipTheoretische Grundlagen der Informatik, Vorlesung, WS18/19
Subscribed: 63Played: 338
Subscribe
Description
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen.
Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: http://webcast.kit.edu
Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: http://webcast.kit.edu
18 Episodes
Reverse
18 |
0:00:00 Start
0:00:26 Werbung
0:01:14 Vorlesung ,,Algorithmen für planare Graphen""
0:02:53 Proseminar ,,Algorithmen für NP-schwere Probleme""
0:05:28 ICPC Praktikum
0:07:38 Kodierung zum Schutz gegen Übertragungsfehler
0:12:34 Paritätscodes - Einfach binär
0:18:38 Kreuzsicherung
0:25:26 Paritätscodes
0:28:05 Beweis
0:30:29 Paritätscodes gegen Vertauschungsfehler
0:36:17 Bsp:ISBN-10
0:40:51 Block-Codes
0:41:50 Hamming-Distanz und Fehlerkorrektur
0:46:58 Block-Codes
0:49:17 Beispiel
17 |
0:00:00 Start
0:00:05 Thema dieses Kapitels
0:05:25 Material für Informationstheorie
0:06:28 Information
0:08:45 Beispiel
0:16:13 Wiederholung: Rechenregeln Logarithmus
0:17:53 Beispiel 2
0:20:11 Entropie
0:25:08 Bemerkung zur Entropie
0:29:31 (Platzsparende) kodierungen
0:33:25 Präfix-Codes
0:35:00 Codierungsbäume
0:41:32 Quellenkodierungstheorem
0:43:27 Beispiel: Schanon-Fano Kodierung
0:51:21 Beispiel: Huffman-Kodierung
0:56:30 Vorbereitendes Lemma
1:05:38 Beweis –Induktionsschluss
1:11:48 Nachteile der Huffman-Kodierung
1:15:27 Lauflängenkodierung
1:21:34 Geometrische Verteilung
1:23:07 Kodierung zum Schutz gegen Übertragungsfehler
16 |
0:00:00 Start
0:00:32 Letzte Vorlesung
0:02:51 Wdh.: Greibach-Normalform, Kellerautomat
0:06:32 Beispiel - Greibach-Normalform
0:12:41 Beispiel - Kellerautomat
0:17:47 Beweis: Greibach-Normalform -NPDA
0:26:14 Übersicht
0:27:41 Beweis:NPDA - kontextfreie Grammatik
0:51:16 Exkurs
0:55:11 Zwischenfazit zu kontextfreien Grammatiken
0:57:12 Unentschedbare Probleme für kontextfreie Grammatiken
1:00:05 Das Post'sche Korrespondenzproblem
1:01:10 Beweis
1:06:43 Eindeutigkeit von kontextfreien Grammatiken
1:09:01 Sprache der korrekten Rechenwege
1:27:34 Zusammenfassung Chomsky-Hierarchie
15 |
0:00:00 Start
0:02:19 weitere Eigenschaften kontextfreier Sprachen
0:12:03 Ein maschinellmodell für Chomsky-2
0:18:04 Greibach-Normalform
0:21:01 Beweis - Ersetzung
0:29:08 Beweis - Definitionen
0:30:57 Beweis - Invarianten
0:36:26 Beweis - Verfahren Schritt 1
0:45:30 Beweis - Verfahren Schritt 2
0:50:05 Beweis - Verfahren Schritt 3
0:53:21 Kellerautomaten
0:59:08 Kellerautomaten - Arbeitsweise
1:15:30 Ein Maschinenmodell für Chomsky-2
14 |
0:00:00 Start
0:06:36 Das Pumping-Lemma für kontextfreie Sprachen
0:10:42 Ogden´s Lemma für kontextfreie Sprachen
0:14:06 Beweis von Odgen´s Lemma
0:29:34 Bemerkung
0:30:52 Echtheit der Chomsky-Hierarchie
0:32:47 Beweis - Teil 1
0:33:46 Beweis - Teil 2
0:48:59 Beweis - Teil 3
0:55:39 Eigenschaften kontextfreier Sprachen
0:58:31 Nutzlose Variablen
1:00:00 Schritt 1
1:07:39 Schritt 2
13 |
0:00:00 Start
0:00:09 Letzte Vorlesung
0:08:30 heutige Themen
0:09:05 Syntaxbäume
0:13:44 Eindeutigkeit
0:19:08 Chomsky-Normalform
0:52:24 CYK-Algorithmus
12 |
0:00:00 Start
0:00:31 Grammatiken, Beispiele
0:09:52 Grammatiken, Bemerkungen
0:16:13 Die Chomsky Hierarchie
0:29:17 Chomsky-0 Grammatiken und Semientscheidbarkeit
0:36:03 Beweis - Beschreibung der Grammatik G
0:42:30 Beweis - Zusammenfassung
0:49:13 Chromsky-3 Grammatiken und reguläre Sprachen
1:02:28 Chromsky-1 Grammatiken bzw. kontextsensitive Sprachen
1:09:49 Wiederholung: Das Problem CLIQUE
1:20:25 Typ-2 / Kontextfreie Grammatiken
11 |
0:00:00 Start
0:00:15 Letzte Vorlesung
0:03:09 Definition
0:09:54 Metrisches TSP
0:20:53 Bemerkungen zur Approximierbarkeit
0:23:46 Approximationsschemata
0:29:50 Ein FPTAS für max-KNAPSACK
0:53:01 min-VERTEX-COLOR und min-EDGE-COLOR
0:54:39 Nicht-Existenz eines FPTAS
1:04:07 Approximierbarkeit von COLOR
1:14:46 Ein allgemeines Resutat
10 |
0:00:00 Start
0:01:01 Verallgemeinerte NP-Schwere
0:03:38 Das Problem INTEGER PROGRAMMING
0:07:18 INTEGER PROGRAMMING ist NP-schwer
0:15:12 Bemerkungen
0:23:00 Pseudopolynomiale Algorithmen
0:33:54 Starke NP-Vollständigkeit
0:40:34 Absolute Approximationsalgorithmen
0:44:01 Das allgemeine KNAPSACK-Suchproblem
0:47:08 Negativ-Resultat
0:50:24 (Kontrapositions-)Beweis
0:55:47 Approximation mit relativer Gütegarantie
0:57:13 Genereller Ansatz
1:06:09 Grenzen für den Greedy-Algorithmus
09 |
0:00:00 Start
0:00:57 Letzte Vorlesung
0:20:50 Diese Vorlesung
0:20:57 Das Problem PARTITION
0:28:58 Das Problem KNAPSACK
0:40:03 Zusammenfasung
0:59:24 Das Problem Subgraphisomorphie
1:00:45 Das Problem Graphisomorphie
1:02:28 Die Polynomielle Hierarchie
1:11:31 Suchprobleme
1:17:35 Aufzählungsprobleme
08 |
0:00:00 Start
0:00:22 Letzte Vorlesung
0:06:59 Plan für heute
0:09:46 Pas Problem 3SAT
0:11:29 Beweis: NP-Vollständigkeit von 3SAT
0:30:58 Das Problem 2SAT
0:31:54 Das Problem MAX2SAT
0:33:51 Das Problem CLIQUE
0:35:32 Beweis: NP - Vollständigkeit von CLIQUE
0:48:25 Das Problem COLOR
0:50:25 NP-Vollständigkeit von 3COLOR
0:52:26 Konstruktion von 3COLOR-Instanz G
0:55:48 Polynomialität der Reduktion
0:56:35 Instanz/ erfüllbar
1:03:01 Zwischenstand Polynomiale Reduktion
1:13:41 Das Problem EXACT COVER
1:16:23 NP - Vollständigkeit von EXACT COVER
1:18:00 Konstruktion
07 |
0:00:00 Start
0:00:03 NP-Vollständigkeit für Sprachen
0:03:38 NP-Vollständigkeit für Entscheidungsprobleme
0:05:28 Transitivität der poly. Transformation
0:06:59 Beobachtung
0:10:58 Das Problem SAT (satisfiability)
0:16:04 Weitere Beispiele für SAT-Instanzen
0:17:42 Der Satz von Cook (Steven Cook, 1971)
0:22:03 Beweis: das Setup
0:28:37 Beweis: Konstruktion der Variablen
0:32:52 Beweis: Zielsetzung
0:37:44 Beweis: Konstruktion der Klauseln
0:38:03 Klauselgruppe 1:
0:39:46 Klauselgruppe 2:
0:40:36 Klauselgruppe 3:
0:41:32 Klauselgruppe 4:
0:44:44 Klauselgruppe 5:
0:45:27 Klauselgruppe 6:
0:47:04 Klauselgruppe 6,1:
0:48:59 Klauselgruppe 6,2:
0:52:30 Zwischenbilanz
0:58:13 Polynomialität der Transformation
0:58:34 Polynomialität - Klauselgruppe 1:
0:59:31 Polynomialität - Klauselgruppe 2:
1:00:12 Polynomialität - Klauselgruppe 3:
1:00:45 Polynomialität - Klauselgruppe 4:
1:01:31 Polynomialität - Klauselgruppe 5:
1:01:44 Polynomialität - Klauselgruppe 6,1:
1:02:15 Polynomialität - Klauselgruppe 6,2:
1:04:09 Heute im Rückblick: Der Satz von Cook
06 |
0:00:00 Start
0:00:09 Letzte Vorlesung
0:03:24 Die Universelle Sprache
0:14:02 Satz von Rice – Motivation
0:17:55 Bemerkungen zum Satz von Rice
0:22:13 Das Post'sche Korrespondenzproblem
0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen
0:32:25 Komplexitätstheorie
0:34:36 Wie sieht ein Problem aus?
0:37:46 Definition: Problem
0:40:37 Definition:Kodierungsschema
0:46:51 Äquivalenz von Kodierungsschemata
0:48:35 Entscheidungsprobleme
0:50:57 Korrespondenz von Entscheidungsproblemen und Sprachen
0:52:43 Entscheidungsprobleme und Turing-Maschinen
0:54:34 Zeitkomplexität
0:57:38 Die Klasse P
1:01:00 Schwierigkeit von Entscheidungs- und Optimierungsproblem
1:04:53 Algorithmus OPT-TOUR (als Beweis)
1:10:08 Bemerkungen zum Algorithmus
1:13:17 Zwischenstand Komplexitätstheorie
1:17:01 Die Nichtdeterministische Turing-Maschine
1:23:02 Übertragung auf Entscheidungsprobleme II
05 |
0:00:00 Start
0:00:10 Letzte Vorlesung
0:09:00 Beispiel - Turing Maschine
0:13:57 Bemerkungen zur TM
0:15:23 Definition zur TM
0:18:43 Notation: Konfiguration
0:19:54 Beispiel: Konfiguration
0:26:21 Definition: berechenbar / totalrekursiv
0:28:10 Beispiel
0:34:10 Entscheidbarkeit und Berechenbarkeit
0:39:01 Korollar
0:40:51 Die Church'sche These
0:44:25 Erweiterung der Turing-Maschine
0:51:23 Die Universelle Turing-Maschine
0:54:51 Die Gödelnummer
0:57:52 Die Gödelnummer - Bemerkungen
1:00:43 Die Gödelnummer - Beispiel
1:01:53 Definition
1:04:27 Die Diagonalsprache
1:09:32 Die Diagonalsprache - Veranschaulichung
1:10:40 Unentscheidbarkeit der Diagonalsprache
1:13:33 Korollar
1:14:03 Paradoxien und Selbstbezüglichkeit
1:15:46 Halteproblem
04 |
0:00:00 Start
0:00:03 letzte Vorlesung - alternative Sicht
0:04:48 Alternative Sicht - Beispiel
0:13:20 Heutiges Thema (Frage, Antwort)
0:20:21 Definitionen: Rechtsinvarianz und Index
0:27:56 Nerode-Relation
0:31:10 Satz von Nerode
0:50:10 Korollar
0:52:20 Minimalität des Äquivalenzklassenautomats
0:59:19 Zusammenfassung
1:07:12 Turing-Maschinen und Berechenbarkeit
1:08:42 Die Registermaschine (RAM)
1:14:26 Die Turing-Maschine (TM)
03 |
0:00:00 Start
0:00:03 Rückblick
0:04:19 Verallgemeinertes PL für reguläre Sprachen
0:16:10 Beispiel (3) - Anwendung Verallgemeinertes PL
0:24:06 Minimierung von Automaten - Äquivalenzklassenautomat
0:27:47 Finden nicht überflüssiger Zustände
0:31:00 Beispiel
0:37:13 Äquivalenz
0:46:38 Der Äquivalenzklassenautomat
1:04:07 Zeugen für Nichtäquivalenz
1:09:26 Vorgehensweise
1:15:59 Zusammenfassung
01 |
0:00:00 Start
0:00:11 Endliche Automaten und Reguläre Sprachen
0:14:38 Nichtdeterministische endliche Automaten
0:21:06 Beispiel für NEA's
0:27:09 Äquivalenz von NEA's und DEA's
0:28:57 Beispiel Potenzmengenkonstruktion
1:11:43 Zusammenfassung
02 |
0:00:00 Start
0:00:07 Letzte Vorlesung
0:04:01 Entfernen von e-Übergängen
0:15:37 EA - Regularität
0:15:51 Beweis
0:33:04 Beispiel
0:39:16 Satz von Kleene
0:40:27 Frage: Was können endliche Automaten nicht?
0:45:19 Pumping-Lemma für reguläre Sprachen
0:58:23 Verwendung des Pumping-Lemmas
1:05:20 Beispiel zum PL
1:18:10 Zusammenfassung
Comments
Download from Google Play
Download from App Store
United States