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)] 3. for i in range(1, n): 4. matrix.append([i]) 5. for j in range(1, m): 6. matrix[i].append(matrix[i-1][j] + matrix[i][j-1]) 7. return matrix[n-1][m-1]