Algorithmen 1, SS2016, Vorlesung podcast

Algorithmen 1, SS2016, Vorlesung

Player FM - Internet Radio Done Right

Vor acht Jahren hinzugefügt

Inhalt bereitgestellt von Karlsruher Institut für Technologie (KIT). Alle Podcast-Inhalte, einschließlich Episoden, Grafiken und Podcast-Beschreibungen, werden direkt von Karlsruher Institut für Technologie (KIT) oder seinem Podcast-Plattformpartner hochgeladen und bereitgestellt. Wenn Sie glauben, dass jemand Ihr urheberrechtlich geschütztes Werk ohne Ihre Erlaubnis nutzt, können Sie dem hier beschriebenen Verfahren folgen https://de.player.fm/legal.

All About Change

1
Tiffany Yu — Smashing Stereotypes and Building a Disability-Inclusive World 30:23

vor 16 Tagen30:23

Später Spielen

Listen

Gefällt mir

Geliked

30:23

Tiffany Yu is the CEO & Founder of Diversability, an award-winning social enterprise to elevate disability pride; the Founder of the Awesome Foundation Disability Chapter, a monthly micro-grant that has awarded $92.5k to 93 disability projects in 11 countries; and the author of The Anti-Ableist Manifesto: Smashing Stereotypes, Forging Change, and Building a Disability-Inclusive World. As a person with visible and invisible disabilities stemming from a car crash, Tiffany has built a career on disability solidarity. Now that she has found success, she works to expand a network of people with disabilities and their allies to decrease stigmas around disability and create opportunities for disabled people in America. Episode Chapters 0:00 Intro 1:26 When do we choose to share our disability stories? 4:12 Jay’s disability story 8:35 Visible and invisible disabilities 13:10 What does an ally to the disability community look like? 16:34 NoBodyIsDisposable and 14(c) 21:26 How does Tiffany’s investment banking background shape her advocacy? 27:47 Goodbye and outro For video episodes, watch on www.youtube.com/@therudermanfamilyfoundation Stay in touch: X: @JayRuderman | @RudermanFdn LinkedIn: Jay Ruderman | Ruderman Family Foundation Instagram: All About Change Podcast | Ruderman Family Foundation To learn more about the podcast, visit https://allaboutchangepodcast.com/…

Algorithmen 1, SS2016, Vorlesung

Serie-Home•Feed

Algorithmen 1, SS2016, Vorlesung

25 Episoden

#Hochschulbildung #Bildung #Vorlesung #Informatik #Strukturen #Daten #Toolbox #Korrektheitsargumente #Effizienzanalyse #Algorithmen #Mathematik #Karlsruher Instituts Für Technologie KIT #Video #KIT

Algorithmen 1, SS2016, Vorlesung

updated vor 9 Jahren

Serie-Home•Feed

Algorithmen 1, SS2016, Vorlesung

25 Episoden

#Hochschulbildung #Bildung #Vorlesung #Informatik #Strukturen #Daten #Toolbox #Korrektheitsargumente #Effizienzanalyse #Algorithmen #Mathematik #Karlsruher Instituts Für Technologie KIT #Video #KIT

Alle Folgen

Algorithmen 1, SS2016, Vorlesung

1
25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016 58:18

vor 9 years58:18

58:18

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…

Algorithmen 1, SS2016, Vorlesung

1
24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016 48:27

vor 9 years48:27

48:27

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 Follows Function 0:30:56 Felder (Arrays) 0:31:46 Amortisierte Komplexität unbeschr. Felder 0:32:39 Beweis: Konto-Methode (oder Versicherung) 0:34:35 Hashing (Streuspeicherung) 0:39:27 Sortieren & Co…

Algorithmen 1, SS2016, Vorlesung

1
23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016 1:29:48

vor 9 years1:29:48

