PODCAST

Algorithmen 1, SS2016, Vorlesung

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:58:18

25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/07/29

25 | 0:00:00 Starten 0:00:06 Prioritätslisten 0:03:14 Binäre Heaps 0:07:39 Adressierbare Prioritätslisten 0:08:26 Adressierbare Binäre Heaps 0:09:05 Sortierte Folgen 0:10:42 Binäre Suchbäume 0:16:08 Repräsentation von Graphen 0:23:11 Graphentraversierung 0:30:07 Kürzeste Wege 0:41:22 Minimale Spannbäume 0:46:37 Generische Optimierungsansätze 0:57:13 Zusammenfassung

00:48:27

24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/07/19

24 | 0:00:00 Starten 0:00:06 Kap. 13: Zusammenfassung 0:03:32 Zusammenfassung - Datenstrukturen 0:06:22 Zusammenfassung - Algorithmen 0:09:41 Zusammenfassung - Entwurfstechniken I 0:12:53 Zusammenfassung - Entwurfstechniken II 0:14:53 Zusammenfassung - Analysetechniken 0:18:06 Zusammenfassung - weitere Techniken 0:18:50 Schnelldurchlauf 0:19:32 Amuse Geule 0:20:05 Exkurs: Pseudocode 0:21:47 Exkurs O-Kalkül, die Erste 0:24:04 Algorithmentheorie 0:25:44 Invarianten 0:26:03 Master Theorem 0:29:27 Form

01:29:48

23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/07/14

Die Vorlesung (23, 11.07.16, SS2016) konnte wegen technischer Probleme nicht aufgezeichnet werden. Der Vorlesungsinhalt ist aber identisch mit der Aufzeichnung vom 06.07.2015 (SS2015) 23 | 0:00:00 Starten 0:00:07 Dynamische Programmierung – Aufbau aus Bausteinen 0:02:12 "Systematische SuchSystematische Suche" 0:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem 0:20:42 Beispielrechnung 0:33:16 Branch-and-Bound – allgemein 0:34:48 Beispielrechnung 0:42:53 Lokale Suche – global

01:23:36

22: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/07/11

22 | 0:00:00 Starten 0:00:10 Erinnerung VL 04.07.2016 0:04:13 Wiederholung Beispiel: Rucksackproblem 0:05:15 Nie zurückschauen - Greedy-Algorithmen 0:08:50 Beispiel: Rucksackproblem (1) 0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen 0:18:29 Beispiel: Rucksackproblem (2) 0:21:09 Dynamische Programmierung 0:22:37 Beweis des Lemmas 0:29:10 Berechnung von P(i,C) elementweise 0:33:21 Rekonstruktion des Lösung 0:34:54 Beispiel 0:40:36 Beginn Übung 11 0:40:41 Roadmap 0:41:22 Schwierige

01:18:15

21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/07/07

21 | 0:00:00 Starten 0:00:06 Erinnerung VL 29.06.2016 0:02:08 Kruskals Algorithmus 0:04:38 Union-Find Datenstruktur 0:18:24 Pfadkompression 0:20:57 Union by Rank 0:26:19 Analyse Union by Rank bzw. Pfadkompression 0:40:55 Kruskal mit Union-Find 0:45:05 Beispiel 0:49:09 Vergleich Jarník-Prim - Kruskal 0:50:55 Mehr MST-Algorithmen 0:54:03 Zusammenfassung 0:56:05 Kap. 12: Generische Optimierungsansätze 0:56:47 Durchgehendes Beispiel: Rucksackproblem 0:58:30 Allgemein: Maximierungsproblem 1:00:28

01:15:02

20: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/07/07

20 | 0:00:00 Starten 0:00:06 Erinnerung VL 27.06.2016 0:02:09 Kap. 11: Minimale Spannbäume 0:02:28 Minimale Spannbäume (MST) 0:03:22 Minimale aufspannende Wälder (MSF) 0:03:36 Anwendungen 0:04:57 MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property) 0:12:19 MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property) 0:15:54 Der Jarník-Prim-Algorithmus 0:28:39 Analyse 0:32:00 Kruskals Algorithmus (1956) 0:37:47 Kruskals Algorithmus - Korrektheit 0:40:56 Union-Find

