PODCAST

Algorithmen 1, SS2018, Vorlesung

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:14:52

23: Algorithmen 1, Vorlesung, SS 2018, 18.07.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/19

23 | 0:00:00 Start 0:00:52 Heutige Vorlesung 0:01:52 Zusammenfassung 0:08:58 Propositional Logic 0:13:39 Staisfiability 0:16:08 Satisfiabilty - Example 0:19:27 Satisfiability - A Practical Example 0:27:15 Satisfiability - Hardness 0:35:41 Satisfiability - History 0:39:37 Applications of SAT solving 0:42:50 SAT Solving in the news 0:44:28 Pythadorean Triples 0:53:13 Arithmetic Progressions 0:56:39 Background: Van der Eaerden Numbers 1:00:11 Graph Coloring 1:02:10 Graph Coloring: Encoding in

01:26:50

22: Algorithmen 1, Vorlesung, SS 2018, 16.07.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/17

22 | 0:00:00 Start 0:00:28 Rückblick Vorlesung 09.07. 0:03:19 Dynamische Programmierung – Aufbau aus Bausteinen 0:09:15 Dynamische Programmierung 0:16:46 Rekonstruktion der Lösung 0:19:07 Algorithmenentwurf mittels dynamischer Programmierung 0:23:33 Anwendungen dynamischer Programmierung 0:28:33 Gegenbeispiel: Teilproblemeigenschaft 0:34:30 Gegenbeispiel: Austauschbarkeit 0:43:54 Systematische Suche 0:51:25 Beispiel: Branch-and-Bound für das Rucksackproblem 1:03:34 Branch-and-Bound

00:41:46

21: Algorithmen 1, Übung, SS 2018, 04.07.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/09

21 | 0:00:00 Start 0:02:30 Dijkstras Algorithmus 0:10:26 Bellman Ford Algorithmus 0:22:16 Minimale Spannbäume 0:27:49 Steinerbäume 0:35:38 Problem des Handlungsreisenden (TSP)

01:24:27

18: Algorithmen 1, Vorlesung, SS 2018, 25.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/06

18 | 0:00:00 Starten 0:00:32 Rückblich Vorlesung 18.06 0:02:48 Kürzeste Wege: Definition 0:04:13 Dijkstras Algorithmus 0:08:01 Dijkstra: Negative Kantengewichte 0:21:54 Negative Zyklen 0:28:26 Zurück zu Basiskonzepten 0:31:34 Mehr Basiskonzepte 0:33:21 Allgemeines Korrektheitskriterium 0:33:52 Bellman-Ford-Algorithmus 0:40:31 Negative Kreise 0:53:56 Azyklische Graphen 0:58:07 Kürzeste Wege: Zusammenfassung 1:03:52 Exkurs: Routing in Straßennetzwerken 1:10:33 Distanz zu einem Zielknoten 1:11:56

01:29:11

19: Algorithmen 1, Vorlesung, SS 2018, 27.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/06

19 | 0:00:00 Start 0:02:10 Rückblick Vorlesung 25.06. 0:05:34 Minimale Spannbäume 0:11:04 Minimale aufspannende Wälder 0:17:03 MST-Kanten auswählen und verwerfen 0:33:48 Der Jarnik-Prim-Algorithmus 0:47:00 Analyse 0:48:53 Kruskals Algorithmus 1:01:44 Kruskals Algorithmus – Korrektheit 1:04:35 Union-Find Datenstruktur 1:19:03 Pfadkompression 1:22:33 Union by Rank

01:17:57

20: Algorithmen 1, Vorlesung, SS 2018, 02.07.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/07/06

20 | 0:00:00 Start 0:00:12 Rückblick 0:19:10 heutige Vorlesung 0:19:43 Analyse – Pfadkompression und Union by Rank 0:28:50 Ackermannfunktion – Beispiele 0:30:58 Kruskal mit Union-Find 0:39:37 Vergleich mit Jarnik-Prim vs. Kruskal 0:42:42 Mehr MST-Algorithmen 0:48:16 Zusammenfassung 0:51:08 Generische Optimierungsprobleme 0:53:39 Durchgehendes Beispiel: Rucksackproblem 0:56:52 Allgemein: Maximierungsproblem 1:00:36 Black-Box-Löser 1:02:10 Lineare Programmierung 1:10:08 Ein einfaches Beispiel 1:15:08

01:24:56

17: Algorithmen 1, Vorlesung, SS 2018, 18.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/06/20

17 | 0:00:00 Starten 0:00:11 Rückblick Vorlesung 11.06 0:02:13 BFS vs. DFS 0:04:05 Begriff ""Zusammenhang"" 0:11:16 Überblick heutige Vorlesung 0:12:03 Kürzeste Wege 0:15:11 Definition 0:24:05 Grundlagen 0:28:02 Dijkstra Algorithmus 0:32:10 Edsger Wybe Dijkstra 0:42:03 Allgemeine Definition 0:45:37 Kante relaxieren 0:49:42 Pseudocode 1:08:15 Implementierung 1:18:38 Laufzeit

