Algorithmen 1, SS2018, Vorlesung

Algorithmen 1, SS2018, Vorlesung

By Karlsruher Institut für Technologie (KIT)Education
Download on the App Store

All Algorithmen 1, SS2018, Vorlesung episodes

  • 13: Algorithmen 1, Vorlesung, SS 2018, 04.06.2018
    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 Einfügen - Korrektheit
    1:01:50 Einfügen - Implementierungsdetails
    1:03:57 EInfügen - Pseudocode
    1:13:31 Entfernen - Algorithmenskizze
    1:19:54 Entfernen - Beispiel
    1:21:52 Entfernen - Korrektheit
    1:23:44 Einfügen und Entfernen - Laufzeit
    1:25:02 Mehr Operationen
    1:26:40 Zusammenfassung
    1 hr 28 min
  • 12: Algorithmen 1, Vorlesung und Übung, SS 2018, 30.05.2018
    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 Erinnerung: Bucketsort
    0:46:03 Bucket Sort Spezial
    0:54:52 Priority Queues
    0:57:02 Spezielle Priority Queues
    0:58:36 Bucket Queue
    1:01:41 Binary Radix Heap
    1:08:58 Binary Radix Heap: deleteMin
    1:11:34 Möglichkeit Ternärer Radix Heaps
    1:13:12 Schnelle Heaps: Zusammenfassung
    1 hr 15 min
  • 11: Algorithmen 1, Vorlesung, SS 2018, 28.05.2018
    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 Prioritätslisten: Zusammenfassung
    59 min
  • 10: Algorithmen 1, Vorlesung und Übung, SS 2018, 23.05.2018
    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 ganzzahligem Sortieren
    0:42:10 Sortieren: vergleichsbasiert vs. ganzzahlig
    0:43:48 Was haben wir jeneseits von Sortieren gelernt?
    0:45:52 Übung
    0:46:19 Roadmap
    0:47:23 Rückblick
    0:49:00 Sortieren durch Einfügen: In-Place
    0:50:11 Sortieren durch Einfügen: Sentinel
    0:51:52 Sound
    0:55:34 Quantifiziertes Chaos: Inversionen
    0:58:22 Quantifiziertes Chaos: Runs
    0:59:42 Quantifiziertes Chaos: Removal
    1:00:26 Adaptives Sortieren
    1:01:21 Insertion Sort: Adaptiv?
    1:02:12 Insertion Sort: Erwartete Laufzeit
    1:06:36 Natural Merge Sort
    1:07:58 Erwartete Anzahl von Runs
    1:16:55 Split Sort
    1:18:49 Split Sort: Beispiel
    1:22:09 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen
    1:23:18 C++
    1:24:23 Java
    1 hr 26 min
  • 09: Algorithmen 1, Vorlesung, SS 2018, 16.05.2018
    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 Komplexität bei gleichen Elementen und Drei-Wege-Partitionierung
    1:22:12 Vergleich Quicksort und Mergesort mit Benchmark
    1 hr 30 min
  • 08: Algorithmen 1, Vorlesung, SS 2018, 14.05.2018
    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 Mischen
    1:07:27 Analyse
    1:11:24 Untere Schranken
    1:13:49 Eine Vergleichsbasierte untere Schranke
    1:16:51 Baumbasierte Sortierdarstellung
    1:19:03 Beweis
    1:22:16 Randomisierung, Mittlere Ausführungszeit
    1:22:58 Quicksort – erster Versuch
    1 hr 29 min
  • 06: Algorithmen 1, Vorlesung, SS 2018, 07.05.2018
    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 zufällige Hash-Funktionen
    0:58:18 Zufällige Hash-Funktionen?
    0:59:34 Universelles Hashing
    0:59:40 Hashing mit linearer Suche
    1:03:04 Der einfache Teil
    1:08:10 Remove
    1:16:07 Verketten vs. Lineare Suche
    1:19:33 Hashtabellen für assoziative Arrays
    1:22:29 Kryptographische Hashfunktionen
    1 hr 28 min
  • 05: Algorithmen 1, Vorlesung, SS 2018, 02.05.2018
    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: Implementierungsvarianten
    0:55:42 Stapel: Anwendungen
    0:56:50 Warteschlangen / FIFO
    0:57:34 FIFO: Implementierungsvarianten
    0:59:00 Bounded FIFO
    1:03:27 Warteschlangen: Anwendungen
    1:04:17 Deque: Double-Ended Queues
    1:05:42 Deque: Anwendungen
    1:06:03 Vergleich: Listen - Felder
    1:08:15 Vergleich Operationen
    1:10:07 Ausblick: Weitere Repräsentationen von Folgen
    1:10:50 Hashing (streuspeicherung)
    1:11:50 Hashtabellen
    1:17:52 Exkurs: Konventionen für Elemente
    1:19:02 Hashing: Anwendung
    1:20:15 Erste Ideen zu Implementierungen
    1:21:23 Ein (über-)optimistischer Ansatz
    1:25:17 Kollisionen
    1 hr 28 min
  • 04: Algorithmen 1, Vorlesung, SS 2018, 30.04.2018
    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 Listen
    1:03:45 Listen: Zusammenfassung
    1:05:48 Felder (Arrays)
    1 hr 11 min