Algorithmen 1, SS2019, Vorlesung

Algorithmen 1, SS2019, Vorlesung

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

All Algorithmen 1, SS2019, Vorlesung episodes

  • 04: Algorithmen I, Übung, SS 2019, 09.05.2019
    04 |
    0:00:00 Start
    0:00:05 Begrüßung
    0:01:16 Übersicht
    0:02:05 1. Effizienz von Algorithmen
    0:08:26 Einabegröße und Laufzeit
    0:11:23 O-Notation
    0:20:35 Betrachtung über Grenzwerte
    0:25:46 Basis des Logarithmus
    0:26:39 2. Invarianten
    0:35:38 3. Teile-und-Herrsche Methode
    48 min
  • 03: Algorithmen I, Vorlesung, SS 2019, 06.05.2019
    03 |
    0:00:00 Start
    0:00:14 Rückblick Vorlesung 29.04
    0:01:22 Korrektheit / Design by Contract
    0:02:25 Beispiel
    0:05:09 Rechenbeispiel
    0:17:45 Algorithm Engineering – was hat das mit der Praxis zu tun?
    0:20:38 Algorithmentheorie (Karikatur)
    0:23:12 Algorithmik als Algorithm Engineering
    0:26:05 (Asymptotische) Algorithmenanalyse
    0:31:40 Zwei Vereinfachung: Asymptotik
    0:50:39 O-Kalkük Rechenregeln
    0:56:13 Maschinenmodell: RAM (Random Access Machine)
    1:02:05 Register
    1:03:23 Speicherzugriff
    1:04:19 ""Kleine"" ganze Zahlen?
    1:06:45 Mehr Maschinenmodell
    1:10:42 RAM vs. Compiler-Zwischensprache LLVM
    1:12:19 Laufzeitanalyse / Rekurrenzen
    1 hr 16 min
  • 02: Algorithmen I, Vorlesung, SS 2019, 29.04.2019
    02 |
    0:00:00 Start
    0:00:16 Rückblick Vorlesung 24.04
    0:03:42 Schulalgorithmus
    0:05:55 Beispiel
    0:07:05 Analyse
    0:12:35 Exkurs: O-Kalkül
    0:26:00 Ein rekursier Algorithmus: Hintergrund
    0:33:22 Analyse
    0:39:48 Exkurs: Algorithmen-Entwurfsmuster
    0:43:01 Karatsuba-Ofman-Multiplikation (1962)
    0:50:32 Gibt es noch besser?
    0:55:41 Pseudocode
    0:58:32 Korrektheit / Design by contract
    1:06:16 Schleifeninvarianten
    1:08:51 Beispiel
    - - - - - - -
    Titel der Serie:
    Algorithmen I, Vorlesung, SS 2019
    Beschreibung der Serie:
    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
    1 hr 18 min
  • 01: Algorithmen I, Vorlesung, SS 2019, 24.04.2019
    01 |
    0:00:00 Start
    0:00:05 Einführung und Materialien
    0:06:40 Algorithmus - Was ist das?
    0:13:43 Eigenschaften eines Algorithmus
    0:20:23 Algorithmik
    0:21:55 Beispiel ""aus der Praxis""
    0:29:06 Datenstruktur
    0:35:19 Basic Toolbox: Unser Werkzeugkasten
    0:36:29 Inhalte Vorlesung
    0:37:17 Ein erster Algorithmus: Langzahl-Multiplikation
    0:49:53 Addition
    0:54:41 Exkurs:Pseudocode
    0:58:12 Exkurs: Wieso nicht C++, Java,etc. ?
    0:59:54 Multiplikation Langzahl mit Ziffer
    1:03:33 Algorithmus Ziffernmultiplikation
    1:06:30 Schulalgorithmus
    1 hr 10 min