Kurs: WS22: Algorithmen und Datenstrukturen, Vecka: Vorlesungsfolien

Section outline

Um sich in diesen Kurs einzuschreiben, klicken Sie auf das Zahnrad oben links auf dieser Seite und wählen Sie die Option "Mich in diesen Kurs einschreiben".
Für die meisten Vorlesungen wird es Videos geben, die man sich spätestens zum jeweiligen Vorlesungstermin anschauen kann.
Dem Chat zur Vorlesung können Sie unter https://chat.uni-wuerzburg.de/invite/TZFubc beitreten.
In der Tabelle unten liefert ein Klick aufs jeweilige Datum die Kurz-/Druckversion der Folien; ein Klick aufs Thema die Langversion.

Datum	Thema	Videos (alt!)
18.10.2022	Organisation und Einführung
18.10.2022	Sortieren I (InsertionSort)	Inkrementeller Algorithmus (24') – Fakultät (11')
20.10.2022	Sortieren II (MergeSort)	Pseudocode + Beispiel (18') – Korrektheit (16')
25.10.2022	Laufzeitanalyse, Groß-Oh-Notation	Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12')
27.10.2022	Laufzeitanalyse am Beispiel	Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22')
03.11.2022	Rekursionsgleichungen lösen	Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10')
08.11.2022	Prioritätsschlangen, Heaps, HeapSort	Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12')
10.11.2022	Zufallsexperimente	Gedankenexperiment (17') – Avagege-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7')
15.11.2022	QuickSort und RandomizedQuickSort	(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19')
22.11.2022	Sortieren in Linearzeit	Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14')
24.11.2022	Das Auswahlproblem	Randomisiertes Select (23') – Deterministisches Select (15')
29.11.2022	Elementare Datenstrukturen	Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8')
01.12.2022	Hashing	direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23')
06.12.2022	Binäre Suchbäume	Vorarbeiten und Traversierung (21') – Methoden (15')
08.12.2022	entfällt!	–
13.12.2022	Rot-Schwarz-Bäume [12.01.: Anmerkung zu RBTransplant]	Logarithmische Höhe (16') – Einfüge-Operation (16')
20.12.2022	Datenstrukturen augmentieren	Augmentieren – komplett (28')
22.12.2022	Nächstes Paar	Leider gibt's für diese Vorlesung kein Video :-(
10.01.2023	Amortisierte Analyse	Aggregationsmethode (9') – Buchhaltermethode (6') – Potentialmethode (9')
12.01.2023	Graphen: Repräsentation und Breitensuche	Beispiele und Repräsentation (16') – Breitensuche (23')
17.01.2023	Kürzeste Wege und Dijkstras Algorithmus	Dijkstras Algorithmus (22') – Kürzeste Wege und T9 (7')
24.01.2023	Tiefensuche und topologische Sortierung	Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') – Topologische Sortierung (Anwendung, Korrektheit) (12')
26.01.2023	Minimale Spannbäume	Generischer Algorithmus und Korrektheit (13') – Algorithmen von Jarník–Prim(–Dijkstra) und von Kruskal (18')
31.01.2023	Dynamisches Programmieren	Stabzerlegung (22') – Längste Wege (8')
02.02.2023	Greedy-Algorithmen	Ein einfaches Problem der Ablaufplanung (15') – Ein gewichtetes Problem der Ablaufplanung (14')
07.02.2023	entfällt wegen GADS-Klausur!	–
09.02.2023	Problem des Handlungsreisenden	Vorlesungsmitschnitt vom WS 2021, leider ohne die ersten 5' (59')

Välj aktivitet Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959)

Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959) URL
Välj aktivitet Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005

Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005 URL
Välj aktivitet William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012) – Schon die Einleitung ist sehr lesenswert!

William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012) – Schon die Einleitung ist sehr lesenswert! URL

Felix Klesen

Alexander Wolff

Section outline