1:29:48

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 denken, lokal handeln 0:47:44 Hill Climbing 0:49:08 Problem: Lokale Optima 0:51:55 Warum die Nachbarschaft wichtig ist 0:53:41 Jenseits von Hill Climbing 1:00:35 Evolutionäre Algorithmen 1:03:40 Zusammenfassung 1:10:03 Werbeblock 1:10:48 Kap. 13: Parallele Algorithmen 1:20:51 Rechnertypen 1:24:10 Gemeinsamer Speicher (shared memory) 1:25:07 Rechenmodell…

Algorithmen 1, SS2016, Vorlesung

1
22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016 1:23:36

vor 9 years1:23:36

1:23:36

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 Probleme 0:46:15 Erinnerung: Lineare Programme 0:47:48 LP graphisch 0:52:37 Erinnerung: Travelling Salesman Problem 0:53:59 Ein ILP für TSP 0:59:25 Heuristiken 1:01:14 Ameisen Algorithmen 1:04:50 Vertex Cover 1:06:25 Approximation 1:07:21 Eine Approximation für Vertex Cover 1:10:53 Metaheuristiken und Nachbarschaften 1:12:22 Nachbarschaftsheuristiken 1:19:10 Lokale Suche für Vertex Cover 1:20:13 Tabu-Suche für Vertex Cover 1:22:29 Zusammenfassung…

Algorithmen 1, SS2016, Vorlesung

1
21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016 1:18:15

vor 9 years1:18:15

1:18:15

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 Black-Box-Löser 1:01:45 Lineare Programmierung 1:04:22 Ein einfaches Beispiel 1:07:13 Beispiel: Kürzester Weg 1:09:27 Eine Anwendung - Tierfutter 1:11:04 Verfeinerungen 1:12:48 Algorithmen und Implementierungen 1:14:14 Ganzzahlige Lineare Programmierung 1:15:09 Beispiel: Rucksackproblem 1:16:20 Umgang mit (M)ILPs…

Algorithmen 1, SS2016, Vorlesung

1
20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016 1:15:02

vor 9 years1:15:02

1:15:02

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 Datenstruktur 0:44:15 Beginn Übung 10 0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford 0:45:40 Bellman-Ford: Pseudo-Code 0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee) 0:48:53 Bellman-Ford: Beispiel 0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises 0:55:03 Minimale Spannbäume 0:57:00 Minimale Spannbäume: Jarník-Prim 0:58:37 Minimale Spannbäume: Kruskal 1:00:00 Steinerbäume 1:05:42 Steinerbaum: Was kann schief gehen? 1:10:09 Problem des Handlungsreisenden (TSP)…

Algorithmen 1, SS2016, Vorlesung

1
19: Algorithmen I, Vorlesung, SS 2016, am 27.06.2016 1:07:50

vor 9 years1:07:50

1:07:50

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 Zielknoten t 0:48:03 Ideen für Routenplanung 0:50:12 Approach: Transit-Node Routing 0:50:43 Beispiel 0:53:58 Erste Beobachtung 0:55:45 Zweite Beobachtung 0:57:22 Beispiel: Transitknoten 0:57:41 Experimente 0:58:23 Offene Fragen 0:59:31 Minimale Spannbäume 1:02:52 Minimale aufspannende Wälder 1:03:23 Anwendungen…

Algorithmen 1, SS2016, Vorlesung

1
18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016 1:00:22

vor 9 years1:00:22

1:00:22

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 zusammenhängende, ungerichtete Graphen 0:35:41 Breitensuche in DAGs für nicht zusammenhängende Graphen 0:38:08 Dijkstras Algorithmus 0:40:56 Bidirektionale Suche 0:45:09 Bidirektionale Suche - Definitionen 0:46:14 Bidirektionale Suche - Vorgehen 0:46:20 Pingo! Was sind gute Abbruchstrategien? 0:49:19 Abbruchstrategie (1) 0:53:36 Abbruchstrategie (2) 0:54:13 Beispiel 0:55:02 Bemerkungen 0:56:01 Graph-Datenstruktur 0:56:07 Pingo! Wie schnell wird eine Routing-Anfrage? 0:57:54 Speedup Techniques 0:59:38 Mehr davon?…

Algorithmen 1, SS2016, Vorlesung

