Skizze der Lösungen zur Klausur zur Vorlesung "Informatik II: Algorithmen und Datenstrukturen" im SS 2017

Alle Angaben ohne Gewähr + hier wird sich in den nächsten Stunden noch einiges ändern.

AUFGABE 1 (O-Notation und Laufzeitbestimmung), Korrektur: Claudius Korzen

1.1 (5 Punkte) sqrt(n) = O(n) aber nicht Theta(n)

sqrt(n) <= 1 * n für alle n >= 1. Daraus folgt sqrt(n) = O(n) mit C = 1 und n₀ = 1. (2 Punkte)

Angenommen sqrt(n) = Omega(n). Dann würde es C und n₀ geben, so dass für alle n >= n0 gilt: sqrt(n) >= C * n. Letzter Ausdruck impliziert n >= C² * n² (auf beiden Seiten quadrieren), darauf folgt 1 >= C² * n und somit n <= 1 / C². Das kann aber nicht sein für alle n >= n0. Also war die Annahme, dass sqrt(n) = Omega(n) falsch. Und damit ist sqrt(n) nicht Theta(n).

1.2 (5 Punkte) Umformung von 2 hoch log_4 n

2 hoch (log₄n) = (4 hoch (1/2)) hoch (log₄ n) = (4 hoch log₄ n) hoch (1/2) = n hoch 1/2 = sqrt(n)

1.3 (10 Punkte) Laufzeit für T(n) <= 2 * T(n/4) + A * sqrt(n)

Durch wiederholtes Einsetzen der Formel auf der rechten Seite (analog dazu, wie wir es in VL2a und für das ÜB2 gemacht haben), erhält man:

T(n)
<= 2 * T(n/4) + A * sqrt(n)
<= 2 * (2 * T(n/4²) + A * sqrt(n/4)) + A * sqrt(n) = 2² * T(n/4²) + 2 * sqrt(n)
<= 2² * (2 * T(n/4³) + A * sqrt(n/4²)) + 2 * sqrt(n) = 2³ * T(n/4³) + 3 * A * sqrt(n)
<= ...
<= 2^k * T(n/4^k) + k * A * sqrt(n)

Für k = log₄ n enthält man T(n) <= sqrt(n) + log₄ n * A * sqrt(n) = Theta(sqrt(n) * log n)

AUFGABE 2 (Programm, Laufzeitbestimmung, Hashing), Korrektur: Markus Näther

2.1 (5 Punkte) Funktion num_unique, die Anzahl der verschiedenen Zahlen ausgibt

def num_uniq(elements):
    uniqs = {}
    for x in input:
        if x not in uniqs:
            uniqs[x] = 1
    return len(unqis.keys())

Wenn man len(...) nicht kannte, konnte man auch einfach explizit mitzählen.

2.2 (5 Punkte) Laufzeit der Funktion num_unique aus Aufgabe 2.1

Es gibt n Schleifendurchläufe. Annahme: das "not in" und das "uniqs[x] = 1" gehen amortisiert in Zeit Theta(1). Dann ist die Laufzeit insgesamt Theta(n).

2.3 (5 Punkte) Erwartungswert der Ausgabe, falls Elemente zufällig aus {0, 1}

Pr(alle Elemente 0) = 2^-n
Pr(alle Elemente 1) = 2^-n
PR(der Rest) = 1 - 2 * 2^-n

Nach der Definition des Erwartungswertes ist dann
E(Anzahl verschiede Elemente) = 1 * 2^-n + 1 * 2^-n + 2 * (1 - 2 * 2^-n) = 2 * (1 - 2^-n).

Für n = 3 ist das 1.75

2.4 (5 Punkte) 1-Universalität der gegebenen Klasse

Die Klasse hat nur 1 Element. Laut Definition ist sie dann 1-universell, wenn für jedes Schlüsselpaar x, y in U mit x != < gilt, dass |{h in H: h(x) == h(y)}| <= 1/m. Da unter h kein solches Schlüsselpaar kollidiert, ist die linke Seite = 0. Damit ist diese Klasse 1-universell.

AUFGABE 3 (Potenzialfunktion), Korrektur: Björn Buchhold

3.1 (5 Punkte) Funktion binary_inc, die einen Binärzähler der Länge n, gegeben als Feld, hochzählt

def binary_inc(counter):
    for i in range(len(counter) - 1, -1, -1):
        if counter[i] == 1:
            counter[i] = 0
        else:
            counter[i] = 1
            return
    return

3.2 (5 Punkte) Laufzeit von binary_inc als Theta(...) in Abhängigkeit von geeigneter Größe

Sei m die Anzahl Nullen "von rechts" (also bis zur ersten 1 bzw. n wenn alle 0) nach der Operation. Dann ist die Laufzeit gerade Theta(m). Begründung: die Schleife läuft von rechts nach links durch und in jeden Schleifendurchlauf wird das entsprechende Element auf 0 gesetzt und dann am Ende (falls nicht alle auf 0 gesetzt) eine 1

3.3 (5 Punkte) Gesamtlaufzeit von 2^n aufeinanderfolgenden Aufrufen

Sei Phi_i die Anzahl Nullen "von rechts" (wie oben) nach der i-iten Operation.
Fall 1: Phi_i = 0. Dann hat die Operation einfach nur die letzte Stelle erhöht und die Kosten waren Theta(1) und das Potential hat sich um 1 geändert.
Fall 2: Phi_i > 0. Dann ist T_i = Theta(Phi_i) gemäß Aufgabe 3.2 und vor der Operation stand an der letzten Stelle eine 1, also Phi_i-1 = 0.

