Algorithmen 1, SS2019, Vorlesung

13 |

0:00:00 Start

0:00:12 Rückblick Vorlesung 03.06

0:01:48 Überblick heutige Vorlesung

0:02:48 Prioritätslisten

0:09:43 Anwendungen

0:10:47 Binäre Heaps

0:16:37 Implizite Baum Repräsentation

0:19:51 Pseudocode

0:23:30 Einfügen

0:32:19 Funktion deleteMin

0:36:23 Funktion siftDown

0:39:35 deleteMin: Beispiel

0:41:12 Binärer Heap - Analyse

0:45:32 Binärer Heap - Konstruktion

0:54:43 Ein nützlicher Rechentrick

1:00:41 Heapsort

1:02:31 Heapsort: Beispiel

1:03:06 Heapsort vs Quicksort vs Mergesort

1:06:15 Adressierbare Prioritätslisten

1:10:35 Adressierbare Binäre Heaps

1:12:55 Adressierbare Prioritätslisten - Laufzeiten

1:14:33 Prioritätslisten: Mehr

1:15:28 Zusammenfassung

1:17:45 Rückblick Vorlesung 12.06

1:17:56 Sortierte Folgen

12 |

0:00:00 Start

0:10:03 Adaptives Sortieren

0:10:59 Insertion Sort: Adaptiv?

0:11:41 Insertion Sort: Erwartete Laufzeit

0:14:09 Natural Merge Sort

0:15:03 Erwartete Anzahl von Runs

0:19:51 Split Sort

0:22:41 Schnelle Mediansuche für Quicksort

0:33:01 Sortieralgorithmen in aktuellen Programmiersprachen

Addison Wesley, 2005

09 |

0:00:00 Starten

0:00:24 Rückblick

0:06:17 Kollisionen

0:11:06 Analyse für zufällige Hash-Funktionen

0:21:54 Universelles Hashing

0:34:35 Beweis Theorem

0:42:08 Hashing mit linearer Suche(""linear probing"")

0:45:08 Der einfache Teil

0:51:03 Remove

1:01:36 Verketten vs. Lineare Suche

1:06:46 Kryptographische Hashfunktionen

1:10:29 Sotieren und Co

1:13:20 Lochkartensortierer

1:19:10 Einfache Sortieralgorithmen

1:21:52 Sentinels am Beispiel Sotieren durch Einfügen

1:24:47 Analyse

- - - - - - -

Titel der Serie:

Algorithmen I, Vorlesung, SS 2019

Beschreibung der Serie:

Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:

- Ergebnisüberprüfung (Checkers) und Zertifizierung

- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert

- Grundbegriffe des Algorithm Engineering

- Effektive Umsetzung verketteter Listen

- Unbeschränkte Arrays, Stapel, und Warteschlangen

- Hashtabellen: mit Verkettung, linear probing, universelles Hashing

- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort

- Selektion: quickselect

- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten

- Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit

- Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)

- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)

Literaturhinweise:

Algorithms and Data Structures - The Basic Toolbox

K. Mehlhorn und P. Sanders

Springer 2008

Weiterführende Literatur

Algorithmen - Eine Einführung

T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein

Oldenbourg, 2007

Algorithmen und Datenstrukturen

T. Ottmann und P. Widmayer

Spektrum Akademischer Verlag, 2002

Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen

R. Sedgewick

Pearson Studium 2003

Algorithm Design

J. Kleinberg and É. Tardos

Addison Wesley, 2005

Vöcking et al.

Taschenbuch der Algorithmen

Springer, 2008

11 |

0:00:00 Start

0:00:05 Rückblick letzte Vorlesung

0:04:51 Quicksort: Effiziente Implementierung

0:10:56 Halbrekursive Implementierung

0:16:10 Quadratische Komplexität bei gleichen Elementen?

0:29:01 Vergleich Quicksort und Mergesort

0:34:13 Benchmark

0:38:52 Auswahl: Anwendungen

0:45:40 Quickselect: Analyse

0:49:28 Durchbrechen der unteren Schranke – Ganzzahliges Sortieren

0:58:59 Array-Implementierung

1:03:54 Least-Significant-Digit Radit Sort

1:09:39 Mehr zu ganzzahligem Sortieren

1:14:24 Mehr zu Sortieren

10 |

0:00:00 Starten

0:00:12 Rückblick Vorlesung 27.05

0:03:46 Einfache Sortieralgorithmen

0:05:29 Sortieren durch Mischen

0:09:04 Beispiel

0:11:31 Mischen

0:12:51 Analyse

0:15:49 Untere Schranke

