Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22
- 00:00:07 Kap. 12: Generische Optimierungsansätze
- 00:00:23 Durchgehendes Beispiel: Rucksackproblem
- 00:01:19 Allgemein: Maximierungsproblem (L,f)
- 00:02:03 Black-Box-Löser
- 00:02:05 Ein einfaches Beispiel
- 00:02:07 Beispiel: Kürzeste Wege
- 00:02:09 Eine Anwendung – Tierfutter
- 00:02:17 Verfeinerungen
- 00:02:21 Ganzzahlige Lineare Programmierung
- 00:02:25 Umgang mit (M)ILPs
- 00:03:19 Nie zurückschauen – Greedy-Algorithmen
- 00:03:31 Optimale Greedy-Algorithmen
- 00:03:35 Beispiel: Rucksackproblem
- 00:03:43 Dynamische Programmierung – Aufbau aus Bausteinen
- 00:04:50 Beispiel: Rucksackproblem
- 00:08:34 Dynamische Programmierung
- 00:09:57 Beweis des Lemmas
- 00:12:27 Berechnung von P(i,C) elementweise
- 00:20:55 Rekonstruktion der Lösung
- 00:25:20 Beispiel
- 00:34:20 Algorithmenentwurf mittels dynamischer Programmierung
- 00:38:49 Anwendung dynamischer Programmierung
- 00:44:55 Gegenbeispiel: Teilproblemeigenschaft
- 00:46:25 Gegenbeispiel: Austauschbarkeit
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 08.12.2015 |
| Erstellungsdatum | 01.07.2015 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2015-936 |
| Identifikator | KITopen-ID: 1000113573 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen 1, Vorlesung und Übung, SS 2015 |
| Folge | 22 |