Prof. Dr. Franz Schweiggert Abteilung Angewandte Informationsverarbeitung 01.06.2006
Norbert Heidenbluth Blatt 5


Uni Logo



Allgemeine Informatik II (SS 2006)
für
(Wirtschafts-)Mathematiker/Physiker und E-Techniker



Abgabetermin: 08. Juni 2006

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.

Aufgabe 9: Quicksort (3 Punkte)

Seit Sie an der Uni sind, haben Sie die Comic-Sammlung aus Ihren Kindertagen leider etwas vernachlässigt. Andererseits haben Sie sich das Denken in Algorithmen zwischenzeitlich so zu eigen gemacht, daß Sie nun auch Ihre Comic-Sammlung mit anderen Augen sehen.

Denn beim letzten Lesen eines Mickey-Maus-Heftes aus den frühen 90er Jahren haben Sie mal notiert, in welcher Reihenfolge die Akteure auftreten:

  1. Trick
  2. Dagobert
  3. Tick
  4. Donald
  5. Mickey
  6. Track
  7. Goofy

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).

Aufgabe 10: Heapsort (3 Punkte)

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!

Zusatzaufgabe

(falls Sie sich mit der Sortieraufgabe unterfordert fühlen): Finden Sie heraus, wer nicht in die Komponistenaufzählung passt$\ldots$!

Aufgabe 11: KMP-Algorithmus (4 Punkte)

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:

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.

Bearbeitunghinweis zu allen Aufgaben:

Viel Erfolg!



Fußnoten

... Quicksort-Algorithmus1
Ja, den gab es bereits damals!


Norbert Heidenbluth 2006-05-31