1
17: Algorithmen I, Vorlesung, SS 2016, am 20.06.2016 1:23:16

vor 9 years1:23:16

1:23:16

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 >= 0 0:48:23 Dijkstras Algorithmus 0:53:07 Korrektheit der Bindfäden 0:54:53 Edsger Wybe Dijkstra 1930-2002 0:57:10 Allgemeine Definition 1:00:17 Kante (u,v) relaxieren 1:03:48 Dijkstras Algorithmus: Pseudocode 1:06:56 Beispiel 1:11:27 Korrektheit 1:13:03 v erreichbar -> v wird irgendwann gescannt…

Algorithmen 1, SS2016, Vorlesung

1
16: Algorithmen I, Vorlesung und Übung, SS 2016, am 15.06.2016 1:10:51

vor 9 years1:10:51

1:10:51

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 Teilbarkeitsgraph 0:41:53 Der Hyperwürfel Q3 0:42:47 Knotengrad 0:43:36 Handshaking Lemma 0:47:19 Adjazenz- und Inzidenzmatrix 0:48:40 Beispiel Adjazenz- und Inzidenzmatrix 0:52:39 Graphen als Matrizen 0:52:57 Wiederholung: DAG 0:54:19 Graphen als Matrizen 0:56:34 Wege, Kreise und Zusammenhang 0:57:20 Eulersche und Hamiltone Kreise 0:59:15 Eulersche Kreise - Anwendungsbeispiel 1:01:07 Satz von Euler (Graphen) 1:07:28 Breitensuche 1:09:46 Beispielanwendung Breitensuche…

Algorithmen 1, SS2016, Vorlesung

1
15: Algorithmen I, Vorlesung, SS 2016, am 13.06.2016 49:03

vor 9 years49:03

49:03

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 Graphrepräsentation: Zusammenfassung…

Algorithmen 1, SS2016, Vorlesung

1
14: Algorithmen I, Vorlesung, SS 2016, am 06.06.2016 1:26:35

vor 9 years1:26:35

1:26:35

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 Initialisierung 0:40:52 Locate 0:42:46 Locate - Laufzeit 0:47:15 Einfügen - Algorithmenskizze 0:51:19 Einfügen - Beispiel 0:57:32 Einfügen - Korrektheit 0:59:20 Einfügen - Implementierungsdetails 1:01:28 Einfügen - Pseudocode 1:08:04 Entfernen - Algorithmenskizze 1:13:50 Entfernen - Beispiel 1:17:15 Entfernen - Korrektheit 1:18:02 Einfügen und Entfernen - Laufzeit 1:18:55 (a,b)-Bäume Implementierungsdetails 1:20:21 Mehr Operationen 1:22:36 Amortiersierte Analyse von insert und remove 1:23:12 Erweiterte (augmentierte) Suchbäume 1:24:07 Elternzeiger 1:25:59 Teilbaumgrößen…

Algorithmen 1, SS2016, Vorlesung

1
13: Algorithmen I, Vorlesung und Übung, SS 2016, am 01.06.2016 1:19:27

vor 9 years1:19:27

1:19:27

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: Beispiel 0:35:11 Dynamische Sortierte Folgen - Grundoperationen 0:35:55 Mehr Operationen 0:38:01 Noch mehr Operationen 0:40:34 BEGINN ÜBUNG 0:40:49 Roadmap 0:41:24 Organisatorisches 0:43:45 Erinnerung: Bucketsort 0:45:20 Bucket Sort für [0,1) 0:53:41 Sortieren- Auf einen Blick 0:56:45 Priority Queues 0:59:00 Bucket Queue 1:02:55 Binary Radix Heap 1:17:48 Schnelle Heaps 1:18:34 Zusammenfassung…

Algorithmen 1, SS2016, Vorlesung

1
12: Algorithmen I, Vorlesung, SS 2016, am 30.05.2016 1:28:56

vor 9 years1:28:56

