Theoretische Grundlagen der Informatik, WS 2014/15, gehalten am 16.12.2014, Lektion 12
Abstract:
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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 21.08.2015 |
| Erstellungsdatum | 16.12.2014 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2015-570 |
| Identifikator | KITopen-ID: 1000113236 |
| Lizenz | KITopen-Lizenz |
| Serie | Theoretische Grundlagen der Informatik, WS 2014/15 |
| Folge | 16 |