#acl -All:read Sabine Storandt:read,write Björn Buchhold:read,write Claudius Korzen:read,write Elmar Haußmann:read,write
== AUFGABE 1 (Programmm + Laufzeitbestimmung) ==
=== 1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2 ===
{{{
def secondLargest(A):
max1, max2 = A[0], A[1]
for i in range(1, len(A)):
if A[i] > max1:
max2 = max1
max1 = A[i]
else if A[i] > max2:
max2 = A[i]
return max2
}}}
=== 1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen ===
Es gilt offensichtlich T,,n,, >= T,,n-1,, + T,,n-2,,.
Induktionsanfang: T_1 >= 2 und T_2 >= 1 gilt offensichtlich.
Induktionschritt: Nach Induktionsvoraussetzung ist T,,n-1,, >= F,,n-1,, und T,,n-2,, >= F,,n-2,,. Damit T,,n,, >= T,,n-1,, + T,,n-2,, >= F,,n-1,, + F,,n-2,, = F,,n,,.
=== 1.3 Funktion zur Berechnung von F_n in Zeit O(n), für n >= 2 ===
{{{
def fastFibonacci(n):
fibs = [1] * n
for i in range(2, n):
fibs[i] = fibs[i - 1] + fibs[i - 2]
return fibs[n-1]
}}}
== AUFGABE 2 (Felder + Hashing) ==
=== 2.1 Funktion zum Suchen und Löschen eines Elementes aus einem Feld ===
{{{
def removeFromArray(A, x):
i = 0
# Find the element.
while i < len(A) and A[i] != x:
i = i + 1
# If found, swap to the end and remove last element.
if i < len(A):
A[i], A[-1] = A[-1], A[i]
A.pop()
}}}
=== 2.2 Funktion zum Löschen eines Elementes aus einer Hashtabelle ===
{{{
def removeFromHashTable(T, h, x):
removeFromArray(T[h(x)], x)
}}}
=== 2.3 Laufzeit der Funktionen aus Aufgabe 2.1 und 2.2 ===
Die Funktion aus Aufgabe 2.1 hat Laufzeit Theta(i), wenn das Element an Stelle i steht bzw. Theta(n) wenn das Element nicht im Feld steht.
Die Funktion aus Aufgabe 2.2 hat Laufzeit Theta(1) im besten Fall (unter h(x) stehen in T nur konstant viele Elemente) und Laufzeit Theta(n) im schlechtesten Fall (alle Elemente in T werden auf h(x) abgebildet und das gesuchte Element ist nicht dabei oder steht ganz am Ende des Feldes).
=== 2.4 Klasse H nicht 1-universell, wenn |H| < m und |U| > m ===
Nach Definition von 1-universell müsste für alle x, y mit x != y gelten, dass |{h: h(x) = h(y)}| <= c * |H| / m < 1, also = 0.
Das heißt, für jedes Schlüsselpaar x, y mit x != y darf es keine Hashfunktion geben, unter der die beiden Schlüssel auf dasselbe abgebildet werden.
Für jede Hashfunktion h muss es aber zwei Schlüssel geben, die auf dasselbe abgebildet werden, weil es > m Schlüssel gibt aber nur m Plätze in der Hashtabelle.
== AUFGABE 3 (Binäre Heaps) ==
=== 3.1 Heapzustand (als Baum und als Feld) nach dem Einfügen von 5, 4, 3, 2, 1 (in der Reihenfolge) ===
Von links nach rechts: oben = Baum, unten = Feld (x = beliebiger Wert an Position 0 im Feld)
{{{
5 4 3 2 1
/ / \ / \ / \
5 5 4 3 4 2 4
/ / \
5 5 3
x5 x45 x354 x2345 x12453
}}}
=== 3.2 Funktion zur Überprüfung der Heapeigenschaft ===
{{{
def checkHeapProperty(heap):
for i in range(2, len(heap)):
child_value = heap(i)
parent_value = heap(i/2)
if child_value < parent_value:
return False
return True
}}}
=== 3.3 Laufzeit der Funktion aus Aufgabe 3.2 ===
Die Laufzeit is Theta(n).
Begründung: die Schleife läuft n - 2 = Theta(n) mal durch und in jedem Durchlauf gibt es eine konstante Anzahl von Anweisungen.
=== 3.4 Anzahl Blockoperationen der Funktion aus Aufgabe 3.2 ===
Die Anzahl Blockoperation is Theta(n/B).
Begründung: für das child_value liest man n Elemente von links nach rechts, eins nach dem anderen, das sind ~ n/B Blockoperationen.
Für das parent_value liest man n/2 Elemente von links nach rechts, eins nach dem anderen (und immer denselben Wert zweimal hintereinander), das sind ~ (n/2)/B Blockoperationen.
== AUFGABE 4 (Graphen) ==
=== 4.1 Zeichnung des Graphen + Darstellung durch Adjazenzlisten und Adjazenmatrix ===
Die Zeichnung ist trivial (ein Dreick, mit den Kanten einmal reihum, Gewicht jeweils 2).
Darstellung durch Adjazenzlisten (statt u,,1,,, u,,2,,, u,,3,, könnte man auch 0, 1, 2 schreiben):
{{{
u,,1,, -> (u,,2,,, 2)
u,,2,, -> (u,,3,,, 2)
u,,3,, -> (u,,1,,, 2)
}}}
Darstellung durch 3 x 3 Adjazentmatrix (x = spezieller Eintrag, der bedeutet "keine Kante"):
{{{
x 2 x
x x 2
2 x x
}}}
=== 4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten ===
{{{
# graph is represented as an array of n adjacency lists, where n = #nodes.
def numEdges(graph):
count = 0
for i in range(0, len(graph)):
count += len(graph[i])
return count
}}}
=== 4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix ===
{{{
# graph is represented as an array of n array, each of size n, where n = #nodes.
def numEdges(graph):
count = 0
n = len(graph)
for i in range(0, n):
for j in range(0, n):
if graph[i][j] > 0:
count += 1
return count
}}}
=== 4.4 Laufzeit der Funktionen aus Aufgabe 4.2 und Aufgabe 4.3 ===
Die Laufzeit der Funktion aus Aufgabe 4.2 ist Theta(n), wobei n die Anzahl der Knoten ist.
Begründung: die Schleife wird n mal durchlaufen, und in jedem Schleifendurchlauf werden nur konstant viele Anweisungen ausgeführt.
Die Laufzeit der Funktion aus Aufgabe 4.3 ist Theta(n^2^), wobei n die Anzahl der Knoten ist.
Begründung: die äußere Schleife wir n mal durchlaufen und die innere ebenfalls, das gibt insgesamt n^2^ Durchläufe des Schleifenkörpers, der aus konstant vielen Anweisungen besteht.
== AUFGABE 5 (Edi-Tier) ==
=== 5.1 Editierdistanz zwischen REGAL und LAGER ===
{{{
e L A G E R
e 0 1 2 3 4 5
R 1 1 2 3 4 4
E 2 2 2 3 3 4
G 3 3 3 2 3 4
A 4 4 3 3 3 4
L 5 4 4 4 4 4
}}}
=== 5.2 ED(x, y) = n - 1, falls n ungerade und x das Wort y rückwärts ist und alle Buchstaben verschieden ===
Falls n ungerade ist, ist der mittlere Buchstabe von x und y gleich.
Man also x mit n - 1 replace Operationen in y überführen.
Das zeigt aber erstmal nur ED(x, y) <= n - 1 (es könnte auch noch mit weniger Operationen gehen).
Die Alternative zu einem Replace wäre die benötigten Buchstaben durch Löschen und Einfügen hinzuzufügen.
Das hat Kosten 2 und hilft aber immer nur höchstens zwei Buchstaben, ist also auch nicht besser.
=== 5.3 ED(x, y) = ?, falls n gerade und x das Wort y rückwärts ist und alle Buchstaben verschieden ===
Falls n gerade ist, haben x und y keinen Buchstaben an derselben Stelle gemeinsam.
Man kann aber auf jeden Fall x mit n Replace Operationen in y überführen.
Mit demselben Argument wie oben (Einfügen und Löschen hilft höchstens zwei Buchstaben) geht es auch nicht besser
=== 5.4 ED(x, y) im niedrigsten Fall, wenn nur mindestens zwei verschiedene Buchstaben ===
Wenn x ein Palindrom ist (z.B. Hannah oder Hannnah), dann ist x = y und ED(x, y) = 0.
== AUFGABE 6 (O-Notation, Logarith-Mus, W-keit) ==
=== 6.1 Zeigen Sie, dass 2n + 17 = O(n^2) über die Definition von O mittels C und n,,0,, ===
Für n >= 5 ist 2n + 17 <= n^2^ + n^2^ <= 2 n^2^. Also Bedingung per Definition erfüllt mit n,,0,, = 5 und C = 2.
=== 6.2 Wert von log,,2,, (2^64^ * 8^12^) ===
log,,2,, (2^64^ * 8^12^) = log,,2,, 2^64^ + log,,2,, 8^12^ = 64 + log,,2,, 2^36^ = 64 + 36 = 100.
Dabei wurde benutzt dass 8 = 2^3^ und "x hoch y hoch z" gleich "x hoch (y * z)" ist.
=== 6.3 Wahrscheinlichkeit guter Pivot (beide Teile >= n/4) bei Quicksort, bei zufälliger Wahl ===
Seien die Elemente ohne Beschränkung der Allgemeinheit 1, ..., n (es zählt nur die Reihenfolge nicht der Wert).
Wählt man eines der n/4 Elemente 1, ..., n/4 als Pivot ist der "vordere" Teil (Elemente < Pivot) kleiner als n/4.
Wählt man eines der n/4 Elemente n - n/4 + 1, ..., n als Pivot ist der "hintere" Teil (Elemente > Pivot) kleiner als n/4.
Wählt man eines der übrigen n/2 Elemente als Pivot, sind beide Teile >= n/4.
Die Wahrscheinlichkeit ist also 1/2.
=== 6.4 Wahrscheinlichkeit von 6.3 bei dreimaliger Wiederholung ===
Wir betrachten erst das Gegenereignis = selbst für die beste Aufteilung ist ein Teil < n/4.
Wenn das passiert, ist für alle drei Aufteilungen (von allen drei Pivots), der kleinste Teil n/4.
Nach Aufgabe 6.3 passiert das für jede Aufteilung mit Wahrscheinlichkeit 1/2.
Die Wahrscheinlichkeit, dass es für alle drei passiert ist also 1/8.
Die gefragt Wahrscheinlichkeit ist also 7/8.