00:57:54

16: Algorithmen 1, Übung, SS 2018, 13.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/06/19

16 | 0:00:00 Starten 0:00:05 Roadmap 0:00:25 Übungsklausur 0:02:58 Graphen und Relationen 0:04:22 Knotengrad 0:05:04 Beispiele 0:08:26 Handshaking Lemma 0:11:58 Adjazenz- und Inzidenzmatrix 0:20:29 Grpahen als Matrizen 0:25:17 Pfade und Kreise 0:26:13 Eulersche und Hamiltonsche Kreise 0:28:11 Satz von Euler 0:36:05 Breitensuche 0:47:48 Tiefensuche

01:24:37

15: Algorithmen 1, Vorlesung, SS 2018, 11.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/06/18

15 | 0:00:00 Starten 0:00:09 Organisatorisches 0:03:12 Randbemerkung zu WWDC 2018 0:05:32 Rückblick Vorlesung 06.06. 0:07:56 Überblick heutige Vorlesung 0:08:18 Adjazenz-Matrix 0:08:52 Pfade zählen mittels LA 0:09:38 Graphentheorie und LA 0:15:39 Zusammenhangstest für Intervallgraphen 0:18:18 Beispiel 0:19:52 Graphenpräsentation: Zusammenfassung 0:21:30 Graph-Traversierung 0:23:14 Graphtraversierung als Kantenklassifizierung 0:26:23 Breitensuche 0:31:57 Repräsentation des Baumes 0:41:59

01:23:55

14: Algorithmen 1, Vorlesung, SS 2018, 06.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/06/12

14 | 0:00:00 Starten 0:00:16 Rückblick 04.06. 0:02:56 Graphen 0:05:51 Königesberger Brückenproblem 0:10:00 Graphen Anwendung 0:13:43 Repräsentation von Graphen 0:19:19 Notation und Konvention 0:22:01 Ungerichtete vs gerichtete Graphen 0:23:01 Operationen 0:27:17 Kantenfolgenrepräsentation 0:30:53 Repräsentation von Graphen 0:31:35 Adjazenzfelder 0:40:55 Beispiel 0:47:58 Kantenanfragen 0:48:56 Adjazenzlisten 0:52:17 Adjazenzlisten Aufrüsten 0:55:18 Customisation 0:57:31 Beispiel:

01:27:19

13: Algorithmen 1, Vorlesung, SS 2018, 04.06.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/06/05

13 | 0:00:00 Start 0:00:30 Überblick heutige Vorlesung 0:00:51 Sortierte Folgen 0:05:42 Binäre Baumsuche 0:10:05 Varianten, Bemerkungen 0:12:19 locate(k) 0:15:58 Invariante von locate(k) 0:17:58 Ergebnisberechnung von locate(k) 0:18:45 Laufzeit von locate(k) 0:20:30 Naives Einfügen 0:25:12 Beispiel 0:27:02 Suchbäume balancieren 0:30:11 (a,b)-Bäume 0:32:29 Items 0:37:10 Initialisierung 0:39:02 Locate 0:43:44 Locate - Laufzeit 0:48:03 Einfügen - Algorithmenskizze 0:51:20 EInfügen - Beispiel 0:58:10

01:14:16

12: Algorithmen 1, Vorlesung und Übung, SS 2018,...

Algorithmen 1, SS2018, Vorlesung ·

2018/06/01

12 | 0:00:00 Start 0:00:05 Rückblick Vorlesung 28.05 0:01:33 Überblick heutige Vorlesung 0:02:30 Sortierte Folgen 0:09:22 Statisch: Sortiertes Feld mit binärer Suche 0:16:26 Binäre Suche: Beispiel k=15 0:19:15 Dynamisch sortierte Folgen - Grundoperationen 0:22:51 Mehr Operationen 0:26:32 Noch mehr Operationen 0:30:24 Abgrenzung 0:34:50 Sortierte Folgen - Anwendungen 0:35:56 Anwendungsbeispiel: Best Fit Bin Packing 0:41:18 Binäre Baumsuche 0:42:52 3. Übung Algorithmen I 0:44:16 Roadmap 0:45:04

00:58:21

11: Algorithmen 1, Vorlesung, SS 2018, 28.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/30

11 | 0:00:00 Start 0:00:05 Einfügen 0:05:32 Funktion deleteMin 0:17:09 deleteMin: Beispiel 0:18:43 Binärer Heap - Analyse 0:20:27 Binärer Heap - Konstruktion 0:31:26 Ein nützlicher Rechentrick 0:36:58 Heapsort 0:43:07 Heapsort: Beispiel 0:44:22 Heapsort vs. Quicksort vs. Mergesort 0:48:19 Adressierbare Prioritätslisten 0:51:26 Adressierbare Prioritätslisten: Anwendungen 0:53:23 Adressierbare Binäre Heaps 0:55:39 Adressierbare Prioritätslisten - Laufzeiten 0:56:43 Prioritätslisten: Mehr 0:57:18

