PODCAST

Algorithmen 1, SS2015, Vorlesung

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

00:46:23

Algorithmen I, SS 2015, gehalten am 15.07.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2016/01/14

26: Übung | Vorbereitung für die Klausur

01:29:57

Algorithmen I, SS 2015, gehalten am 13.07.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2016/01/14

25: Vorlesung | 00:00:12 Ziele von PRAM-Algorithmen 00:01:47 Summe auf der PRAM 00:02:06 Das Prinzip von Arbeit und Laufzeit 00:05:17 Diskussion 00:06:06 Konvexe Hülle 00:07:03 Obere konvexe Hülle 00:13:32 Obere gemeinsame Tangente 00:16:14 Algorithmus UCH 00:33:27 Zusammenfassung 00:36:16 Kap. 14: Zusammenfassung 00:37:33 Zusammenfassung-Datenstruktur 00:42:51 Zusammenfassung- Algorithmen 00:45:24 Zusammenfassung- Entwurfstechniken I 00:53:01 Zusammenfassung- Entwurfstechniken II 00:58:56

00:42:49

Algorithmen I, SS 2015, gehalten am 08.07.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/14

24: Vorlesung | 00:00:07 Systematische Suche 00:00:24 Beispiel: Branch-and-Bound für das Rucksackproblem 00:00:32 Beispielrechnung 00:00:37 Lokale Suche – global denken, lokal handeln 00:00:48 Hill Climbing 00:00:50 Warum die Nachbarschaft wichtig ist 00:00:54 Jenseits von Hill Climbing 00:01:19 Evolutionäre Algorithmen 00:01:23 Zusammenfassung 00:01:25 Kap. 13: Parallele Algorithmen 00:01:27 Werbeblock 00:02:07 Rechnertypen 00:02:16 Gemeinsamer Speicher (shared memory) 00:02:31

01:29:49

Algorithmen I, SS 2015, gehalten am 06.07.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/08

23: Vorlesung | 00:00:07 Dynamische Programmierung – Aufbau aus Bausteinen 00:02:12 Systematische Suche 00:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem 00:20:42 Beispielrechnung 00:33:16 Branch-and-Bound – allgemein 00:34:48 Beispielrechnung 00:42:53 Lokale Suche – global denken, lokal handeln 00:47:44 Hill Climbing 00:49:08 Problem: Lokale Optima 00:51:55 Warum die Nachbarschaft wichtig ist 00:53:41 Jenseits von Hill Climbing 01:00:35 Evolutionäre Algorithmen 01:03:40

00:50:02

Algorithmen I, SS 2015, gehalten am 01.07.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/08

22: Vorlesung | 00:00:07 Kap. 12: Generische Optimierungsansätze 00:00:23 Durchgehendes Beispiel: Rucksackproblem 00:01:19 Allgemein: Maximierungsproblem (L,f) 00:02:03 Black-Box-Löser 00:02:05 Ein einfaches Beispiel 00:02:07 Beispiel: Kürzeste Wege 00:02:09 Eine Anwendung – Tierfutter 00:02:17 Verfeinerungen 00:02:21 Ganzzahlige Lineare Programmierung 00:02:25 Umgang mit (M)ILPs 00:03:19 Nie zurückschauen – Greedy-Algorithmen 00:03:31 Optimale Greedy-Algorithmen 00:03:35 Beispiel:

01:09:58

Algorithmen I, SS 2015, gehalten am 29.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/08

21: Vorlesung | 00:00:07 Der Jarnik-Prim-Algorithmus 00:04:27 Analyse 00:05:08 Kruskals Algorithmus (1956) 00:06:27 Kruskals Algorithmus – Korrektheit 00:07:14 Union-Find Datenstruktur 00:08:30 Union-Find Datenstruktur – Erste Vision 00:09:58 Pfadkompression 00:10:26 Union by Rank 00:10:58 Analyse – nur Union by rank 00:11:35 Analyse – nur Pfadkompression 00:12:04 Analyse – Pfadkompression + Union by rank 00:15:22 Ackermannfunktion – Beispiele 00:18:31 Kruskal mit Union-Find 00:21:15 Union-Find

00:46:59

Algorithmen I, SS 2015, gehalten am 24.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/08

20: Vorlesung | 00:00:07 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte 00:00:17 Allgemeines Korrektheitskriterium 00:00:49 Zyklische Graphen (10.2 im Buch) 00:01:01 Von überall nach überall 00:01:16 Kürzeste Wege: Zusammenfassung 00:01:20 Straßennetzwerke 00:01:21 Ideen für Routenplanung 00:02:01 Beispiel 00:02:06 Transit-Node Routing 00:02:40 Kap. 11: Minimale Spannbäume 00:03:01 Minimale Spannbäume (MST) 00:03:06 Minimale spannende Wälder (MSF) 00:03:07

01:28:47