1:28:56

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 queues) 0:42:43 Prioritätslisten - Anwendungen 0:46:20 Binäre Heaps 0:49:33 Implizite Baum-Repräsentation 1:01:53 Funktion deleteMin 1:07:50 Procedure siftDown 1:10:53 Beispiel: deleteMin 1:11:36 Binärer Heap - Analyse 1:12:47 Binärer Heap - Konstruktion 1:22:09 Ein nützlicher Rechentrick 1:24:00 Heapsort 1:27:03 Beispiel: Heapsort…

Algorithmen 1, SS2016, Vorlesung

1
11: Algorithmen I, Vorlesung und Übung, SS 2016, am 25.05.2016 1:21:58

vor 9 years1:21:58

1:21:58

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 Sortieren…

Algorithmen 1, SS2016, Vorlesung

1
10: Algorithmen I, Vorlesung, SS 2016, am 23.05.2016 1:23:58

vor 9 years1:23:58

1:23:58

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 Implementierung 1:07:20 Beispiel: Partitionierung, k=1 1:12:06 Größerer Basisfall 1:17:40 Halbrekursive Implementierung…

Algorithmen 1, SS2016, Vorlesung

1
09: Algorithmen I, Vorlesung und Übung, SS 2016, am 18.05.2016 1:21:48

vor 9 years1:21:48

1:21:48

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 Sentinels am Beispiel Sortieren durch Einfügen 0:46:02 Anschaulich...(Rumänischer Volkstanz) 0:49:34 Adaptives Sortieren 0:52:35 Insertion Sort 0:56:09 Insertion Sort - Average Case 0:58:41 Natural Merge Sort 1:05:48 Runs 1:11:30 Removals 1:12:31 Split Sort 1:15:00 Adaptives Sortieren (Zusammenfassung) 1:16:09 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen 1:17:19 C++ 1:20:41 Java…

Algorithmen 1, SS2016, Vorlesung

1
08: Algorithmen I, Vorlesung und Übung, SS 2016, am 11.05.2016 1:17:44

vor 9 years1:17:44

1:17:44

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 Hashtables…

Algorithmen 1, SS2016, Vorlesung

1
07: Algorithmen I, Vorlesung, SS 2016, am 09.05.2016 1:25:54

vor 9 years1:25:54

1:25:54

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 Hashing mit Linearer Suche (Linear Probing) 1:07:50 Der einfache Teil 1:13:37 Remove…

Algorithmen 1, SS2016, Vorlesung

1
06: Algorithmen I, Vorlesung und Übung, SS 2016, am 04.05.2016 1:21:25

vor 9 years1:21:25

1:21:25

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 Organisatorisches 0:37:49 Roadmap 0:38:38 Verkettete Listen 0:39:26 Listen - Mit Überholspur 0:41:43 Skip Lists 0:48:23 Skip Lists - Performance 0:50:06 Amortisierte Analyse 0:52:32 Amortisierte Analyse - Beispiel 0:55:26 Amortisierte Anlalyse - Erinnerung 0:56:31 Amortisierte Analyse - Beispiel 1:00:43 Hotlist 1:01:40 Hotlist - Operationen 1:04:17 Hotlist - Amortisierung 1:06:20 Hotlist - Operationen 1:08:51 Hotlist - Zusammenfassung 1:09:37 Zusammenfassung 1:10:17 Verkettete Listen 1:12:22 Verkettete Listen - Drei Arrays 1:14:11 Verkettete Listen - Ein Array 1:16:59 Variablenwechsel 1:20:33 Zusammenfassung…

Algorithmen 1, SS2016, Vorlesung

1
05: Algorithmen I, Vorlesung, SS 2016, am 02.05.2016 1:12:52

vor 9 years1:12:52

1:12:52

