Theoretische Grundlagen der Informatik, Vorlesung, WS15/16

Karlsruher Institut für Technologie (KIT)
  • 0.0 (0)
  • COURSES
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 Podcast

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

  1. 15/02/2016

    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

    1h 7m

  2. 15/02/2016

    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

  3. 08/02/2016

    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

    1h 22m

  4. 05/02/2016

    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

    1h 23m

  5. 04/02/2016

    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

    1h 29m

  6. 01/02/2016

    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

    1h 22m

  7. 28/01/2016

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 26.01.2016, Vorlesung - 21

    21: Vorlesung | 0:00:00 Starten 0:03:23 1.1 Allgemeines 0:04:18 1.1.1 Grammatiken 0:05:19 1.1.2 Chomsky-Hierachie 0:11:12 1.1.3 Wortproblem 0:12:17 1.1.4 Syntaxbäume 0:13:02 1.2 Reguläre Sprachen 0:14:03 1.2.1 (Deterministische) endliche Automaten 0:14:30 1.2.2 Nichtderterministische (endliche) Automaten 0:19:52 1.2.3 Reguläre Ausdrücke 0:27:01 1.2.4 Das Pumping Lemma (für reguläre Sprachen) 0:33:11 1.2.5 Äquivalenzrelationen und Minimalautomaten 0:46:13 1.2.6 Abschlusseigenschaften 0:58:50 1.3 Kontextfreie Sprachen 0:59:11 1.3.1 Normalformen 1:01:14 1.3.2 Das Pumping Lemma

    1h 6m

  8. 21/01/2016

    Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 19.01.2016, Vorlesung - 19

    19: Vorlesung | 0:00:00 Starten 0:03:08 Beweis SUBSET SUM 0:03:31 Beweis ""SUBSET SUM ist NP-hart"" 0:03:34 SUBSET SUM 0:06:04 Die SUBSET SUM Instanz 0:10:08 Beispiel 0:13:55 Beweisidee 0:18:29 F erfüllbar -> Instanz lösbar 0:20:42 Instanz lösbar -> F erfüllbar 0:23:44 Beispiel Rucksackproblem 0:24:29 Rucksackproblem 0:26:11 Reduktionen 0:26:56 PARTITION 0:28:30 Beweis SUBSET SUM = pPARTITION 0:38:39 Integer Linear Programming (ILP) 0:40:14 Beweis von ""ILP ist NP-hart"" 0:41:18 Ist ILP in NP ? 0:44:52 Umgang mit NP-harten Probleme 0:55:29 Optimierungsprobleme 0:56:11 NP vollständig 0:57:26 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 1:00:20 alpha-Approximation von TSP 1:01:13 HamiltonCycle=palpha-Approximation von TSP 1:05:45 Pseudopolynomielle Algorithmen 1:07:56 Beispiel Rucksackproblem

    1h 9m
See All (27)

About

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

Information

More From Karlsruher Institut für Technologie

To listen to explicit episodes, sign in.

Stay up to date with this show

Sign in or sign up to follow shows, save episodes and get the latest updates.
Select a country or region

Africa, Middle East, and India

Asia Pacific

Europe

Latin America and the Caribbean

The United States and Canada