Section outline

◄Allgemeine Informationen
►Zwischentests
    • Ab sofort finden alle Vorlesungen (mindestens bis Neujahr, wahrscheinlich sogar bis 14.01.22) per Zoom statt. Am Do, 10.02.22 findet keine Vorlesung statt. Nutzen Sie die Zeit für die Vorbereitung auf die Klausur am Mi, 16.02.22 in der Posthalle.
    • 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 (fast) alle 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/AvDQsy beitreten.
    • 00. Vorlesung (19.10.2021): Organisatorisches Файл
    • 00. Vorlesung (19.10.2021): Druckversion Файл
    • 01. Vorlesung (19.10.2021): Sortieren I Файл
    • 01. Vorlesung (19.10.2021): Druckversion Файл
    • 01. Vorlesung (19.10.2021): Video I – InsertionSort, 24' Файл
    • 01. Vorlesung (19.10.2021): Video II – Korrektheitsbeweis für die Berechnung der Fakultät, 11' Файл
    • 02. Vorlesung (21.10.2021): Sortieren II (MergeSort) Файл
    • 02. Vorlesung (21.10.2021): Druckversion Файл
    • 02. Vorlesung (21.10.2021): Video I – MergeSort Pseudocode & Beispiel, 18' Файл
    • 02. Vorlesung (21.10.2021): Video II – Korrektheit von Merge & MergeSort, 16' Файл
    • 03. Vorlesung (26.10.2021): Laufzeitanalyse Файл
    • 03. Vorlesung (26.10.2021): Druckversion Файл
    • 03. Vorlesung (26.10.2021): Video I – Vergleich InsertionSort und MergeSort, 18' (sorry, habe in der zweiten Hälfte des Videos vergessen, das Gitter abzuschalten) Файл
    • 03. Vorlesung (26.10.2021): Video II – Klassifikationsschema für Funktionen, 12' (kennt jedeR InformatikerIn!) Файл
    • 04. Vorlesung (28.10.2021): Laufzeitanalyse am Beispiel Файл
    • 04. Vorlesung (28.10.2021): Druckversion Файл
    • 04. Vorlesung (28.10.2021): Video I – Kubischer Algorithmus für MaxSum, 15' Файл
    • 04. Vorlesung (28.10.2021): Video II – Schnellere Algorithmen, 22' Файл
    • 05. Vorlesung (02.11.2021): Rekursionsgleichungen lösen Файл
    • 05. Vorlesung (02.11.2021): Druckversion Файл
    • 05. Vorlesung (02.11.2021): Video I – Substitutionsmethode, 10' Файл
    • 05. Vorlesung (02.11.2021): Video II – Rekursionsbaummethode, 10' Файл
    • 05. Vorlesung (02.11.2021): Video III – Meistermethode, 10' Файл
    • 06. Vorlesung (04.11.2021): Prioritätsschlangen, Heaps und HeapSort Файл
    • 06. Vorlesung (04.11.2021): Druckversion Файл
    • 06. Vorlesung (04.11.2021): Video I – Prioritätsschlange, MaxHeapify, BuildMaxHeap, 23' Файл
    • 06. Vorlesung (04.11.2021): Video II – HeapSort, 12' Файл
    • 07. Vorlesung (09.11.2021): Zufallsexperimente [09.11., 12:10: kleine Änderungen, besonders rot-grün vermieden] Файл
    • 07. Vorlesung (09.11.2021): Druckversion Файл
    • 07. Vorlesung (09.11.2021): Video I – Gedankenexperiment, 17' Файл
    • 07. Vorlesung (09.11.2021): Video II – Avarage-Case-Laufzeit von InsertionSort, 11' Файл
    • 07. Vorlesung (09.11.2021): Video III – Geburtstagsparadoxon & Bonustrack, 7' Файл
    • 08. Vorlesung (11.11.2021): QuickSort und RandomizedQuickSort Файл
    • 08. Vorlesung (11.11.2021): Druckversion Файл
    • 08. Vorlesung (11.11.2021): Video I – (Deterministisches) QuickSort; Beispiel, Best- und Worst-Case-Laufzeit, 16' Файл
    • 08. Vorlesung (11.11.2021): Video II – Erwartete Laufzeit von Randomized QuickSort, 19' Файл
    • 09. Vorlesung (16.11.2021): Sortieren in Linearzeit Файл
    • 09. Vorlesung (16.11.2021): Druckversion Файл
    • 09. Vorlesung (16.11.2021): Video I – Untere Schranke für vergleichsbasierte Sortierverfahren, 13' Файл
    • 09. Vorlesung (16.11.2021): Video II – CountingSort, 10' Файл
    • 09. Vorlesung (16.11.2021): Video III – RadixSort, 7' Файл
    • 09. Vorlesung (16.11.2021): Video IV – BucketSort, 14' Файл
    • 10. Vorlesung (23.11.2021): Das Auswahlproblem Файл
    • 10. Vorlesung (23.11.2021): Druckversion Файл
    • 10. Vorlesung (23.11.2021): Video I – RandomizedSelect, 23' Файл
    • 10. Vorlesung (23.11.2021): Video II – deterministisches Select, 15' Файл
    • 11. Vorlesung (25.11.2021): Elementare Datenstrukturen Файл
    • 11. Vorlesung (25.11.2021): Druckversion Файл
    • 11. Vorlesung (25.11.2021): Video I – Abstrakter Datentyp: Dynamische Menge, 8' Файл
    • 11. Vorlesung (25.11.2021): Video II – Stapel + Schlange + Liste, 10' Файл
    • 11. Vorlesung (25.11.2021): Video III – Von Pseudocode zu Javacode: Die Liste, 8' Файл
    • 12. Vorlesung (30.11.2021): Hashing [kleine Änderungen am 30.11., z.B. alle Tabellen v.u.n.o. nummeriert] Файл
    • 12. Vorlesung (30.11.2021): Druckversion Файл
    • 12. Vorlesung (30.11.2021): Video I – direkte Adressierung und Hashing mit Verkettung, 22' Файл
    • 12. Vorlesung (30.11.2021): Video II – gute Hashfunktionen und Hashing mit offener Adressierung, 23' Файл
    • 13. Vorlesung (02.12.2021): Binäre Suchbäume Файл
    • 13. Vorlesung (02.12.2021): Druckversion Файл
    • 13. Vorlesung (02.12.2021): Video I – Binäre Suchbäume: Vorarbeiten und Traversierung, 21' Файл
    • 13. Vorlesung (02.12.2021): Video II – Methoden der binären Suchbäume, 15' Файл
    • 14. Vorlesung (07.12.2021): Rot-Schwarz-Bäume Файл
    • 14. Vorlesung (07.12.2021): Druckversion Файл
    • 14. Vorlesung (07.12.2021): Video I – Logarithmische Höhe, 16' Файл
    • 14. Vorlesung (07.12.2021): Video II – Einfügen in einen Rot-Schwarz-Baum, 16' Файл
    • 15. Vorlesung (09.12.2021): Augmentieren von Datenstrukturen [Monat des 2. Zwischentests von Nov. auf Dez. korrigiert] Файл
    • 15. Vorlesung (09.12.2021): Druckversion Файл
    • 15. Vorlesung (09.12.2021): Video, Augmentieren (komplett), 28' Файл
    • 16. Vorlesung (14.12.2022): Amortisierte Analyse Файл
    • 16. Vorlesung (14.12.2022): Druckversion Файл
    • 16. Vorlesung (14.12.2022): Video I – Aggregationsmethode, 9' Файл
    • 16. Vorlesung (14.12.2022): Video II – Buchhaltermethode, 6' Файл
    • 16. Vorlesung (14.12.2022): Video III – Potentialmethode und zwei Übungsaufgaben, 9' Файл
    • 17. Vorlesung (21.12.2021): Nächstes Paar Файл
    • 17. Vorlesung (21.12.2021): Druckversion Файл

    • 17. Vorlesung (21.12.2021): Leider gibt es zu dieser Vorlesung kein Video :-(
      Am Do, 23.12.2021 findet keine Vorlesung statt!

    • 18. Vorlesung (11.01.2022): Graphen: Repräsentation und Breitensuche Файл
    • 18. Vorlesung (11.01.2022): Druckversion Файл
    • 18. Vorlesung (11.01.2022): Video I – Beispiele und Repräsentation, 16' Файл
    • 18. Vorlesung (11.01.2022): Video II – Breitensuche, 23' Файл
    • 19. Vorlesung (13.01.2022): Kürzeste Wege und Dijkstras Algorithmus Файл
    • 19. Vorlesung (13.01.2022): Druckversion Файл
    • 19. Vorlesung (13.01.2022): Video I – Dijkstras Algorithmus, 22' Файл
    • 19. Vorlesung (13.01.2022): Video II – Kürzeste Wege und T9, 7' Файл
    • Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959) Гиперссылка
    • Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005 Гиперссылка
    • 20. Vorlesung (18.01.2022): Tiefensuche und topologische Sortierung Файл
    • 20. Vorlesung (18.01.2022): Druckversion Файл
    • 20. Vorlesung (18.01.2022): Video I – Tiefensuche (Beispiel, Pseudocode, Eigenschaften), 22' Файл
    • 20. Vorlesung (18.01.2022): Video II – Topologisches Sortieren (Anwendung und Korrektheit), 12' Файл
    • 21. Vorlesung (25.01.2022): Minimale Spannbäume [25.1. – historische Notiz: auch Dijkstra hat den Alg. von Jarník-Prim entdeckt – 1959 :-) ] Файл
    • 21. Vorlesung (25.01.2022): Druckversion Файл
    • 21. Vorlesung (25.01.2022): Video I – Generischer Algorithmus und Erweiterungssatz (Korrektheit), 13' Файл
    • 21. Vorlesung (25.01.2022): Video II – Algorithmen von Jarník-Prim und Kruskal, 18' Файл
    • 22. Vorlesung (27.01.2022): Dynamisches Programmieren Файл
    • 22. Vorlesung (27.01.2022): Druckversion Файл
    • 22. Vorlesung (27.01.2022): Video I – Stabzerlegung, 22' Файл
    • 22. Vorlesung (27.01.2022): Video II – Längste Wege, 8' Файл
    • 23. Vorlesung (31.01.2022): Greedyalgorithmen [01.02., 12:00 Uhr – winzige Änderung: e_0 -> e[0] Файл
    • 23. Vorlesung (31.01.2022): Druckversion Файл
    • 23. Vorlesung (31.01.2022): Video I – GA & DP für ein einfaches Problem der Ablaufplanung, 15' Файл
    • 23. Vorlesung (31.01.2022): Video II – GA & DP für ein gewichtetes Problem der Ablaufplanung, 14' Файл
    • 24. Vorlesung (03.02.2022): Das Problem der Handlungsreisenden (TSP: Approximation & DP) Файл
    • 24. Vorlesung (03.02.2022): Druckversion Файл
    • 24. Vorlesung (03.02.2022): Zoom-Live-Mitschnitt vom WS 2021 (leider fehlen die ersten 5', sorry!), 59' Страница
    • William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012) – Schon die Einleitung ist sehr lesenswert! Гиперссылка
    • 25. Vorlesung (08.02.2022): Leichte Kreise (DP) [nach der VL: letzte Folie: k=1 to n statt n-1] Файл
    • 25. Vorlesung (08.02.2022): Druckversion Файл

    • Für heute (08.02.2022) gibt es leider kein Video! Dies was die letzte Vorlesung in diesem Semester. Sorry für die technischen Probleme am Anfang.

◄Allgemeine Informationen
►Zwischentests