PODCAST

Algorithmen 1, SS2019, Vorlesung

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:31:25

23: Algorithmen I, Übung, SS 2019, 24.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/30

23 | 0:00:00 Start 0:00:13 Übung: Überblick 0:03:26 Dijkstras Algorithmus 0:07:19 Bellmann Ford Algorithmus 0:14:50 Minimale Spannbäume 0:20:31 Steinerbäume 0:27:20 Problem des Handlungsreisenden (TSP)

01:24:44

22: Algorithmen I, Vorlesung, SS 2019, 22.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/25

22 | 0:00:00 Start 0:00:23 Generische Optimierungsansätze 0:05:36 Rucksackproblem 0:09:28 Maximierungsprolem 0:12:42 Black-Box-Löser 0:17:38 Lineare Programmierung 0:24:53 Kürzeste Wege 0:29:29 Tierfutter 0:35:21 Algorithmen und Implementierungen 0:39:09 Ganzzahlige Lineare Programmierung 0:53:05 Greedy-Algorithmen 1:00:00 Dynamische Programmierung 1:17:32 Algorithmenentwurf mittels dynamischer Programmierung 1:23:01 Systematische Suche

01:27:57

21: Algorithmen I, Vorlesung, SS 2019, 17.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/18

21 | 0:00:00 Start 0:00:10 Rückblick 0:01:58 Heutige Vorlesung 0:03:31 Minimale Spannbäume 0:08:34 MST-Kanten auswählen und verwerfen 0:22:22 Jarnik-Prim-Algorithmus 0:37:10 Analyse - Jarnik-Prim-Algorithmus 0:38:04 Kruskals-Algorithmus 0:45:14 Kruskals Algorithmus - Korrektheit 0:49:51 Union-Find Datenstruktur 1:03:25 Pfadkompression 1:08:34 Union by Rank 1:10:11 Analyse - nur Union by Rank 1:11:33 Analyse - nur Pfadkompression 1:12:05 Analyse - Pfadkompression und Union by Rank 1:15:21

01:25:19

20: Algorithmen I, Vorlesung, SS 2019, 15.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/16

20 | 0:00:00 Start 0:01:21 Kürzeste Wege: Definition 0:02:23 Dijkstras Algorithmus. Pseudocode 0:08:12 Dijkstra: negative Kantengewichte 0:17:02 Monotone ganzzahlige Prioritätslisten 0:19:49 Negative Zyklen 0:21:55 Zurück zu Basiskonzepten 0:26:31 Allgemeines Korrektheitskriterium 0:31:09 Bellman-Ford-Algorithmus 0:39:29 Beispiel 0:43:57 Bellman-Ford: Laufzeit 0:45:30 Azyklische Graphen 0:49:38 Von überall nach überall 0:52:15 Kürzeste Wege: Zusammenfassung 0:57:10 Exkurs: Routing in

01:09:53

19: Algorithmen I, Vorlesung, SS 2019, 03.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/05

19 | 0:00:00 Start 0:00:11 Rückblick: Kürzeste Wege 0:02:00 Dijkstras Algorithmus 0:02:54 Allgemeine Definition 0:07:38 Kante relaxieren 0:13:02 Dijkstras Algorithmus: Pseudocode 0:16:44 Beispiel 0:23:52 Korrektheit 0:37:29 Implementierung 0:40:10 Prioritätsliste 0:46:50 Beispiel 0:49:18 Dijkstra: Laufzeit 0:58:32 Analyse im Mittel 0:59:32 Monotone ganzzahlige Prioritätslisten 1:01:18 Negative Kosten 1:03:38 Zurück zu Basiskonzepten 1:06:34 Allgemeines Korrektheitskriterium 1:08:46 Bellman-Ford

01:26:04

18: Algorithmen I, Vorlesung, SS 2019, 01.07.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/07/04

18 | 0:00:00 Start 0:07:02 Graph-Traversierung 0:11:13 Breitensuche 0:13:13 Tiefensuche 0:21:56 DFS-Baum 0:28:14 DFS-Nummerierung 0:38:39 Topologische Sortierung 0:43:27 Topologisches Sortieren mittels DFS 0:55:01 Begriff Zusammenhang 1:02:26 BFS vs DFS 1:07:16 Kürzeste Wege : Definition 1:17:22 Dijkstras Algorithmus

01:27:10

17: Algorithmen I, Vorlesung, SS 2019, 26.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/27

17 | 0:00:00 Start 0:00:05 Rückblick und Überblick 0:01:35 Graphen 0:02:12 Repräsentation von Graphen 0:02:33 Kantenfolgenrepräsentation 0:03:31 Adjazenzfelder 0:05:59 Kantenliste -> Adjazenzfeld 0:07:29 Adjazenzlisten 0:13:10 Customization (Zuschneiden) 0:13:53 Beispiel: DAG-Erkennung 0:23:23 Adjazenz-Matrix 0:31:24 Pfade zählen mittels linearer Algebra (LA) 0:35:54 Beispiel, wo Graphentheorie bei LA hilft 0:38:56 Implizite Repräsentation 0:40:53 Zusammenhangstest für Intervallgraphen 0:43:46

01:31:16

16: Algorithmen I, Vorlesung, SS 2019, 24.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/25

16 | 0:00:00 Start 0:00:11 Wiederholung 0:11:16 Locate 0:19:22 Einfügen-Algorithmenskizze 0:50:36 Zusammenfassung 0:53:43 Graphen 0:58:43 Graphen-Anwendung 1:05:15 Operationen 1:10:05 Kantenfolgenrepräsentation 1:13:28 Adjazenzfelder