Algorithmen I, SS 2015, gehalten am 15.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/08

17: Vorlesung | 00:00:07 Kap. 9: Graphtraversierung 00:00:21 Graphtraversierung als Kantenklassifizierung 00:01:52 Breitensuche 00:06:16 Repräsentation des Baums 00:11:52 Repräsentation von Q und Q‘ mittels FIFO 00:13:22 Alternative Repräsentation von Q und Q‘ 00:14:43 Tiefensuche 00:15:55 Tiefensuchschema für G = (V,E) 00:21:14 DFS-Baum 00:28:47 DFS-Nummerierung 00:31:18 Fertigstellungszeit 00:33:33 Kantenklassifizierung bei DFS 00:42:34 Topologische Sortierung 00:45:36 Topologisches Sortieren

01:16:15

Algorithmen I, SS 2015, gehalten am 22.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/07

19: Vorlesung | 00:00:07 Dijkstra: Laufzeit 00:02:21 Laufzeit 00:03:55 Negative Kosten 00:04:43 Allgemeines Korrektheitskriterium 00:09:44 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte 00:11:00 Allgemeines Korrektheitskriterium 00:12:16 Negative Kreise finden 00:14:35 Beispiel 00:18:37 Bellmann-Ford – Laufzeit 00:18:57 Laufzeit 00:19:53 Zyklische Graphen (10.2 im Buch) 00:22:04 Von überall nach überall 00:24:40 Kürzeste Wege: Zusammenfassung 00:25:56 Mehr zu kürzesten

00:45:52

Algorithmen I, SS 2015, gehalten am 17.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/07

18: Vorlesung | 00:00:07 Tiefensuche 00:00:27 Tiefensuchschema für G = (V,E) 00:01:21 DFS-Baum 00:01:22 Fertigstellungszeit 00:01:26 DFS-Nummerierung 00:01:43 Topologische Sortierung 00:01:50 Topologische Sortieren mittels DFS 00:01:58 Kap. 10: Kürzeste Wege 00:02:00 BFS – DFS 00:02:30 Anwendungen 00:02:42 Kantengewichte größer gleich Null 00:02:52 Dijkstras Algorithmus 00:02:57 Allgemeine Definitionen 00:03:07 Kante (u,v) relaxieren 00:03:53 Dijkstras Algorithmus: Pseudocode 00:05:04

00:47:28

Algorithmen I, SS 2015, gehalten am 10.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/07

16: Vorlesung | 00:00:07 Kap. 8: Repräsentation von Graphen 00:00:49 Notation und Konvention 00:01:02 Ungerichtete – gerichtete Graphen 00:01:06 Operationen 00:01:28 Weitere Operationen 00:01:31 Kantenfolgenrepräsentation 00:02:20 Adjazenzfelder 00:02:25 Kantenliste – Adjazenzfeld 00:02:40 Beispiel 00:02:45 Operationen für Adjazenzfelder 00:02:49 Kantenanfragen 00:02:52 Adjazenzlisten 00:03:10 Adjazenzlisten aufrüsten 00:04:18 Customization (Zuschneiden) 00:08:43 Beispiel: DAG-Erkennung 00:15:55

00:51:05

Algorithmen I, SS 2015, gehalten am 29.04.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

06: Übung | - Kurze Wiederholung, Nachtrag zum O-Kalkül - Teile- und Herrsche-Paradigma, Karatsuba-Ofman - Rekurrenzen - Amortisierte Analyse - Unbounded Arrays

00:51:03

Algorithmen I, SS 2015, gehalten am 06.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

08: Vorlesung | 00:00:10 Erinnerung 00:07:08 Hashing mit Linearer Suche (Linear Probing) 00:10:34 Der einfache Teil 00:21:14 Remove 00:30:59 Verketten – Lineare Suche 00:36:48 Perfektes Hashing 00:37:03 Mehr Hashing 00:38:43 Hashtabellen für assoziative Arrays 00:44:43 Kryptographische Hashfunktionen

01:25:29

Algorithmen I, SS 2015, gehalten am 11.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

09: Vorlesung | 00:00:07 Sortieren & Co 00:00:07 Formaler 00:06:02 Anwendungsbeispiele 00:07:51 Beispiele aus Kurs/Buch 00:10:48 Überblick 00:12:09 Einfache Sortieralgorithmen 00:15:25 Sentinels am Beispiel Sortieren durch Einfügen 00:16:24 Einfache Sortieralgorithmen 00:18:51 Analyse 00:21:04 Sortieren durch Mischen 00:24:20 Beispiel 00:27:47 Mischen 00:33:29 Untere Schranken 00:35:15 Eine vergleichsbasierte untere Schranke 00:38:31 Baumbasierte Sortierer-Darstellung 00:45:29 Beweis 00:53:18

01:21:55

Algorithmen I, SS 2015, gehalten am 13.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