01:07:50

19: Algorithmen I, Vorlesung, SS 2016, am 27.06.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/07/01

19 | 0:00:00 Starten 0:02:13 Negative Kosten 0:07:10 Zurück zu Basiskonzepten 0:09:47 Mehr Basiskonzepte 0:11:45 Allgemeines Korrektheitskriterium 0:19:06 Algorithmen brutal - Bellman-Ford-Algorithmus für beliebige Kantengewichte 0:26:44 Beispiel 0:30:07 Bellman-Ford - Laufzeit 0:32:06 Ayklische Graphen 0:36:15 Von überall nach überall 0:38:54 Kürzeste Wege: Zusammenfassung 0:40:17 Mehr zu kürzesten Wegen 0:43:29 Exkurs: Routing in Straßennetzwerken 0:46:00 Straßennetzwerke 0:46:23 Distanz zu einem

01:00:22

18: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/06/28

18 | 0:00:00 Starten 0:00:06 Erinnerung VL 20.06.2016 0:02:10 Erinnerung: analoger Algorithmus 0:03:25 Dijkstra: Implementierung? 0:08:39 Prioritätsliste 0:10:22 Implementierung ≈ BFS mit PQ statt FIFO 0:15:06 Beispiel 0:17:27 Dijkstra: Laufzeit 0:26:20 Analyse im Mittel 0:28:34 Monotone ganzzahlige Prioritätslisten 0:29:57 Negative Kosten 0:30:33 Beginn Übung 9 0:30:39 Roadmap 0:30:59 Organisatorisches 0:31:37 Aufgabe 3 0:32:26 Breitensuche (Wie war das nochmal...) 0:34:48 Breitensuche für nicht

01:23:16

17: Algorithmen I, Vorlesung, SS 2016, am 20.06.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/06/28

17 | 0:00:00 Starten 0:00:08 Erinnnerung VL 15.06.2016 0:06:19 DFS-Nummerierung 0:09:29 Fertigstellungszeit 0:11:10 Kantenklassifizierung bei DFS 0:12:31 Erinnerung: Tiefensuchschema 0:16:48 Topologische Sortierung 0:19:43 Topologische Sortieren mittels DFS 0:25:19 Starke Zusammenhangskomponenten 0:29:45 Mehr DFS-basierte Linearzeitalgorithmen 0:32:40 BFS <-> DFS 0:36:14 Kap. 10: Kürzeste Weg 0:40:50 Anwendungen 0:43:23 Grundlagen 0:46:19 Azyklische Graphen 0:46:39 Kantengewicht

01:10:51

16: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/06/21

16 | 0:00:00 Starten 0:02:17 Graphentraversierung 0:03:44 Graphentraversierung als Kantenklassifizierung 0:07:01 Breitensuche 0:15:47 Repräsentation des Baums 0:22:01 Repräsentation von Q und Q' mittels FIFO 0:23:47 Alternative Repräsentation von Q und Q' 0:25:59 Tiefensuche 0:28:51 Tiefensuchschema für G = (V,E) 0:32:49 DFS-Baum 0:35:59 BEGINN ÜBUNG 0:36:12 Nachtrag: Quicksort, alternative Partitionierung 0:37:27 Grundlagen der Graphentheorie 0:37:37 Graphen und Relationen 0:40:14

00:49:03

15: Algorithmen I, Vorlesung, SS 2016, am 13.06.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/06/17

