Claim OwnershipTheoretische Grundlagen der Informatik, Vorlesung, WS16/17
Subscribed: 34Played: 106
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 Starten
0:00:07 Fortsetzung Informationstheorie
0:01:06 Wiederholung Quellkodierung
0:01:46 Kanalkodierung
0:02:24 Codierung zum Schutz gegen Übertragungsfehler
0:04:17 Paritätscodes - Einfach Binär
0:07:27 Kreuzsicherung
0:12:20 Paritätscodes
0:13:33 Beweis
0:15:09 Paritätscodes gegen Vertauschungsfehler
0:18:42 Bsp: ISBN-10
0:18:56 ISBN
0:19:59 Block-Codes
0:20:31 Hamming-Distanz und Fehlerkorrektur
0:21:58 Maximum-Likelihood-Decoding
0:23:08 Shannon's Theorem
0:23:52 Block-Codes
0:25:13 Beweisskizze
0:26:37 Werbung
0:28:18 Vorlesung Planare Graphen
0:36:07 Proseminar Theoretical Computer Science Classics
0:39:53 ICPC Praktikum
0:42:04 PSE Energieinformatik
17 |
0:00:00 Starten
0:01:45 Thema dieses Kapitels
0:04:52 Material für Informationstheorie
0:05:32 Information
0:12:45 Wiederholung: Rechenregeln Logarithmus
0:13:53 Definition Information
0:14:52 Entropie
0:19:16 Bemerkung zur Entropie
0:19:31 Entropie einer Münze mit Wkt p für Zahl
0:20:44 (Platzsparende) Codierungen
0:22:12 Codierungsbäume
0:26:49 Präfix-Codes
0:29:08 Beispiel: Morse-Alphabet
0:30:15 Quellencodierungstheorem
0:31:47 Beispiel: Shannon-Fano Codierung
0:38:01 Codierungsbaum Shannon-Fano
0:38:59 Beispel: Huffman-Codierung
0:44:36 Optimalität der Huffman-Codierung
0:45:13 Vorbereitendes Lemma
0:47:00 VorbereitendesLemma: Beweis
0:51:10 Beweis - Induktionsschluss
0:57:00 Nachteile der Huffman-Codierung
0:59:05 Lauflängenkodierung
16 |
0:00:00 Starten
0:00:37 Kellerautomaten
0:03:49 Satz
0:05:15 Satz (2)
0:06:09 Beweis
0:30:19 Korollar
0:30:41 Übersicht Chomsky-2
0:32:46 Exkurs
0:34:16 Zwischenfazit zu kontextfreien Grammatiken
0:36:10 Satz (3)
0:38:18 Das Post'sche Korrespondenzproblem
0:39:47 Beweis (2)
0:43:33 Beweisskizze
0:44:07 Beweis (3)
0:45:50 Sprache der korrekten Rechenwege
0:51:59 Lemma
0:52:28 Beweis (4)
1:01:26 Bemerkung
1:02:03 Lemma (2)
1:02:27 Beweis (5)
15 |
0:00:00 Starten
0:00:07 Beweis
0:03:26 Kellerautomaten
0:09:17 Kellerautomaten - Visualisierung
0:10:09 Kellerautomaten - Arbeitsweise
0:18:33 Kellerautomaten - Beispiel
0:27:20 Kellerautomaten - Beispiel 2
0:31:02 Satz (1)
0:35:44 Satz (2)
0:39:19 Satz (3)
14 |
0:00:00 Starten
0:00:07 Wiederholung
0:12:03 Ogden´s Lemma für kontextfreie Sprachen
0:14:31 Beweis
0:29:20 Beweis - Teil 1
0:30:23 Beweis - Teil 2
0:39:23 Beweis - Teil 3
0:41:58 Nutzlose Variablen
0:43:38 Schritt 1
0:47:24 Beispiel: Schritt 1
0:51:28 Schritt 2
0:53:16 Beispiel: Schritt 2
0:56:45 Korollar
0:59:27 Beispielgraph
13 |
0:00:00 Starten
0:00:31 Wiederholung
0:02:13 Die Chmosky Hierarchie
0:08:16 Syntaxbäume
0:10:28 Syntaxbäume - Beispiel
0:15:54 Links/Rechtsabteilung, Eindeutigkeit
0:17:31 Beispiel
0:19:37 Chomsky-Normalform
0:20:56 Die Chomsky Hierarchie
0:21:21 Chomsky-Normalform
0:31:01 Schritt 1
0:34:21 Schritt 2
0:38:20 Schritt 3
0:49:34 Schritt 4
0:53:36 Abhängigkeitsgraph
0:54:42 Schritt 4 – Phase 1
0:56:47 Schritt 4 – Phase 2
1:02:02 Der CYK-Algorithmus
1:05:15 Beweis - Beschreibung des CYK-Algorithmus
1:08:33 CYK-Algorithmus – Beispiel
1:12:31 CYK-Algorithmus – Vorgehen
1:14:50 Beweis - Beschreibung des CYK-Algorithmus
1:15:39 CYK-Algorithmus – Vorgehen
1:16:10 CYK-Algorithmus – Beispiel
1:22:11 CYK-Algorithmus – Vorgehen
1:22:48 Ergebnisse zum Wortproblem
12 |
0:00:00 Starten
0:00:28 Grammatiken
0:01:26 Beispiele
0:05:33 Grammatiken
0:07:12 Bemerkungen
0:08:32 Beispiel
0:09:22 Die Chomsky Hierarchie
0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit
0:24:58 Beweis - Beschreibung der Grammatik G
0:28:28 Beweis - Zusammenfassung
0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit
0:32:04 Zwischenfazit
0:34:01 Chomsky-3-Grammatiken und reguläre Sprachen
0:35:27 Beweis
0:42:00 Bemerkung
0:43:05 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen
0:48:01 Satz
0:48:59 Bemerkung
0:49:17 Wiederholung: Das Problem CLIQUE
0:50:02 Satz
0:54:02 Bemerkung 1
0:54:53 Bemerkung 2
0:56:12 Notation
0:57:15 Typ-2 / Kontextfreie Grammatiken
0:57:40 Typ-2 Grammatiken: Beispiel 1
0:58:51 Typ-2 Grammatiken: Beispiel 2
1:00:44 Typ-2 Grammatiken: Beispiel 3
11 |
0:00:00 Starten
0:02:50 Approximation mit relativer Gütegarantie
0:03:31 Definition
0:04:49 Approximierbarkeit von COLOR
0:18:45 Approximierbarkeit von TSP
0:28:12 Approximationsschemata
0:38:45 Ein FPAS für KNAPSACK (1)
0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK
0:43:49 Ein FPAS für KNAPSACK (2)
0:58:51 Ein allgemeineres Resultat
10 |
0:00:00 Starten
0:03:37 VerallgemeinerteNP-Schwere
0:07:17 Das Problem INTEGER PROGRAMMING
0:26:15 Pseudopolynomiale Algorithmen
0:29:56 Beispiel: Problem KNAPSACK
0:40:20 Starke NP-Vollständigkeit
0:44:14 Absolute Approximationsalgorithmen
0:46:31 Das allgemeine KNAPSACK-Suchproblem
0:57:09 Approximation mit relativer Gütegarantie
0:59:53 Beispiel: Greedy-Algorithmus für KNAPSACK
09 |
0:00:00 Starten
0:06:41 Das Problem SUBSET SUM
0:07:46 NP-Vollständigkeit von SUBSET SUM
0:24:03 Das Problem PARTITION
0:31:06 Das Problem KNAPSACK
0:37:32 Auswirkungen auf die Frage P=NP
0:45:42 Zusammenfassung
0:47:57 Die Klassen NPI, co-P und co-NP
0:54:22 Das TSP-Komplement-Problem
0:57:40 Lemma
1:00:00 Bemerkung
1:01:25 Das Problem Subgraphisomorphie
1:03:14 Das Problem Graphismorphie
1:09:06 Suchprobleme
1:10:21 Beispiel: TSP-Suchproblem
1:11:03 Beispiel: Hamilton–Kreis Suchproblem
1:12:04 Aufzählungsprobleme
1:12:44 Reduzierbarkeit für Suchprobleme
1:15:36 Orakel-Turing-Machine
1:19:40 NP-schwer
1:20:39 Beweisskizze
08 |
0:00:00 Starten
0:00:37 Wiederholung: NP-Vollständigkeit
0:06:10 Wiederholung: Transitivität der poly. Transformation
0:06:40 Wiederholung: Korollar
0:07:37 Wiederholung: Das Problem SAT (satisfiability)
0:12:17 Das Problem 3-SAT
0:13:13 Beweis: NP-Vollständigkeit von 3-SAT
0:30:07 Das Problem 2SAT
0:34:40 Das Problem MAX2SAT
0:38:02 Das Problem CLIQUE
0:39:32 Beweis: NP-Vollständigkeit von CLIQUE
0:51:19 Das Problem COLOR
0:54:56 Beweis: NP-Vollständigkeit von 3COLOR
0:57:29 Konstruktion von 3COLOR-Instanz G
1:01:05 Beispielgraph zur Reduktion
1:04:20 Polynomialität der Reduktion
1:04:56 Instanz I erfüllbar => Instanz G erfüllbar
1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar
1:08:02 Das Problem EXACT COVER
1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER
1:14:28 Konstruktion von (X,S)
1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung
1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung
07 |
0:00:00 Starten
0:01:06 Die Klasse P
0:03:19 Die Klasse NP
0:04:47 Die Nichtdeterministische Turingmaschine
0:05:17 Zeitkomplexität für NTM
0:08:55 Große Frage der Theoretischen Informatik
0:11:38 NP-Vollständigkeit
0:24:35 Transitivität der poly. Transformation
0:25:46 Korollar
0:28:28 Das Problem SAT (satisfiability)
0:31:05 Weitere Beispiele für SAT-Instanzen
0:33:44 Der Satz von Cook (Steven Cook, 1971)
0:36:00 Beweis
0:42:53 Beweis: Konstruktion der Variablen
0:49:48 Beweis
0:53:35 Beweis: Konstruktion der Klauseln - Übersicht
0:56:09 Klauselgruppe 1:
0:59:10 Klauselgruppe 2:
1:00:15 Klauselgruppe 3:
1:01:50 Klauselgruppe 4:
1:03:23 Klauselgruppe 5:
1:04:36 Klauselgruppe 6:
1:06:51 Klauselgruppe 6, 1:
1:09:51 Klauselgruppe 6,2:
1:13:35 Konstruktion der Klauseln - Zwischenergebnis
1:15:11 Polynomialität der Transformation
1:15:45 Polynomialität - Klauselgruppe 1:
1:16:20 Polynomialität - Klauselgruppe 2:
1:17:25 Polynomialität - Klauselgruppe 3:
1:17:56 Polynomialität - Klauselgruppe 4:
1:18:38 Polynomialität - Klauselgruppe 5:
06 |
0:00:00 Starten
0:00:54 Definitionen zur TM
0:05:21 Notation: Konfiguration
0:07:49 Beispiel: Konfiguration
0:20:00 Definition: berechenbar / totalrekursiv
0:22:30 Beispiel
0:26:57 Entscheidbarkeit und Berechenbarkeit
0:30:18 Korollar
0:33:13 Die Church´sche These
0:36:20 Erweiterungen der Turing-Maschine
0:39:17 Die universelle Turing-Maschine
0:45:24 Die Gödelnummer
0:50:45 Die Gödelnummer - Bemerkungen
0:54:43 Die Gödelnummer - Beispiel
0:58:54 Definition
1:00:08 Die Diagonalsprache
1:05:42 Die Diagonalsprache - Veranschaulichung
1:07:03 Unentscheidbarkeit der Die Diagonalsprache
1:09:24 Korollar
1:14:01 Paradoxien und Selbstbezüglichkeit
1:17:13 Das Halteproblem
1:24:15 Halteproblem nicht entscheidbar
05 |
0:00:00 Starten
0:00:54 Definitionen zur TM
0:05:56 Notation: Konfiguration
0:07:50 Beispiel: Konfiguration
0:20:37 Definition: berechenbar / totalrekursiv
0:23:01 Beispiel
0:27:27 Entscheidbarkeit und Berechenbarkeit
0:30:19 Korollar
0:33:21 Die Church´sche These
0:36:38 Ertweiterungen der Turing-Maschine
0:39:39 Die universelle Turing-Maschine
0:44:35 Die Gödelnummer
0:50:58 Die Gödelnummer - Bemerkungen
0:53:35 Die Gödelnummer - Beispiel
0:59:14 Definition
1:01:05 Die Diagonalsprache
1:05:35 Die Diagonalsprache - Veranschaulichung
1:07:32 Unentscheidbarkeit der Diagonalsprache
1:10:06 Korollar
1:11:03 Paradoxien und Selbstbezüglichkeit
1:14:47 Das Halteproblem
1:21:00 Grenzen der Berechenbarkeit
1:22:05 Halteproblem nicht entscheidbar
04 |
0:00:00 Starten
0:00:12 Endliche Automaten, reguläre Sprachen
0:00:57 Frage
0:01:40 Äquivalenz
0:04:24 Der Äquivalenzklassenautomat
0:06:29 Vorgehensweise
0:08:44 Frage
0:10:29 Antwort
0:13:49 Definitionen: Rechtsinvarianz und Index
0:17:08 Nerode-Relation
0:20:55 Satz von Nerode
0:24:06 Beweis zu Satz von Nerode: (1) – (2)
0:28:54 Beweis zu Satz von Nerode: (2) – (3)
0:31:43 Beweis zu Satz von Nerode: (3) – (1)
0:37:00 Satz von Nerode
0:37:38 Korollar
0:40:52 Minimalität des Äquivalenzklassenautomats
0:44:19 Zusammenfassung
0:48:45 Kapitel: Turing-Maschinen und Berechenbarkeit
0:52:00 Die Registermaschine (RAM)
0:53:23 Befehle der Registermaschine (RAM)
0:53:52 Kostenmodell der Registermaschine (RAM)
0:54:56 Die Turingmaschine (TM)
0:57:54 Die Turingmaschine (TM)
0:58:20 Formale Definition der Turingmaschine
1:01:51 Bermerkungen zur TM
1:05:09 Beispiel-Turingmaschine
1:15:15 Bemerkungen zur TM
1:16:48 Definitionen zur TM
02 |
0:00:00 Starten
0:00:24 Letzte Vorlesung
0:09:53 Entfernen von e-Übergängen
0:20:42 EA – Regulärität
0:22:44 Beweis: EA – Regulärität
0:44:02 Beispiel
0:54:15 Satz von Kleene
0:55:54 Frage: Was können endliche Automaten nicht?
0:59:14 Pumping-Lemma für reguläre Sprachen
1:10:10 Bemerkung
1:11:49 Beispiel (1) zum PL
1:14:18 Beispiel (2) zum PL
1:18:31 Beispiel (3) zum PL
03 |
0:00:00 Starten
0:00:25 Verallgemeinertes PL für reguläre Sprachen
0:17:18 Kapitel Minimierung von Automaten und Äquivalenzklassenautomat
0:20:14 Frage: Kann man konstruktiv die Anzahl der Zustände eines deterministischen endlichen Automatens erheblich verringern?
0:22:04 Beispiel
0:34:34 Äquivalenz
0:37:22 Der Äquivalenzklassenautomat
0:48:03 Frage: Wie berechnet man alle Äquivalenzklassen zu den Zuständen von A?
0:53:43 Frage: Wann kann dieses Verfahren abgebrochen werden?
0:57:26 Vorgehensweise
1:00:09 Beispiel zur Vorgehensweise
01 |
0:00:00 Starten
0:00:30 Ziele der Vorlesung TGI
0:13:46 Wiederholung aus Grundbegriffe der Informatik
0:17:17 Wörter
0:21:24 Formale Sprachen
0:31:12 Reguläre Sprachen
0:36:04 Reguläre Ausdrücke
0:39:46 Reguläre Ausdrücke – Beispiele
0:43:48 Endliche Automaten
0:53:24 Kontextfreie Grammatiken
0:58:07 Beispiel Kontextfreie Grammatiken
Comments
Download from Google Play
Download from App Store
United States