Auf diesem Übungsblatt wollen wir mit drei der in der Vorlesung behandelten Algorithmen konkret arbeiten: mit Quicksort, Heapsort und Knuth-Morris-Pratt. Wir beschäftigen uns auf diesem Blatt daher ausnahmsweise einmal nicht mit dem Programmieren sondern mit der Anwendung der genannten Algorithmen. Daher ist dieses Blatt nicht am Rechner zu lösen, sondern ``manuell''. Siehe dazu auch die Bearbeitungshinweise am Ende des Blattes.
Denn beim letzten Lesen eines Mickey-Maus-Heftes aus den frühen 90er Jahren haben Sie mal notiert, in welcher Reihenfolge die Akteure auftreten:
Nach dem Genuß der Comics haben Sie sich dann überlegt, warum Sie nicht schon als Kind auf die Idee gekommen sind, diese Comic-Figuren nun alphabetisch aufsteigend zu sortieren - und das unter Verwendung des Quicksort-Algorithmus1.
Da es bekanntlich nie zu spät ist, dürfen Sie das nun rund 15 Jahre später nachholen:
Sortieren Sie die oben notierten Comicfiguren selbständig (d.h. ohne Verwendung des Rechners), so daß sie am Ende alphabetisch aufsteigend sortiert sind. Wählen Sie als Sortieralgorithmus den Quicksort (aus dem Skript).
Da Sie ja aus dem Comic-Alter mittlerweile (leider) heraus sind, haben Sie sich als kulturinteressierte(r) Studierende(r) von infantilen Bildergeschichten verabschiedet und sich stattdessen eine Sammlung klassischer Musik (beim Discounter um die Ecke) zugelegt. Um den Wandel der Musik im Laufe der Jahrhunderte verfolgen zu können, möchten Sie nun die sechs Stücke auf der CD nach dem Geburtsdatum des Komponisten aufsteigend sortiert abspielen lassen. Es handelt sich hierbei um:
Das Programmieren des CD-Spielers ist kein Problem für Sie, sobald Sie einmal die gewünschte Reihenfolge haben. Aha - Sie merken es schon: es läuft auf eine weitere Sortier-Aufgabe hinaus:
Sortieren Sie die vorstehend genannten Komponisten aufsteigend sortiert nach Geburtsdatum. Verwenden Sie hierzu den Heapsort!
Nach diesen beiden theoretischen Aufgaben, sehnen Sie sich mal wieder nach einer praktischen. Aber - so ist das Leben: auch die dritte und letzte Aufgabe auf diesem Blatt beschäftigt sich mit einem in der Vorlesung vorgestellten Algorithmus und bleibt ohne Verwendung des Rechners: wir verwenden den Knuth-Morris-Pratt-Algorithmus.
Gegeben seien:
gatcgatcacatcatcacgaaaaa
atcacatcatca
Führen Sie mit diesen Daten eine Textsuche gemäß dem KMP-Algorithmus durch und notieren Sie insbesondere auch das Array, das sich durch das ``Preprocessing'' ergibt.
Viel Erfolg!