Algorithmen 1, SS2017, Vorlesung

Algorithmen 1, SS2017, Vorlesung

By Karlsruher Institut für Technologie (KIT)Education
Download on the App Store

All Algorithmen 1, SS2017, Vorlesung episodes

  • 04: Algorithmen 1, Vorlesung, SS 2017, 08.05.2017
    04 |
    0:00:00 Starten
    0:00:15 P und NP
    0:03:17 Folgen
    0:05:22 Form Follows Function
    0:11:36 Listenglieder (Items)
    0:13:41 Trick: dummy header
    0:17:39 Die Listenklasse
    0:33:08 Items löschen
    0:35:41 Elemente einfügen
    0:40:29 Suchen
    0:46:15 Einfach verkettete Listen
    0:52:41 Listen: Zusammenfassung, Verallgemeinerungen
    0:53:44 Felder (Arrays)
    0:56:32 Unbeschränkte Felder
    1:14:42 Amortisierte Analyse - allgemeiner
    1 hr 18 min
  • 02: Algorithmen 1, Vorlesung, SS 2017, 26.04.2017, 02
    0:00:00 Starten
    0:00:07 Erinnerung VL 24.04.2017
    0:01:55 Karatsuba-Ofman Multiplikation
    0:04:33 Skalierung
    0:06:59 Blick über den Tellerrand
    0:09:45 Algorithmenanalyse
    0:13:07 Zweite Vereinfachung: Asymptotik
    0:19:44 O-Kalkül Rechenregeln
    0:23:29 Maschinenmodell: RAM
    0:31:59 ""Kleine"" ganze Zahlen?
    0:35:00 Algorithmenanalyse im RAM-Modell
    0:38:15 Mehr Maschinenmodell
    0:40:56 Pseudocode
    0:41:56 Design by Contract / Schleifeninvarianten
    0:56:16 Programmanalyse
    1:00:30 Eine Rekurrenz für Teile und Herrsche
    1:02:54 Master Theorem (Einfache Form)
    Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:
    - Ergebnisüberprüfung (Checkers) und Zertifizierung
    - Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
    - Grundbegriffe des Algorithm Engineering
    - Effektive Umsetzung verketteter Listen
    - Unbeschränkte Arrays, Stapel, und Warteschlangen
    - Hashtabellen: mit Verkettung, linear probing, universelles Hashing
    - Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
    - Selektion: quickselect
    - Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
    - Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
    - Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
    - Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
    Literaturhinweise:
    Algorithms and Data Structures - The Basic Toolbox, K. Mehlhorn und P. Sanders
    Springer 2008
    Weiterführende Literatur
    Algorithmen - Eine Einführung
    T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein, Oldenbourg, 2007
    Algorithmen und Datenstrukturen
    T. Ottmann und P. Widmayer, Spektrum Akademischer Verlag, 2002
    Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen
    R. Sedgewick, Pearson Studium 2003
    Algorithm Design
    J. Kleinberg and É. Tardos, Addison Wesley, 2005
    Vöcking et al.
    Taschenbuch der Algorithmen, Springer, 2008
    Lehrinhalt:
    Dieses Modul soll Studierenden grundlegende Algorithmen und Datenstrukturen vermitteln.
    Die Vorlesung behandelt unter anderem:
    - Grundbegriffe des Algorithm Engineering
    - Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch, amortisiert)
    - Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen
    - Hashtabellen
    - Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)
    - Prioritätslisten
    - Sortierte Folgen,Suchbäume und Selektion
    - Graphen (Repräsentation, Breiten-/Tiefensuche, Kürzeste Wege, Minimale Spannbäume)
    - Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
    - Geometrische Algorithmen
    1 hr 17 min
  • 01: Algorithmen 1, Vorlesung, SS 2017, 24.04.2017, 01
    01 |
    0:00:00 Starten
    0:00:10 Algorithmus? Kann man das essen?
    0:01:30 Algorithmik
    0:02:59 Datenstruktur
    0:03:56 Themenauswahl: Werkzeugkasten
    0:06:34 Inhaltsübersicht
    0:10:11 Amuse Geule
    0:14:59 Addition
    0:18:47 Exkurs: Pseudocode
    0:21:38 Exkurs vom Exkurs: Wieso nicht C++/Java-like?
    0:24:00 Ziffernmultiplikation
    0:32:18 Schulmultiplikation
    0:38:06 Exkurs O-Kalkül, die Erste
    0:44:11 Ein rekursiver Algorithmus
    0:53:39 Exkurs: Algorithmen-Entwurfsmuster
    0:55:22 Karatsuba-Ofman Multiplikation
    1:02:26 Algorithm Engineering - was hat das mit der Praxis zu tun?
    1:04:27 Algorithmentheorie (Karikatur)
    1:05:31 Algorithmik als Algorithm Engineering
    1 hr 8 min