|
Size: 9676
Comment:
|
Size: 2214
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 6: | Line 6: |
| === 1.1 Programm für zweitgrößte Zahl === | === 1.1 Funktion zur Berechnung der zweitgrößten Zahl in einem Feld der Größe >= 2 === |
| Line 27: | Line 27: |
| === 1.3 Funktion zur Berechnung von F_n in Zeit O(n) === | === 1.3 Funktion zur Berechnung von F_n in Zeit O(n), für n >= 2 === |
| Line 78: | Line 78: |
| == AUFGABE 4 (Graphen) == | |
| Line 79: | Line 80: |
== AUFGABE 1 (Diverses) == === 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: |
=== 4.2 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzlisten === |
| Line 116: | Line 83: |
| 0 : 5, 10 1 : 1, 4, 6, 9 2 : nix 3 : nix 4 : 2, 3, 7, 8 |
# 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 123: | Line 91: |
| === 2.2 Beweis, dass h(x + 5) = h(x) === | === 4.3 Funktion zur Berechnung der Anzahl Kanten mit Adjazenzmatrix === |
| Line 126: | Line 94: |
| 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) |
# 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 131: | Line 104: |
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) }}} === 2.3 Pr(h(x) = i) für i = 0, 1, 2, 3, 4 === 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: {{{ 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 }}} === 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 {{{ 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 }}} Da H1 und H2 disjunkt ist ein h aus H entweder in H1 oder in H2, und |H| = |H1| + |H2|, und somit {{{ |{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. }}} 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 === {{{ #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 }}} == AUFGABE 4 (a,b-Bäume) == === 4.1 (2,3)-Baum nach Einfügen von 1, 2, 3, 4, 5, 6 === {{{ 2|4|6 / | \ 1|2 3|4 5|6 / \ / \ / \ 1 2 3 4 5 6 }}} === 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). {{{ A --1-- B --1-- C | | | 2 2 2 | | | D --1-- E --1-- F | | | 2 2 2 | | | G --1-- H --1-- J }}} Dann macht Dijkstra Folgendes: {{{ 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. }}} 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 === {{{ 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; } }}} == AUFGABE 6 (String Matching) == === 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). |
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]
max2 = A[i]
return max2
1.2 Laufzeit rekursive Berechnung Fibonacci-Zahlen
TODO
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 Suchen und Löschen eines Elementes aus einem Feld
def removeFromArray(A, x):
i = 0
while i < len(A) and A[i] != x:
i = i + 1
if i < len(A):
A[i], A[-1] = A[-1], A[i]
A.pop()
2.2 Löschen eines Elementes aus einer Hashtabelle
def removeFromHashTable(T, h, x):
removeFromArray(T[h(x)], x)
AUFGABE 3 (Binäre Heaps)
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
AUFGABE 4 (Graphen)
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