26 Folgen

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

Algorithmen 1, SS2015, Vorlesung Karlsruher Institut für Technologie

    • Kurse

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)

    Algorithmen I, SS 2015, gehalten am 15.07.2015, Vorlesung 26 (+ Übung)

    26: Übung |
    Vorbereitung für die Klausur

    • 46 Min.
    • video
    Algorithmen I, SS 2015, gehalten am 13.07.2015, Vorlesung 25

    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

    • 1 Std. 29 Min.
    • video
    Algorithmen I, SS 2015, gehalten am 08.07.2015, Vorlesung 24

    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

    • 42 Min.
    • video
    Algorithmen I, SS 2015, gehalten am 06.07.2015, Vorlesung 23

    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

    • 1 Std. 29 Min.
    • video
    Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22

    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

    • 50 Min.
    • video
    Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21

    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

    • 1 Std. 9 Min.

Top‑Podcasts in Kurse

Mehr von Karlsruher Institut für Technologie