Claim OwnershipTheoretische Grundlagen der Informatik, Vorlesung, WS19/20
Subscribed: 30Played: 238
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:11 Kodierung zum Schutz gegen Übertragungsfehler
0:01:42 Paritätscodes - Einfach binär
0:04:45 Kreuzsicherung
0:10:05 Paritätscodes
0:16:27 Block-Codes
0:17:03 Hamming-Distanz und Fehlerkorrektur
0:21:23 Beispiel
17 |
0:00:00 Start
0:03:24 Material für Informationstheorie
0:03:57 Information
0:12:08 Wiederholung: Rechenregeln Logarithmus
0:17:45 Entropie
0:24:46 Entropie zu einer Münze
0:26:09 (Platzsparende) Kodierungen
0:28:48 Präfix-Codes
0:31:13 Kodierungsbäume
0:36:18 Beispiel: Morse-Alphabet
0:37:38 Quellenkodierungstheorem
0:39:41 Beispiel: Shannon-Fano-Kodierung
0:44:44 Kodierungsbaum Shannon-Fano
0:45:44 Beispiel: Huffman-Kodierung
0:49:25 Vorbereitendes Lemma
0:55:09 Beweis - Induktionsschluss
1:00:43 Nachteile der Huffman-Kodierung
1:02:46 Lauflängenkodierung
1:10:49 Kodierung zum Schutz gegen Übertragungsfehler
16 |
0:00:00 Start
0:00:21 Letzte Vorlesung
0:07:22 Wdh.: Greibach-Normalform, Kellerautomat
0:11:54 Kellerautomaten
0:15:10 Beispiel - Greibach-Normalform
0:18:13 Beipiel - Kellerautomat
0:21:23 Beweis: Greibach-Normalform -> NPDA
0:27:20 Beweis: NPDA -> Kontextfreie Grammatik
0:52:53 Zwischenfazit zu kontextfreien Grammatiken
0:59:24 Das Post´sche Korrespondenzproblem
1:06:53 Eindeutigkeit von kontextfreien Grammatiken
1:10:13 Sprache der Korrekten Rechenwege
15 |
0:00:00 Start
0:00:19 Letzte Vorlesung
0:01:21 Heutige Vorlesung
0:03:24 Weiere Eigenschaften kontextfreier Sprachen
0:17:59 Ein Maschinenmodell für Chomsky-2
0:23:18 Greibach-Normalform
0:26:01 Beweis
0:53:04 Kellerautomaten
14 |
0:00:00 Start
0:00:31 Übersicht
0:04:47 Das Pumping-Lemma für kontextfreie Sprachen
0:13:52 Ogden´s Lemma für kontextfreie Sprachen
0:15:48 Beweis von Ogden´s Lemma
0:28:07 Echtheit der Chomsky-Hierarchie
0:30:18 Beweis
0:44:49 Eigenschaften kontextfreier Sprachen
0:48:12 Nutzlose Variablen
0:51:27 Schritt 1
1:01:10 Schritt 2
1:05:22 Endliche kontextfreie Sprachen
1:08:51 Beispielgraph
13 |
0:00:00 Start
0:01:20 Beispiele
0:04:40 Grammatiken
0:06:42 Bemerkungen
0:11:29 Die Chomsky-Hierarchie
0:24:56 Chomsky-0-Grammatiken und Semientscheidbarkeit
0:30:11 Beweis – Beschreibung der Grammatik G
0:40:28 Chomsky-3-Grammatiken und reguläre Sprachen
0:42:26 Beweis
0:53:06 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen
0:57:03 Satz
12 |
0:00:00 Start
0:00:42 Wiederholung letzte Vorlesung
0:08:12 Definition
0:14:31 Metrisches TSP
0:16:07 Approximation von min-METRIC-TSP
0:27:08 Bemerkungen zur Approximierbarkeit
0:31:25 Approximationsschemata
0:37:51 Ein FPTAS für max-KNAPSACK
0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK
0:52:46 Maximierungsprobleme
1:01:47 Optimierungsprobleme
1:10:58 Approximierbarkeit von min-Vertex-Color
1:23:39 Abschluss des Kapitels zur Komplexitätstheorie
11 |
0:00:00 Start
0:01:57 Verallgemeinerte NP-Schwere
0:04:05 Das Problem INTEGER PROGRAMMING
0:07:55 INTEGER PROGRAMMING ist NP-schwer
0:16:21 Bemerkungen
0:21:18 Kapitel
0:24:34 Pseudopolynomiale Algorithmen
0:28:14 Beispiel: Problem KNAPSACK
0:37:52 Starke NP-Vollständigkeit
0:44:41 Kapitel
0:47:54 Absolute Approximationsalgorithmen
0:49:27 Das allgemeine KNAPSACK-Suchproblem
0:51:56 Negativ-Resultat
0:53:52 (Kontrapositions-)Beweis
0:59:35 Approximation mit relativer Gütegarantie
1:01:11 Genereller Ansatz
1:03:54 Beispiel: Greedy-Algorithmus für KNAPSACK
1:12:18 Grenzen für den Greedy-Algorithmus
10 |
0:00:00 Start
0:00:27 Letzte/Diese Vorlesung
0:04:04 Das Problem SUBSET SUM
0:05:37 NP-Vollständigkeit von SUBSET SUM
0:21:39 Das Problem PARTITION
0:22:29 Beweis: NP-Vollständigkeit von PARTITION
0:28:40 Das Problem KNAPSACK
0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK
0:33:39 Auswirkung auf die Frage P= NP
0:40:15 Zusammenfassung
0:45:01 Die Klassen NPC und NPI
0:46:23 Die Klassen co-P und co-NP
0:51:28 Das TSP-Komplement-Problem
0:54:27 NP-vollständig vs. co-NP
0:58:19 Das Problem Subgraphisomorphie
1:00:17 Das Problem Graphisomorphie
1:02:06 Die Polynomielle Hierarchie
1:12:34 Suchprobleme
1:13:13 Beispiel: TSP-Suchproblem
1:14:53 Beispiel: Hamilton-Kreis Suchproblem
1:16:18 NP-Schwere bei Suchproblemen
1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem
09 |
0:00:00 Start
0:00:08 Letzte Vorlesung
0:08:16 Plan für heute
0:10:46 Das Problem 3SAT
0:12:53 Beweis: NP-Vollständigkeit von 3SAT
0:31:50 Das Problem 2SAT
0:34:00 Das Problem MAX2SAT
0:36:49 Das Problem CLIQUE
0:39:07 Beweis: NP-Voillständigkeit von CLIQUE
0:54:25 Das Problem COLOR
0:55:33 Beweis: NP-Vollständigkeit von 3COLOR
0:57:09 Konstruktion von 3COLOR-Instanz G
1:02:30 Polynomialität der Reduktion
1:03:12 Instanz G 3-färbbar
1:08:08 Zwischenstand Polynomiale Reduktion
1:10:27 Das Problem EXACT COVER
1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER
1:14:34 Konstruktion von (X, S)
1:22:00 G 3-färbbar -> exakte Überdeckung
08 |
0:00:00 Start
0:07:42 Bemerkungen zur NTM
0:11:20 Zeitkomplexität für NTM
0:14:40 Die Klasse NP
0:18:28 P vs NP
0:24:03 Polynomiale Transformation
0:34:35 Das Problem SAT
0:39:55 Satz von Cook
0:43:37 Setup
0:48:19 Konstruktion der Variablen
1:05:51 Zwischenbilanz
07 |
0:00:00 Start
0:00:29 Letzte Vorlesung
0:04:12 Halteproblem
0:10:25 Die universelle Sprache
0:16:34 Satz von Rice - Motivation
0:20:52 Bemerkungen zum Satz von Rice
0:22:30 Das Post´sche Korrespondenzproblem
0:34:51 Eigenschaften von (semi-) entscheidbaren Sprachen
0:39:07 Komplexitätstheorie
0:42:09 Wie sieht das Problem aus?
0:47:37 Definition: Problem
0:49:42 Definition: Kodierungsschema
0:55:30 Äquivalenz von kodierungsschemata
0:57:11 Entscheidungsproblem
1:02:21 Zeitkomplexität
1:07:08 Schwierigkeit von Entscheidungs- und Optimierungsproblem
1:11:35 Algorithmus OPT-TOUR (als beweis) 1/2
1:16:27 Laufzeit des Algorithmus
1:18:26 Zwischenstand Komplexitätstheorie
1:21:56 Die Nichtdeterministische turing-Maschine
1:23:25 Die Orakel-Turing-Maschine
06 |
0:00:00 Start
0:01:05 (deterministische) Turing-Maschine
0:06:34 Beispiel-Turing-Maschine
0:16:35 Definitionen zur TM
0:19:46 Notation: Konfiguration
0:29:18 Definition: berechenbar/ totalrekursiv
0:42:20 Entscheidbarkeit und Berechenbarkeit
0:48:02 Korollar
0:49:57 Die Church´sche These
0:55:21 Erweiterung der Turing-maschine
0:59:49 Die universelle Turing-Maschine
1:03:07 Die Gödelnummer
1:13:24 Die Diagonalsprache
1:18:20 Unentscheidbarkeit der Diagonalsprache
1:21:17 Paradoxien und Selbstbezüglichkeit
1:23:10 Halteproblem
05 |
0:00:00 Start
0:00:39 Kapitel 2
0:07:31 Alternative Sicht – Beispiel
0:16:52 Wiederholung Äquivalemzklassenautomat
0:19:38 Rechtsinvarianz und Index
0:26:04 Nerode-Relation
0:29:50 Satz von Nerode
0:46:15 Korollar
0:52:35 Minimalität des Äquivalenzklassenautomats
0:55:26 Zusammenfassung
1:01:27 Turing-Maschinen und Berechenbarkeit
1:03:20 Die Registermaschine (RAM)
1:11:08 Formale Definition der Turingmaschine
1:18:14 Beispiel-Turing-Maschine
04 |
0:00:00 Start
0:00:41 Satz (Pumping-Lemma für reguläre Sprachen)
0:03:23 Satz (Verallgemeinertes Pumping-Lemma)
0:13:22 Beispiel (3) - Anwendung Verallgemeinertes PL
0:21:54 Finden nicht überflüssiger Zustände
0:29:44 Der Äquivalenzklassenautomat
0:49:04 Beispiel zur Vorgehensweise
0:57:27 Zusammenfassung
1:01:50 Testen Sie sich
03 |
0:00:00 Start
0:00:00 Start
0:00:20 Nichtdeterministische endliche Automaten
0:05:09 Zwischenstand
0:10:45 Entfernen von ɛ-Übergängen
0:21:09 EA -> Regularität
0:41:31 Beispiel
0:47:34 Satz von Kleene
0:48:58 Was können endliche Automaten nicht?
0:53:44 Pumping-Lemma für reguläre Sprachen
1:19:05 Zusammenfassung
1:20:03 Bemerkungen zu 'Testen Sie sich'-Aufgabe
02 |
0:00:00 Start
0:00:41 Kontextfreie Grammatiken
0:06:34 Kontextfreie Grammatiken - Beispiele
0:14:35 Endliche Automaten und Reguläre Sprachen
0:23:43 Nichtderterministische endliche Automaten
0:28:31 Beispiele für NEAs
0:31:52 Äquivalenz von NEAs und DEAs
0:34:54 Beispiel Potenzmengenkonstruktion
0:41:26 Erweiterung von ẟ
0:58:24 Induktionsanfang
1:13:24 Zusammenfassung
01 |
0:00:00 Start
0:03:28 Ziele der Vorlesung TGI
0:10:29 Wörter
0:20:06 Formale Sprachen
0:33:42 Reguläre Sprachen
0:38:59 Reguläre Ausdrücke
0:44:55 Reguläre Ausdrücke -Beispiele
0:53:09 Endliche Automaten
Comments
Download from Google Play
Download from App Store
United States