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.
Termine:
- Vorlesung 17 am 13.01.21 (11:30 Uhr): Aufgabenstellung, Mergesort
- Vorlesung 18 am 19.01.21 (09:45 Uhr): Behandeln von Rekursionen
- Vorlesung 19 am 20.01.21 (11:30 Uhr): Erzeugende Funktionen, Master-Theorem
- Übung 6 am 21.01.21 (11:30 Uhr): Mergesort, Master-Theorem, andere Sortierverfahren
- Vorlesung 20 am 26.01.21 (09:45 Uhr): Nichtlineare Rekursionen
- Vorlesung 21 am 27.01.21 (11:30 Uhr): Quicksort
- Vorlesung 22 am 02.02.21 (09:45 Uhr): Mediane
- Vorlesung 23 am 03.02.21 (11:30 Uhr): Sortieren in linearer Zeit
- Übung 7 am 04.02.21 (11:30 Uhr): Quicksort, Mediane
- Vorlesung 24 am 09.02.21 (09:45 Uhr): Paralleles Sortieren
- Vorlesung 25 am 10.02.21 (11:30 Uhr): Zusammenfassung
- Übung 8 am 11.02.21 (11:30 Uhr): Fragestunde, Quiz
Stream: [YouTube], Chat: [Discord]
Vorlesungen
-
Übung 8Die letzte große Übung von AuD mit Spiel, Spaß, Spannung und vielen Fragen.
-
Vorlesung 25Diese Vorlesung markiert das Ende der Vorlesungszeit. Es werden noch einmal einige Hinweise zur Klausur und Klausurvorbereitung gegeben. Zudem gab es noch einmal die Möglichkeit Fragen zu stellen.
-
Vorlesung 24
In dieser Vorlesung beenden wir das Kapitel zum Thema Sortieralgorithmen und werfen abschließend einen Blick auf parallelisierte Sortierverfahren. -
Übung 7
In dieser Übung schauen wir uns noch einmal das Sortierverfahren Quicksort an und sprechen über die Berechnung von Medianen. Außerdem schauen wir uns mit den kd-Bäumen eine spezielle Datenstruktur für mehrdimensionale Daten an. -
Vorlesung 23
In dieser Vorlesung beschäftigen wir uns mit Sonderfällen für Sortieralgorithmen, durch die Sortieren in linearer Zeit ermöglicht wird. -
Vorlesung 22In dieser Vorlesung beschäftigen wir uns mit Medianen.
-
Vorlesung 21
In dieser Vorlesung kehren wir zurück zu Sortieralgorithmen und stellen den Quicksort-Algorithmus vor. -
Vorlesung 20
In dieser Vorlesung haben wir einen Exkurs in die nichtlineare Rekursion gemacht. -
Übung 6
Wir betrachten ein weiteres Beispiel für Mergesort und leiten erneut die Laufzeit des Sortieralgorithmus her, indem das Master-Theorem benutzt wird. Außerdem betrachten wir einen weiteren Sortieralgorithmus: Heapsort. -
Vorlesung 19In dieser Vorlesung besprechen wir weitere Details zu erzeugenden Funktionen und führen das Master-Theorem ein.
-
Vorlesung 18
In dieser Vorlesung leiten wir konkrete Laufzeitschranken für das Problem des Sortierens einer Liste von Zahlen her. Zudem machen wir uns Gedanken über das Lösen von Rekursionsgleichungen. -
Vorlesung 17
In dieser Vorlesung geben wir eine Einführung in das Oberthema Sortieren. Wir stellen außerdem einen Sortieralgorithmus mit dem Namen Mergesort vor und stellen grundlegende Überlegungen zur Laufzeit von Sortieralgorithmen an.