Algorithmen 1, SS2017, Vorlesung

Algorithmen 1, SS2017, Vorlesung

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

All Algorithmen 1, SS2017, Vorlesung episodes

  • 13: Algorithmen 1, Vorlesung, SS 2017, 12.06.2017
    13 |
    0:00:00 Starten
    0:00:25 Sortierte Folgen
    0:01:35 Dynamische Sortierte Folgen
    0:02:34 Binäre Suchbäume
    0:03:16 Varianten, Bemerkung
    0:04:28 locate(k)
    0:07:26 Invariante von locate(k)
    0:09:06 Ergebnisberechnung von locate(k)
    0:11:09 Laufzeit von locate(k)
    0:12:47 Naives Einfügen
    0:15:22 Suchbäume balancieren
    0:17:48 (a, b)-Bäume
    1:06:59 Erweiterte Suchbäume
    1:09:22 Elternzeiger
    1:10:23 Teilbaumgrößen
    1:13:15 Zusammenfassung
    1:14:00 Mehr zu sortierten Folgen
    1 hr 18 min
  • 12: Algorithmen 1, Vorlesung und Übung, SS 2017, 07.06.2017
    12 |
    0:00:00 Starten
    0:00:09 Adressierbare Prioritätslisten
    0:06:42 Adressierbare Binäre Heaps
    0:09:16 Adressierbare Prioritätslisten-Laufzeiten
    0:11:56 Prioritätslisten-Zusammenfassung
    0:13:41 Sortierte Folgen
    0:16:44 Statisch: Sortiertes Feld mit binärer Suche
    0:29:06 Dynamische Sortierte Folgen-Grundoperationen
    0:30:21 Mehr Operationen
    0:34:10 Abgrenzung
    0:36:25 Sortierte Folgen-Anwendungen
    0:39:38 Binäre Suchbäume
    0:42:07 Anfang der Übung
    0:43:12 Graphen und Relationen
    0:48:29 Teilbarkeitsgraph
    0:49:38 Der Hyperwürfel Q3
    0:51:17 Knotengrad
    0:53:58 Handshaking Lemma
    0:59:51 Adjazenz-und Inzidenzmatrix
    1:06:46 Graphen als Matrizen
    1:07:58 Wiederholung: DAG
    1:10:47 Graphen als Matrizen
    1:15:13 Wege, Kreise und Zusammenhang
    1:16:48 Eulerische und Hamiltonische Kreise
    1:21:35 Satz von Euler (Graphen)
    1 hr 26 min
  • 11: Algorithmen 1, Vorlesung und Übung, SS 2017, 31.05.2017
    11 |
    0:00:00 Starten
    0:00:11 Vorlesung
    0:00:14 Heap-Algorithmus
    0:04:52 Prozedur siftDown
    0:12:20 deleteMin: Beispiel
    0:15:46 Binärer Heap
    0:27:34 Nützlicher Rechentrick
    0:32:02 Heapsort
    0:38:16 Heapsort, Quicksort, Mergesort
    0:40:43 Adressierbare Prioritätslisten
    0:40:48 Übung
    0:41:39 Roadmap
    0:43:44 Erinnerung: Bucketsort
    0:44:45 Bucket Sort für [0, 1)
    0:51:48 Priority Queues
    0:55:18 Bucket Queue
    0:58:09 Binary Radix Heap
    1:12:41 Schnelle Heaps
    1:13:58 Zusammenfassung
    1 hr 16 min
  • 10: Algorithmen 1, Vorlesung, SS 2017, 29.05.2017
    10 |
    0:00:00 Starten
    0:00:08 Halbrekursive Implementierung
    0:04:39 Quadratische Komplexität bei gleichen Elementen?
    0:11:21 Vergleich Quicksort Mergesort
    0:15:33 Auswahl (Selection)
    0:20:18 Quickselect
    0:37:05 Array-Implementierung
    0:47:51 Least-Sigmificant-Digit Radix-Sortieren
    0:55:05 Mehr zu ganzzahligem Sortieren
    1:04:41 Prioritätslisten
    1:09:21 Binäre Heaps
    1:12:43 Implizite Baum-Repräsentation
    1 hr 24 min
  • 09: Algorithmen 1, Vorlesung, SS 2017, 24.05.2017
    09 |
    0:00:00 Starten
    0:00:13 Quicksort-zufälliger Pivot
    0:05:32 Satz: Quicksort hat erwartete Laufzeit
    0:20:42 Exkurs: Harmonische Summe
    0:27:19 Quicksort: Effiziente Implementierung
    0:38:01 Beispiel: Partinonierung
    0:41:31 Beispiel: Rekursion
    0:43:42 Größerer Basisfall
    0:45:48 Inplace? Wirklich?
    0:47:33 Halbrekursive Implementierung
    0:50:15 Quadratische Komplexität bei gleichen Elementen?
    0:50:52 Anfang der Übung
    0:54:07 Rückblick: Insertion Sort
    0:57:36 Sentinels am Beispiel Sortieren durch Einfügen
    1:04:01 adaptives Sortieren
    1:08:04 Insertion Sort: Adaptiv?
    1:10:13 Insertion Sort: Erwartete Laufzeit
    1:14:15 Natural Merge Sort
    1:14:54 Runs
    1:21:23 Zusammenfassung: Adaptives Sortieren
    1:22:17 Beispiel: C++
    1 hr 27 min
  • 07: Algorithmen 1, Vorlesung und Übung, SS 2017, 17.05.2017
    07 |
    0:00:00 Starten
    0:02:06 Verketten <-> Lineare Suche
    0:06:50 Mehr Hashing
    0:10:29 Hashtabellen für assoziative Arrays
    0:14:49 Kryptographische Hashfunktion
    0:20:50 Sortieren & Co
    0:36:21 4. Übung zu Algorithmen 1
    0:36:55 Hashtabelle mit einfach verketteten Listen
    0:40:13 Duplikaterkennung
    1:10:13 Bloom Filter
    1 hr 20 min
  • 06: Algorithmen 1, Vorlesung, SS 2017, 15.05.2017
    06 |
    0:00:00 Starten
    0:00:08 Hashing (Streuspeicherung)
    0:03:07 Hashtabellen
    0:06:19 Hashing: Anwendungen
    0:10:49 Ein (über)optimistischer Ansatz
    0:12:44 Kollisionen
    0:15:16 Kollisionsauflösung
    0:15:48 Hashing mit verketteten Listen
    0:22:30 Etwas Wahrscheinlichkeitstheorie für den Hausgebrauch
    0:41:59 Analyse für zufällige Hash-Funktion
    0:49:42 Universelles Hashing
    1:10:23 Hashing mit Linearer Suche (Linear Probing)
    1 hr 27 min
  • 05: Algorithmen 1, Vorlesung und Übung, SS 2017, 10.05.2017
    05 |
    0:00:00 Starten
    0:00:08 Beginn Vorlesung
    0:01:08 Erinnerung VL vom 08.05.2017
    0:01:47 Stapel und Schlangen
    0:06:03 Stapel
    0:10:30 Warteschlangen / First-In-First-Out / FIFO
    0:11:12 FIFO
    0:17:58 Warteschlangen
    0:20:38 Deque
    0:24:29 Vergleich: Listen - Felder
    0:27:57 Ausblick: Weitere Repräsentationen von Folgen
    0:29:15 Hashings (Steuerspeicherung)
    0:29:50 Hashtabellen
    0:31:20 Exkurs: Konventionen für Elemente
    0:31:53 Hashing: Anwendungen
    0:34:22 Beginn Übung
    0:34:42 Roadmap
    0:35:05 Verkettete Listen
    0:35:18 Listen - Mit Überholspur
    0:38:03 Skip Lists
    0:46:08 Amotisierte Analyse
    0:55:20 Hotlist
    1:03:01 Zusammenfassung
    1:04:56 Verkettete Listen
    1:10:00 Variablenwechsel
    1 hr 15 min
  • 03: Algorithmen 1, Übung, SS 2017, 03.05.2017
    03 |
    0:00:00 Starten
    0:01:03 Organisatorisches
    0:06:08 Effizienz von Algorithmen
    0:14:41 Eingabegröße und Laufzeit
    0:17:23 Genauer: (asymptotische) Laufzeit
    0:21:29 (Asymptotische) O-Notation
    0:22:56 O-Notation (Intuition)
    0:28:09 Asymptotische Notationen
    0:31:28 Betrachtung über Grenzwerte
    0:42:11 Basis des Logarithmus
    0:45:48 Invarianten
    1:06:51 Teile-und-Herrsche-Paradigma
    1:11:46 Karatsuba-Ofman Multiplikation
    1:14:01 Mastertheorem, einfache/gerundete Form
    1:15:17 Abschätzung von Rekurrenzen
    1 hr 20 min