Week: Vorlesungsfolien | WS20: Algorithmen und Datenstrukturen

Weekly outline

Foren
- Ankündigungen Forum
  
  Forum
  
  Not available unless: Your Last name is not empty
- Diskussionsforum
  
  Forum
  
  Not available unless: Your Last name is not empty

Vorlesungsfolien
Die erste Vorlesung am Di, 3.11., 10:15–11:45 Uhr, findet per Zoom in diesem Zeitraum statt. Der Link geht Ihnen kurz vorher per Email zu, wenn Sie sich in diesen Kurs eingetragen haben. Klicken Sie dazu auf das Zahnrad oben links auf dieser Seite und wählen Sie die Option "Mich in diesen Kurs einschreiben".

Für alle weiteren Vorlesungen wird es nach aktueller Planung Videos geben, die man sich spätestens zum jeweiligen Vorlesungstermin anschauen kann. Die Übungen werden immer auf den Vorlesungen der aktuellen Woche (oder älterem Stoff) aufbauen.

Dem Chat zur Vorlesung könnt ihr unter https://chat.uni-wuerzburg.de/invite/usFr7Q beitreten.
- 00. Vorlesung (03.11.2020): Organisatorisches (3.11., 12:30: Chat-Adresse korrigiert) File
  
  File
- 00. Vorlesung (03.11.2020): Druckversion File
  
  File
- 00. Vorlesung (03.11.2020): Video (Zoom-Mitschnitt) Page
  
  Page
  
  Not available unless: Your Last name is not empty
- 01. Vorlesung (03.11.2020): Sortieren I File
  
  File
- 01. Vorlesung (03.11.2020): Druckversion File
  
  File
- 01. Vorlesung (03.11.2020): Video I – InsertionSort, 24' File
  
  File
  
  Not available unless: Your Last name is not empty
- 01. Vorlesung (03.11.2020): Video II – Korrektheitsbeweis für die Berechnung der Fakultät, 11' File
  
  File
  
  Not available unless: Your Last name is not empty
- 02. Vorlesung (05.11.2020): Sortieren II (MergeSort) File
  
  File
- 02. Vorlesung (05.11.2020): Druckversion File
  
  File
- 02. Vorlesung (05.11.2020): Video I – MergeSort Pseudocode & Beispiel, 18' File
  
  File
  
  Not available unless: Your Last name is not empty
- 02. Vorlesung (05.11.2020): Video II – Korrektheit von Merge & MergeSort, 16' File
  
  File
  
  Not available unless: Your Last name is not empty
- 03. Vorlesung (10.11.2020): Laufzeitanalyse File
  
  File
- 03. Vorlesung (10.11.2020): Druckversion File
  
  File
- 03. Vorlesung (10.11.2020): Video I – Vergleich InsertionSort und MergeSort, 18' (sorry, habe in der zweiten Hälfte des Videos vergessen, das Gitter abzuschalten) File
  
  File
  
  Not available unless: Your Last name is not empty
- 03. Vorlesung (10.11.2020): Video II – Klassifikationsschema für Funktionen, 12' (kennt jedeR InformatikerIn!) File
  
  File
  
  Not available unless: Your Last name is not empty
- 04. Vorlesung (12.11.2020): Laufzeitanalyse am Beispiel File
  
  File
- 04. Vorlesung (12.11.2020): Druckversion File
  
  File
- 04. Vorlesung (12.11.2020): Video I – Kubischer Algorithmus für MaxSum, 15' File
  
  File
  
  Not available unless: Your Last name is not empty
- 04. Vorlesung (12.11.2020): Video II – Schnellere Algorithmen, 22' File
  
  File
  
  Not available unless: Your Last name is not empty
- 05. Vorlesung (17.11.2020): Rekursionsgleichungen lösen File
  
  File
- 05. Vorlesung (17.11.2020): Druckversion File
  
  File
- 05. Vorlesung (17.11.2020): Video I – Substitutionsmethode, 10' File
  
  File
  
  Not available unless: Your Last name is not empty
- 05. Vorlesung (17.11.2020): Video II – Rekursionsbaummethode, 10' File
  
  File
  
  Not available unless: Your Last name is not empty
- 05. Vorlesung (17.11.2020): Video III – Meistermethode, 10' File
  
  File
  
  Not available unless: Your Last name is not empty
- 06. Vorlesung (19.11.2020): Prioritätsschlangen, Heaps und HeapSort File
  
  File
- 06. Vorlesung (19.11.2020): Druckversion File
  
  File
- 06. Vorlesung (19.11.2020): Video I – Prioritätsschlange, MaxHeapify, BuildMaxHeap, 23' File
  
  File
  
  Not available unless: Your Last name is not empty
- 06. Vorlesung (19.11.2020): Video II – HeapSort, 12' File
  
  File
  
  Not available unless: Your Last name is not empty
