Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 episodes:

• February 06, 202018: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 04.02.2020

  18 |

  0:00:00 Start

  0:00:11 Kodierung zum Schutz gegen Übertragungsfehler

  0:01:42 Paritätscodes - Einfach binär

  0:04:45 Kreuzsicherung

  0:10:05 Paritätscodes

  0:16:27 Block-Codes

  0:17:03 Hamming-Distanz und Fehlerkorrektur

  0:21:23 Beispiel

  ...more

  ---

• January 30, 202017: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.01.2020

  17 |

  0:00:00 Start

  0:03:24 Material für Informationstheorie

  0:03:57 Information

  0:12:08 Wiederholung: Rechenregeln Logarithmus

  0:17:45 Entropie

  0:24:46 Entropie zu einer Münze

  0:26:09 (Platzsparende) Kodierungen

  0:28:48 Präfix-Codes

  0:31:13 Kodierungsbäume

  0:36:18 Beispiel: Morse-Alphabet

  0:37:38 Quellenkodierungstheorem

  0:39:41 Beispiel: Shannon-Fano-Kodierung

  0:44:44 Kodierungsbaum Shannon-Fano

  0:45:44 Beispiel: Huffman-Kodierung

  0:49:25 Vorbereitendes Lemma

  0:55:09 Beweis - Induktionsschluss

  1:00:43 Nachteile der Huffman-Kodierung

  1:02:46 Lauflängenkodierung

  1:10:49 Kodierung zum Schutz gegen Übertragungsfehler

  ...more

  ---

• January 24, 202016: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 23.01.2020

  16 |

  0:00:00 Start

  0:00:21 Letzte Vorlesung

  0:07:22 Wdh.: Greibach-Normalform, Kellerautomat

  0:11:54 Kellerautomaten

  0:15:10 Beispiel - Greibach-Normalform

  0:18:13 Beipiel - Kellerautomat

  0:21:23 Beweis: Greibach-Normalform -> NPDA

  0:27:20 Beweis: NPDA -> Kontextfreie Grammatik

  0:52:53 Zwischenfazit zu kontextfreien Grammatiken

  0:59:24 Das Post´sche Korrespondenzproblem

  1:06:53 Eindeutigkeit von kontextfreien Grammatiken

  1:10:13 Sprache der Korrekten Rechenwege

  ...more

  ---

• January 14, 202015: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 14.01.2020

  15 |

  0:00:00 Start

  0:00:19 Letzte Vorlesung

  0:01:21 Heutige Vorlesung

  0:03:24 Weiere Eigenschaften kontextfreier Sprachen

  0:17:59 Ein Maschinenmodell für Chomsky-2

  0:23:18 Greibach-Normalform

  0:26:01 Beweis

  0:53:04 Kellerautomaten

  ...more

  ---

• January 10, 202014: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 09.01.2020

  14 |

  0:00:00 Start

  0:00:31 Übersicht

  0:04:47 Das Pumping-Lemma für kontextfreie Sprachen

  0:13:52 Ogden´s Lemma für kontextfreie Sprachen

  0:15:48 Beweis von Ogden´s Lemma

  0:28:07 Echtheit der Chomsky-Hierarchie

  0:30:18 Beweis

  0:44:49 Eigenschaften kontextfreier Sprachen

  0:48:12 Nutzlose Variablen

  0:51:27 Schritt 1

  1:01:10 Schritt 2

  1:05:22 Endliche kontextfreie Sprachen

  1:08:51 Beispielgraph

  ...more

  ---

• December 17, 201913: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 17.12.2019

  13 |

  0:00:00 Start

  0:01:20 Beispiele

  0:04:40 Grammatiken

  0:06:42 Bemerkungen

  0:11:29 Die Chomsky-Hierarchie

  0:24:56 Chomsky-0-Grammatiken und Semientscheidbarkeit

  0:30:11 Beweis – Beschreibung der Grammatik G

  0:40:28 Chomsky-3-Grammatiken und reguläre Sprachen

  0:42:26 Beweis

  0:53:06 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen

  0:57:03 Satz

  ...more

  ---

