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 16
- Datum: Dienstag, 08.01.2019
- 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
Vorlesung 17
- Datum: Mittwoch, 09.01.2019
- Inhalt: Schranken; Behandeln von Rekursionen
- Notizen: HIER
- Weitere Links:
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 18
- Datum: Dienstag, 15.01.2019
- Inhalt: Master-Theorem
- Notizen: HIER
- Weitere Links:
Master Theorem (engl.)
Master-Theorem (deutsch)
(Die dort besprochenen Versionen sind spezieller als in der Vorlesung!)
Vorlesung 19
- Datum: Mittwoch, 16.01.2019
- Inhalt: Nichtlineare Rekursionen
- Folien: 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 gehört)
xkcd #195!
Große Übung 6
- Datum: Donnerstag, 17.01.2019
- Inhalt: Mergesort, Master-Theorem, andere Sortierverfahren
- Notizen: HIER
Vorlesung 20
- Datum: Dienstag, 22.01.2019
- Inhalt: Quicksort
- Folien: HIER
- Notizen: HIER
- Weitere Links:
Wikipedia über Quicksort
Kvick Sört bei Idea Instructions
Vorlesung 21
- Datum: Mittwoch, 23.01.2019
- 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 22
- Datum: Dienstag, 29.01.2019
- Inhalt: Sortieren in linearer Zeit
- Notizen: HIER
Vorlesung 23
- Datum: Mittwoch, 30.01.2019
- Inhalt: Analoge Methoden, diverse Videos und Toneffekte, Hinweise für die Klausur, Kapitelzusammenfassung
- Diverse Links:
- Wikipedia über Spaghetti Sort (engl.))
- Ein Video zu Forschungsarbeit über programmierbare Materie
- Artikel dazu: A. Becker, E.D. Demaine, S. P. Fekete, J. Lonsford, R. Morris-Wright. Particle Computation: Complexity, Algorithms, and Logic. To appear in: Natural Computing.
- Ein Vortrag über Analogrechner beim 34C3
- 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...
- Maggie Sort: Einsatz von IsNextLargest() im Nachwuchsbereich!
- Bogosort bei IDEA instructions
- Bogosort
- Bogosort (engl.)
- Diskussion von Quantum Bogosort (engl.)
(Zitat: "Explaining Big-O notation to my girlfriend?! You bastards are trying to ruin my relationship!")
- Slowsort (Nicht ganz ernst gemeinte Sortiervariante)
- Liedtext
- Wikipedia über Spaghetti Sort (engl.))
Große Übung 7
- Datum: Donnerstag, 31.01.2019
- Inhalt: Bubblesort, Odd-Even-Sort, Mediane, kd-Bäume
- Notizen: HIER
- Weitere Links:
Coordinated Motion Planing: The Video
Mehr zu kd-Trees