Skip to main content
Side panel
More
English (en)
Català (ca)
Deutsch (de)
Deutsch (du) (de_du)
English (en)
Español - Internacional (es)
Français (fr)
Italiano (it)
Português - Portugal (pt)
Svenska (sv)
Türkçe (tr)
Русский (ru)
العربية (ar)
You are currently using guest access
Log in
Open course index
Home
WS19_ADS
Vorlesungsfolien
25. Vorlesung (30.01.2020): Karps Algorithmus zur Berechnung leichter Kreise
25. Vorlesung (30.01.2020): Karps Algorithmus zur Berechnung leichter Kreise
Click
ads-ws19-vl25-leichte-kreise.pdf
link to view the file.
◄ William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012)
Jump to...
Jump to...
Ankündigungen
Klausurbonus
Kenntnisnahme und Einhaltung der Covid-19 Infektionsschutzmaßnahmen zur Teilnahme an einer schriftlichen oder mündlichen Prüfung in Präsenz
Allgemeine Informationen WS 2019/20 (Letztes Update: 10.02.2020, Bonus Nachklausur)
Wer nicht kommt, verliert! (Die ZEIT, 26.11.2015)
01. Vorlesung (15.10.2019): Organisatorisches
01. Vorlesung (15.10.2019): Druckversion
01. Vorlesung (15.10.2019): Sortieren I (InsertionSort) – 17.10.: kleiner Zusatz bei Factorial(k)
01. Vorlesung (15.10.2019): Druckversion (Sortieren I)
02. Vorlesung (17.10.2019): Sortieren II (MergeSort)
02. Vorlesung (17.10.2019): Druckversion
03. Vorlesung (22.10.2019): Groß-Oh-Notation
03. Vorlesung (22.10.2019): Druckversion
04. Vorlesung (24.10.2019): Laufzeitanalyse [8.11.: Folie 8: Zeilenumbruch verbessert]
04. Vorlesung (24.10.2019): Druckversion
05. Vorlesung (29.10.2019): Lösen von Rekursionsgleichungen
05. Vorlesung (29.10.2019): Druckversion
06. Vorlesung (31.10.2019): Prioritätsschlangen und HeapSort [05.11.19: ein paar ganz kleine Korrekturen]
06. Vorlesung (31.10.2019): Druckversion
07. Vorlesung (05.11.2019): Zufallsexperiment, erwartete Laufzeit von InsertionSort, Geburtstagsparadoxon [14.11.: Umfang 1. Zwischentest korrigiert]]
07. Vorlesung (05.11.2019): Druckversion
08. Vorlesung (07.11.2019): (Randomized) QuickSort
08. Vorlesung (07.11.2019): Druckversion
09. Vorlesung (12.11.2019): Untere Schranke für vergleichsbasierte Sortierverfahren, Linearzeit-Sortieralgorithmen
09. Vorlesung (12.11.2019): Druckversion
10. Vorlesung (14.11.2019): Auswahlproblem (Median)
10. Vorlesung (14.11.2019): Druckversion
11. Vorlesung (19.11.2019): Elementare Datenstrukturen (Stapel, Liste, Schlange)
11. Vorlesung (19.11.2019): Druckversion
12. Vorlesung (26.11.2019): Hashing
12. Vorlesung (26.11.2019): Druckversion
13. Vorlesung (28.11.2019): Binäre Suchbäume
13. Vorlesung (28.11.2019): Druckversion
14. Vorlesung (03.12.2019): Rot-Schwarz-Bäume
14. Vorlesung (03.12.2019): Druckversion
15. Vorlesung (05.12.2019): Augmentieren von Datenstrukturen
15. Vorlesung (05.12.2019): Druckversion
16. Vorlesung (10.12.2019): Amortisierte Analyse
16. Vorlesung (10.12.2019): Druckversion
17. Vorlesung (12.12.2019): Nächstes Paar (Teile und Herrsche)
17. Vorlesung (12.12.2019): Druckversion
18. Vorlesung (17.12.2019): Graphen, Breitensuche
18. Vorlesung (17.12.2019): Druckversion
19. Vorlesung (07.01.2020): Kürzeste Wege und Dijkstras Algorithmus
19. Vorlesung (07.01.2020): Druckversion
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 (09.01.2020): Tiefensuche und topologische Sortierung
20. Vorlesung (09.01.2020): Druckversion
21. Vorlesung (14.01.2020): Minimale Spannbäume (Jarník-Prim, Kruskal)
21. Vorlesung (14.01.2020): Druckversion
22. Vorlesung (16.01.2020): Dynamische Programmierung
22. Vorlesung (16.01.2020): Druckversion
23. Vorlesung (21.01.2020): Greedy- und Approximationsalgorithmen
23. Vorlesung (21.01.2020): Druckversion
24. Vorlesung (28.01.2020): TSP – Approximation und exakte Lösung
24. Vorlesung (28.01.2020): Druckversion
William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012)
25. Vorlesung (30.01.2020): Druckversion
Karps Originalartikel "A characterization of the minimum cycle mean in a digraph" (nur drei Seiten!)
Probeklausur
Anleitung zur Bearbeitung von Programmieraufgaben
0. Übungsblatt (Abgabe bis 17.10.2019)
1. Übungsblatt (Abgabe bis 24.10.2019)
2. Übungsblatt (Abgabe bis 31.10.2019)
3. Übungsblatt (Abgabe bis 07.11.2019)
4. Übungsblatt (Abgabe bis 14.11.2019)
1. Präsenzübung (für 19./20.11.2019)
5. Übungsblatt (Abgabe bis 28.11.2019)
6. Übungsblatt (Abgabe bis 05.12.2019)
7. Übungsblatt (Abgabe 12.12.2019)
2. Präsenzübung (für 17./18.12.2019)
8. Übungsblatt (Abgabe bis 09.01.2020) [Update Aufgabe 3]
9. Übungsblatt (Abgabe bis 16.01.2020)
3. Präsenzübung (für 21./22.01.2020)
10. Übungsblatt (Abgabe bis 30.01.2020)
4. Präsenzübung (für 4.2./5.2.2020)
Tag 1
Tag 2
Tag 3
Tag 4
Tag 5
Quiz 0 (Konvergenz, Pseudocode)
Quiz 1 (InsertionSort, Schleifeninvariante)
Quiz 2 (Laufzeitklassifikation, Merge)
Quiz 3 (InsertionSort, MergeSort, Laufzeitklassifikation)
Quiz 4 (Laufzeiten, Heaps)
Quiz 5 (Meistermethode, Heaps)
Quiz 6 (Partition, RadixSort, Stabilität)
Quiz 7 (Partition, RadixSort, InSitu)
Quiz 8 (Hashing, Binärbäume)
Quiz 9 (Hashing, Binäre Suche)
Quiz 10 (Rot-Schwarz Bäume)
Quiz 11 (Rot-Schwarz-Bäume, Tiefensuche)
Quiz 12 (Spannbäume, Prim & Kruskal)
25. Vorlesung (30.01.2020): Druckversion ►