27 Folgen

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 (KIT)

    • Bildung

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 Std. 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 Std. 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 Std. 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 Std. 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 Std. 22 Min.

Top‑Podcasts in Bildung

Eine Stunde History - Deutschlandfunk Nova
Deutschlandfunk Nova
100 Sekunden Wissen
Schweizer Radio und Fernsehen (SRF)
The Mel Robbins Podcast
Mel Robbins
G Spot - mit Stefanie Giesinger
Stefanie Giesinger & Studio Bummens
Easy German: Learn German with native speakers | Deutsch lernen mit Muttersprachlern
Cari, Manuel und das Team von Easy German
Allez j'ose !
Martange

Mehr von Karlsruher Institut für Technologie

Digitale Revolution: Technik verstehen und gestalten?
Karlsruher Institut für Technologie (KIT)
Softwaretechnik 1, Vorlesung, SS2018
Karlsruher Institut für Technologie (KIT)
Digitaltechnik und Entwurfsverfahren, SS2017, Vorlesung
Karlsruher Institut für Technologie (KIT)
Parallele Algorithmen, Vorlesung, WS17/18
Karlsruher Institut für Technologie (KIT)
Kognitive Systeme, SS2017, Vorlesung
Karlsruher Institut für Technologie (KIT)
Algorithmen 1, SS2017, Vorlesung
Karlsruher Institut für Technologie (KIT)