05 | 0:00:00 Starten 0:00:06 Wiederholung 0:04:58 Felder (Arrays) 0:07:59 Unbeschränkte Felder - Anwendungen 0:08:49 Unbeschränkte Felder - Grundidee 0:11:55 Unbeschränkte Felder mit teilweise ungenutztem Speicher 0:18:06 Kürzen 0:20:01 Amortisierte Komplexität unbeschr. Felder 0:23:20 Beweis: Konto- Methode (oder Versicherung) 0:30:38 Amortisierte Analyse - allgemeiner 0:33:48 Amortisierte Analyse - Diskussion 0:39:18 Stapel und Schlange 0:41:20 Stapel 0:42:12 Stapel - Implementierungsvaraianten 0:44:36 Stapel - Anwendungen 0:47:16 Warteschlangen / First-In-First-Out/FIFO 0:48:31 FIFO - Implementierungsvarianten 0:55:59 Warteschlangen - Anwendungen 0:58:07 Deque - Double-Ended Queues 0:59:04 Deque - Anwendungen 1:00:08 Vergleich: Listen - Felder 1:03:47 Ausblick: Weitere Repräsentationen von Folgen 1:05:12 Hashing (Streuspeicherung) 1:06:30 Hashtabellen 1:09:37 Exkurs: Konventionen für Elemente 1:10:20 Hashing: Anwendungen…

Algorithmen 1, SS2016, Vorlesung

1
04: Algorithmen I, Vorlesung und Übung, SS 2016, am 27.04.2016 1:17:44

vor 9 years1:17:44

1:17:44

04 | 0:00:00 Starten 0:00:06 Folgen als Felder und Listen 0:01:05 Folgen 0:01:16 Form Follow Function 0:01:37 Verkettete Listen 0:02:19 Listenglieder (Items) 0:06:31 Trick: dummy header 0:09:33 Dummy header - Beispiel〈a,b,c〉 0:10:19 Die Listenklasse 0:15:09 Splice Beispiel 0:15:45 Der Rest sind Einzeiler (?) 0:17:56 Oder doch nicht? Speicherverwaltung! 0:21:28 Items löschen 0:22:45 Elemente einfügen 0:25:41 Ganze (Teil)Listen Manipulieren 0:26:16 Suchen 0:29:39 Funktionalität <-> Effizienz 0:31:08 Einfach verkettete Listen 0:34:13 Einfach verkettete Listen - splice 0:35:02 Einfach verkette Listen - pushBack 0:35:47 Listen: Zusammenfasssung, Verallgemeinerung 0:37:59 Übung 0:38:20 Teile-und-Herrsche-Paradigma 0:43:42 Karatsuba-Ofman, Beispiel 0:45:26 Karatsuba-Ofman, Laufzeit 0:46:58 Mastertheorem, einfache Form 0:51:16 Abschätzung von Rekurrenzen 1:06:06 Bisektion von Bäumen…

Algorithmen 1, SS2016, Vorlesung

1
03: Algorithmen I, Vorlesung, SS 2016, am 25.04.2016 1:16:43

vor 9 years1:16:43

1:16:43

03 | 0:00:00 Starten 0:00:06 Wiederholung und Überblick 0:01:38 Pseudocode 0:07:18 Schleifeninvarianten 0:11:46 Beispiel 0:16:38 Rechenbeispiele: 2^5 0:21:59 Programmanalyse 0:24:39 Schleifenanalyse -> Summen ausrechnen 0:24:54 Eine Rekurrenz für Teile und Herrsche 0:28:09 Master Theorem (Einfache Form) 0:30:05 Beweisskizze 0:34:12 Beweisskizze Fall d b 0:41:00 Master Theorem Beispiele 0:42:01 Analyse im Mitttel 0:42:37 Graphen 0:49:27 Bäume 0:52:39 Ein erster Graphalgorithmus 1:01:05 Beispiel (Graphalgorithmus) 1:02:33 P und NP 1:05:53 Folgen als Felder und Listen 1:09:32 Folgen 1:12:37 Anwendungen 1:13:29 Form Follows Function…

Algorithmen 1, SS2016, Vorlesung

1
02: Algorithmen I, Vorlesung und Übung, SS 2016, am 20.04.2016 1:24:54

vor 9 years1:24:54

1:24:54