• December 12, 201912: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 10.12.2019

  12 |

  0:00:00 Start

  0:00:42 Wiederholung letzte Vorlesung

  0:08:12 Definition

  0:14:31 Metrisches TSP

  0:16:07 Approximation von min-METRIC-TSP

  0:27:08 Bemerkungen zur Approximierbarkeit

  0:31:25 Approximationsschemata

  0:37:51 Ein FPTAS für max-KNAPSACK

  0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK

  0:52:46 Maximierungsprobleme

  1:01:47 Optimierungsprobleme

  1:10:58 Approximierbarkeit von min-Vertex-Color

  1:23:39 Abschluss des Kapitels zur Komplexitätstheorie

  ...more

  ---

• December 06, 201911: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 05.12.2019

  11 |

  0:00:00 Start

  0:01:57 Verallgemeinerte NP-Schwere

  0:04:05 Das Problem INTEGER PROGRAMMING

  0:07:55 INTEGER PROGRAMMING ist NP-schwer

  0:16:21 Bemerkungen

  0:21:18 Kapitel

  0:24:34 Pseudopolynomiale Algorithmen

  0:28:14 Beispiel: Problem KNAPSACK

  0:37:52 Starke NP-Vollständigkeit

  0:44:41 Kapitel

  0:47:54 Absolute Approximationsalgorithmen

  0:49:27 Das allgemeine KNAPSACK-Suchproblem

  0:51:56 Negativ-Resultat

  0:53:52 (Kontrapositions-)Beweis

  0:59:35 Approximation mit relativer Gütegarantie

  1:01:11 Genereller Ansatz

  1:03:54 Beispiel: Greedy-Algorithmus für KNAPSACK

  1:12:18 Grenzen für den Greedy-Algorithmus

  ...more

  ---

• November 28, 201910: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.2019

  10 |

  0:00:00 Start

  0:00:27 Letzte/Diese Vorlesung

  0:04:04 Das Problem SUBSET SUM

  0:05:37 NP-Vollständigkeit von SUBSET SUM

  0:21:39 Das Problem PARTITION

  0:22:29 Beweis: NP-Vollständigkeit von PARTITION

  0:28:40 Das Problem KNAPSACK

  0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK

  0:33:39 Auswirkung auf die Frage P= NP

  0:40:15 Zusammenfassung

  0:45:01 Die Klassen NPC und NPI

  0:46:23 Die Klassen co-P und co-NP

  0:51:28 Das TSP-Komplement-Problem

  0:54:27 NP-vollständig vs. co-NP

  0:58:19 Das Problem Subgraphisomorphie

  1:00:17 Das Problem Graphisomorphie

  1:02:06 Die Polynomielle Hierarchie

  1:12:34 Suchprobleme

  1:13:13 Beispiel: TSP-Suchproblem

  1:14:53 Beispiel: Hamilton-Kreis Suchproblem

  1:16:18 NP-Schwere bei Suchproblemen

  1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem

  ...more

  ---

• November 26, 201909: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019

  09 |

  0:00:00 Start

  0:00:08 Letzte Vorlesung

  0:08:16 Plan für heute

  0:10:46 Das Problem 3SAT

  0:12:53 Beweis: NP-Vollständigkeit von 3SAT

  0:31:50 Das Problem 2SAT

  0:34:00 Das Problem MAX2SAT

  0:36:49 Das Problem CLIQUE

  0:39:07 Beweis: NP-Voillständigkeit von CLIQUE

  0:54:25 Das Problem COLOR

  0:55:33 Beweis: NP-Vollständigkeit von 3COLOR

  0:57:09 Konstruktion von 3COLOR-Instanz G

  1:02:30 Polynomialität der Reduktion

  1:03:12 Instanz G 3-färbbar

  1:08:08 Zwischenstand Polynomiale Reduktion

  1:10:27 Das Problem EXACT COVER

  1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER

  1:14:34 Konstruktion von (X, S)

  1:22:00 G 3-färbbar -> exakte Überdeckung

  ...more

  ---