Claim OwnershipTheoretische Grundlagen der Informatik, Vorlesung, WS17/18
Subscribed: 64Played: 253
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. Vorlesungsaufzeichnung: http://webcast.kit.edu
19 Episodes
Reverse
19 |
0:00:00 Starten
0:01:39 Rückblick: Chomsky Typ 3
0:04:53 Rückblick: Chomsky-3 Verfahren
0:22:29 Rückblick: Chomsky-2
0:35:13 Rückblick: Chomsky-0/1
0:40:32 Entscheidbarkeit
0:47:05 Domino
0:53:04 2-PLAYER COOPERATIVE DOMINOES
18 |
0:00:00 Starten
0:03:53 Information
0:12:40 Entropie
0:18:49 (Platzsparende) Codierung
0:20:33 Codierungsbäume
0:25:54 Präfix-Codes
0:28:27 Quellencodierungstheorem
0:29:58 Beispiel: Shannon-Fano Codierung
0:38:11 Beispiel: Huffman-Codierung
0:46:53 Vorbereitendes Lemma
0:56:09 Beweis - Induktionsschluss
1:05:03 Lauflängenkodierung
17 |
0:00:00 Starten
0:00:24 Übersicht Chomsky-2
0:03:13 WDh.: Greibach-Normalform, Kellerautomat
0:09:07 Beweis
0:47:57 Korollar
0:48:46 Exkurs
0:50:37 Zwischenfazit zu kontextfreien Grammatiken
0:53:05 Unentscheidbare Probleme für kontextfreie Grammatiken
0:55:26 Das Post'sche Korrespondenzproblem
1:03:51 Eindeutigkeit von kontextfreien Grammatiken
1:05:26 Beweisskizze
1:09:07 Sprache der korrekten Rechenwege
16 |
0:00:00 Starten
0:01:12 Chomsky Hierarchie
0:15:28 Chomsky-0-Grammatiken und DTM's
0:28:42 Konstruktion von Grammatiken
0:46:58 Sprache der korrekten Klammerausdrücke
0:57:09 Chomsky-Normalform
1:08:19 Der Cocke-Younger-Kasami Algorithmus
15 |
0:00:00 Starten
0:00:19 Kontextfreie Sprachen, Kontextfreie Grammatiken
0:06:01 Pumping-Lemma für kontextfreie Sprachen
0:08:05 Ogden's Lemma für kontextfreie Sprachen
0:23:12 Satz
0:37:41 Nutzlose Variablen
0:54:28 Korrolar
0:58:14 Beispielgraph
14 |
0:00:00 Starten
0:00:22 Die Chomsky Hierarchie
0:08:09 Typ-2/Kontextfrwiw Grammatiken
0:08:51 Typ-2/ Grammatiken: Beispiel 1
0:09:25 Typ-2/ Grammatiken: Beispiel 2
0:11:56 Syntacbäume
0:13:34 Syntaxbäume Beispiel
0:18:27 Links/ Rechtsabteilung, Eindeutigkeit
0:20:14 Beispiel
0:23:08 Chomsky- Normalform
0:30:41 Schritt 1
0:34:39 Schritt 2
0:38:44 Schritt 3
0:47:14 Schritt 4
0:52:48 Abhängigkeitsgraph
0:54:23 Schritt 4- Phase 1
0:56:45 Schritt 4 - Phase 2
1:01:32 Sonderbehandlung
1:02:24 Der CYK-Algorithmus
1:04:53 Beweis - Beschreibung des CYK-Algorithmus
1:09:04 CYK- Algorithmus - Beispiel
1:10:47 Beweis - Beschreibung des CYK-Algorithmus
1:12:54 CYK-Algorithmus - Vorgehen
1:24:32 Ergebnisse zum Wortproble
12 |
0:00:00 Starten
0:02:26 Approximation mit relativer Gütegarantie
0:03:38 Beispiel: Greedy-Algorithmus für KNAPSACK
0:04:51 Definition
0:06:07 Approximierbarkeit von COLOR
0:20:05 Approximierbarkeit von TSP
0:35:12 Approximationsschemata
0:45:02 Ein FPAS für KNAPSACK
1:04:10 Ein allgemeineres Resultat
13 |
0:00:00 Starten
0:01:15 Grammatiken
0:06:22 Bemerkungen
0:09:12 Die Chomsky Hierarchie
0:19:54 Chomsky-0 Grammatiken und Semientscheidbarkeit
0:22:25 Beweis- Beschreibung der Grammatik G
0:28:36 Chomsky-3-Grammatiken und reguläre Sprachen
0:37:52 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen
0:41:58 Wiederholung: Das Problem CLIQUE
0:49:01 Typ-2/ Kontextfreie Grammatiken
11 |
0:00:00 Starten
0:00:57 Nichtdeterministische Turingmaschine(n)
0:06:41 Die Klassen NP und ANP
0:11:10 A-NTMs sind nicht mächtiger als NTMs
0:23:31 Polynomiale Transformation
0:25:23 Polynomielle Transformation
0:29:26 Komplexitätsklassen und Werkzeugkasten
0:38:14 2SAT ∈ P
0:54:26 NP-Vollständigkeit
0:57:35 MAX2SAT
1:11:27 Tipps für Reduktion auf Max2Color
10 |
0:00:00 Starten
0:03:27 Das Problem SUBSET SUM
0:04:50 NP-Vollständigkeit von SUBSET SUM
0:18:59 Das Problem Partition
0:25:38 Das Problem KNAPSACK
0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK
0:32:43 Auswirkung auf die Frage P=NP
0:37:29 Zusammenfassung
0:41:47 Die Klassen NPI, co-P und co-NP
0:45:07 Vermutete Situation
0:50:03 Das TSP-Komplement-Problem
0:52:03 Lemma
1:02:23 Suchprobleme
1:05:08 Beispiel: TSP-Suchproblem
1:06:53 Beispiel: Hamilton-Kreis Suchproblem
1:08:09 Aufzählungsprobleme
1:09:11 Reduzierbarkeit für Suchprobleme
1:12:28 Orakel-Turing-Maschine
1:13:56 Orakel-TM: Verhalten im Fragezustand
1:16:35 Turing-Reduktion
1:19:07 NP-schwer
1:22:30 Beweisskizze
09 |
0:00:00 Starten
0:00:39 NP-Vollständigkeit
0:02:03 Transitivität der poly. Transformation
0:02:31 Korollar
0:03:49 Das Problem 3-SAT
0:05:37 Beweis: NP-Vollständigkeit von 3-SAT
0:20:16 Das Problem 2SAT
0:22:09 Das Problem MAX2SAT
0:24:18 Das Problem CLIQUE
0:27:48 Beweis: NP-Vollständigkeit von CLIQUE
0:36:44 Das Problem COLOR
0:37:57 Beweis: NP-Vollständigkeit von 3COLOR
0:39:06 Konstruktion von 3COLOR-Instanz G
0:43:16 Beispielgraph zur Reduktion
0:45:12 Polynomialität der Reduktion
0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar
0:45:57 Instanz G ist 3-färbbar
0:50:30 Das Problem EXACT COVER
0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER
0:55:30 Konstruktion von (X,S)
1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung
08 |
0:00:00 Starten
0:00:17 Gliederung
0:01:30 Turingmaschinen
0:19:04 Erweiterung von Turingmaschinen
0:19:18 Mehrere Spuren
0:23:26 Mehrere Bänder
0:25:01 Erweiterte Turingmaschinen
0:31:56 Entscheidbarkeit
0:32:09 Entscheidbarkeit - Definitionen
0:36:34 Entscheidbarkeit - Zusammenhänge
0:45:32 Entscheidbarkeit - Überblick
0:46:31 Entscheidbarkeit - Komplementbildung
0:48:09 Entscheidbarkeit - Überblick
0:51:01 Entscheidbarkeit - Beispiele
0:51:33 Diagonalsprache
0:55:42 Halteproblem
0:58:52 Iniverselle Sprache
0:59:23 Post'sches Korrespondenzproblem
1:02:59 Hilberts zehntes Problem
1:08:44 Äquivalenzproblem
1:09:35 Entscheidbarkeit - Werkzeugkasten
1:10:01 Satz von Rice
1:14:02 Zusammenfassung (Werkzeugkasten)
07 |
0:00:00 Starten
0:00:06 Definitionen zur TM
0:01:15 Unentscheidbarkeit der Diagonalsprache
0:02:42 Die Universelle Sprache
0:09:51 Satz von Rice - Motivation
0:17:10 Das Post'sche Korrespondenzproblem
0:21:44 Eigenschaften von (semi-)entscheibaren Sprachen
0:28:02 Komplexitätstheorie
0:32:53 Wie sieht ein Problem aus?
0:37:56 Definition: Problem
0:39:34 Definition: Kodierungsschema
0:43:19 Äquivalenz von Kodierungsschemata
0:44:33 Entscheidungsprobleme
0:46:43 Korrespondenz von Entscheidungsproblemen und Sprachen
0:51:27 Zeitkomplexität
0:53:04 Die Klasse P
0:56:35 Algorithmus OPT-TOUR (als Beweis)
0:59:27 Die Nichtdeterministische Turingmaschine
1:04:41 Übertragung auf Entscheidungsprobleme PI
1:07:16 Bemerkungen zur NTM
1:13:15 Die Klasse NP
06 |
0:00:00 Starten
0:01:54 Formale Definition der Tuting-Maschine
0:04:18 Definition zur TM
0:07:42 Motation: Konfiguration
0:10:03 Beispiel: Konfiguration
0:20:09 Definition: berechenbar/ totalrekursiv
0:22:30 Beispiel
0:30:39 Entscheidbarkeit und Berechenbarkeit
0:32:46 Korollar
0:34:56 Die Church'sche These
0:39:00 Erweiterungen der Turing-Maschine
0:44:35 Die universelle Turing-Maschine
0:48:15 Die Gödelnummer
0:53:04 Die Gödelnummer - Bemerkungen
0:55:28 Die Gödelnummer - Beispiel
0:58:51 Definition
0:59:21 Die Diagonalsprache
1:04:09 Die Diagonalsprache - Veranschaulichung
1:05:41 Unentscheidbarkeit der Diagonalsprache
1:07:53 Korollar
1:10:12 Paradoxien und Selbstbezüglichkeit
1:11:32 Halteproblem
05 |
0:00:00 Starten
0:00:21 Frage
0:04:24 Wiederholung Äquivalenzklassenautomat
0:09:44 Definitionen: Rechtsinvarianz und Index
0:17:24 Nerode- Relation
0:22:12 Satz von Nerode
0:25:40 Beweis zu Satz von Nerode: (1)-->(2)
0:31:49 Beweis zu Satz von Nerode: (2)-->(3)
0:37:57 Beweis zu Satz von Nerode: (3)-->(1)
0:46:16 Korollar
0:49:09 Minimalitäat des Äquivalenzklassenautomats
0:53:15 Zusammenfassung
0:56:04 Historisches
0:59:37 Turing-Maschinen und Berechenbarkeit
1:00:59 Die Registermaschine (RAM)
1:02:13 Befehle der Registermaschine (RAM)
1:03:12 Die Turing-Maschine (TM)
1:06:53 Formale Definition der Turing-Maschine
1:08:59 Bemerkung zur TM
1:12:15 Beispiel-Turing-Maschine
1:18:17 Definition zur TM
04 |
0:00:00 Starten
0:01:20 Pumping-Lemma für reguläre Sprachen
0:08:08 Verallgemeintertes PL für reguläre Sprachen
0:23:36 Beispiel
0:31:37 Äquivalenz
0:34:26 Der Äquivalenzklassenautomat
0:44:21 Frage
0:54:24 Vorgehensweise
0:55:57 Beispiel zur Vorgehensweise
03 |
0:00:00 Starten
0:00:05 letzte Vorlesung...
0:05:42 Entfernen von Epsilon-Übergängen
0:16:09 EA-Regularität
0:37:53 Beispiel
0:52:18 Frage: Was können endliche Automaten nicht?
0:55:53 Pumping-Lemma für reguläre Sprachen
1:06:31 Bemerkung und Beispiele
02 |
0:00:00 Starten
0:00:38 Endliche Automaten und Reguläre Sprachen
0:16:02 Nichtdeterministische endliche Automaten
0:22:10 Beispiele für NEA's
0:27:11 Äquivalenz von NEA's und DEA's
0:28:54 Beispiel Potenzmengenkonstruktion
01 |
0:00:00 Starten
0:01:06 Ziel der Vorlesung TGI
0:07:08 Wiederholung aus Grundbegriffe der Informatik
0:09:11 Wörter
0:13:56 Formale Sprachen
0:25:28 Reguläre Sprachen
0:32:09 Reguläre Ausdrücke
0:41:42 Endliche Automaten
0:48:57 Kontextfreie Grammatiken
Comments
Download from Google Play
Download from App Store
United States