0:17:47 Nicht vergleichsbasierte untere Schranke

0:22:34 Baumbasierte Sortierer Darstellung

0:24:59 Beweis

0:32:29 Randomisierung, Mittlere Ausführungszeit

0:34:42 Quicksort

1:21:24 Größerer Basisfall

1:24:50 Halbrekursive Implementierung

09 |

0:00:00 Starten

0:00:24 Rückblick

0:06:17 Kollisionen

0:11:06 Analyse für zufällige Hash-Funktionen

0:21:54 Universelles Hashing

0:34:35 Beweis Theorem

0:42:08 Hashing mit linearer Suche(""linear probing"")

0:45:08 Der einfache Teil

0:51:03 Remove

1:01:36 Verketten vs. Lineare Suche

1:06:46 Kryptographische Hashfunktionen

1:10:29 Sotieren und Co

1:13:20 Lochkartensortierer

1:19:10 Einfache Sortieralgorithmen

1:21:52 Sentinels am Beispiel Sotieren durch Einfügen

1:24:47 Analyse

08 |

0:00:00 Starten

0:00:05 Roadmap

0:01:12 Verkettete Liste

0:02:56 Skip List

0:06:33 Amortisierte Liste

0:09:45 Aggregat Methode

0:11:28 Hotlist

0:13:39 Hotlist Lookup

0:14:42 Hotlist Insert

0:16:25 Hotlist Amortisierung

0:18:07 Hotlist Delete

0:19:55 Hotlist Aufräumen

0:20:50 Hashtabelle

0:22:14 Duplikaterkennung

0:27:57 Bloom Filter

07 |

0:00:00 Start

0:00:09 Rückblick

0:01:47 Rückblick: unbeschränkte Arrays

0:02:37 Rückblick: amortisierte Analyse

0:03:37 Rückblick: Account-Methode

0:13:22 Stapel und Schlange

0:18:42 Stapel: Operationen

0:22:07 Warteschlangen

0:24:24 zyklisches Array

0:31:12 Deque: Double-Ended Queues

0:34:13 Vergleich: Listen - Felder

0:35:48 Vergleich: Operationen

0:45:54 Ausblick: Weitere Repräsentationen von Folgen

0:47:57 Hashing (Streuspeicherung)

0:51:07 Hashtabellen

0:55:44 Exkurs: Konventionen für Elemente

0:56:50 Hashing: Anwendungen

1:04:29 Kollisionen

1:07:20 Kollisionsauflösung

1:08:03 Hashing mit verketteten Listen

1:22:25 Beispiel: Variante des Geburtstagsparadoxon

06 |

0:00:00 Start

0:00:09 Rückblick Vorlesung 13.05

0:02:26 Folgen als Felder und Listen

0:05:06 Folgen

0:05:09 Ausblick: Komplexität typischer Operationen

0:05:39 Verkettete Listen

0:05:54 Listenglieder (Items)

0:09:22 Trick: Dummy Header

0:10:49 Die Listenklasse

0:16:07 Splice-Operation

0:24:24 Splice: Beispiel

0:25:31 Weitere Operationen: Einfach mit splice

0:27:52 Doch nicht so einfach? Speicherverwaltung!

0:31:14 Items löschen

0:32:49 Elemente einfügen

0:35:47 Ganze Listen manipulieren

0:39:54 Suchen

0:40:33 Ganze Listen manipulieren

0:42:55 Suchen

0:47:19 Funktionalität vs. Effizienz

0:51:24 Einfach verkettete Listen

0:52:44 Einfach verkettete Listen: Invariante?

0:53:59 Einfach verkettete Listen: splice

0:56:55 Einfach verkettete Listen: pushBack

0:59:23 Listen: Zusammenfassung

1:01:50 Felder (Arrays)

1:04:33 Unbeschränkte Felder

1:08:02 Unbeschränkte Felder: Grundidee

1:11:33 Unbeschränkte Felder mit teilweise ungenutztem Speicher

1:15:42 Unbeschränkte Felder: Vergrößern

1:20:08 Unbeschränkte Felder: Verkleinern

1:20:59 Amortisierte Komplexität für unbeschränkte Felder

1:23:40 Beweis: Account-Methode (Konto-Methode)

1:27:57 Amortisierte Analyse: verallgemeinert

05 |

0:00:00 Start

0:00:05 Rückblick Vorlesung 06.05.

0:02:49 Laufzeitanalyse / Rekurrenzen

0:11:03 Eine Rekurrenz für Teile und Herrsche

0:15:43 Master Theorem (einfache Form)

0:20:13 Beweisskizze: Allgemeines

0:25:10 Beweisskizze Fall d