10: Vorlesung | 00:00:10 Erinnerung: Sortieren 00:06:28 Erinnerung: Quicksort 00:07:52 Quicksort: Effiziente Implementierung 00:20:44 Beispiel: Partitionierung, k = 1 00:23:48 Beispiel: Rekursion 00:25:04 Größerer Basisfall 00:30:01 Halbrekursive Implementierung 00:33:26 Quadratische Komplexität bei gleichen Elementen? 00:34:10 Quicksort: Effiziente Implementierung 00:35:29 Quadratische Komplexität bei gleichen Elementen? 00:36:35 Halbrekursive Implementierung 00:39:44 Vergleich Quicksort und

01:17:42

Algorithmen I, SS 2015, gehalten am 18.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

11: Vorlesung | 00:00:07 Erinnerung 00:01:57 Erinnerung Quicksort-Partitionierung 00:04:02 Auswahl (Selection) 00:06:16 Beispiel 00:07:38 Auswahl – Anwendungen 00:10:18 Quickselect 00:10:52 Auswahl (Selection) 00:12:27 Quickselect 00:18:23 Beispiel 00:20:26 Quickselect – Analyse 00:24:15 Mehr zum Auswahlproblem 00:30:49 Durchbrechen der unteren Schranke – Ganzzahliges Sortieren 00:33:20 Schlüssel 0..K-1 – Eimer-Sortieren (bucket sort) 00:36:33 Beispiel: K = 4 00:37:54 Array-Implementierung 00:43:01

01:26:04

Algorithmen I, SS 2015, gehalten am 20.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

12: Vorlesung und Übung | 00:00:24 Prioritätslisten 00:00:48 Prioritätslisten (priority queues) 00:01:26 Prioritätslisten – Anwendungen 00:01:48 Binäre Heaps 00:03:33 Implizite Baum-Repräsentation 00:04:56 Pseudocode 00:06:07 Einfügen 00:21:01 deleteMin: Beispiel 00:23:49 Binärer Heap – Analyse 00:25:16 Binärer Heap – Konstruktion 00:29:12 Beispiel: Binärer Heap – Konstruktion 00:30:01 Binärer Heap – Konstruktion 00:34:46 Ein nützlicher Rechentrick 00:37:57 Heapsort 00:40:57 Heapsort:

01:11:14

Algorithmen I, SS 2015, gehalten am 27.05.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

13: Vorlesung und Übung | Vorlesung 00:00:08 Prioritätslisten 00:00:31 Prioritätslisten (priority Queues) 00:00:52 Prioritätslisten – Anwendungen 00:00:54 Binäre Heaps 00:01:54 Implizite Baum-Repräsentation 00:02:48 deletMin: Beispiel 00:02:54 Binärer Heap – Analyse 00:03:00 Beispiel: Binärer Heap – Konstruktion 00:03:01 Binärer Heap – Konstruktion 00:03:15 Ein nützlicher Rechentrick 00:03:18 Heapsort: Beispiel 00:03:22 Heapsort 00:04:03 Heapsort – Quicksort – Mergesort 00:04:28 Adressierbare

01:30:20

Algorithmen I, SS 2015, gehalten am 01.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

14: Vorlesung | 00:00:11 Sortierte Folgen 00:01:26 Statisch: Sortiertes Feld mit binärer Suche 00:01:59 Dynamische Sortierte Folgen – Grundoperationen 00:02:52 Abgrenzung 00:03:26 Binäre Suchbäume 00:06:03 Suchbäume balancieren 00:09:36 items 00:12:59 Initialisierung 00:14:47 Locate 00:17:51 Lockte – Laufzeit 00:23:17 Einfügen – Algorithmenskizze 00:27:58 Einfügen – Beispiel 00:33:39 Einfügen – Korrektheit 00:36:05 Einfügen – Implementierungsdetails 00:39:42 Einfügen – Pseudocode 00:49:04 Entfernen

01:20:31

Algorithmen I, SS 2015, gehalten am 03.06.2015,...

Algorithmen 1, SS2015, Vorlesung ·

2015/12/03

15: Vorlesung und Übung | 00:00:11 Wiederholung: Suchbäume balancieren 00:00:38 (a,b)-Bäume 00:01:20 Items 00:02:58 Initialisierung 00:03:02 Locate 00:03:04 Locate – Laufzeit 00:03:26 Einfügen – Algorithmenskizze 00:03:30 Einfügen – Beispiel 00:04:42 Entfernen – Beispiel 00:05:10 Einfügen und Entfernen – Laufzeit 00:05:27 Erweiterte (augmentierte) Suchbäume 00:05:47 Elternzeiger 00:06:10 Teilbaumgrößen 00:06:37 Zusammenfassung 00:06:46 Was haben wir noch gelernt? 00:07:58 Kap. 8: Repräsentation

26 results

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