Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

By Karlsruher Institut für Technologie (KIT)

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18... more

· Education

Download on the App Store

Download on the App Store

Get it on Google Play

FAQs about Theoretische Grundlagen der Informatik, Vorlesung, WS17/18:

How many episodes does Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 have?

The podcast currently has 19 episodes available.

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 episodes:

December 05, 2017 09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 28.11.2017
09 |
0:00:00 Starten
0:00:39 NP-Vollständigkeit
0:02:03 Transitivität der poly. Transformation
0:02:31 Korollar
0:03:49 Das Problem 3-SAT
0:05:37 Beweis: NP-Vollständigkeit von 3-SAT
0:20:16 Das Problem 2SAT
0:22:09 Das Problem MAX2SAT
0:24:18 Das Problem CLIQUE
0:27:48 Beweis: NP-Vollständigkeit von CLIQUE
0:36:44 Das Problem COLOR
0:37:57 Beweis: NP-Vollständigkeit von 3COLOR
0:39:06 Konstruktion von 3COLOR-Instanz G
0:43:16 Beispielgraph zur Reduktion
0:45:12 Polynomialität der Reduktion
0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar
0:45:57 Instanz G ist 3-färbbar
0:50:30 Das Problem EXACT COVER
0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER
0:55:30 Konstruktion von (X,S)
1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung
...more
1h 10min
November 30, 2017 08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 21.11.2017
08 |
0:00:00 Starten
0:00:17 Gliederung
0:01:30 Turingmaschinen
0:19:04 Erweiterung von Turingmaschinen
0:19:18 Mehrere Spuren
0:23:26 Mehrere Bänder
0:25:01 Erweiterte Turingmaschinen
0:31:56 Entscheidbarkeit
0:32:09 Entscheidbarkeit - Definitionen
0:36:34 Entscheidbarkeit - Zusammenhänge
0:45:32 Entscheidbarkeit - Überblick
0:46:31 Entscheidbarkeit - Komplementbildung
0:48:09 Entscheidbarkeit - Überblick
0:51:01 Entscheidbarkeit - Beispiele
0:51:33 Diagonalsprache
0:55:42 Halteproblem
0:58:52 Iniverselle Sprache
0:59:23 Post'sches Korrespondenzproblem
1:02:59 Hilberts zehntes Problem
1:08:44 Äquivalenzproblem
1:09:35 Entscheidbarkeit - Werkzeugkasten
1:10:01 Satz von Rice
1:14:02 Zusammenfassung (Werkzeugkasten)
...more
1h 19min
November 21, 2017 07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 16.11.2017
07 |
0:00:00 Starten
0:00:06 Definitionen zur TM
0:01:15 Unentscheidbarkeit der Diagonalsprache
0:02:42 Die Universelle Sprache
0:09:51 Satz von Rice - Motivation
0:17:10 Das Post'sche Korrespondenzproblem
0:21:44 Eigenschaften von (semi-)entscheibaren Sprachen
0:28:02 Komplexitätstheorie
0:32:53 Wie sieht ein Problem aus?
0:37:56 Definition: Problem
0:39:34 Definition: Kodierungsschema
0:43:19 Äquivalenz von Kodierungsschemata
0:44:33 Entscheidungsprobleme
0:46:43 Korrespondenz von Entscheidungsproblemen und Sprachen
0:51:27 Zeitkomplexität
0:53:04 Die Klasse P
0:56:35 Algorithmus OPT-TOUR (als Beweis)
0:59:27 Die Nichtdeterministische Turingmaschine
1:04:41 Übertragung auf Entscheidungsprobleme PI
1:07:16 Bemerkungen zur NTM
1:13:15 Die Klasse NP
...more
1h 20min
November 21, 2017 06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.11.2017
06 |
0:00:00 Starten
0:01:54 Formale Definition der Tuting-Maschine
0:04:18 Definition zur TM
0:07:42 Motation: Konfiguration
0:10:03 Beispiel: Konfiguration
0:20:09 Definition: berechenbar/ totalrekursiv
0:22:30 Beispiel
0:30:39 Entscheidbarkeit und Berechenbarkeit
0:32:46 Korollar
0:34:56 Die Church'sche These
0:39:00 Erweiterungen der Turing-Maschine
0:44:35 Die universelle Turing-Maschine
0:48:15 Die Gödelnummer
0:53:04 Die Gödelnummer - Bemerkungen
0:55:28 Die Gödelnummer - Beispiel
0:58:51 Definition
0:59:21 Die Diagonalsprache
1:04:09 Die Diagonalsprache - Veranschaulichung
1:05:41 Unentscheidbarkeit der Diagonalsprache
1:07:53 Korollar
1:10:12 Paradoxien und Selbstbezüglichkeit
1:11:32 Halteproblem
...more
1h 20min
November 11, 2017 05: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 07.11.2017
05 |
0:00:00 Starten
0:00:21 Frage
0:04:24 Wiederholung Äquivalenzklassenautomat
0:09:44 Definitionen: Rechtsinvarianz und Index
0:17:24 Nerode- Relation
0:22:12 Satz von Nerode
0:25:40 Beweis zu Satz von Nerode: (1)-->(2)
0:31:49 Beweis zu Satz von Nerode: (2)-->(3)
0:37:57 Beweis zu Satz von Nerode: (3)-->(1)
0:46:16 Korollar
0:49:09 Minimalitäat des Äquivalenzklassenautomats
0:53:15 Zusammenfassung
0:56:04 Historisches
0:59:37 Turing-Maschinen und Berechenbarkeit
1:00:59 Die Registermaschine (RAM)
1:02:13 Befehle der Registermaschine (RAM)
1:03:12 Die Turing-Maschine (TM)
1:06:53 Formale Definition der Turing-Maschine
1:08:59 Bemerkung zur TM
1:12:15 Beispiel-Turing-Maschine
1:18:17 Definition zur TM
...more
1h 24min
November 06, 2017 04: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 02.11.2017
04 |
0:00:00 Starten
0:01:20 Pumping-Lemma für reguläre Sprachen
0:08:08 Verallgemeintertes PL für reguläre Sprachen
0:23:36 Beispiel
0:31:37 Äquivalenz
0:34:26 Der Äquivalenzklassenautomat
0:44:21 Frage
0:54:24 Vorgehensweise
0:55:57 Beispiel zur Vorgehensweise
...more
1h 3min
November 06, 2017 03: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 24.10.2017
03 |
0:00:00 Starten
0:00:05 letzte Vorlesung...
0:05:42 Entfernen von Epsilon-Übergängen
0:16:09 EA-Regularität
0:37:53 Beispiel
0:52:18 Frage: Was können endliche Automaten nicht?
0:55:53 Pumping-Lemma für reguläre Sprachen
1:06:31 Bemerkung und Beispiele
...more
1h 18min
November 03, 2017 02: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 19.10.2017
02 |
0:00:00 Starten
0:00:38 Endliche Automaten und Reguläre Sprachen
0:16:02 Nichtdeterministische endliche Automaten
0:22:10 Beispiele für NEA's
0:27:11 Äquivalenz von NEA's und DEA's
0:28:54 Beispiel Potenzmengenkonstruktion
...more
1h 20min
November 03, 2017 01: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 17.10.2017
01 |
0:00:00 Starten
0:01:06 Ziel der Vorlesung TGI
0:07:08 Wiederholung aus Grundbegriffe der Informatik
0:09:11 Wörter
0:13:56 Formale Sprachen
0:25:28 Reguläre Sprachen
0:32:09 Reguläre Ausdrücke
0:41:42 Endliche Automaten
0:48:57 Kontextfreie Grammatiken
...more
1h 2min

FAQs about Theoretische Grundlagen der Informatik, Vorlesung, WS17/18:

How many episodes does Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 have?

The podcast currently has 19 episodes available.

More shows like Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

IEEE International Conference on Robotics and Automation, 2013 by Karlsruher Institut für Technologie (KIT)

IEEE International Conference on Robotics and Automation, 2013

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2015 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2015

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung

0 Listeners

Algorithmen 1, SS2017, Vorlesung by Karlsruher Institut für Technologie (KIT)

Algorithmen 1, SS2017, Vorlesung

0 Listeners

Einführung in die Geophysik 1, WS17/18, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Geophysik 1, WS17/18, Vorlesung

0 Listeners

Softwaretechnik 1, Vorlesung, SS2018 by Karlsruher Institut für Technologie (KIT)

Softwaretechnik 1, Vorlesung, SS2018

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019

0 Listeners

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 by Karlsruher Institut für Technologie (KIT)

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

0 Listeners