PODCAST

Theoretische Grundlagen der Informatik, Vorlesung, WS15/16

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:07:17

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/15

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

00:58:08

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/15

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

01:21:56

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/08

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

01:23:05

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/05

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:

01:29:29

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/04

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

01:22:23

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/02/01

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

01:05:34

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/01/28

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

01:08:38

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/01/21

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

01:31:10

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/01/21

18: Vorlesung und Übung| 0:00:00 Starten 0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig 0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart"" 0:02:47 Wiederholung: Negationen in die Blätter drücken 0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen 0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz 0:05:05 Exkurs: 2SAT ∈ P 0:10:27 CLIQUE 0:14:22 Beweis Clique ∈ NP 0:15:01 Beweis von ""CLIQUE ist NP-hart"" 0:19:57 Beispiel 0:29:19 VERTEX COVER

01:13:00

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/01/14

17: Vorlesung| 0:00:00 Starten 0:00:53 Wiederholung Komplexitätstheorie 0:08:54 Polynominale Reduzierbarkeit 0:09:55 Beispiel 0:10:57 NP-harte und Np-Vollständige Probleme 0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ? 0:13:50 SAT: Das Erfüllbarkeitsproblem 0:17:03 Beweis von SAT 0:17:31 Beweis das SAT-NP-hart ist. 0:19:45 Variablen für F 0:24:53 Die Architektir von F= 0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist 0:31:44 Es kann nur einen geben 0:33:05

01:24:21

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2016/01/07

16: Übung und Vorlesung| 0:00:00 Starten 0:00:56 Rückblick: Chomsky-3 0:05:29 Rückblick: Chomsky-3 Verfahren 0:16:18 Rückblick: Chomsky-2 0:19:33 Rückblick: Chomsky-2 Verfahren 0:27:23 Rückblick: Chomsky-0/1 0:30:41 Rückblick: Entscheidbarkeit 0:36:54 Ausblick: Komplexitätstheorie 0:38:54 Video: Game of Life Automat 0:43:27 Video: Variante von Game of Life mit realen Werten 0:45:23 Vorlesung 0:46:03 Kapitel 2: Komplexitätstheorie 0:46:34 Obere Schranken 0:46:54 Untere Schranken 0:47:23 Untere

01:11:06

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/12/28

15: Vorlesung| 0:00:00 Starten 0:01:24 Halteproblem 0:02:27 Das beschränkte Halteproblem 0:02:57 Mehr unentscheidbare Probleme 0:03:15 Unentscheidbarkeit von Leerheit 0:09:13 Unentscheidbarkeit von Vollständigkeit 0:09:31 Metaprogrammierung 0:11:03 Postsches Korrespondenzproblem (PKP) 0:12:16 Beispiel 0:19:04 PCP ist semientscheidbar 0:20:25 PCP ist unentscheidbar 0:22:56 Hilberts 10. Problem- Diophantische Gleichungen 0:25:32 Abgeschlossenheit entscheidbarer Sprachen 0:27:58 Anwendung der

00:59:17

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/12/14

14: Vorlesung und Übung| 0:00:00 Starten 0:00:10 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit 0:00:44 Paradoxien und Selbstbezüglichkeit 0:01:28 Entscheidbarkeit 0:01:47 Äquivalente Aussagen 0:02:37 2.7 Nicht-entscheidbare Probleme 0:03:04 Normierung von Turing-Maschinen 0:04:24 Gödelnummer (M) einer Turingmaschine M 0:09:01 Gödelnummer 0:09:59 Beispiel 0:10:39 Diagonalsprache 0:12:09 Kapitel 12 0:12:33 Satz: Diagonalsprache ist unentscheidbar 0:15:53 Korollar 0:16:20 Universelle

01:10:05

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/12/10

13: Vorlesung| 0:00:00 Starten 0:00:10 LOOP-Programme 0:01:22 2.5 Die Ackermannfunktion 0:04:23 Totalität der Ackermannfunktion 0:07:53 Wie große Zahlen berechnet ein Loop Programm? 0:10:35 Die Ackermann Funktion ist nicht Loop-berechenbar 0:12:30 Beispiele 0:14:46 Monotonie der Ackermann Funktion 0:15:41 Beweis 0:34:56 Mehr schnell wachsende Funktionen 0:37:13 Wissen über Fleißige Biber 0:38:36 Rekordhalter 0:40:47 Langsam wachsende Funktionen 0:41:34 Union-Find Datenstruktur 0:44:30 2.6

01:19:35

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/12/10

