Trace:
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| repds15:hausaufgaben [2015/08/28 09:01] – [Listen] mario | repds15:hausaufgaben [Unknown date] (current) – removed - external edit (Unknown date) 127.0.0.1 | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Hausaufgaben ====== | ||
| - | |||
| - | ===== Tag 1 ===== | ||
| - | ==== Mathematische Grundlagen, Asymptotik, Landau-Notation ==== | ||
| - | |||
| - | - Welche Rechenregeln für Logarithmen gibt es? | ||
| - | - Vereinfache die folgenden Terme: | ||
| - | * $\log_2(8)$ | ||
| - | * $\log_3(1)$ | ||
| - | * $\log_2(n^4)$ | ||
| - | * $\log_{10}\left(\frac{1}{n^2}\right)$ | ||
| - | * $2^{\log_4(n)}$ | ||
| - | * $\log_n(n)$ | ||
| - | * $\log_a(b) \cdot \log_b(n)$ | ||
| - | * $\log_2(4n^3)$ | ||
| - | * $\log_2(\sqrt{n})$ | ||
| - | * $\log_2\left( \sum_{i=0}^n i \right)$ | ||
| - | * $\log_3\left(\prod_{i=1}^n 3^i \right)$ | ||
| - | * $\sum_{i=1}^n n \cdot i$ | ||
| - | * $\sum_{k=0}^n 2^{-k}$ | ||
| - | * $\sum_{k=1}^{\frac{n}{2}} 4^{-k}$ | ||
| - | * $\sum_{i=1}^n \frac{2}{i} < | ||
| - | - Wahr oder falsch? Begründe deine Antwort. | ||
| - | * $1 = \Theta(3)$ | ||
| - | * $2 = \Omega(1)$ | ||
| - | * $3 = \omega(2)$ | ||
| - | * $n = \omega(1)$ | ||
| - | * $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f) \iff f = \Theta(g)$ | ||
| - | * $\sum_{k=0}^n 2^{-k} = \mathcal{O}(1)$ | ||
| - | * $\log_2(n) = \Theta(\log_8(n))$ | ||
| - | * $2^{\log_2(2n)} = \mathcal{O}(n^2)$ | ||
| - | * $f_1 = \Omega(g_1)$ und $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$ | ||
| - | * $f = o(g) \iff f = \mathcal{O}(g)$ | ||
| - | * $f(n) = g(\frac{n}{2}) \implies f = \Omega(g)$ | ||
| - | * $f = o(g) \implies 2^f = o(2^g)$ | ||
| - | |||
| - | ==== Pseudocode und Laufzeitanalyse ==== | ||
| - | Welchen Wert hat k in Abhängigkeit von n nach der Ausführung des Programms? | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + 1 | ||
| - | for j=1, | ||
| - | k = k + 2 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1, | ||
| - | k = k + 2 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=n, | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | for i=1,2,...,n | ||
| - | k = k + i | ||
| - | </ | ||
| - | - < | ||
| - | k = 1 | ||
| - | while i < n | ||
| - | i = i + i | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | - < | ||
| - | i = 0 | ||
| - | k = 0 | ||
| - | while i < n | ||
| - | i = i + k | ||
| - | k = k + 1 | ||
| - | </ | ||
| - | |||
| - | Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten: | ||
| - | - $\Theta(1)$ | ||
| - | - $\Theta(n)$ | ||
| - | - $\Theta(n^3)$ | ||
| - | - $\Theta(2^n)$ | ||
| - | - $\Theta(\sqrt{n})$ | ||
| - | - $\Theta(\log{n})$ | ||
| - | - $\Theta(\log{n^3})$ | ||
| - | - $\Theta(n!)$ | ||
| - | |||
| - | ==== Rekursionsgleichungen aufstellen und lösen ==== | ||
| - | Aufstellen: | ||
| - | - < | ||
| - | def f(n): | ||
| - | if n == 1 | ||
| - | return 1 | ||
| - | else | ||
| - | return n + f(n-1) | ||
| - | </ | ||
| - | - < | ||
| - | def g(n): | ||
| - | if n > 1: | ||
| - | return g(n/2) | ||
| - | </ | ||
| - | |||
| - | Lösen: | ||
| - | - $T(1) = 0$ und $T(n) = 2 T(\frac{n}{2}) + \frac{n}{2}$ für $n > 1$ | ||
| - | - $T(2) = 1$ und $T(n) = T(\frac{n}{2}) + n - 1$ für $n > 2$ | ||
| - | |||
| - | ==== Arrays ==== | ||
| - | * Was ist ein Array? | ||
| - | * Wie sieht ein Array im Arbeitsspeicher aus? | ||
| - | * Wie lang dauert ein Zugriff (lesen oder schreiben) auf das n. Element A[n]? Wieso? | ||
| - | * Schreibe ein Programm in Pseudocode, das ein gegebenes Array A[1,...,n] mit den Werten 2, 4,..., 2n befüllt. | ||
| - | * Schreibe ein Programm in Pseudocode, das die Summe der Einträge dieses Arrays ausgibt. | ||
| - | |||
| - | ==== Listen ==== | ||
| - | * Was ist eine Liste? | ||
| - | * Wie sieht eine Liste im Arbeitsspeicher aus? | ||
| - | * Wie unterscheiden sich Arrays und Listen? | ||
| - | * Welche Zeiger und Funktionen hat die Listen-Implementierung aus der Vorlesung zur Verfügung? | ||
| - | * Wie lange dauert es, das größte Element einer aufsteigend (absteigend) sortierten Liste zu finden? | ||
| - | * Wie lange dauert das Einfügen der Zahl 7 in eine (un)sortierte Liste? | ||
| - | * Wieso ist binäre Suche auf Listen keine gute Idee? | ||
| - | * Schreibe ein Programm in Pseudocode, das beide Aufgaben (sortiert und unsortiert) erledigt. | ||
| - | |||
| - | ==== Stacks ==== | ||
| - | * Was ist ein Stack? | ||
| - | * Wie lange dauert ein Zugriff auf das oberste/ | ||
| - | * Beschreibe, wie mit einer Liste ein Stack implementiert werden kann. | ||
| - | * Schreibe ein Programm, das einen Stack A als Eingabe erhält und den Stack B ausgibt, wobei B die Elemente aus A in umgekehrter Reihenfolge enthält. | ||
| - | * Bonusfrage: Wie werden Stacks in Programmiersprachen beim Aufruf von Funktionen verwendet? | ||
| - | |||
| - | ==== Queues ==== | ||
| - | * Was ist eine Queue? | ||
| - | * Befolgen Queues das Prinzip LIFO oder FIFO? | ||
| - | * Beschreibe die Situation im Supermarkt an der Kasse mithilfe einer Queue. | ||
| - | * Wie würde sich das Einkaufen verändern, wenn Supermarkt-Kassen wie Stacks funktionieren würden? | ||
| - | * Welche Algorithmen aus der Vorlesung verwenden Queues? Wieso? | ||
| - | * Schreibe ein Programm in Pseudocode, das eine Liste L erhält und den Wert jedes Listenelements in eine Queue einfügt. | ||