27 episodes

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

Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 Karlsruher Institut für Technologie

    • Courses

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

    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 11.02.2016, Übung - 26

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 11.02.2016, Übung - 26

    26: Übung|
    0:00:00 Starten
    0:00:12 Vorbereitung Klausur: 1. Übungsblatt
    0:05:44 2. Übungsblatt
    0:06:34 3. Übungsblatt
    0:08:49 4. Übungsblatt
    0:18:32 5. Übungslbatt
    0:25:58 6. Übungsblatt
    0:30:05 7. Übungsblatt
    0:34:44 8. Übungsblatt
    0:41:35 Weihnachtsblatt
    0:42:46 10. Übungsblatt
    0:45:17 Weiterführende Vorlesungen
    0:52:01 11. Übungsblatt
    0:55:22 12. Übungsblatt
    0:59:14 13. Übungsblatt
    1:03:44 14. Übungsblatt

    • 1 hr 7 min
    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 09.02.2016, Vorlesung und Übung - 25

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 09.02.2016, Vorlesung und Übung - 25

    25: Vorlesung und Übung |
    0:00:00 Starten
    0:02:07 Caesar-Chiffre
    0:05:07 Monoalphabetische Verschiebungschiffre
    0:06:57 Vigenère-Verschlüsselung
    0:20:34 Set Cover
    0:27:01 Set Cover Beispiel 1
    0:27:37 Set Cover ist NP-vollständig
    0:27:53 Beweis ""Set Cover ist NP-hart""
    0:35:36 Set Cover Beispiel 2
    0:37:40 Beweis F erfüllbar
    0:41:18 Bewies ""3SAT ist NP-hart""
    0:42:14 Negation in die Blätter drücken
    0:43:25 Nichtblattknoten -> Neue Variablen
    0:47:21 Clique
    0:47:43 Clique Beispiel
    0:50:22 Subset Sum
    0:50:50 Die Subset Sum Instanz
    0:52:51 Integer Linear Programming (ILP)
    0:53:30 Directed Hamilton Cycle (DHC)
    0:56:23 Umgang mit NP-harten Problemen

    • 58 min
    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 04.02.2016, Vorlesung und Übung - 24

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 04.02.2016, Vorlesung und Übung - 24

    24: Vorlesung und Übung |
    0:00:00 Starten
    0:00:18 Übung: Gedächtnislose Quellen
    0:02:16 Übung: Entropiemaximierung
    0:06:59 Übung: Decodierbarkeit
    0:11:32 Übung: Theoretische Grenzen der Kompression
    0:15:27 Übung: Fakten zur Kolmogorov Koplexität
    0:20:03 Übung: Einige Beispiele für obere Schranken
    0:23:46 Vorlesung: Elias-Fano Kodierung
    0:24:37 Vorlesung: Elias-Fano Kodierung - Funktionsweise
    0:33:53 Vorlesung: Elias-Fano Kodierung - Anwendung
    0:37:15 Vorlesung: Wechselseitiger und bedingter Informationsgehalt
    0:47:22 Vorlesung: Verbundentropie und bedingte Entropie
    0:49:10 Vorlesung: Übertragungsmodell
    0:49:35 Vorlesung: Der Symmetrische Binärkanal
    0:53:31 Vorlesung: Transinformation (mutual information)
    0:57:41 Vorlesung: Kanalkapazität
    1:02:19 Vorlesung: Codierung zum Schutz gegen Übertragungsfehler
    1:03:47 Vorlesung: Paritätscodes
    1:13:56 Vorlesung: Beispiel ISBN-10
    1:14:27 Vorlesung: Block-Codes

    • 1 hr 21 min
    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 21.01.2016, Vorlesung und Übung - 20

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 21.01.2016, Vorlesung und Übung - 20

    20: Vorlesung und Übung |
    0:00:00 Starten
    0:00:11 Directed Hamilton Cycle (DHC)
    0:01:35 Beweis von »DHC ist NP-hart«
    0:02:03 Reduktionen
    0:02:43 DHC
    0:03:34 Beweis von »DHC ist NP-hart«
    0:05:07 Ein Knoten pro Variable
    0:05:47 Gadget Kj mit 6 Knoten je Klausel
    0:08:35 »Vorgesehene« Hamiltonkreise
    0:12:12 Unmögliche Hamiltonkreise
    0:14:16 Verbindungen der Gadgets
    0:18:35 Beispiel
    0:27:46 F erfüllbar - Instanz lösbar
    0:29:28 Instanz lösbar - F erfüllbar
    0:30:41 DHC - Hamilton Circle
    0:34:32 Exkurs: Euler-Tour
    0:36:11 Gesehene Reduktionen
    0:36:53 Komplexität (verallgemeinerter) klassischer Spiele
    0:43:48 10. Übung
    0:44:23 Integer Linear Programming
    0:44:51 ILP: 0-1-Belegung erzwingen
    0:45:29 Beispiel: KNAPSACK
    0:47:01 Pseudo-polynomieller Knapsack Algorithmus
    0:56:04 Approximation von Knapsack
    1:01:16 Domino
    1:03:34 Domino: Probleme
    1:04:00 2-Player Cooperative Dominoes
    1:08:19 Weitere Domino-Varianten
    1:09:28 Portal 2
    1:12:14 3Sat - Super Mario World

    • 1 hr 23 min
    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 02.02.2016, Vorlesung - 23

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 02.02.2016, Vorlesung - 23

    23: Vorlesung|
    0:00:00 Starten
    0:00:42 Thema dieses Kapitels
    0:04:32 Information
    0:09:03 Wiederholung: Rechenregeln Logarithmus
    0:11:49 Entropie
    0:13:45 Bemerkungen zur Entropie
    0:15:22 Entropie einer Münze mit Wkt p für Zahl
    0:16:01 (Platzsparende) Codierungen
    0:16:48 Codierungsbäume
    0:19:51 Beispiel
    0:20:57 Präfix-Codes
    0:21:43 Beispiel
    0:23:16 Quellencodierungstheorem
    0:24:48 Quellencodierungstheorem-Beweis
    0:34:37 Shannon-Fano Codierung
    0:37:33 Codierungsbaum Shannon-Fano
    0:37:46 Bemerkung
    0:38:17 Beispiel: Shannon-Fano Codierung
    0:38:36 Beispiel: Huffman-Codierung
    0:40:41 Huffman-Codierung
    0:41:28 Optimalität der Huffman-Codierung
    0:41:37 Vorbereitendes Lemma
    0:42:44 Vorbreitendes Lemma: Beweis
    0:47:00 Beweis-Induktionsschluss
    0:51:00 Nachteile der Huffman-Codierung
    0:52:49 Lauflängenkodierung
    0:59:53 Succinct Datenstrukturen
    1:05:59 Bitvektoren mit Zugriff und Rank Operation
    1:14:23 Komprimierte Datenstrukturen
    1:16:32 Komprimierte Datenstrukturen: Wavelet Tree
    1:26:49 Elias-Fano Kodierung

    • 1 hr 29 min
    • video
    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 28.01.2016, Vorlesung und Übung - 22

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 28.01.2016, Vorlesung und Übung - 22

    22: Vorlesung und Übung|
    0:00:00 Starten
    0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
    0:00:41 Berechenbarkeit Hauptergebnis
    0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff
    0:01:48 Beispiel
    0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
    0:08:41 LOOP-Programme
    0:10:29 Äquivalenz von Maschinenmodellen
    0:12:04 Markov-Algorithmen
    0:14:08 Zellularautomaten
    0:15:16 2.4 Primitiv rekursive Funktionen
    0:16:11 2.5 Die Ackermannfunktion
    0:18:06 Mehr schnell wachsende Funktionen
    0:19:06 Wissen über Fleißige Biber
    0:20:12 2.6 Halterproblem, Unentscheidbarkeit, Reduzierbarkeit
    0:21:05 Paradoxien und Selbstbezüglichkeit
    0:22:07 Semi-Entscheidbarkeit
    0:24:02 Rekursive Aufzählbarkeit
    0:24:51 Äquivalente Aussagen
    0:25:30 2.7 Nicht-entscheidbare Probleme
    0:26:32 Gödelnummer einer Turingmaschine
    0:26:52 Diagonalsprache
    0:28:34 Universelle Turingmaschine
    0:30:35 Halteproblem
    0:31:48 Das beschränkte Halteproblem
    0:31:57 Mehr unentscheidbare Probleme
    0:32:46 Unentscheidbarkeit von Leerheit
    0:33:50 Postsches Korrespondenzproblem (PKP)
    0:34:32 Hilberts 10. Problem - Diophantische Gleichungen
    0:35:05 Abgeschlossenheit entscheidbarer Sprachen
    0:35:31 Nebenläufige Ausführung
    0:36:11 Terminologie und Konventionen
    0:36:26 Komplexitätsmaße
    0:37:37 Obere Schranken
    0:37:53 Untere Schranken: Lösungsansätze
    0:38:43 Eine Komplexitätsklasse
    0:41:07 Polynomiale Reduzierbarkeit
    0:43:20 Beispiel
    0:48:02 Weitere NP-vollständige Probleme
    0:48:31 11. Übung
    0:49:09 NP-Schwere Reduktionen

    • 1 hr 22 min

Top Podcasts In Courses

Listeners Also Subscribed To

More by Karlsruher Institut für Technologie