In beiden Fällen ist T_i <= A + B * (Phi_i - Phi_i-1), für geeignete A und B. Damit ist die Gesamtlaufzeit Theta(2ⁿ).

3.4 (5 Punkte) Gesamtlaufzeit, wenn bei einem anderen Zählerstand begonnen wird

Die Kosten sind identisch. Begründung: die Menge der Argumente, mit denen die Funktion aufgerufen wird, ist identisch. Nur die Reihenfolge ist eine andere.

AUFGABE 4 (Bäume), Korrektur: Axel Lehmann

4.1 (5 Punkte) Vollständiger binärer Baum der Tiefe 2 (3 Ebenen), der die Heapeigenschaft erfüllt, aber kein binärer Suchbaum ist

          1
        /    \
       2      3
      / \    / \
     4   5  6   7

Begründung: Heapeigenschaft erfüllt (jeder Knoten ist größer als sein Elternknoten), aber kein binärer Suchbaum (zum Beispiel müsste für die Wurzel gelte: größer als linkes Kind, kleiner als rechtes Kind; das ist nicht der Fall).

4.2 (5 Punkte) Vollständiger ternärer Baum der Tiefe 2 (3 Ebenen), mit Knoten von 1 bis 13 durchnummeriert

               1
        /      |      \
       2       3       4
     / | \   / | \   / | \
    5  6  7  8 9 10 11 12 13

4.3 (5 Punkte) Anzahl Knoten in einem vollständigen ternären Baum in Abhängigkeit der Tiefe d

Nehmen wir an, die Wurzel ist auf Tiefe 0. Dann:<<BR> Anzahl Knoten mit Tiefe 0: 1 = 3⁰
Anzahl Knoten mit Tiefe 1: 3 = 3¹
Anzahl Knoten mit Tiefe 2: 9 = 3²
Usw.

Anzahl Knoten bei Gesamttiefe d: 3⁰ + 3¹ + ... + 3^d
Laut gegebener Formel ist das: (3^d+1 - 1) / (3 - 1) = 1/2 * (3^d+1 - 1)

4.4 (5 Punkte) Indizes der Kinder und des Elternknoten für Knoten mit Index i

Indizes Kinder: 3i - 1, 3i, 3i + 1
Index Elternknoten: (i + 1) / 3 abgerundet

AUFGABE 5 (Graphen), Korrektur: Niklas Schnelle

5.1 (5 Punkte) Adjazenzlisten und Länge der kürzesten Wege

Die Adjazentlisten sehen so aus (wenn jede ungerichtete Kante, als Kante in beide Richtungen eingetragen wird):

u₁: u₂, u₃ ... u₂: u₁, u₃, u₄ ... u₃: u₁, u₂, u₅ ... u₄: u₂ ... u₅: u₃

Die Längen der kürzesten Wege:

Für {u₁, u₂}, {u₁, u₃}, {u₂, u₃}, {u₂, u₄}, {u₃, u₅} : jeweils 1
Für {u₁, u₄}, {u₁, u₅}, {u₂, u₅}, {u₃, u₄} : jeweils 2
Für {u₄, u₅}: 3

5.2 (5 Punkte) Funktion für Länge des kürzesten Weges zwischen u und v

def dist(adjacency_lists, u, v):
    visited = {}
    nodes = [(u, 0)]    
    while len(nodes) > 0:
        (x, dist) = nodes.pop(0)
        if x in visited: continue
        visited[x] = 1
        if x == v: return dist
        for y in adjacency_lists[x]:
           nodes.append((y, dist + 1))

Bemerkung: da der Graph zusammenhängend ist, wird v sicher erreicht und man braucht kein zusätzliches return am Ende.

5.3 (5 Punkte) Laufzeit der Funktionen dist

Wie bei BFS wird jeder Knoten und jede Kante genau einmal angeschaut.
Die Laufzeit ist deshalb Theta(n + m).
Da der Graph zusammenhängend ist, und somit m >= n - 1, ist das Theta(m).

AUFGABE 6 (String-Suche), Korrektur: Hannah Bast

6.1 (10 Punkte) Funktion für vereinfachten Karp-Rabin mit Musterlänge 3

def num_hits(T, P):
    if len(T) < 3: return 0
    w = 100 * T[0] + 10 * T[1] + T[2]
    p = 100 * P[0] + 10 * P[1] + P[2]
    hit_count = 0 
    for i in range(3, len(T)):
       if w == p: hit_count += 1
       w = 10 * (w % 100) + T[i]
    return hit_count

6.2 (5 Punkte) Anzahl Blockoperationen der Funktion num_hits

Die Funktion geht einmal von vorne nach hinten durch das Feld der Länge n. Die Anzahl Blockoperationen ist von daher Theta(n / B).

6.3 (5 Punkte) Erwartete Anzahl Treffer bei zufälligem Text und Muster

Sei I_i = 1 genau dann wenn das Muster an Stelle matched.

Die Wahrscheinlichkeit, dass eine feste Stelle des Musters zu einer festen Stelle des Textes passt ist 10 * 1/10 * 1/10 = 1/10. Also ist Pr(I_i = 1) = 1/1000, für i = 0, ..., n-3 (an der vorletzten und letzten Stelle kann ein Muster der Länge 3 nicht mehr matchen).

Die erwartete Anzahl Matches ist gerade sum_i=0,...,n-3 E I_i = sum_i=0,...,n-3 Pr(I_i = 1) = (n - 2)/1000. Für n = 3 ist das 1/1000. Für n = 1002 ist das 1.