Algorithmen 1, SS2015, Vorlesung Karlsruher Institut für Technologie (KIT)
-
- Education
Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz, Jun.-Prof. Henning Meyerhenke | Übungsleiter: Christian Staudt, Christoph Striecks | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
-
- video
Algorithmen I, SS 2015, gehalten am 15.07.2015, Vorlesung 26 (+ Übung)
26: Übung |
Vorbereitung für die Klausur -
- video
Algorithmen I, SS 2015, gehalten am 13.07.2015, Vorlesung 25
25: Vorlesung |
00:00:12 Ziele von PRAM-Algorithmen
00:01:47 Summe auf der PRAM
00:02:06 Das Prinzip von Arbeit und Laufzeit
00:05:17 Diskussion
00:06:06 Konvexe Hülle
00:07:03 Obere konvexe Hülle
00:13:32 Obere gemeinsame Tangente
00:16:14 Algorithmus UCH
00:33:27 Zusammenfassung
00:36:16 Kap. 14: Zusammenfassung
00:37:33 Zusammenfassung-Datenstruktur
00:42:51 Zusammenfassung- Algorithmen
00:45:24 Zusammenfassung- Entwurfstechniken I
00:53:01 Zusammenfassung- Entwurfstechniken II
00:58:56 Zusammenfassung- Analysentechniken
01:01:59 Zusammenfassung- weitere Techniken
01:06:36 Themen zur Klausur -
- video
Algorithmen I, SS 2015, gehalten am 08.07.2015, Vorlesung 24
24: Vorlesung |
00:00:07 Systematische Suche
00:00:24 Beispiel: Branch-and-Bound für das Rucksackproblem
00:00:32 Beispielrechnung
00:00:37 Lokale Suche – global denken, lokal handeln
00:00:48 Hill Climbing
00:00:50 Warum die Nachbarschaft wichtig ist
00:00:54 Jenseits von Hill Climbing
00:01:19 Evolutionäre Algorithmen
00:01:23 Zusammenfassung
00:01:25 Kap. 13: Parallele Algorithmen
00:01:27 Werbeblock
00:02:07 Rechnertypen
00:02:16 Gemeinsamer Speicher (shared memory)
00:02:31 Rechenmodell
00:04:23 PRAM-Modelle
00:05:42 Ziele von PRAM-Algorithmen
00:08:13 Summe auf der PRAM
00:21:56 Bewertung paralleler Algorithmen
00:24:16 Das Prinzip von Arbeit und Laufzeit
00:26:17 Summe auf der PRAM
00:34:26 Das Prinzip von Arbeit und Laufzeit (Work-Time-Principle)
00:37:46 Optimalität
00:40:20 Diskussion -
- video
Algorithmen I, SS 2015, gehalten am 06.07.2015, Vorlesung 23
23: Vorlesung |
00:00:07 Dynamische Programmierung – Aufbau aus Bausteinen
00:02:12 Systematische Suche
00:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem
00:20:42 Beispielrechnung
00:33:16 Branch-and-Bound – allgemein
00:34:48 Beispielrechnung
00:42:53 Lokale Suche – global denken, lokal handeln
00:47:44 Hill Climbing
00:49:08 Problem: Lokale Optima
00:51:55 Warum die Nachbarschaft wichtig ist
00:53:41 Jenseits von Hill Climbing
01:00:35 Evolutionäre Algorithmen
01:03:40 Zusammenfassung
01:10:03 Werbeblock
01:10:48 Kap. 13: Parallele Algorithmen
01:20:51 Rechnertypen
01:24:10 Gemeinsamer Speicher (shared memory)
01:25:07 Rechenmodell -
- video
Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22
22: Vorlesung |
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 -
- video
Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21
21: Vorlesung |
00:00:07 Der Jarnik-Prim-Algorithmus
00:04:27 Analyse
00:05:08 Kruskals Algorithmus (1956)
00:06:27 Kruskals Algorithmus – Korrektheit
00:07:14 Union-Find Datenstruktur
00:08:30 Union-Find Datenstruktur – Erste Vision
00:09:58 Pfadkompression
00:10:26 Union by Rank
00:10:58 Analyse – nur Union by rank
00:11:35 Analyse – nur Pfadkompression
00:12:04 Analyse – Pfadkompression + Union by rank
00:15:22 Ackermannfunktion – Beispiele
00:18:31 Kruskal mit Union-Find
00:21:15 Union-Find Datenstruktur
00:22:56 Beispiel
00:27:45 Vergleich Jarnik-Prim – Kruskal
00:28:55 Analyse
00:29:42 Mehr MST-Algorithmen
00:33:54 Messungen, Zufallsgraph
00:36:06 Zusammenfassung
00:38:21 Kap. 12: Generische Optimierungsansätze
00:39:27 Durchgehendes Beispiel: Rucksackproblem
00:42:08 Allgemein: Maximierungsproblem (L, f)
00:43:24 Black-Box-Löser
00:44:36 Lineare Programmierung
00:47:38 Ein einfaches Beispiel
00:50:16 Beispiel: Kürzeste Wege
00:53:59 Eine Anwendung – Tierfutter
00:56:08 Verfeinerungen
00:57:49 Algorithmen und Implementierungen
00:59:30 Ganzzahlige Lineare Programmierung
01:01:04 Beispiel: Rucksackproblem
01:02:04 Umgang mit (M)ILPs
01:03:45 Nie zurückschauen – Greedy-Algorithmen
01:04:38 Optimale Greedy-Algorithmen
01:05:16 Beispiel: Rucksackproblem