All Episodes - Algorithmen 1, SS2016, Vorlesung
Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischenHerangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
View Podcast Details25 Episodes
25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016
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
24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016
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
23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016
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
22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016
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
21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016
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
20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016
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)
19: Algorithmen I, Vorlesung, SS 2016, am 27.06.2016
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
18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016
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?
17: Algorithmen I, Vorlesung, SS 2016, am 20.06.2016
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
16: Algorithmen I, Vorlesung und Übung, SS 2016, am 15.06.2016
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
15: Algorithmen I, Vorlesung, SS 2016, am 13.06.2016
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
14: Algorithmen I, Vorlesung, SS 2016, am 06.06.2016
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
13: Algorithmen I, Vorlesung und Übung, SS 2016, am 01.06.2016
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
12: Algorithmen I, Vorlesung, SS 2016, am 30.05.2016
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
11: Algorithmen I, Vorlesung und Übung, SS 2016, am 25.05.2016
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
10: Algorithmen I, Vorlesung, SS 2016, am 23.05.2016
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
09: Algorithmen I, Vorlesung und Übung, SS 2016, am 18.05.2016
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
08: Algorithmen I, Vorlesung und Übung, SS 2016, am 11.05.2016
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
07: Algorithmen I, Vorlesung, SS 2016, am 09.05.2016
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
06: Algorithmen I, Vorlesung und Übung, SS 2016, am 04.05.2016
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
05: Algorithmen I, Vorlesung, SS 2016, am 02.05.2016
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
04: Algorithmen I, Vorlesung und Übung, SS 2016, am 27.04.2016
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
03: Algorithmen I, Vorlesung, SS 2016, am 25.04.2016
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:36:49 Beweisskizze Fall d=b 0:38:16 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
02: Algorithmen I, Vorlesung und Übung, SS 2016, am 20.04.2016
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
01: Algorithmen I, Vorlesung, SS 2016, am 18.04.2016
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