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 logb1 und logb2 nur um einen (positiven) konstanten Faktor ln b1 / ln b2 untertscheiden, für b1, b2 > 1.
Für alle n >= 2 ist log n >= 1 und damit, log n <= (log n)2, also gilt O mit n0 = 2 und C = 1.
Falls Theta, müsste auch Omega sein, dann würde es C, n0 geben, so dass für alle n >= n0 gilt, dass log n >= C * log2 n. Dann wäre aber log n <= 1/C für alle n >= n0. Aber z.B. für n = max(n0, 21 + 1/C) ist n >= n0 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(n2). 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(n2).
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) = x2 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:
0 : 5, 10 1 : 1, 4, 6, 9 2 : nix 3 : nix 4 : 2, 3, 7, 8
2.2 Beweis, dass h(x + 5) = h(x)
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)
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| / mDa 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 = 21. Induktionsschritt i -> i + 1: Nach Induktionsvoraussetzung ist die Kapazität nach der i-ten Reallokation 2i. Es wird also das nächste Mal beim Einfügen des (2i + 1)-sten Elementes wieder realloziert, und dann auf 2 * 2i = 2i+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 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).