10: Algorithmen 1, Vorlesung und Übung, SS 2018, 23.05.2018

https://is1-ssl.mzstatic.com/image/thumb/Podcasts115/v4/a7/b9/23/a7b923db-1f10-a621-b683-e124335e0adc/mza_4506831800992500288.jpg/600x600bb.jpg

Algorithmen 1, SS2018, Vorlesung

Karlsruher Institut für Technologie (KIT)

23 episodes

7 months ago

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) Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

Courses

Education

RSS

All content for Algorithmen 1, SS2018, Vorlesung is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.

Courses

Education

10: Algorithmen 1, Vorlesung und Übung, SS 2018, 23.05.2018

Algorithmen 1, SS2018, Vorlesung

1 hour 25 minutes 28 seconds

7 years ago

10: Algorithmen 1, Vorlesung und Übung, SS 2018, 23.05.2018

0:00:00 Start 0:00:40 Rückblick Vorlesung 16.05 0:01:07 Überblick heutige Vorlesung 0:03:48 Auswahl (Selection) 0:06:36 Beispiel 0:08:29 Auswahl: Anwendungen 0:10:08 Quickselect 0:14:16 Beispiel 0:17:01 Quickselect: Analyse 0:18:03 Mehr zum Auswahlproblem 0:21:41 Durchbrechen der unten Schranke - Ganzzahliges Sortieren 0:25:17 Schlüssel 0....k-1: Bucket Sort 0:28:49 Beispiel: k=4 0:30:46 Array-Implementierung 0:31:13 Beispiel 0:35:37 K^d Schlüssel 0:41:49 LSD-Radix-Sort: Beispiel 0:41:56 Mehr zu ganzzahligem Sortieren 0:42:10 Sortieren: vergleichsbasiert vs. ganzzahlig 0:43:48 Was haben wir jeneseits von Sortieren gelernt? 0:45:52 Übung 0:46:19 Roadmap 0:47:23 Rückblick 0:49:00 Sortieren durch Einfügen: In-Place 0:50:11 Sortieren durch Einfügen: Sentinel 0:51:52 Sound 0:55:34 Quantifiziertes Chaos: Inversionen 0:58:22 Quantifiziertes Chaos: Runs 0:59:42 Quantifiziertes Chaos: Removal 1:00:26 Adaptives Sortieren 1:01:21 Insertion Sort: Adaptiv? 1:02:12 Insertion Sort: Erwartete Laufzeit 1:06:36 Natural Merge Sort 1:07:58 Erwartete Anzahl von Runs 1:16:55 Split Sort 1:18:49 Split Sort: Beispiel 1:22:09 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen 1:23:18 C++ 1:24:23 Java