|
Size: 8196
Comment:
|
Size: 5894
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| #acl -All:read | #acl -All:read Sabine Storandt:read,write Björn Buchhold:read,write Claudius Korzen:read,write Elmar Haußmann:read,write |
| Line 4: | Line 4: |
| == AUFGABE 1 (Diverses) == | == AUFGABE 1 (Programmm + Laufzeitbestimmung) == |
| Line 6: | Line 6: |
| === 1.1 log n = O(log^2 n) aber nicht Theta === Sei log der Logarithmus zur Basis 2. (Wir können die Basis beliebig wählen, weil sich log,,b1,, und log,,b2,, nur um einen (positiven) konstanten Faktor ln b1 / ln b2 untertscheiden, für b1, b2 > 1. Für alle n >= 2 ist log n >= 2 und damit, log n <= (log n)^2^, also gilt O mit n,,0,, = 2 und C = 1. Falls Theta, müsste auch Omega sein, dann würde es C, n,,0,, geben, so dass für alle n >= n,,0,, gilt, dass log n >= C * log^2^ n. Dann wäre aber log n <= 1/C für alle n >= n,,0,,. Aber z.B. für n = max(n,,0,,, 2^1 + 1/C^) ist n >= n,,0,, und log n > 1/C. Es reicht auch als Argument, dass log n für hinreichend große n beliebig groß wird (wenn auch langsam). === 1.2 Was macht das Programm das da steht === Es berechnet die Anzahl der ''verschiedenen'' Elemente im Eingabefeld. Begründung: zu Beginn nimmt man an, dass alle Elemente verschieden sind, dann wäre diese Anzahl = #Größe des Feldes. Dann geht man von links nach rechts durch, und immer wenn man ein Element findet, dass man schon mal gesehen hat, zieht man 1 ab. === 1.3 Laufzeit im besten und schlechtesten Fall === Bester Fall: Theta(n). Begründung: das passiert z.B. wenn alle Elemente gleich sind. Dann bricht die innere Schleife immer schon nach dem ersten Durchlauf ab. Schneller als Theta(n) geht nicht, weil die äußere Schleife immer n mal durchläuft. Schlechtester Fall: Theta(n^2^). Begründung: das passiert z.B. wenn alle Elemente verschieden sind. Dann läuft die innere Schleife immer ganz zum Ende und die Laufzeit ist proportional zu sum_{i=1,...,n} i = Theta(n^2^). == AUFGABE 2 (Hashing) == === 2.1 Zustand der Hashtabelle nach Einfügen von 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 === Für h(x) = x^2^ mod 5 ist: h(1) = 1, h(2) = 4, h(3) = 4, h(4) = 1, h(5) = 0, h(6) = 1, h(7) = 4, h(8) = 4, h(9) = 1, h(10) = 0. Zustand der Hashtabelle also: |
=== 1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2 === |
| Line 32: | Line 9: |
| 0 : 5, 10 1 : 1, 4, 6, 9 2 : nix 3 : nix 4 : 2, 3, 7, 8 |
def secondLargest(A): max1 = A[0] max2 = A[1] if max2 > max1: max1, max2 = max2, max1 for i in range(2, len(A)): if A[i] > max2: if A[i] > max1: max2 = max1 max1 = A[i] else: max2 = A[i] return max2 |
| Line 39: | Line 24: |
| === 2.2 Beweis, dass h(x + 5) = h(x) === | === 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 === |
| Line 42: | Line 35: |
| h(x+5) = (x+5)^2 mod 5 = (x^2 + 10x + 5) mod 5 = (x^2 mod 5) + (10x mod 5) + (5 mod 5) = x^2 mod 5 = h(x) }}} Alternativ: {{{ h(x+5) = (x+5)^2 mod 5 = (((x+5) mod 5) * ((x+5) mod 5)) mod 4 = ((x mod 5) * (x mod 5)) mod 5 = x^2 mod 5 = h(x) |
def fastFibonacci(n): fibs = [1] * n for i in range(2, n): fibs[i] = fibs[i - 1] + fibs[i - 2] return fibs[n-1] |
| Line 58: | Line 44: |
| === 2.3 Pr(h(x) = i) für i = 0, 1, 2, 3, 4 === | == AUFGABE 2 (Felder + Hashing) == |
| Line 60: | Line 46: |
| Nach 2.2 ist die Verteilung für einen zufälligen Schlüssel aus N dieselbe wie für einen zufälligen Schlüssel aus {1, 2, 3, 4, 5}. Und dafür ist: | === 2.1 Funktion zum Suchen und Löschen eines Elementes aus einem Feld === |
| Line 63: | Line 49: |
| Pr(h(x) = 0) = 1/5 ... nur die 5 wird auf 0 abgebildet Pr(h(x) = 1) = 2/5 ... 1 und 4 werden auf 1 abgebildet Pr(h(x) = 2) = 0 ... nix wird auf 2 abgebildet Pr(h(x) = 3) = 0 ... nix wird auf 3 abgebildet Pr(h(x) = 4) = 2/5 ... 2 und 3 werden auf 4 abgebildet |
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() |
| Line 70: | Line 60: |
| === 2.4 Additivität von Universalität === Sei m die Größe der Hashtabelle und x, y ein beliebiges Schlüsselpaar mit x != y. Dann |
=== 2.2 Funktion zum Löschen eines Elementes aus einer Hashtabelle === |
| Line 75: | Line 63: |
| H1 c-universell => |{h in H1 : h(x) = h(y)|| <= c * |H1| / m H2 c-universell => |{h in H2 : h(x) = h(y)|| <= c * |H2| / m |
def removeFromHashTable(T, h, x): removeFromArray(T[h(x)], x) |
| Line 79: | Line 67: |
| Da H1 und H2 disjunkt ist ein h aus H entweder in H1 oder in H2, und |H| = |H1| + |H2|, und somit | === 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) |
| Line 82: | Line 87: |
| |{h in H : h(x) = h(y)}| = |{h in H1 : h(x) = h(y)}| + |{h in H2 : h(x) = h(y)}| <= c * |H1| / m + c * |H2| / m = c * |H| / m. |
5 4 3 2 1 / / \ / \ / \ 5 5 4 3 4 2 4 / / \ 5 5 3 x5 x45 x354 x2345 x12453 |
| Line 87: | Line 96: |
| Und damit ist H auch c-universell. == AUFGABE 3 (Dynamische Felder) == === 3.1 Wann i-te Reallokation wenn c1 = 1 und immer Verdoppelung === Dann Größe nach i-ter Reallokation 2^i. Induktionsanfang i = 1: erste Reallokation beim Einfügen des zweiten Elemente. Größe vor der Reallokation 1, danach 2 = 2^1^. Induktionsschritt i -> i + 1: Nach Induktionsvoraussetzung ist die Kapazität nach der i-ten Reallokation 2^i^. Es wird also das nächste Mal beim Einfügen des (2^i^ + 1)-sten Elementes wieder realloziert, und dann auf 2 * 2^i^ = 2^i+1^. === 3.2 Gesamtanzahl Blockoperationen bei Einfügen von n Elementen === |
=== 3.2 Funktion zur Überprüfung der Heapeigenschaft === |
| Line 100: | Line 99: |
| #IOs bis zur ersten Reallokation: Theta(1) #IOs von der i-ten Reallokation: Theta(2^i / B) #IOs ab da bis zur (i+1)-ten Reallokation: Theta(2^i / B) #IOs insgesamt also Theta(sum_{i=1}^k 2^i / B) = Theta(2^k / B) = Theta(n / B), k = #Anzahl Reallokationen |
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 |
| Line 106: | Line 108: |
| === 3.3 Laufzeit der Funktion aus Aufgabe 3.2 === | |
| Line 107: | Line 110: |
| == AUFGABE 4 (a,b-Bäume) == | 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. |
| Line 109: | Line 113: |
| === 4.1 (2,3)-Baum nach Einfügen von 1, 2, 3, 4, 5, 6 === | === 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): |
| Line 112: | Line 128: |
| 2|4|6 / | \ 1|2 3|4 5|6 / \ / \ / \ 1 2 3 4 5 6 |
u,,1,, -> (u,,2,,, 2) u,,2,, -> (u,,3,,, 2) u,,3,, -> (u,,1,,, 2) |
| Line 119: | Line 133: |
| === 4.2 Wann zum ersten Mal Tiefe 3 === Nach dem Einfügen von 8. Begründung: dann bekommt die Wurzel zum ersten Mal 4 Kinder und muss aufgespalten werden. === 4.3 Wann zum ersten Mal Tiefe 4 === Nach dem Einfügen von 16. Begründung: der Baum für die Knoten 9, 10, 11, 12, 13, 14, 15, 16 sieht dann so aus wie der Baum für 1, 2, 3, 4, 5, 6, 7, 8 und die (nach 4.2 neue) Wurzel bekommt dann zum ersten Mal wieder vier Kinder und muss aufgespalten werden. === 4.4 Amortisierte Kosten für n beliebige Operationen === Theta(n * log n), siehe [[http://ad-teaching.informatik.uni-freiburg.de/AlgoDatSS2013/vorlesung-8b.pdf#page=12|Vorlesung 8b, Folie 12]]. == AUFGABE 5 (Graphen) == === 5.1 Dijkstra von S nach Z === Hier erst nochmal der Graph mit Buchstaben als Knotennamen (A, B, C, D, E, F, G, H, J). Startknoten ist A, Zielknoten ist G (nicht J). |
Darstellung durch 3 x 3 Adjazentmatrix (x = spezieller Eintrag, der bedeutet "keine Kante"): |
| Line 138: | Line 136: |
| A --1-- B --1-- C | | | 2 2 2 | | | D --1-- E --1-- F | | | 2 2 2 | | | G --1-- H --1-- J |
x 2 x x x 2 2 x x |
| Line 149: | Line 141: |
| Dann macht Dijkstra Folgendes: | === 4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten === |
| Line 152: | Line 144: |
| Runde 1: dist[A] = 0 gelöst, dist[B] = 1, dist[D] = 2 Runde 2: dist[B] = 1 gelöst, dist[C] = 2 neu, dist[E] = 3 neu, dist[D] = 2 unverändert Runde 3: dist[D] = 2 gelöst, dist[G] = 4 neu, dist[C] = 2 und dist[E] = 3 unverändert Runde 4: dist[C] = 2 gelöst, dist[F] = 4 neu, dist[G] = 4 und dist[E] = 3 unverändert Runde 5: dist[E] = 3 gelöst, dist[H] = 5 neu, dist[F] = 4 und dist[G] = 4 unverändert Runde 6: dist[G] = 4 gelöst. |
# 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 |
| Line 160: | Line 152: |
| Bemerkung 1: man kennt den richtigen Wert für dist[G] zwar schon in Runde 4, aber aufhören darf man erst in Runde 6. Da sollte man dann aber auch aufhören. Bemerkung 2: Man hat an zwei Stellen die Auswahl zwischen zwei Knoten für die nächste Runde. In Runde 3 könnte man statt D auch C lösen (beide dist = 2). In Runde 6 könnte man statt G auch erst F lösen (beide dist = 4), dann würde G erst in Runde 7 gelöst. === 5.2 Programm zur Berechnung des Durchmessers === |
=== 4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix === |
| Line 167: | Line 155: |
| void computeDiameter(Graph G) { int maxSoFar = -INFINITY; for (int i = 0; i < G.size(); i++) { int[] dist = computeDijkstra(G, i); for (int j = 0; j < G.size(); j++) { if (dist[j] != INFINITY && dist[j] > maxSoFar) { maxSoFar = dist[j]; } } } return maxSoFar; } |
# 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 |
| Line 179: | Line 166: |
| === 4.4 Laufzeit der Funktionen aus Aufgabe 4.2 und Aufgabe 4.3 === | |
| Line 180: | Line 168: |
| == AUFGABE 6 (String Matching) == | 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. |
| Line 182: | Line 171: |
| === 6.1 Knuth-Morris-Pratt für T = BANANANENA und P = NANA === Vorberechnung für das Muster (Positionen hier 1 bis 4, nicht 0 bis 3, kann man aber machen wie man will): {{{ 1234 NANA 0012 }}} Ausführung des Algorithmus (Positionen hier 1 bis 10, nicht 0 bis 9, kann man aber machen wie man will): {{{ 1234567890 BANANANENA N N NANA ... MATCH an Positionen 3 bis 6 in T, weiter in T ab Stelle 7 - P[4] = 5 NANA ... MISMATCH an Position 8 in T / 4 in P, weiter in T ab Stelle 8 - P[3] = 7 NA ... MISMATCH an Position 8 in T / 2 in P, weiter in T ab Stelle 8 - P[1] = 8 N ... ENDE, weil < |P| Positionen in T übrig }}} === 6.2 Anzahl Vergleiche des trivialen Algorithmus === 14 Vergleiche, wenn der Algorithmus aufhört wenn <|P| Positionen in T übrig. Sonst 18 Vergleiche. Beide Lösungen OK. {{{ 1234567890 BANANANENA N 1 N 1 NANA 4 N 1 NANA 4 N 1 NA 2 ------------- N 1 NA 2 N 1 }}} === 6.3 Maximal viele Vergleiche beim trivialen Algorithmus === T = a...a (n mal), P = a...a (m mal). Dann an jeder Position m Vergleiche (mehr geht nicht). Insgesamt Theta(n * m). |
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 1 (Programmm + Laufzeitbestimmung)
1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2
def secondLargest(A):
max1 = A[0]
max2 = A[1]
if max2 > max1:
max1, max2 = max2, max1
for i in range(2, len(A)):
if A[i] > max2:
if A[i] > max1:
max2 = max1
max1 = A[i]
else:
max2 = A[i]
return max2
1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen
Es gilt offensichtlich Tn >= Tn-1 + Tn-2.
Induktionsanfang: T_1 >= 2 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, 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 u1, u2, u3 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(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.