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.
Folien: VL19.pdf
Notizen: VL19b.pdf
Video: [YouTube], [IBR]
Weitere Links
YouTube: Puzzle aus Brooklyn99 (engl.)
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)