Kapitel 5: Sortieren
Sortieren ist ein grundlegendes algorithmische Problem, das für viele komplexere Aufgaben benötigt wird. Zugleich bieten die zugehörigen Methoden und Prinzipien einen Einstieg in zahlreiche weiterführende Themen.
Vorlesung 17
- Datum: Mittwoch, 08.01.2020
- Inhalt: Aufgabenstellung; Mergesort; Laufzeit
- Folien: HIER
- Notizen: HIER
- Literatur:
Goodrich/Tamassia - Data Structures and Algorithms in Java
Elektronische Ausgabe der 4.Auflage; hier: Kapitel 11.1, Seiten 678ff.
- Weitere Links:
Wikipedia über Mergesort
Merge Sört bei Idea Instructions
Große Übung 4
- Datum: Donnerstag, 09.01.2020
- Inhalt: AVL-Bäume, Sortieren mit Heaps
- Folien: HIER
Vorlesung 18
- Datum: Dienstag, 14.01.2020
- Inhalt: Schranken; Behandeln von Rekursionen
- Notizen: HIER
- Weitere Links:
Wikipedia über Wägeprobleme (engl.)
Wikipedia über Entscheidungsbäme
Ein Kapitel von Jeff Erickson über untere Schranken
Wikipedia über Sortierverfahren (mit einem Beweis der unteren Schranke)
Recursion (englisch, länger)
Rekursionen (deutsch)
Generating Functions (englisch, länger)
Erzeugende Funktionen (deutsch)
Vorlesung 19
- Datum: Mittwoch, 15.01.2020
- Inhalt: Erzeugende Funktionen, Master-Theorem
- Notizen: HIER
- Weitere Links:
Master Theorem (engl.)
Master-Theorem (deutsch)
(Die dort besprochenen Versionen sind spezieller als in der Vorlesung!)
Vorlesung 20
- Datum: Dienstag, 21.01.2020
- Inhalt: Nichtlineare Rekursionen
- Folien: HIER
- Quiz: HIER
- Weitere Links:
Wikipedia über "Die Grenzen des Wachstums"
Diskrete logistische Iterationen
Mehr dazu (mit Animationen) bei Wolfram
The Mandelbrot Set (engl.)
Das gezeigte Mandelbrot-Video
Noch ein Mandelbrot-Video
Und noch ein Mandelbrot-Video
Lineare, nichtlineare Rekursionen, Zahlentheorie und die Mandelbrotmenge
How long is the coast line of Britain?
Wikipedia über Fraktale
Wikipedia on Fractals (engl.)
Life in Life: Game of Life simuliert sich selbst
Epic Game of Life (mit epischer Musik, wie sich's gehört)
Eine kontinuierliche Variante
xkcd #195!
Vorlesung 21
- Datum: Mittwoch, 22.01.2020
- Inhalt: Quicksort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Quicksort
Kvick Sört bei Idea Instructions
Große Übung 5
- Datum: Donnerstag, 23.01.2020
- Inhalt: Mergesort, Master-Theorem, andere Sortierverfahren
- Notizen: HIER
Vorlesung 22
- Datum: Dienstag, 28.01.2020
- Inhalt: Mediane
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Mediane
Wikipedia über Medianberechnung (englisch, aber lohnend)
Eine sehr detaillierte Darstellung des Median-Agorithmus
Vorlesung 23
- Datum: Mittwoch, 29.01.2020
- Inhalt: Sortieren in linearer Zeit
- Notizen: HIER
Vorlesung 24
- Datum: Dienstag, 04.02.2020
- Inhalt: Paralleles Sortieren, diverse Videos und Toneffekte
- Quiz: HIER
- Notizen: HIER
- Diverse Links:
- Visualisierung einiger Sortierverfahren
- Bubblesort als ungarischer Volkstanz
- Mergesort als ungarischer Volkstanz
- Quicksort als ungarischer Volkstanz (Man beachte, dass die Vertauschungen und Pointerabfolge eine gleichwertige Variation dessen sind, was in der Vorlesung besprochen wurde.)
- The Sound of Sorting
- The Sound of Quicksort
- Roboterduell zwischen Quicksort und Bubblesort
- "What's the best way to sort 1 million 32-bit integers?" - Barack Obama antwortet...
- Bogosort bei IDEA instructions
- Bogosort
- Bogosort (engl.)
- Coordinated Motion Planning (Forschungsvideo)
- Visualisierung einiger Sortierverfahren
Vorlesung 25
- Datum: Mittwoch, 05.02.2020
- Inhalt: Hinweise zur Klausur, Vorbereitung, Ask Aything
Große Übung 6
- Datum: Donnerstag, 06.02.2020
- Inhalt: Quicksort, Mediane, kd-Trees, Quiz
- Folien: HIER
- Quiz: HIER
- Weitere Links:
Mehr zu kd-Trees