U.
Köthe: Vorlesung „Algorithmen und Datenstrukturen“ Heidelberg, SS 2025
Übung 2 Abgabe 13.5.2025
Aufgabe 1 – Eigenschaften von Sortierverfahren 20 Punkte
a) Um Daten sortieren zu können, muss auf den Elementen eine Relation '≤' definiert sein, die die 3 Punkte
Eigenschaften einer totalen Ordnung (siehe https://de.wikipedia.org/wiki/Ordnungsrelation)
hat. Zeigen Sie, dass dadurch auch die anderen Relationen '<', '>', '≥', '==' und '!=' festgelegt
sind, indem Sie diese so definieren, dass in den Definitionen nur die '≤' Relation und logische
Operationen (not, and, or) vorkommen.
b) Nach dem Sortieren eines Arrays a der Größe N ist das folgende Axiom erfüllt: Für alle Paare 5 Punkte
von Indizes j und k mit j < k sind die zugehörigen Arrayelemente sortiert, d.h. es gilt a[j] ≤ a[k].
Das sind N(N-1)/2 Bedingungen (eine für jedes mögliche Paar j < k), die man alle prüfen muss,
um die Korrektheit der Sortierung nachzuweisen. Zeigen Sie mit Hilfe der Eigenschaften der '≤'
Relation (also mit den Axiomen einer totalen Ordnung), dass dieser Aufwand unnötig ist und
man auch mit (N-1) Tests auskommt. Welche Tests sollte man ausführen, und warum sind die
übrigen dann automatisch erfüllt?
c) Implementieren Sie insertion_sort() und quick_sort() (mit geschickter Wahl des Pivots) 7 Punkte
so, dass die Gesamtzahl der Vergleiche von Arrayelementen gezählt und am Ende zurückgege-
ben wird (andere Vergleiche, z.B. von Schleifenindizes, werden nicht mitgezählt):
count1 = insertion_sort(a)
count2 = quick_sort(a)
Führen Sie diese Funktionen mit zufällig sortierten Arrays verschiedener Größe aus. Ein zufällig
sortiertes Array erzeugen Sie folgendermaßen:
import random # Python's Zufallszahlenmodul
N = ... # Arraygröße
a = list(range(N)) # erzeuge ein sortiertes Array
random.shuffle(a) # mische das Array
Lassen Sie die Sortierfunktion für jedes N mehrmals (mit jeweils anders gemischten Elementen)
laufen und bestimmen Sie die Mittelwerte c1 (insertion sort) und c2 (quick sort) der Zähler über
die zufälligen Arrays der gleichen Größe. Benutzen Sie das Modul "matplotlib", um die Anzahl
der Vergleiche in Abhängigkeit von N zu plotten1. Prüfen Sie die Aussage aus der Vorlesung,
dass die Kurven für große N durch die Funktionen 𝑐1 ≈ 𝑑1 𝑁 2 (für insertion sort) bzw. 𝑐2 ≈
𝑑2 𝑁𝑙𝑜𝑔𝑁 (für quick sort) mit geeigneten Konstanten 𝑑1 , 𝑑2 approximiert werden. Plotten Sie
die Approximationsfunktionen ins gleiche Diagramm. (Zur Verbesserung der Fits können Sie
auch die Funktionen 𝑑1 𝑁 2 + 𝑒1 𝑁 + 𝑓1 bzw. 𝑑2 𝑁𝑙𝑜𝑔𝑁 + 𝑒2 𝑁 + 𝑓2 verwenden, aber die Genau-
igkeit muss zur Lösung der Aufgabe nicht sonderlich hoch sein.)
Machen Sie das entsprechende Experiment außerdem mit bereits sortierten Arrays und verglei-
chen Sie die Ergebnisse und Kurven. Vergleichen Sie quick_sort() auf sortierten Arrays außer-
dem mit einer neuen Implementation quick_sort_2(), die das Pivot absichtlich ungeschickt
wählt.
d) Testen Sie nun, ob die Anzahl der Vergleiche aus c) eine gute Vorhersage der tatsächlichen 5 Punkte
Laufzeit erlaubt. Messen Sie dazu die Laufzeiten 𝑡1 (insertion sort) und 𝑡2 (quick sort) mit dem
1 Siehe https://matplotlib.org/gallery/lines_bars_and_markers/simple_plot.html. Um mehrere Kurven ins
selbe Diagramm zu zeichnen, ruft man ax.plot(...) einfach mehrmals auf. matplotlib wird am einfachsten
mittels Anaconda installiert.
U. Köthe: Vorlesung „Algorithmen und Datenstrukturen“ Heidelberg, SS 2025
timeit-Modul (eine Anleitung finden Sie am Ende des Übungsblattes). Berechnen Sie das Ver-
hältnis 𝑐1 ⁄𝑡1 von insertion sort und überprüfen Sie, dass es für große N gegen eine Konstante
konvergiert. Wiederholen Sie dasselbe für das Verhältnis 𝑐2 ⁄𝑡2 von quick sort.
Der Code für die gesamte Aufgabe soll im File "sortieren.py" bzw. "sortieren.ipynb" abgegeben
werden.
Aufgabe 2 – Zelluläre Automaten 20 Punkte
Algorithmen werden wesentlich durch die Menge der elementaren Operationen geprägt, aus denen
sie aufgebaut sind. Zelluläre Automaten sind interessant, weil sie aus sehr einfachen elementaren Ope-
rationen erstaunlich komplexes Verhalten generieren. Das bekannteste Beispiel ist Conway’s Game of
Life (de.wikipedia.org/wiki/Conways_Spiel_des_Lebens). Wir beschränken uns hier aber auf die eindi-
mensionale Variante, die in den Kapiteln 2 und 3 von Stephen Wolfram's Buch "A new kind of science"
ausführlich diskutiert wird.
Jeder zelluläre Automat besteht aus unabhängigen Zellen, die auf einem regelmäßigen Gitter ange-
ordnet sind und K vorher festgelegte Zustände annehmen können. Die Zustände werden meist durch
druckbare Zeichen wie " " (Leerzeichen), "*", "#" etc. symbolisiert. Der Automat entwickelt sich in dis-
kreten Zeitschritten, und der Zustand jeder Zelle zum Zeitpunkt T+1 ergibt sich deterministisch aus den
Zuständen dieser Zelle sowie ihrer unmittelbaren Nachbarn zum Zeitpunkt T. Die Menge der erlaubten
Zustandsübergänge in Abhängigkeit der möglichen Nachbarschafts-Konstellationen wird als Regel des
Automaten bezeichnet. Die Regel wird einmal festgelegt und bleibt dann für alle Zeitschritte gleich.
a) Eindimensionale zelluläre Automaten kann man bequem als Strings einer vorher festgelegten 5 Punkte
Länge darstellen, sodass jedes Zeichen im String eine Zelle repräsentiert. Der neue Zustand
einer Zelle j ergibt sich dann aus dem alten Zustand dieser Zelle und dem Zustand ihrer linken
und rechten Nachbarzelle (Zellen j-1 und j+1), also jeweils aus Teilstrings der Länge 3. Deshalb
kann man die Regel bequem in einem Python-Dictionary darstellen: Strings der Länge 3 bilden
die Schlüssel, und die zugehörigen Werte geben den neuen Zustand der mittleren Zelle an, z.B.:
rule = {" ": " ", # drei Leerzeichen => Leerzeichen
" * ": "*", # Stern zwischen zwei Leerzeichen => Stern
... # weitere Zustandsübergänge
Implementieren Sie im File "cellular_atomata.py" bzw. "cellular_atomata.ipynb" eine
Funktion
ca2 = ca_step(ca1, rule)
der der String ca1 (Zustand zur Zeit T) sowie die Regel übergeben werden und die daraus den
neuen String ca2 (mit gleicher Länge wie ca1) als Zustand zur Zeit T+1 berechnet. Definieren
Sie dabei eine geeignete Randbehandlung für die beiden Enden von ca1, also für die Zellen,
die keinen linken bzw. rechten Nachbarn haben. Diese Funktion wird in b) und c) benutzt.
b) Elementare zelluläre Automaten haben nur zwei Zustände " " und "*". Wie viele verschiedene 5 Punkte
Regeln kann man daraus aufbauen? Manche dieser Regeln führen zu interessantem Verhalten.
Experimentieren Sie mit den Regeldefinitionen (indem Sie die Dictionaries variieren) und be-
rechnen Sie jeweils die ersten 30 Zeitschritte, wobei der Anfangszustand immer ein String der
Länge 71 ist, bei dem sich nur das Element 35 im Zustand "*" befindet, alle übrigen sind im
Zustand " ". Geben Sie mit print den aktuellen Zustand nach jeder Iteration aus. Implemen-
tieren Sie vier Funktionen "elementary1()" bis "elementary4()" (die jeweils eine Regeldefi-
nition und die Schleife enthalten) im File "cellular_atomata.py", die nette Muster erzeugen.
c) Implementieren Sie jetzt eine Funktion ping_pong(), deren Regel eine Art Ping-Pong-Spiel re- 10 Punkte
alisiert. Es gibt hier neben dem Zustand " " einen Zustand "#", der die beiden Spielfeldränder
U. Köthe: Vorlesung „Algorithmen und Datenstrukturen“ Heidelberg, SS 2025
angibt, sowie einen Ball, der immer zwischen den beiden Rändern hin- und herfliegt und auto-
matisch reflektiert wird. Der Ball wird durch zwei benachbarte Zellen symbolisiert, die die Zu-
stände "o-" haben, wenn der Ball gerade nach links fliegt, und "-o" wenn er nach rechts fliegt.
Der Anfangszustand ist der String " # o- # " (der Abstand zwischen den beiden "#"
beträgt 12 Zeichen und soll unverändert bleiben). Implementieren Sie die zeitliche Entwicklung
des Automaten als Endlosschleife (diese kann man in Python durch die Tastenkombination
"Ctrl-C" abbrechen, wenn man lange genug zugeschaut hat). Um die Animation besser be-
obachten zu können, sollten Sie in jeder Iteration eine gewisse Wartezeit einbauen (Funktion
"sleep()" aus dem Modul "time"). Beachten Sie, dass die Regel während des Ablaufs fix bleibt
und nicht verändert werden darf (um z.B. die Flugrichtung des Balls umzukehren).
Verwendung des timeit-Moduls
Das timeit-Modul1 dient zur Messung der Laufzeit in Python. Der Code, dessen Laufzeit gemessen
werden soll, wird der Timeit-Klasse bei der Initialisierung als (mehrzeiliger) String übergeben. In einem
zweiten String kann man außerdem Initialisierungscode angeben, der zuvor ausgeführt werden muss,
dessen Zeit aber nicht in die Messung eingehen soll. Für die Sortier-Aufgabe sieht dies so aus:
import timeit
import random
def quick_sort(a):
... # your implementation
code_to_be_measured = '''
quick_sort(a)
'''
initialization = '''
N = 1000
a = list(range(N))
random.shuffle(a)
'''
t = timeit.Timer(code_to_be_measured, initialization, globals=globals())
Die eigentliche Zeitmessung erfolgt dann mit der Methode t.repeat(M, 1), wobei M angibt, wie
häufig das Programm ausgeführt werden soll. Das Ergebnis ist ein Array mit den Laufzeiten der einzel-
nen Durchläufe, so dass man den Mittelwert berechnen kann. Beachten Sie, dass die Methode
t.timeit(M) (an Stelle von t.repeat(M, 1)) hier nicht anwendbar ist, weil die Initialisierung dabei
nur einmal ausgeführt wird, so dass alle Wiederholungen auf einem bereits sortierten Array arbeiten
würden.
M = 100
# run 'initialization' and ’code_to_be_measured’ M times
times = t.repeat(M, 1)
print("average execution time:", sum(times) / M)
Verpacken Sie Ihre Lösung in ein zip-File und laden Sie es bis zum 13.5.2025 um 16:00 Uhr auf MaMPF
hoch. Vergessen Sie nicht, der Abgabe Ihres Teams rechtzeitig beizutreten.
1 https://docs.python.org/3/library/timeit.html