15 | 0:00:00 Starten 0:00:10 Adjazenzfelder 0:02:11 Kantenliste --> Adjazenzfeld 0:06:06 Beispiel 0:07:28 Operationen für Adjanzenzfelder 0:11:40 Kantenanfragen 0:13:17 Adjazenzlisten 0:16:30 Adjazenzlisten aufrüsten 0:18:18 Customization (Zuschneiden) 0:19:37 Beispiel: DAG-Erkennung 0:26:59 Adjazenz-Matrix 0:33:00 Pfade zählen mittels LA 0:35:42 Beispiel, wo Graphentheorie bei LA hilft 0:40:09 Implizite Repräsentation 0:41:54 Zusammenhangstest für Intervallgraphen 0:42:01 Beispiel 0:47:21

01:26:35

14: Algorithmen I, Vorlesung, SS 2016, am 06.06.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/06/09

14 | 0:00:00 Starten 0:00:06 Erinnerung letzte Vorlesung 0:01:32 Erinnerung Grundidee sortierte Folgen 0:02:57 Abgrenzung 0:06:18 Sortierte Folgen - Anwendungen 0:07:19 Anwendungsbeispiel: Best Fit Bin Packing 0:11:52 Binäre Suchbäume 0:14:33 Varianten, Bemerkungen 0:16:12 locate(k) 0:22:07 Invariante von locate(k) 0:23:39 Ergebnisberechnung von locate(k) 0:25:11 Laufzeit von locate(k) 0:27:17 Naives Einfügen 0:30:41 Beispiel 0:32:14 Suchbäume balancieren 0:34:48 (a,b)-Bäume 0:37:31 Items 0:39:55

01:19:27

13: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/06/06

13 | 0:00:00 Starten 0:04:45 Heapsort <-> Quicksort <-> Mergesort 0:08:11 Adressierbare Prioritätslisten 0:12:46 Adressierbare Prioritätslisten: Anwendungen 0:16:26 Adressierbare Binäre Heaps 0:20:36 Adressierbare Prioritätslisten - Laufzeiten 0:21:33 Prioritätslisten: Mehr 0:23:22 Prioritätslisten: Zusammenfassung 0:24:21 Was haben wir jenseits von Prioritätslisten gelernt? 0:25:16 Sortierte Folgen 0:28:59 Statisch: Sortiertes Feld mit binärer Suche 0:33:44 Binäre Suche:

01:28:56

12: Algorithmen I, Vorlesung, SS 2016, am 30.05.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/06/02

