Skizze der Lösungen zur Klausur zur Vorlesung "Informatik II: Algorithmen und Datenstrukturen" im SS 2015
Alle Angaben ohne Gewähr. Bei Fehlern bitte kurze Mail an die Dozentin.
AUFGABE 1 (Programmm + Laufzeitbestimmung)
1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2
def secondLargest(A):
max1 = max(A[0], A[1])
max2 = min(A[0], A[1])
for i in range(2, 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 Tn >= Tn-1 + Tn-2.
Induktionsanfang: T_1 >= 1 und T_2 >= 1 gilt offensichtlich.
Induktionschritt: Nach Induktionsvoraussetzung ist Tn-1 >= Fn-1 und Tn-2 >= Fn-2. Damit Tn >= Tn-1 + Tn-2 >= Fn-1 + Fn-2 = Fn.
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, copy last element and shrink array by 1.
if i < len(A):
A[i] = A[-1]
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 (u1 -> 0, u2 -> 1, u3 -> 2):
0 -> (1, 2) 1 -> (2, 2) 2 -> (0, 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(n2), wobei n die Anzahl der Knoten ist. Begründung: die äußere Schleife wir n mal durchlaufen und die innere ebenfalls, das gibt insgesamt n2 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. Also in dem Fall ED(x, y) = n.
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. Für n = 2 geht das allerdings nicht, weil es mindestens zwei verschiedene Buchstaben geben muss, da ist dann ED(x, y) = 2.
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 <= n2 + n2 <= 2 n2. Also Bedingung per Definition erfüllt mit n0 = 5 und C = 2.
6.2 Wert von log,,2,, (2^64^ * 8^12^)
log2 (264 * 812) = log2 264 + log2 812 = 64 + log2 236 = 64 + 36 = 100. Dabei wurde benutzt dass 8 = 23 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.