00:27:12

15: Algorithmen I, Übung, SS 2019, 19.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/25

15 | 0:00:00 Start 0:00:08 Übungsblatt 7, Pseudocode 0:02:49 4. Übung 0:02:52 Roadmap, Bucket Sort Spezial, Bucket Queue, Binary Radix Heap 0:03:14 Erinnerung: Bucketsort 0:06:46 Bucket Sort Spezial 0:13:55 Spezielle Priority Queues 0:14:55 Bucket Queue 0:17:40 Binary Radix Heap 0:22:52 Binary Radix Heap: deleteMin 0:24:06 Binary Radix Heap 0:25:54 Möglichkeit Ternärer Radix Heaps

01:26:56

14: Algorithmen I, Vorlesung, SS 2019, 17.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/25

14 | 0:00:00 Start 0:00:05 Rückblick und Überblick 0:02:06 Sortierte Folgen 0:07:56 Statisch: Sortiertes Feld mit binärer Suche 0:18:14 Dynamisch sortierte Folgen 0:26:49 Abgrenzung 0:32:27 Sortierte Folgen - Anwendungen 0:46:39 Binäre Baumsuche 0:52:08 locate (k) 1:00:15 Laufzeit von locate (k) 1:03:05 Naives Einfügen 1:08:07 Naives Einfügen - Beispiel 1:11:25 Suchbäume balancieren 1:16:25 Items 1:20:24 Initialisierung 1:22:27 Locate

01:24:29

13: Algorithmen I, Vorlesung, SS 2019, 12.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/13

13 | 0:00:00 Start 0:00:12 Rückblick Vorlesung 03.06 0:01:48 Überblick heutige Vorlesung 0:02:48 Prioritätslisten 0:09:43 Anwendungen 0:10:47 Binäre Heaps 0:16:37 Implizite Baum Repräsentation 0:19:51 Pseudocode 0:23:30 Einfügen 0:32:19 Funktion deleteMin 0:36:23 Funktion siftDown 0:39:35 deleteMin: Beispiel 0:41:12 Binärer Heap - Analyse 0:45:32 Binärer Heap - Konstruktion 0:54:43 Ein nützlicher Rechentrick 1:00:41 Heapsort 1:02:31 Heapsort: Beispiel 1:03:06 Heapsort vs Quicksort vs

00:36:48

12: Algorithmen I, Übung, SS 2019, 05.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/07

12 | 0:00:00 Start 0:10:03 Adaptives Sortieren 0:10:59 Insertion Sort: Adaptiv? 0:11:41 Insertion Sort: Erwartete Laufzeit 0:14:09 Natural Merge Sort 0:15:03 Erwartete Anzahl von Runs 0:19:51 Split Sort 0:22:41 Schnelle Mediansuche für Quicksort 0:33:01 Sortieralgorithmen in aktuellen Programmiersprachen Addison Wesley, 2005

01:27:03

09: Algorithmen I, Vorlesung, SS 2019, 27.05.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/06

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 Lochkartensortierer 1:19:10 Einfache Sortieralgorithmen 1:21:52 Sentinels am Beispiel Sotieren durch Einfügen 1:24:47

01:22:28

11: Algorithmen I, Vorlesung, SS 2019, 03.06.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/06

11 | 0:00:00 Start 0:00:05 Rückblick letzte Vorlesung 0:04:51 Quicksort: Effiziente Implementierung 0:10:56 Halbrekursive Implementierung 0:16:10 Quadratische Komplexität bei gleichen Elementen? 0:29:01 Vergleich Quicksort und Mergesort 0:34:13 Benchmark 0:38:52 Auswahl: Anwendungen 0:45:40 Quickselect: Analyse 0:49:28 Durchbrechen der unteren Schranke – Ganzzahliges Sortieren 0:58:59 Array-Implementierung 1:03:54 Least-Significant-Digit Radit Sort 1:09:39 Mehr zu ganzzahligem Sortieren 1:14:24

01:26:16

10: Algorithmen I, Vorlesung, SS 2019, 29.05.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/06/03

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ößerer Basisfall 1:24:50 Halbrekursive Implementierung

00:38:25

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

Algorithmen 1, SS2019, Vorlesung ·

2019/05/23

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

01:27:25

07: Algorithmen I, Vorlesung, SS 2019, 20.05.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/05/22

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: Weitere Repräsentationen von Folgen 0:47:57 Hashing (Streuspeicherung) 0:51:07 Hashtabellen 0:55:44 Exkurs: Konventionen für

01:28:19

06: Algorithmen I, Vorlesung, SS 2019, 15.05.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/05/16

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 so einfach? Speicherverwaltung! 0:31:14 Items löschen 0:32:49 Elemente einfügen 0:35:47 Ganze Listen

01:28:27

05: Algorithmen I, Vorlesung, SS 2019, 13.05.2019

Algorithmen 1, SS2019, Vorlesung ·

2019/05/14

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 Folgen als Felder und Listen 1:17:04 Ausblick: Komplexität typischer Operationen 1:21:27 Listenglieder (Items)

00:47:55

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

Algorithmen 1, SS2019, Vorlesung ·

2019/05/10

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

23 results

Algorithmen 1, SS2019, Vorlesung

All Episodes

Similar Podcasts

Science Talk

Albert Einstein College of Medicine

五分钟心理学

柠檬心理

Daily Facts

Amalia Dupray and Montgomery Jones.

Les dents et dodo

BFMTV

Veterinary Clinical Podcasts

The Royal Veterinary College