Algorithmen II, Übung und Vorlesung, WS 2016/17, 24.01.2017, 23

Autor

Michael Axtmann, Simon Gog

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

23 |
0:00:00 Starten
0:00:07 Übung 12 - Online Algorithmen
0:02:44 Grundlagen
0:04:19 Gütemaß
0:05:21 Ski Rental Problem
0:06:46 Randomisierte Ski Rental Strategie
0:18:02 Doubling Strategie
0:18:52 Online Bidding
0:40:30 Zusammenfassung
0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen
0:45:17 Elementare Geometrische Objekte
0:49:22 Typische Fragestellungen
0:53:29 Verweissensitive Grafik (Wikipedia)
0:54:30 Datenstrukturen für Punktemengen
0:54:42 Mehr Fragestellungen
0:59:47 9.1 Streckenschnitt (line segment intersection)
1:01:02 Streckenschnitt: Anwendungen
1:01:44 Streckenschnitt: Naiver Algorithmus
1:02:18 Streckenschnitt: Untere Schranke
1:04:17 Idee: Plane-Sweep-Algorithmen
1:04:54 Plane-Sweep für orth. Streckenschnitt
1:10:02 Analyse orth. Streckenschnitt
1:12:03 Verallgemeinerung - aber erstmal ""nicht ganz""
1:12:55 Verallgemeinerung - Grundidee
1:16:48 Verallgemeinerung - Korrektheit
1:17:46 Verallgemeinerung - Implementierung
1:23:05 Verallgemeinerung - Beispiel
1:24:05 Verallgemeinerung - Analyse

Laufzeit (hh:mm:ss)

01:25:15

Serie

Algorithmen II, Vorlesung, WS 2016/17

Publiziert am

02.02.2017

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz