Algorithmen 1, SS2019, Vorlesung

Jul 30 2019 49

Algorithmen 1, SS2019, Vorlesung Podcast artwork

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)

Subscribe on Podcast Addict

01: Algorithmen I, Vorlesung, SS 2019, 24.04.2019

Apr 25 2019 69 mins

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 Exkur

02: Algorithmen I, Vorlesung, SS 2019, 29.04.2019

Apr 30 2019 77 mins

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:

03: Algorithmen I, Vorlesung, SS 2019, 06.05.2019

May 08 2019 75 mins

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-Kal

04: Algorithmen I, Übung, SS 2019, 09.05.2019

May 10 2019 47 mins

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

05: Algorithmen I, Vorlesung, SS 2019, 13.05.2019

May 14 2019 88 mins

05 | 0:00:00 Start 0:00:05 Rückblick Vorlesung 06.05. 0:02:49 Laufzeitanalyse / Rekurrenzen 0:11:03 Eine Rekurrenz für Teile und Herrsche 0:15:43 Master Theorem (einfache Form) 0:20:13 Beweisskizze: Allgemeines 0:25:10 Beweisskizze Fall d<b 0:36:09 Master Theorem Beispiele 0:39:16 Graphen 0:43:09 Bäume 0:44:56 Ein erster Graphalgorithmus 0:54:08 Exkurs: P und NP 1:13:20 Folge

06: Algorithmen I, Vorlesung, SS 2019, 15.05.2019

May 16 2019 88 mins

06 | 0:00:00 Start 0:00:09 Rückblick Vorlesung 13.05 0:02:26 Folgen als Felder und Listen 0:05:06 Folgen 0:05:09 Ausblick: Komplexität typischer Operationen 0:05:39 Verkettete Listen 0:05:54 Listenglieder (Items) 0:09:22 Trick: Dummy Header 0:10:49 Die Listenklasse 0:16:07 Splice-Operation 0:24:24 Splice: Beispiel 0:25:31 Weitere Operationen: Einfach mit splice 0:27:52 Doch nicht

07: Algorithmen I, Vorlesung, SS 2019, 20.05.2019

May 22 2019 87 mins

07 | 0:00:00 Start 0:00:09 Rückblick 0:01:47 Rückblick: unbeschränkte Arrays 0:02:37 Rückblick: amortisierte Analyse 0:03:37 Rückblick: Account-Methode 0:13:22 Stapel und Schlange 0:18:42 Stapel: Operationen 0:22:07 Warteschlangen 0:24:24 zyklisches Array 0:31:12 Deque: Double-Ended Queues 0:34:13 Vergleich: Listen - Felder 0:35:48 Vergleich: Operationen 0:45:54 Ausblick: Weit

08: Algorithmen I, Übung, SS 2019, 22.05.2019

May 23 2019 38 mins

08 | 0:00:00 Starten 0:00:05 Roadmap 0:01:12 Verkettete Liste 0:02:56 Skip List 0:06:33 Amortisierte Liste 0:09:45 Aggregat Methode 0:11:28 Hotlist 0:13:39 Hotlist Lookup 0:14:42 Hotlist Insert 0:16:25 Hotlist Amortisierung 0:18:07 Hotlist Delete 0:19:55 Hotlist Aufräumen 0:20:50 Hashtabelle 0:22:14 Duplikaterkennung 0:27:57 Bloom Filter

09: Algorithmen I, Vorlesung, SS 2019, 27.05.2019

Jun 06 2019 87 mins

09 | 0:00:00 Starten 0:00:24 Rückblick 0:06:17 Kollisionen 0:11:06 Analyse für zufällige Hash-Funktionen 0:21:54 Universelles Hashing 0:34:35 Beweis Theorem 0:42:08 Hashing mit linearer Suche(""linear probing"") 0:45:08 Der einfache Teil 0:51:03 Remove 1:01:36 Verketten vs. Lineare Suche 1:06:46 Kryptographische Hashfunktionen 1:10:29 Sotieren und Co 1:13:20

10: Algorithmen I, Vorlesung, SS 2019, 29.05.2019

Jun 03 2019 86 mins

10 | 0:00:00 Starten 0:00:12 Rückblick Vorlesung 27.05 0:03:46 Einfache Sortieralgorithmen 0:05:29 Sortieren durch Mischen 0:09:04 Beispiel 0:11:31 Mischen 0:12:51 Analyse 0:15:49 Untere Schranke 0:17:47 Nicht vergleichsbasierte untere Schranke 0:22:34 Baumbasierte Sortierer Darstellung 0:24:59 Beweis 0:32:29 Randomisierung, Mittlere Ausführungszeit 0:34:42 Quicksort 1:21:24 Grö