- 07. Vorlesung (24.11.2020): Zufallsexperimente [Korrektur: Der 1. Zwischentest ist am 10.12. von 8:30–10:00 Uhr!] File
  
  File
- 07. Vorlesung (24.11.2020): Druckversion File
  
  File
- 07. Vorlesung (24.11.2020): Video I – Gedankenexperiment, 17' File
  
  File
  
  Not available unless: Your Last name is not empty
- 07. Vorlesung (24.11.2020): Video II – Avarage-Case-Laufzeit von InsertionSort, 11' File
  
  File
  
  Not available unless: Your Last name is not empty
- 07. Vorlesung (24.11.2020): Video III – Geburtstagsparadoxon & Bonustrack, 7' File
  
  File
  
  Not available unless: Your Last name is not empty
- 08. Vorlesung (26.11.2020): QuickSort und RandomizedQuickSort File
  
  File
- 08. Vorlesung (26.11.2020): Druckversion File
  
  File
- 08. Vorlesung (26.11.2020): Video I – (Deterministisches) QuickSort; Beispiel, Best- und Worst-Case-Laufzeit, 16' File
  
  File
  
  Not available unless: Your Last name is not empty
- 08. Vorlesung (26.11.2020): Video II – Erwartete Laufzeit von Randomized QuickSort, 19' File
  
  File
  
  Not available unless: Your Last name is not empty
- 09. Vorlesung (01.12.2020): Sortieren in Linearzeit File
  
  File
- 09. Vorlesung (01.12.2020): Druckversion File
  
  File
- 09. Vorlesung (01.12.2020): Video I – Untere Schranke für vergleichsbasierte Sortierverfahren, 13' File
  
  File
  
  Not available unless: Your Last name is not empty
- 09. Vorlesung (01.12.2020): Video II – CountingSort, 10' File
  
  File
  
  Not available unless: Your Last name is not empty
- 09. Vorlesung (01.12.2020): Video III – RadixSort, 7' File
  
  File
  
  Not available unless: Your Last name is not empty
- 09. Vorlesung (01.12.2020): Video IV – BucketSort, 14' File
  
  File
  
  Not available unless: Your Last name is not empty
- 10. Vorlesung (03.12.2020): Das Auswahlproblem File
  
  File
- 10. Vorlesung (03.12.2020): Druckversion File
  
  File
- 10. Vorlesung (03.12.2020): Video I – RandomizedSelect, 23' File
  
  File
  
  Not available unless: Your Last name is not empty
- 10. Vorlesung (03.12.2020): Video II – deterministisches Select, 15' File
  
  File
  
  Not available unless: Your Last name is not empty
- 11. Vorlesung (08.12.2020): Elementare Datenstrukturen File
  
  File
- 11. Vorlesung (08.12.2020): Druckversion File
  
  File
- 11. Vorlesung (08.12.2020): Video I – Abstrakter Datentyp: Dynamische Menge, 8' File
  
  File
  
  Not available unless: Your Last name is not empty
- 11. Vorlesung (08.12.2020): Video II – Stapel + Schlange + Liste, 10' File
  
  File
  
  Not available unless: Your Last name is not empty
- 11. Vorlesung (08.12.2020): Video III – Von Pseudocode zu Javacode: Die Liste, 8' File
  
  File
  
  Not available unless: Your Last name is not empty
- 12. Vorlesung (15.12.2020): Hashing File
  
  File
- 12. Vorlesung (15.12.2020): Druckversion File
  
  File
- 12. Vorlesung (15.12.2020): Video I – direkte Adressierung und Hashing mit Verkettung, 22' File
  
  File
  
  Not available unless: Your Last name is not empty
- 12. Vorlesung (15.12.2020): Video II – gute Hashfunktionen und Hashing mit offener Adressierung, 23' File
  
  File
  
  Not available unless: Your Last name is not empty
- 13. Vorlesung (17.12.2020): Binäre Suchbäume File
  
  File
- 13. Vorlesung (17.12.2020): Druckversion File
  
  File
- 13. Vorlesung (17.12.2020): Video I – Binäre Suchbäume: Vorarbeiten und Traversierung, 21' File
  
  File
  
  Not available unless: Your Last name is not empty
- 13. Vorlesung (17.12.2020): Video II – Methoden der binären Suchbäume, 15' File
  
  File
  
  Not available unless: Your Last name is not empty
- 14. Vorlesung (22.12.2020): Nächstes Paar File
  
  File
- 14. Vorlesung (22.12.2020): Druckversion File
  
  File
- 15. Vorlesung (07.01.2021): Rot-Schwarz-Bäume File
  
  File
- 15. Vorlesung (07.01.2021): Druckversion File
  
  File
- 15. Vorlesung (07.01.2021): Video I – Logarithmische Höhe, 16' File
  
  File
  
  Not available unless: Your Last name is not empty
