Stand: 19. November 1997
Lösungen zu Blatt 4
- Aufgabe 12:
- Das lauffähige Programm select.c gibt's zum Download hier. Nachdem es mit c++ select.c -o select übersetzt worden ist, kann man es mit select 500 250 1000 derart starten, daß aus 1000 Zufallsfolgen der Länge 500 die 250-größte Zahl bestimmt wird.
Eine graphische Darstellung der Laufzeiten bis
|S|=30000 ist in der Datei selectionZeiten.ps hier zu finden. Dieses Programm hat die mittlere Kurve.
- Aufgabe 13:
- (a) + (b)
- Eine sehr schöne Beschreibung und Analyse des Verfahrens kann man im Buch »The Design and Analysis of Computer Algorithms« von Aho/Hopcroft/Ullman in Abschnitt 3.6 nachlesen. Im Buch »Introduction to Algorithms« von Cormen/Leiserson/Rivest wird in Abschnitt 10.3 ein leicht abgeändertes Verfahren präsentiert. Und schließlich wird dieses Verfahren im Buch »Algorithmen und Datenstrukturen« von Ottmann/Widmayer in Abschnitt 3.1 behandelt.
- (b)
- Die Rekursionsbeziehung sieht folgendermaßen aus:
T(n) <= T(n/5) + T(3n/4) + cn. Die Begründung für diese Beziehung findet man in den oben genannten Lehrbüchern. Es ist einfach zu zeigen, daß T(n) <= 20cn. Der »Trick«, der zu der linearen Laufzeit führt, besteht darin, daß
n/5 + 3n/4 < n ist.- (c)
- Die Laufzeit dieser Variante ist nicht linear in n, da hier die Rekursionsbeziehung
T(n) <= T(n/3) + T(2n/3) + cn. ist. Hier ist
n/3 + 2n/3 = n .Zugabe: Ein lauffähiges Programm 3select.c gibt's zum Download hier. Eine graphische Darstellung der Laufzeiten bis
n=30000 ist in der Datei selectionZeiten.ps hier zu finden. Dieses Programm hat die obere Kurve.
- Aufgabe 14:
- Das lauffähige Programm rselect.c gibt's zum Download hier.
Eine graphische Darstellung der Laufzeiten bis
n=30000 ist in der Datei selectionZeiten.ps hier zu finden. Dieses Programm hat die untere Kurve.
- Aufgabe 15:
- Eine angepaßte Implementierung der drei Verfahren ergab diese Ausgabe.
Rolf Wanka (email: wanka@uni-paderborn.de)