12 | 0:00:00 Starten 0:00:06 Erinnerung VL 25.03.2016 0:03:43 Erinnerungsfolie: Bucketsort 0:04:58 Erinnerungsfolie: Beispiel K=4 0:06:09 Array-Implementierung 0:13:04 Beispiel: a=(3,1,2,3,0,0,3,2,1), K=4 0:15:55 Kd Schlüssel 0:22:34 Beispiel: LSD-Radix-Sort 0:23:56 Mehr zu ganzzahligem Sortieren 0:30:18 Sortieren: vergleichsbasiert - ganzzahlig 0:34:21 Mehr zu Sortieren 0:38:18 Was haben wir jenseits von Sortieren gelernt? 0:40:05 Prioritätslisten 0:40:37 Prioritätslisten (priority

01:21:58

11: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/05/30

11 | 0:00:00 Starten 0:00:06 Erinnerung VL vom 23.05.2016 0:13:52 Vergleich Quicksort vs Mergesort 0:21:31 Auswahl (Selection) 0:24:50 Beispiel 0:26:52 Auswahl Anwendungen 0:29:18 Quickselect 0:33:56 Beispiel 0:37:04 Quickselect - Analyse 0:37:59 Mehr zum Auswahlproblem 0:42:01 Durchbrechen der unteren Schranke - Ganzzahliges Sortieren 0:43:11 Schlüssel 0..K-1 - Eimer-Sortieren (bucket sort) 0:47:54 6.Übung zu Algorithmen 0:49:53 Quicksort 1:09:05 Dual Pivot Quicksort 1:19:21 Ganzzahliges

01:23:58

10: Algorithmen I, Vorlesung, SS 2016, am 23.05.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/05/30

10 | 0:00:00 Starten 0:00:06 Erinnerung VL vom 18.05.2016 0:03:16 Nachtrag zur unteren Schranke: Randomisierung, Mittlere Ausführungszeit 0:05:11 Erinnerung: Mergesort 0:06:50 Quicksort - erster Versuch 0:13:10 Quicksort - Analyse im schlechtesten Fall 0:17:36 Quicksort - Analyse im besten Fall 0:21:12 Quicksort - zufälliger Pivot 0:22:25 Satz: Quicksort hat erwartete Laufzeit 0( nlog n ) 0:26:39 Beweisansatz 1: Rekurrenzen 0:52:14 Exkurs: Harmonische Summe 0:58:34 Quicksort: Effiziente

01:21:48

09: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/05/30

09 | 0:00:00 Starten 0:00:06 Rückblick: Sortieren & Co 0:01:33 Überblick 0:02:13 Einfache Sortieralgorithmen 0:05:55 Sentinels am Beispiel Sortieren durch Einfügen 0:11:03 Analyse 0:13:38 Sortieren durch Mischen 0:16:55 Beispiel 0:19:03 Mischen 0:21:10 Analyse 0:21:58 Sortieren durch Mischen 0:25:09 Untere Schranken 0:26:20 Eine vergleichsbasierte untere Schranke 0:29:21 Baumbasierte Sortierer-Darstellung 0:35:40 Beweis 0:43:29 Übung 5 0:43:36 Roadmap 0:44:34 Rückblick: Insertion Sort 0:45:32

01:17:44

08: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/05/19

08 | 0:00:00 Starten 0:00:06 Erinnerung VL vom 09.05.2016 0:03:54 Verketten <--> Lineare Suche 0:13:17 Perfektes Hashing 0:13:49 Mehr Hashing 0:17:12 Hashtabellen für assoziative Arrays 0:23:38 Kryptographische Hashfunktionen 0:27:37 Sortieren & Co 0:29:52 Formaler 0:30:38 Anwendungsbeispiele 0:32:37 Beispiele aus Kurs/Buch 0:35:50 Überblick 0:38:56 4. Übung zu Algorithmen I 0:39:15 Hashtabelle mit einfach verketteten Listen 0:41:13 Duplikaterkennung 0:59:00 Bloom Filter 1:12:50 Unbounded

01:25:54

07: Algorithmen I, Vorlesung, SS 2016, am 09.05.2016

Algorithmen 1, SS2016, Vorlesung ·

2016/05/19

07 | 0:00:00 Starten 0:00:06 Erinnerung VL vom 04.05.2016 0:03:50 Hashing mit verketteten Listen (Wdh.) 0:06:47 Etwas Wahrscheinlichkeitstheorie für den Hausgebraucht 0:31:42 Beispiel: Variante des Geburtstagsparadoxon 0:35:22 Mehr zum Geburtstagsparadoxon 0:36:49 Analyse für zufällige Hash-Funktionen 0:43:42 Zufällige Hash-Funktionen? 0:45:38 Universelles Hashing 0:48:48 Eine einfache universelle Familie 0:52:03 Beispiel für H 0:53:30 Beweis 0:59:16 Bit-basierte Universelle Familien 1:04:14

01:21:25

06: Algorithmen I, Vorlesung und Übung, SS 2016, am...

Algorithmen 1, SS2016, Vorlesung ·

2016/05/09

06 | 0:00:00 Starten 0:00:06 Hashing (Streuspeicherung) 0:01:02 Erinnerung VL vom 02.05.2016 0:03:08 Hashtabellen 0:04:48 Exkurs: Konventionen für Elemente 0:05:45 Hashing: Anwendungen 0:09:28 Überblick: Grundidee, Hashing mit verketteten Listen, Analyse, Hasing mit Arrays 0:10:25 Erste Ideen zu Implementierungen 0:12:39 Ein (über)optimistischer Ansatz 0:16:13 Kollisionen 0:22:24 Kollisionsauflösung 0:23:41 Hashing mit verketteten Listen 0:27:24 Beispiel 0:33:15 Analyse 0:36:16 Übung 0:37:01

25 results

Algorithmen 1, SS2016, 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