- 15. Vorlesung (07.01.2021): Video II – Einfügen in einen Rot-Schwarz-Baum, 16' File
  
  File
  
  Not available unless: Your Last name is not empty
- 16. Vorlesung (12.01.2021): Augmentieren von Datenstrukturen File
  
  File
- 16. Vorlesung (12.01.2021): Druckversion File
  
  File
- 16. Vorlesung (12.01.2021): Video, 28' File
  
  File
  
  Not available unless: Your Last name is not empty
- 17. Vorlesung (14.01.2021): Amortisierte Analyse File
  
  File
- 17. Vorlesung (14.01.2021): Druckversion File
  
  File
- 17. Vorlesung (14.01.2021): Video I – Aggregationsmethode, 9' File
  
  File
  
  Not available unless: Your Last name is not empty
- 17. Vorlesung (14.01.2021): Video II – Buchhaltermethode, 6' File
  
  File
  
  Not available unless: Your Last name is not empty
- 17. Vorlesung (14.01.2021): Video III – Potentialmethode und zwei Übungsaufgaben, 9' File
  
  File
  
  Not available unless: Your Last name is not empty
- 18. Vorlesung (19.01.2021): Graphen: Repräsentation und Breitensuche File
  
  File
- 18. Vorlesung (19.01.2021): Druckversion File
  
  File
- 18. Vorlesung (19.01.2021): Video I – Beispiele und Repräsentation, 16' File
  
  File
  
  Not available unless: Your Last name is not empty
- 18. Vorlesung (19.01.2021): Video II – Breitensuche, 23' File
  
  File
  
  Not available unless: Your Last name is not empty
- 19. Vorlesung (26.01.2021): Kürzeste Wege und Dijkstras Algorithmus File
  
  File
- 19. Vorlesung (26.01.2021): Druckversion File
  
  File
- 19. Vorlesung (26.01.2021): Video I – Dijkstras Algorithmus, 22' File
  
  File
  
  Not available unless: Your Last name is not empty
- 19. Vorlesung (26.01.2021): Video II – Kürzeste Wege und T9, 7' File
  
  File
  
  Not available unless: Your Last name is not empty
- Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959) URL
  
  URL
- Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005 URL
  
  URL
- 20. Vorlesung (28.01.2021): Tiefensuche und topologische Sortierung File
  
  File
- 20. Vorlesung (28.01.2021): Druckversion File
  
  File
- 20. Vorlesung (28.01.2021): Video I – Tiefensuche (Beispiel, Pseudocode, Eigenschaften), 22' File
  
  File
  
  Not available unless: Your Last name is not empty
- 20. Vorlesung (28.01.2021): Video II – Topologisches Sortieren (Anwendung und Korrektheit), 12' File
  
  File
  
  Not available unless: Your Last name is not empty
- 21. Vorlesung (02.02.2021): Minimale Spannbäume File
  
  File
- 21. Vorlesung (02.02.2021): Druckversion File
  
  File
- 21. Vorlesung (02.02.2021): Video I – Generischer Algorithmus und Erweiterungssatz (Korrektheit), 13' File
  
  File
  
  Not available unless: Your Last name is not empty
- 21. Vorlesung (02.02.2021): Video II – Algorithmen von Jarník-Prim und Kruskal, 18' File
  
  File
  
  Not available unless: Your Last name is not empty
- 22. Vorlesung (04.02.2021): Dynamisches Programmieren File
  
  File
- 22. Vorlesung (04.02.2021): Druckversion File
  
  File
- 22. Vorlesung (04.02.2021): Video I – Stabzerlegung, 22' File
  
  File
  
  Not available unless: Your Last name is not empty
- 22. Vorlesung (04.02.2021): Video II – Längste Wege, 8' File
  
  File
  
  Not available unless: Your Last name is not empty
- 23. Vorlesung (09.02.2021): Greedyalgorithmen [08.02., 12:12 Uhr: kleine Korrektur auf Folie 16] File
  
  File
- 23. Vorlesung (09.02.2021): Druckversion File
  
  File
- 23. Vorlesung (09.02.2021): Video I – GA & DP für ein einfaches Problem der Ablaufplanung, 15' File
  
  File
  
  Not available unless: Your Last name is not empty
- 23. Vorlesung (09.02.2021): Video II – GA & DP für ein gewichtetes Problem der Ablaufplanung, 14' File
  
  File
  
  Not available unless: Your Last name is not empty
- 24. Vorlesung (11.02.2021): Das Problem der Handlungsreisenden (TSP: Approximation & DP) File
  
  File
- 24. Vorlesung (11.02.2021): Druckversion File
  
  File
- 24. Vorlesung (11.02.2021): Zoom-Mitschnitt (leider fehlen die ersten 5', sorry!), 59' Page
  
  Page
  
  Not available unless: Your Last name is not empty
- 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
  
  URL

Weekly outline

Foren

Vorlesungsfolien