Algorithmen 1, SS2018, Vorlesung

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

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

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

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

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

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

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

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

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

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)