01:25:28

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

Algorithmen 1, SS2018, Vorlesung ·

2018/05/25

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

01:29:45

09: Algorithmen 1, Vorlesung, SS 2018, 16.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/17

09 | 0:00:00 Starten 0:00:13 Rückblick 14.05. 0:04:16 Überblicke aktuelle Vorlesung 0:05:46 Erinnerung: Mergesort 0:06:53 Quicksort 0:09:32 Quicksort: Analyse im schlechtesten Fall 0:15:21 Quicksort: Analyse im besten Fall 0:19:16 Quicksort: Zufälliger Pivot 0:20:26 Quicksort: Laufzeit 0:26:46 Beweise 0:51:15 Quicksort: Effiziente Implementierung 1:03:03 Beispiel: Partitionierung 1:06:23 Beispiel: Rekursion 1:06:49 Größerer Basisfall 1:15:40 Halbrekursive Implementierung 1:18:44 Quadratische

01:28:20

08: Algorithmen 1, Vorlesung, SS 2018, 14.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/15

08 | 0:00:00 Start 0:00:12 Rückblick Vorlesung 07.05. 0:03:57 Analyse für zufällige Hash-Funktionen 0:10:12 Universelles Hashing 0:13:50 Eine einfache universelle Familie 0:22:36 Beispiele für H 0:25:13 Beweis Theorem 0:33:14 Sortieren & Co 0:36:47 Lochkartensortierer 0:41:28 Grundproblem Sortieren 0:45:33 Anwendungsbeispiele 0:47:49 Einfache Sortieralgorithmen 0:51:17 Sentinels am Beispiel Sortieren durch Einfügen 0:57:07 Analyse 1:00:25 Sortieren durch Mischen 1:03:33 Beispiel 1:05:00

00:36:22

07: Algorithmen 1, Übung, SS 2018, 09.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/11

07 | 0:00:00 Start 0:00:39 Verkettete Listen 0:01:43 Skip Lists 0:06:10 Amortisierte Analyse 0:11:59 Hotlists 0:19:28 Hashtabelle mit einfach verketteten Listen 0:21:00 Duplikaterkennung 0:25:39 Bloom Filter

01:27:02

06: Algorithmen 1, Vorlesung, SS 2018, 07.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/08

06 | 0:00:00 Start 0:00:13 Rückblick Vorlesung 02.05 0:02:40 Überblick heutige Vorlesung 0:03:36 Hashing 0:03:58 Hashtabellen 0:09:48 Ein (Über-)optimistischer Ansatz 0:15:00 Kollisionen 0:19:53 Kollisionsauflösung 0:21:13 Hashing mit verketteten Listen 0:26:12 Hashing mit verketteten Listen: Beispiel 0:31:30 Hashing mit verketteten Listen: Analyse 0:33:08 Etwas Wahrscheinlichkeitstheorie 0:46:18 Beispiel: Variante des Geburtstagsparadoxon 0:55:09 Mehr zum Geburtstagsparadoxon 0:56:50 Analyse für

01:27:51

05: Algorithmen 1, Vorlesung, SS 2018, 02.05.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/03

05 | 0:00:00 Start 0:00:17 Rückblick 0:03:35 Felder (Arrays) 0:09:16 Unbeschränkte Felder 0:20:49 Unbeschränkte Felder mit teilweise ungenutztem Speicher 0:25:26 Unbeschränkte Felder: Vergrößern 0:30:50 Unbeschränkte Felder: Verkleinern 0:34:46 Amprtisierte Komplexität für unbeschränkte Felder 0:38:34 Beweis: Account-Methode (Konto-Methode) 0:43:14 Amortisierte Analyse: verallgemeinert 0:45:56 Amortisierte Analyse: Diskussion 0:48:47 Stapel und Schlange 0:52:30 Stapel: Operationen 0:53:08 Stapel:

01:10:17

04: Algorithmen 1, Vorlesung, SS 2018, 30.04.2018

Algorithmen 1, SS2018, Vorlesung ·

2018/05/03

04 | 0:00:00 Start 0:00:05 P und NP 0:02:43 Folgen als Felder und Listen 0:06:11 Ausblick: Komplexität typischer Operationen 0:13:27 Listenglieder (Items) 0:21:00 Trick: Dummy Header 0:24:18 Die Listenklasse 0:27:12 Splice-Operation 0:35:09 Weitere Operationen: Einfach mit splice 0:37:32 Doch nicht so einfach? Speicherverwaltung ! 0:43:08 Items löschen 0:45:11 Elemente einfügen 0:47:59 Ganze Listen manipulieren 0:53:33 Suchen 0:57:14 Funktionalität vs. Effizienz 0:58:50 Einfach verkettete

23 results

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