Algorithmen 1, SS2016, Vorlesung

Karlsruher Institut für Technologie (KIT)
  • 0.0 (0)
  • COURSES
Algorithmen 1, SS2016, Vorlesung

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 | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

  1. 29/07/2016 · VIDEO

    25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016

    25 | 0:00:00 Starten 0:00:06 Prioritätslisten 0:03:14 Binäre Heaps 0:07:39 Adressierbare Prioritätslisten 0:08:26 Adressierbare Binäre Heaps 0:09:05 Sortierte Folgen 0:10:42 Binäre Suchbäume 0:16:08 Repräsentation von Graphen 0:23:11 Graphentraversierung 0:30:07 Kürzeste Wege 0:41:22 Minimale Spannbäume 0:46:37 Generische Optimierungsansätze 0:57:13 Zusammenfassung

    58 min

  2. 19/07/2016 · VIDEO

    24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016

    24 | 0:00:00 Starten 0:00:06 Kap. 13: Zusammenfassung 0:03:32 Zusammenfassung - Datenstrukturen 0:06:22 Zusammenfassung - Algorithmen 0:09:41 Zusammenfassung - Entwurfstechniken I 0:12:53 Zusammenfassung - Entwurfstechniken II 0:14:53 Zusammenfassung - Analysetechniken 0:18:06 Zusammenfassung - weitere Techniken 0:18:50 Schnelldurchlauf 0:19:32 Amuse Geule 0:20:05 Exkurs: Pseudocode 0:21:47 Exkurs O-Kalkül, die Erste 0:24:04 Algorithmentheorie 0:25:44 Invarianten 0:26:03 Master Theorem 0:29:27 Form Follows Function 0:30:56 Felder (Arrays) 0:31:46 Amortisierte Komplexität unbeschr. Felder 0:32:39 Beweis: Konto-Methode (oder Versicherung) 0:34:35 Hashing (Streuspeicherung) 0:39:27 Sortieren & Co

    48 min

  3. 14/07/2016 · VIDEO

    23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016

    Die Vorlesung (23, 11.07.16, SS2016) konnte wegen technischer Probleme nicht aufgezeichnet werden. Der Vorlesungsinhalt ist aber identisch mit der Aufzeichnung vom 06.07.2015 (SS2015) 23 | 0:00:00 Starten 0:00:07 Dynamische Programmierung – Aufbau aus Bausteinen 0:02:12 "Systematische SuchSystematische Suche" 0:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem 0:20:42 Beispielrechnung 0:33:16 Branch-and-Bound – allgemein 0:34:48 Beispielrechnung 0:42:53 Lokale Suche – global denken, lokal handeln 0:47:44 Hill Climbing 0:49:08 Problem: Lokale Optima 0:51:55 Warum die Nachbarschaft wichtig ist 0:53:41 Jenseits von Hill Climbing 1:00:35 Evolutionäre Algorithmen 1:03:40 Zusammenfassung 1:10:03 Werbeblock 1:10:48 Kap. 13: Parallele Algorithmen 1:20:51 Rechnertypen 1:24:10 Gemeinsamer Speicher (shared memory) 1:25:07 Rechenmodell

    1h 30m

  4. 11/07/2016 · VIDEO

    22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016

    22 | 0:00:00 Starten 0:00:10 Erinnerung VL 04.07.2016 0:04:13 Wiederholung Beispiel: Rucksackproblem 0:05:15 Nie zurückschauen - Greedy-Algorithmen 0:08:50 Beispiel: Rucksackproblem (1) 0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen 0:18:29 Beispiel: Rucksackproblem (2) 0:21:09 Dynamische Programmierung 0:22:37 Beweis des Lemmas 0:29:10 Berechnung von P(i,C) elementweise 0:33:21 Rekonstruktion des Lösung 0:34:54 Beispiel 0:40:36 Beginn Übung 11 0:40:41 Roadmap 0:41:22 Schwierige Probleme 0:46:15 Erinnerung: Lineare Programme 0:47:48 LP graphisch 0:52:37 Erinnerung: Travelling Salesman Problem 0:53:59 Ein ILP für TSP 0:59:25 Heuristiken 1:01:14 Ameisen Algorithmen 1:04:50 Vertex Cover 1:06:25 Approximation 1:07:21 Eine Approximation für Vertex Cover 1:10:53 Metaheuristiken und Nachbarschaften 1:12:22 Nachbarschaftsheuristiken 1:19:10 Lokale Suche für Vertex Cover 1:20:13 Tabu-Suche für Vertex Cover 1:22:29 Zusammenfassung

    1h 24m

  5. 07/07/2016 · VIDEO

    21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016

    21 | 0:00:00 Starten 0:00:06 Erinnerung VL 29.06.2016 0:02:08 Kruskals Algorithmus 0:04:38 Union-Find Datenstruktur 0:18:24 Pfadkompression 0:20:57 Union by Rank 0:26:19 Analyse Union by Rank bzw. Pfadkompression 0:40:55 Kruskal mit Union-Find 0:45:05 Beispiel 0:49:09 Vergleich Jarník-Prim - Kruskal 0:50:55 Mehr MST-Algorithmen 0:54:03 Zusammenfassung 0:56:05 Kap. 12: Generische Optimierungsansätze 0:56:47 Durchgehendes Beispiel: Rucksackproblem 0:58:30 Allgemein: Maximierungsproblem 1:00:28 Black-Box-Löser 1:01:45 Lineare Programmierung 1:04:22 Ein einfaches Beispiel 1:07:13 Beispiel: Kürzester Weg 1:09:27 Eine Anwendung - Tierfutter 1:11:04 Verfeinerungen 1:12:48 Algorithmen und Implementierungen 1:14:14 Ganzzahlige Lineare Programmierung 1:15:09 Beispiel: Rucksackproblem 1:16:20 Umgang mit (M)ILPs

    1h 18m

  6. 07/07/2016 · VIDEO

    20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016

    20 | 0:00:00 Starten 0:00:06 Erinnerung VL 27.06.2016 0:02:09 Kap. 11: Minimale Spannbäume 0:02:28 Minimale Spannbäume (MST) 0:03:22 Minimale aufspannende Wälder (MSF) 0:03:36 Anwendungen 0:04:57 MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property) 0:12:19 MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property) 0:15:54 Der Jarník-Prim-Algorithmus 0:28:39 Analyse 0:32:00 Kruskals Algorithmus (1956) 0:37:47 Kruskals Algorithmus - Korrektheit 0:40:56 Union-Find Datenstruktur 0:44:15 Beginn Übung 10 0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford 0:45:40 Bellman-Ford: Pseudo-Code 0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee) 0:48:53 Bellman-Ford: Beispiel 0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises 0:55:03 Minimale Spannbäume 0:57:00 Minimale Spannbäume: Jarník-Prim 0:58:37 Minimale Spannbäume: Kruskal 1:00:00 Steinerbäume 1:05:42 Steinerbaum: Was kann schief gehen? 1:10:09 Problem des Handlungsreisenden (TSP)

    1h 15m

  7. 01/07/2016 · VIDEO

    19: Algorithmen I, Vorlesung, SS 2016, am 27.06.2016

    19 | 0:00:00 Starten 0:02:13 Negative Kosten 0:07:10 Zurück zu Basiskonzepten 0:09:47 Mehr Basiskonzepte 0:11:45 Allgemeines Korrektheitskriterium 0:19:06 Algorithmen brutal - Bellman-Ford-Algorithmus für beliebige Kantengewichte 0:26:44 Beispiel 0:30:07 Bellman-Ford - Laufzeit 0:32:06 Ayklische Graphen 0:36:15 Von überall nach überall 0:38:54 Kürzeste Wege: Zusammenfassung 0:40:17 Mehr zu kürzesten Wegen 0:43:29 Exkurs: Routing in Straßennetzwerken 0:46:00 Straßennetzwerke 0:46:23 Distanz zu einem Zielknoten t 0:48:03 Ideen für Routenplanung 0:50:12 Approach: Transit-Node Routing 0:50:43 Beispiel 0:53:58 Erste Beobachtung 0:55:45 Zweite Beobachtung 0:57:22 Beispiel: Transitknoten 0:57:41 Experimente 0:58:23 Offene Fragen 0:59:31 Minimale Spannbäume 1:02:52 Minimale aufspannende Wälder 1:03:23 Anwendungen

    1h 8m

  8. 28/06/2016 · VIDEO

    18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016

    18 | 0:00:00 Starten 0:00:06 Erinnerung VL 20.06.2016 0:02:10 Erinnerung: analoger Algorithmus 0:03:25 Dijkstra: Implementierung? 0:08:39 Prioritätsliste 0:10:22 Implementierung ≈ BFS mit PQ statt FIFO 0:15:06 Beispiel 0:17:27 Dijkstra: Laufzeit 0:26:20 Analyse im Mittel 0:28:34 Monotone ganzzahlige Prioritätslisten 0:29:57 Negative Kosten 0:30:33 Beginn Übung 9 0:30:39 Roadmap 0:30:59 Organisatorisches 0:31:37 Aufgabe 3 0:32:26 Breitensuche (Wie war das nochmal...) 0:34:48 Breitensuche für nicht zusammenhängende, ungerichtete Graphen 0:35:41 Breitensuche in DAGs für nicht zusammenhängende Graphen 0:38:08 Dijkstras Algorithmus 0:40:56 Bidirektionale Suche 0:45:09 Bidirektionale Suche - Definitionen 0:46:14 Bidirektionale Suche - Vorgehen 0:46:20 Pingo! Was sind gute Abbruchstrategien? 0:49:19 Abbruchstrategie (1) 0:53:36 Abbruchstrategie (2) 0:54:13 Beispiel 0:55:02 Bemerkungen 0:56:01 Graph-Datenstruktur 0:56:07 Pingo! Wie schnell wird eine Routing-Anfrage? 0:57:54 Speedup Techniques 0:59:38 Mehr davon?

    1 hr
See All (25)

About

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 | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

Information

More From Karlsruher Institut für Technologie

  • Grundbegriffe der Informatik, Vorlesung, WS18/19
    Courses
    Courses

    Updated 07/02/2019

  • Arbeitswelten der Zukunft: Visionen, Chancen, Risiken
    Courses
    Courses

    Updated 05/11/2018

  • Herausforderung demografischer Wandel
    Courses
    Courses

    Updated 17/02/2014

  • Technische Mechanik 4, SS2014, Vorlesung
    Courses
    Courses

    Updated 10/07/2014

  • Die pluralistische Gesellschaft und ihre Feinde
    Courses
    Courses

    Updated 09/05/2017

  • Ethik heute. Fehlt uns ein Wertekompass?
    Courses
    Courses

    Updated 05/08/2013

  • Technische Mechanik 3, Vorlesung, WS15/16
    Courses
    Courses

    Updated 04/02/2016

To listen to explicit episodes, sign in.

Stay up to date with this show

Sign in or sign up to follow shows, save episodes and get the latest updates.
Select a country or region

Africa, Middle East, and India

Asia Pacific

Europe

Latin America and the Caribbean

The United States and Canada