KIT | KIT-Bibliothek | Impressum | Datenschutz

Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 15.12.2015, Vorlesung - 15

Sanders, Peter

Abstract:
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 nebenläufigen Ausführung
0:30:05 Nebenläufige Ausführung
0:33:51 2 Kompexitätstheorie
0:35:04 Terminologie und Konventionen
0:35:47 Komplexitätsmaße
0:38:34 Beispiel: Hamiltonkreisproblem
0:41:42 Beispiel Rucksackproblem
0:43:32 Beispiel: Handlungsreisendenproblem
0:46:08 Obere Schranken
0:47:05 Untere Schranken
0:51:19 Untere Schranken: Lösungsansätze
0:53:32 Eine Komplexitätsklasse
0:55:14 Polynom
0:56:00 Komplexitätsklasse P
0:57:02 P für verschiedene Maschinenmodelle
0:59:19 Transformation Optimierungsproblem -> Entscheidungsproblem
1:02:22 Noch eine Komplexitätsklasse
1:05:15 Komplexitätsklasse NP
1:05:50 Beispiel: Rucksackproblem
1:06:49 Alternative Definition von NTIME: Orakel
... mehr

Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 28.12.2015
Erstellungsdatum 15.12.2015
DOI 10.5445/DIVA/2015-979
Identifikator KITopen-ID: 1000113612
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2015/2016
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page