02 | 0:00:00 Starten 0:00:07 Erinnerung VL 18.04.2016 0:02:33 Erinnerung rekursiver Algorithmus 0:04:00 Karatsuba-Ofman Multiplikation (1962) 0:06:24 Beispiel 0:07:54 Analyse 0:09:31 Algorithm Engineering – was hat das mit der Praxis zu tun? 0:10:17 Algorithmentheorie (Karikatur) 0:11:38 Algorithmik als Algorithm Engineering 0:12:26 Zurück zur Langzahlmultiplikation 0:15:41 Skalierung 0:17:01 Blick über den Tellerrand 0:20:57 Einführendes 0:21:35 Zurück zur Langzahlmultiplikation 0:23:28 Überblick 0:24:14 (Asymptotische) Algorithmenanalyse 0:25:49 Zweite Vereinfachung: Asymptotik 0:28:39 O-Kalkül Rechenregeln 0:29:45 Maschinenmodell: RAM (Random Access Machine) 0:31:19 Register 0:32:20 Hauptspeicher 0:33:09 Speicherzugriff 0:34:15 Rechnen 0:34:58 Bedingte Sprünge 0:36:43 »Kleine« ganze Zahlen? 0:38:57 Algorithmenanalyse im RAM-Modell 0:40:53 Mehr Maschinenmodell 0:45:26 Übung 0:46:07 Organ im Suchdurchlauf – Wo finde ich Was? 0:47:30 Effizienz von Algorithmen 0:49:22 Generelles Beispiel 0:50:39 Eingabegröße und Laufzeit 0:51:57 Genauer: (asymptotische) Laufzeit 0:53:47 (Asymptotische) O-Notation 0:54:28 O-Notation (Intuition) 0:56:13 Asymptotische Notationen 0:57:23 Nochmal anschaulich ... 0:58:39 Betrachtung über Grenzwerte 0:59:22 Betrachtung über Grenzwerte: Beispiel 0:59:59 Ein kniffligeres Beispiel ... 1:05:34 Basis des Logarithmus 1:07:24 Korrektheit von Algorithmen 1:08:00 Invarianten…

Algorithmen 1, SS2016, Vorlesung

1
01: Algorithmen I, Vorlesung, SS 2016, am 18.04.2016 1:11:31

vor 9 years1:11:31

1:11:31

01 | 0:00:00 Starten 0:01:19 Organisatorisches 0:03:27 Materialien 0:05:27 Weitere Bücher 0:06:50 Übung - Algorithmen I 0:07:00 Übungsleiter 0:08:23 Tutorien 0:09:46 Übung 0:10:24 Übungsblätter 0:11:28 Bonuspunkte für die Klausur 0:12:01 Fragen und Tipps 0:14:30 Mittsemesterklausur 0:15:06 Klausur 0:15:27 Weitere Bücher 0:15:55 Algorithmus? Kann man das essen? 0:18:34 Algorithmik 0:20:13 Datenstruktur 0:21:55 Themenauswahl: Werkzeugkasten 0:23:57 Inhaltsübersicht 0:28:36 Amuse Geule | Beispiel: Langzahl-Multiplikation 0:33:52 Addition 0:36:09 Beispiel 0:37:02 Exkurs: Pseudocode 0:39:42 Exkurs vom Exkurs: Wies nicht C++ / Java-like? 0:41:07 Ziffernmultiplikation 0:43:11 Beispiel 0:47:29 Schulmultiplikation 0:50:25 Schulmultiplikation Beispiel 0:51:09 Schulmultiplikation Analyse 0:53:24 Exkurs O-Kalkül, die Erste 0:57:40 Ein rekursiver Algorithmus 1:03:15 Beispiel 1:04:25 Analyse 1:08:17 Exkurs: Algorithmen-Entwurfsmuster 1:10:27 Karatsuba-Ofman Multiplikation (1962) 1:10:52 Analyse…

Willkommen auf Player FM!

Player FM scannt gerade das Web nach Podcasts mit hoher Qualität, die du genießen kannst. Es ist die beste Podcast-App und funktioniert auf Android, iPhone und im Web. Melde dich an, um Abos geräteübergreifend zu synchronisieren.