13: Algorithmen 2, Vorlesung, WS 2017/18, 04.12.2017

Autor

Thomas Worsch

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

13 |
0:00:00 Starten
0:02:50 Eine Reihe von Beispiele
0:05:39 Beispiel Job-Scheduling
0:07:07 Beispiel Skiausleihe
0:09:30 Speicherverwaltung
0:12:04 Auswahl von Experten
0:14:23 Beispiel Selbstorganisierende Datenstrukturen
0:15:12 Online-Algorithmus
0:19:55 Competitive Analysis
0:24:45 Wettbewerbsfaktor
0:27:53 Strikte c-Kompetitivität
0:30:07 Wettbewerbsfaktor und strikte Kompetitivität
0:37:13 Nicht-strikte c-Kompetitivität
0:43:36 ListScheduling ist (fast) ein Onlinealgorithmus
0:46:48 Skiausleihe
0:47:19 Optimale Kosten
0:49:27 Deterministische Entscheidung für Skilauf
0:52:03 Speicherverwaltung
0:54:28 Plan für diesen Abschnitt
0:56:17 Longest Forward Distance (LFD)
0:59:14 Optimalität von LFD
0:59:41 Optimalität von LFD-Beweisskizze
1:05:38 Deterministische Onlinealgorithmen
1:15:10 Untere Schranke für den Wettbewerbsfaktor
1:15:39 Untere Schranke für den Wettbewerbsfaktor-Beweisskizze

Laufzeit (hh:mm:ss)

01:23:45

Serie

Algorithmen 2, Vorlesung, WS 2017/18

Publiziert am

05.12.2017

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz