DiscoverTheoretische Grundlagen der Informatik, Vorlesung, WS14/15
Theoretische Grundlagen der Informatik, Vorlesung, WS14/15
Claim Ownership

Theoretische Grundlagen der Informatik, Vorlesung, WS14/15

Author: Karlsruher Institut für Technologie (KIT)

Subscribed: 20Played: 28
Share

Description

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
26 Episodes
Reverse
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 04.12.2014, Lektion 10

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 04.12.2014, Lektion 10

2015-08-2101:15:21

10: Vorlesung: NP-Vollständigkeit | Das Problem 3-SAT | Beweis: NP-Vollständigkeit von 3-SAT | Das Problem 2SAT | Das Problem MAX2SAT | Das Problem CLIEQUE | Beweis: NP-Vollständigkeit von CLIQUE | Das Problem COLOR | Beweis: NP-Vollständigkeit von 3COLOR | Konstruktion von 3COLOR-Instanz G | Beispielgraph zur Reduktion | Polynomialität der Reduktion
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 09.12.2014, Lektion 11

2015-08-2101:24:00

11: Vorlesung: Das Problem COLOR
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.12.2014, Übung 4

2015-08-2158:02

Übung 4: Turingmaschinen und Berechenbarkeit | Komplexitätsklassen
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12

2015-08-2101:24:37

12: Vorlesung: Das Problem Subgraphisomorphie | Suchprobleme | Beispiel: TSP-Suchproblem | Beispiel: Hamilton-Kries Suchproblem | Aufzählungsprobleme | Reduzierbarkeit für Suchprobleme | Orakel-Turing-Maschine | Orakel-TM: Verhalten im Fragezustand | Turing-Reduktion | NP-schwer | Beweisskizze | Verallgemeinerte NP-Schwere | Das Problem INTERGER PROGRAMMING | Beweis | Pseudopolynomielle Algorithmen | Beispiel: Problem KNAPSACK | Starke NP-Vollständigkeit | Absolute Approximationsalgorithmen | Das allgemeine KNAPPSACK-Suchproblem | Satz | (Widerspruchs-)Beweis | Approximation mit relativer Gütegarantie | Beispiel: Greedy-Algorithmus für KNAPSACK
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.12.2014, Lektion 13

2015-08-2101:08:13

13: Vorlesung: Komlexitätsklassen
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 08.01.2015, Übung 5

2015-08-2101:17:25

Übung 5: Optimierungsproblem, Optimalwertproblem, Entscheidungsproblem | NP-vollständige Probleme
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 13.01.2015, Lektion 14

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 13.01.2015, Lektion 14

2015-08-2101:11:43

14: Vorlesung: Grammatiken
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 15.01.2015, Lektion 15

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 15.01.2015, Lektion 15

2015-08-2101:23:49

15: Vorlesung: Grammatiken
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.01.2015, Übung 6

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.01.2015, Übung 6

2015-08-2101:22:23

Übung 6: NP und co-NP | Pseudopolynomielle Algorithmen | Approximationsalgorithmen |Ganzzahlige Programme
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 22.01.2015, Lektion 16

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 22.01.2015, Lektion 16

2015-08-2101:24:11

16: Vorlesung: Kontextfreie Sprachen
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.01.2015, Lektion 17

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.01.2015, Lektion 17

2015-08-2101:28:55

17: Vorlesung: Kontextfreie Sprachen
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 03.02.2015, Lektion 19

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 03.02.2015, Lektion 19

2015-08-2101:23:05

19: Vorlesung: Kontextfreie Sprachen
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 05.02.2015, Lektion 19

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 05.02.2015, Lektion 19

2015-08-2101:17:46

19: Vorlesung: Informationstheorie
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 12.02.2015, Übung 8

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 12.02.2015, Übung 8

2015-08-2101:10:12

Übung 8: Kellerautomaten
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.11.2014, Übung 3

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 27.11.2014, Übung 3

2015-08-1801:21:16

Übung 3: Minimierung von Automaten | Nerode-Relation | Turing-Maschinen | Erweiterte Turingmaschinen | Universelle Turingmaschine
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 25.11.2014, Lektion 09

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 25.11.2014, Lektion 09

2015-08-1701:28:30

09: Vorlesung: NP-vollständige Probleme
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.11.2014, Übung 2

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 18.11.2014, Übung 2

2015-08-1443:56

Übung 2: Formale Sprachen und reguläre Ausdrücke | Nicht deterministische endliche Automaten | Pumping-Lemma | Eigenschaften von endlichen Automaten | Potenzmengenkonstruktion
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.11.2014, Lektion 08

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 20.11.2014, Lektion 08

2015-08-1401:18:28

08: Vorlesung: Sprachen, Probleme und Zeitkomplexität | Nichtdeterministische Turingmaschinen und die Klasse NP
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.11.2014, Lektion 06

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 11.11.2014, Lektion 06

2015-08-1301:28:13

06: Vorlesung: Turing-Maschinen und Berechenbarkeit
Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 06.11.2014, Lektion 05

Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 06.11.2014, Lektion 05

2015-08-1353:53

05: Vorlesung: Organisatorisches | Definitionen: Rechtsinvarianz und Index | Nerode-Relation | Satz von Nerode | Beweis zu Satz von Nerode | Korollar | Minimalität des Äquivalenzklassenautomats | Zusammenfassung
loading
Comments 
Google Play
Download from Google Play
Castbox
Download from App Store
usUnited States