Skizze der Lösungen zur Nachklausur zur Vorlesung "Informatik II: Algorithmen und Datenstrukturen" im SS 2017
Alle Angaben ohne Gewähr.
AUFGABE 1 (O-Notation, Laufzeitbestimmung, Programm), Korrektur: Claudius Korzen
1.1 (5 Punkte) sqrt(n^2) = O(2^n) aber nicht Theta(2^n)
1. L'Hôpital #1: lim n^2 / 2^n = lim 2n / (ln 2 * 2^n) = 2 / ln 2 * lim n / 2^n 2. L'Hôpital #2: lim n / 2^n = lim 1 / (ln 2 * 2^n) 3. Der zweite Grenzwert ist offensichtlich 0 für n gegen unendlich 4. Damit gilt O(...) aber nicht Theta(...)
1.2 (5 Punkte) Ausgabe der Funktion in einer 4 x 4 Tabelle
0 1 2 3 1 2 4 7 2 4 8 15 3 7 15 30
1.3 (5 Punkte) Beweisen oder widerlegen Sie T(n, n) = Theta(n^2)
1. Es gilt T(n, n) >= T(n - 1, n) + T(n, n - 1) >= 2 * T(n - 1, n - 1) 2. Damit T(n, n) >= 2^n und somit Omega(2^n) 3. Damit nach Aufgabe 1.1 sicher nicht Theta(n^2)
1.4 (5 Punkte) Funktion mit selber Ausgabe und Laufzeit O(n * m)
1. def ftw(n, m): 2. matrix = [[i for i in range(m + 1)]] 3. for i in range(1, n + 1): 4. matrix.append([i]) 5. for j in range(1, m + 1): 6. matrix[i].append(matrix[i-1][j] + matrix[i][j-1]) 7. return matrix[n][m]
AUFGABE 2 (Hashing), Korrektur: Axel Lehmann
2.1 (5 Punkte) Cuckoo Hashing mit m = 4, h1(x) = x mod 4, h2(x) = x^2 mod 4, Operationen: insert(7), insert(3), insert(5)
insert(7) -> h1(7) = 3, h2(7) = 1 -> T = [x, x, x, 7] insert(3) -> h1(3) = 3, h2(3) = 1 -> T = [x, 7, x, 3] insert(5) -> h1(5) = 1, h2(5) = 1 -> T = [x, 5, x, 7] und für die 3 ist kein Platz mehr (Zyklus)
2.2 (5 Punkte) Funktion, die nachprüft, ob ein insert gelingen wird
1. def check_insert(T, x): 2. i = h1(x), i0 = h1(x) 3. while True: 4. if T[i] == -1: 5. return True 6. x = T[i] 7. i = h1(x) if h1(x) != i else h2(x) 8. if i == i0: 9. return False
2.3 (5 Punkte) Wahrscheinlichkeit, dass Pr(h1(x) = h2(x)) für zufällige natürliche Zahl x
1. h1(x) = 0, 1, 2, 3, 0, 1, 2, 3, ... 2. h2(x) = 0, 1, 0, 1, 0, 1, 0, 1, ... 3. h1(x) = h2(x) genau dann wenn x mod 4 = 0 oder x mod 4 = 1 4. Die Wahrscheinlichkeit ist also 1/2
2.4 (5 Punkte) Beweis oder Gegenbeispiel, dass H = {h0, ..., hm-1 } 1-universell, mit hi(x) = i
1. Sei m > 1 und x und y zwei beliebige Schlüssel mit x != y
2. Dann ist hi(x) = i = hi(y) für alle i
3. Damit ist |{h : h(x) = h(y)}| = |H|
4. Für 1-Universalität müsste |...| <= |H| / m sein
5. Also nicht 1-universell
AUFGABE 3 (Vermischtes), Korrektur: Hannah Bast
3.1 (5 Punkte) Beweis, dass vollständiger ternärer Baum Tiefe <= floor(log_3 n) hat
1. Auf Tiefe 0 gibt es 1 Knoten 2. Auf Tiefe 1 gibt es 3 Knoten 3. Auf Tiefe d gibt es 3^d Knoten 4. Also n > 3^d 5. Also d < log_3 n <= floor(log_3 n)
3.2 (5 Punkte) Beispielmuster für KMP mit shift Feld 0, 1, 0, 1, 2, 3, 0, 1
DDUDDUXD 01012301
3.3 (5 Punkte) Kosten von Dikstra für Liniengraph mit n Knoten
1. Es gibt n insert Operationen auf der PW 2. Es gibt n deleteMin Operationen auf der PW 3. Es ist zu jedem Zeitpunkt höchstens ein Element in der PW 4. Sowohl insert als auch deleteMin laufen also in konstanter Zeit 5. Die Laufzeit ist damit Theta(n)
3.4 (5 Punkte) Anzahl Blockoperationen von Bubble Sort
1. Wir betrachten die Durchläufe der äußeren Schleife 2. Für i = 0 ist die Anzahl Blockoperationen ceil(n/B) 3. Für i = 1 ist die Anzahl Blockoperationen ceil((n-1)/B) 4. Allgemein ist die Anzahl Blockoperationen des i-ten Durchlaufes ceil((n-i)/B) 5. Addiert über alle Iterationen ergibt das Theta(n^2 / B)