12: Vorlesung und Übung | 0:00:00 Starten 0:00:10 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit 0:01:04 LOOP-Programme 0:09:28 While-Programm 0:11:26 Äquivalenz von Maschinenmodellen 0:13:55 Turingmaschine emuliert k-Band-TM 0:20:07 k-Band-TM emuliert Registermaschine 0:22:40 Registermaschine emuliert RAM 0:27:59 Markov-Algorithmen 0:36:03 Semi-Thue-Systeme 0:37:16 Zellularautomaten 0:44:32 Quantencomputer 0:49:16 2.4 Primitiv rekursive und µ-rekursive Funktionen 0:50:02 2.5

01:08:45

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/12/03

11: Vorlesung | 0:00:00 Starten 0:00:09 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These 0:00:43 2.2 Intuitiver Berechenbarkeitsbegriff 0:02:41 Beispiel 0:04:51 Exkurs: einige Nährungen für Pi 0:07:47 Beispiel 0:13:09 Nichtberechenbare Funktionen 0:17:58 Church´sche These 0:18:56 Turingmaschinen berechnen Funktionen 0:22:07 Turingmaschinen berechnen numerische Funktionen 0:23:17 Akzeption -> Funktion 0:24:44 Beispiel 0:32:02 Funktionsweise 0:35:24 Beispiel: Die überall undefinierte

01:16:40

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/11/30

10: Vorlesung | 0:00:00 Starten 0:00:08 Abschlusseigenschaften Typ 1 0:01:39 Abschluss Vereinigung Typ 0/1 0:03:19 Abschluss Produkt Typ 0/1 0:05:11 Abschluss Komplement Typ 1 0:12:39 Berechnung 0:20:02 Typ 0 Sprachen 0:22:49 Überblick Chomsky-Hierarchie 0:27:54 Abschlusseigenschaften 0:30:09 Entscheidbarkeitsprobleme 0:31:02 Komplexität des Wortproblemes 0:32:27 Überblick Chomsky-Hierarchie 0:33:43 Chomsky-Hierarchie: Eine Kritik 0:37:29 2 Berechenbarkeitstheorie, 2.1 Intuitiver

01:09:25

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/11/30

08-02: Vorlesung | 0:00:00 Starten 0:00:07 1.3.2 Das Pumping Lemma 0:00:41 Beweis Pumping Lemma 0:01:03 Konsturktion von Wiederholungen: 0:01:24 Faustregeln für Beweise mit dem Pumping Lemma 0:01:47 Abgeschlossenheit von KFG unter U 0:02:07 Nichtabgeschlossenheit von KFG unter U 0:02:30 Beispiel 0:02:56 1.3.5 Kellerautomaten 0:04:08 Konfiguration einer Kellermaschine 0:04:30 Funktionsweise einer Kellermaschine 0:04:54 Kellermaschine als Akzeptor 0:05:19 Beispiel 0:06:04 Satz: L ist

01:04:50

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/11/26

09: Vorlesung | 0:00:00 Starten 0:00:08 1.4 Kontextsensitive und Typ 0-Sprachen 0:00:35 Kuroda Normalform 0:02:10 Turing Maschine 0:03:32 Deterministische Einband-Turingmaschine 0:06:23 Nichtdeterministische Turingmaschine 0:07:21 Warum Turingmaschine? 0:10:39 Ursprüngliche Motivation 0:13:23 Potentiell unendlicher Speicher? 0:15:32 Konfiguration einer TM 0:16:47 Funktionsweise DTM 0:18:12 Funktionsweise NTM 0:18:24 Wann hält eine DTM? 0:19:30 Wann hält eine NTM? 0:20:06 Graphinterpretation 0:22:24

01:21:38

Theoretische Grundlagen der Informatik, WS 2015/2016,...

Theoretische Grundlagen der Informatik, Vorlesung,... ·

2015/11/24

08: Vorlesung | 0:00:00 Starten 0:00:07 Wiederholung 0:01:05 1.3.2 Das Pumping Lemma 0:03:48 Beweis Pumping Lemma 0:13:10 Hilfs Lemma 0:14:39 Anwendung Pumping Lemma 0:22:02 Faustregeln für Beweise mit dem Pumping Lemma 0:26:21 Abschlusseigenschaften 0:27:26 Abgeschlossenheit von KFG unter Vereinigungsmengen 0:29:37 Abgeschlossenheit von KFG unter Produktbildungen 0:30:38 Abgeschlossenheit von KFG unter * 0:33:25 Nichtabgeschlossenheit von KFG 0:38:23 1.3.4 Der CYK-Algorithmus ( Das Wortproblem für

27 results

Theoretische Grundlagen der Informatik, Vorlesung, WS15/16

All Episodes

Similar Podcasts

Science Talk

Albert Einstein College of Medicine

五分钟心理学

柠檬心理

Daily Facts

Amalia Dupray and Montgomery Jones.

Les dents et dodo

BFMTV

Veterinary Clinical Podcasts

The Royal Veterinary College