Ubung 6 - WueCampus2 - Universität Würzburg

Lehrstuhl für Informatik I
Würzburg, den 21. November 2013
Effiziente Algorithmen und
wissensbasierte Systeme
Prof. Dr. Alexander Wolff
M.Sc. Krzysztof Fleszar
Universität Würzburg
Vorlesung Algorithmen und Datenstrukturen WS 2013/14
Übung 6
Bitte geben Sie Ihre Lösungen bis Do, 28. November 2013, 12:00 Uhr in 2er- oder 3erGruppen (nur innerhalb einer Übungsgruppe!) als ein pdf-Dokument über die WueCampus-Seite
der Lehrveranstaltung ab. Andere Dateiformate werden ignoriert! Geben Sie stets die Namen aller
BearbeiterInnen und die Nummer Ihrer Übungsgruppe an. Abgaben ohne Namen und ohne
Gruppennummer werden nicht korrigiert!
Geben Sie Ihren Quelltext zu den Aufgaben 2 (a) und (b) online auf PABS ab:
https://pabs.uni-wuerzburg.de/courses/151
Klicken Sie bei Ihrer endgültigen Abgabe auf Submit as solution (dies ist nun auch bei abgelehnten Lösungen möglich.) Vermerken Sie in Ihrer schriftlichen Ausarbeitung, wer aus Ihrem
2er- oder 3er-Team den Quelltext hochgeladen hat. Ohne diesen Vermerk korrigieren wir Ihre
PABS-Einreichungen nicht!
Aufgabe 1
4 Punkte
Onkel Dagobert möchte seinen Geldspeicher in weihnachtlichem Glanz erstrahlen lassen und hat
dafür n Leuchtsterne mit Koordinaten {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )} auf der Fassade montiert.
Um Kosten zu sparen, möchte er die Stromkabel so kurz wie möglich halten. Er plant eine vertikale Hauptleitung, von der horizontale Leitungen zu den einzelnen Sternen abzweigen. Schlagen
Sie einen Algorithmus vor, welcher die x-Koordinate der Hauptleitung einer Lösung mit insgesamt
kürzester Leitungslänge zurückgibt, und begründen Sie, warum der Algorithmus korrekt ist.
Aufgabe 2
3 + 5 + 8 = 16 Punkte
In dieser Aufgabe sollen verschiedene Sortieralgorithmen programmiert und experimentell verglichen werden. Implementieren Sie alle geforderten Methoden sowie gegebenenfalls zusätzliche
Hilfsmethoden in einer Java-Klasse Sortierverfahren in einem Paket sortierverfahren.
a) Programmieren Sie einen Algorithmus in Java, der eine Folge von n ganzen Zahlen aus dem
Intervall [0, k] in der Laufzeit O(n + k) sortiert. Implementieren Sie dafür die Methode
public static void linearSort(int[] a, int k) .
b) Programmieren Sie einen Sortieralgorithmus in Java, der für (Teil-)Felder ab einer bestimmten
Anzahl t von Elementen QuickSort verwendet und für (Teil-)Felder mit weniger als t Elementen
InsertionSort ausführt. Implementieren Sie dafür eine Methode
public static void combinedSort(int[] a, int t)
1
Algorithmen und Datenstrukturen
c) Testen Sie die Methoden linearSort, combinedSort und easySort (aus Übung 2) für
zufällig generierte Folgen der Größe 100.000 · a für a = 1, 2, . . . , 100 sowohl
(i) für ganze Zahlen im Wertebereich [0, 10.000] als auch
(ii) für ganze Zahlen im Wertebereich [0, 10.000.000],
und halten Sie jeweils die Laufzeit fest. Wenn einer Ihrer Algorithmen mehr als zehn Sekunden
für eine Folge braucht, müssen Sie keine größeren Folgen mit demselben Algorithmus sortieren.
Experimentieren Sie bei der Methode combinedSort auch mit verschiedenen Werten für den
Parameter t. Für welchen Wert erzielen Sie die beste Laufzeit?
Stellen Sie die Ergebnisse Ihrer Tests in einem Diagramm für den Wertebereich (i) und einem zweiten Diagramm für den Wertebereich (ii) dar (z.B. mit gnuplot oder Excel), die für
linearSort und easySort je eine Laufzeitkurve und für combinedSort drei Laufzeitkurven
für verschiedene Werte für den Parameter t enthalten. Auf der x-Achse soll die Größe der Folge
aufgetragen sein und auf der y-Achse die benötigte Zeit. Vermelden Sie die Einheit Ihrer Zeitmessung, Betriebssystem, Taktfrequenz und die Größe des Hauptspeichers Ihres Computers.
Diskutieren Sie kurz Ihre Beobachtungen. Welche Gründe gibt es für die Ergebnisse?
2
/Lehrstuhl für Informatik I