Differences

This shows you the differences between two versions of the page.

--- repds15:hausaufgaben [2015/08/28 09:12] – [Stacks] 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} <\underline{\qquad}$
-  - 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?
-  - <code>
-k = 1
-for i=1,2,...,n
-    k = k + 1
-</code>
-  - <code>
-k = 1
-for i=1,2,...,n
-    k = k + 1
-for j=1,2,...,100
-    k = k + 2
-</code>
-  - <code>
-k = 1
-for i=1,2,...,n*n
-    k = k + 2
-</code>
-  - <code>
-k = 1
-for i=n,n/2,n/4...,1
-    k = k + 1
-</code>
-  - <code>
-k = 1
-for i=1,2,...,n
-    k = k + i
-</code>
-  - <code>
-k = 1
-while i < n
-    i = i + i
-    k = k + 1
-</code>
-  - <code>
-i = 0
-k = 0
-while i < n
-    i = i + k
-    k = k + 1
-</code>
-  - <code>
-k = 1
-for i=sqrt(n), 2sqrt(n),...,n
-   k = k + 1
-</code>
-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:
-  - <code>
-def f(n):
-    if n == 1
-        return 1
-    else
-        return n + f(n-1)
-</code>
-  - <code>
-def g(n):
-    if n > 1:
-        return g(n/2)
-</code>
-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/unterste Element?
-  * 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.
-  * Erweitere die Datenstruktur Stack um die Funktion ''bottom()'', die das unterste Element des Stacks in Laufzeit O(1) ausgibt.
-  * 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.