22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016

Autor

Hofheinz. Dennis, Lisa Kohl

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

22 |
0:00:00 Starten
0:00:10 Erinnerung VL 04.07.2016
0:04:13 Wiederholung Beispiel: Rucksackproblem
0:05:15 Nie zurückschauen - Greedy-Algorithmen
0:08:50 Beispiel: Rucksackproblem (1)
0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen
0:18:29 Beispiel: Rucksackproblem (2)
0:21:09 Dynamische Programmierung
0:22:37 Beweis des Lemmas
0:29:10 Berechnung von P(i,C) elementweise
0:33:21 Rekonstruktion des Lösung
0:34:54 Beispiel
0:40:36 Beginn Übung 11
0:40:41 Roadmap
0:41:22 Schwierige Probleme
0:46:15 Erinnerung: Lineare Programme
0:47:48 LP graphisch
0:52:37 Erinnerung: Travelling Salesman Problem
0:53:59 Ein ILP für TSP
0:59:25 Heuristiken
1:01:14 Ameisen Algorithmen
1:04:50 Vertex Cover
1:06:25 Approximation
1:07:21 Eine Approximation für Vertex Cover
1:10:53 Metaheuristiken und Nachbarschaften
1:12:22 Nachbarschaftsheuristiken
1:19:10 Lokale Suche für Vertex Cover
1:20:13 Tabu-Suche für Vertex Cover
1:22:29 Zusammenfassung

Laufzeit (hh:mm:ss)

01:23:36

Serie

Algorithmen I, Vorlesung und Übung, SS 2016

Publiziert am

11.07.2016

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz