Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Karlsruher Institut für Technologie (KIT)
27 episodes
8 months ago
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
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
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, WS 2015/2016, gehalten am 24.11.2015, Vorlesung - 09
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 4 minutes 50 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 24.11.2015, Vorlesung - 09
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 Turingmaschine als Akzeptor
0:23:14 Beispiel: Akzeptor für L=1(0,1)*
0:25:14 Vervollständigung
0:27:15 Beispiele
0:39:14 Varianten von Turingmaschinen
0:41:16 Linear Beschränkte Nichtdet. Turingmaschinen
0:49:21 Unterprogramm: Passende linke Seite suchen
0:51:18 Unterprogramm: Ersetzung für AB -> CD
0:51:48 Unterprogramm: Ersetzung für AB -> C
0:58:21 Phase 1: generiere Wort aus Summe*
0:59:57 Phase 2: simuliere Berechnung der TM
1:02:13 Phase 3: regeneriere Eingabewort
1:03:24 Abschlusseigenschaften Typ 1
1:04:22 Überblick Chomsky-Hierarchie
1:04:27 Chomsky-Hierarchie: Eine Kritik
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
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
