Differences

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

--- repds15:hausaufgaben [2015/08/28 10:04] – [Arrays] 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)$
-==== 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!)$
-Was tut der folgende Pseudocode? Angenommen $n = 2^k$ für ein beliebiges $k \in \mathbb{N}$.
-<code>
-function raetsel(Array A[0,..,n-1], int l, int r)
-{
-    if l == r
-    {
-        return A[l]
-    }
-    else
-    {
-        grenze = floor( (l+r)/2 )        // untere Gaußklammer
-        m_l = raetsel(A, l, grenze)
-        m_r = raetsel(A, grenze + 1, r)
-        if m_l > m_r
-        {
-            return m_l
-        }
-        else
-        {
-            return m_r
-        }
-    }
-}
-</code>
-Welche Ausgabe liefert raetsel(A, 0, 7) für A = [1,5,3,10,2,11,9,4]?
-==== 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.
-  * Entwerfe eine Datenstruktur, die Zahlen aus dem Intervall {0,1,...,n-1} speichert und die Operationen ''lookup(x)'', ''insert(x)'' und ''remove(x)'' in der Laufzeit O(1) unterstützt.
-==== 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.
-  * Die Datenstruktur Liste aus der Vorlesung ist eine einfach verkettete Liste, d.h. jedes Element hat nur einen Zeiger ''next'' auf seinen Nachfolger in der Liste. Erweitere die Datenstruktur, sodass auch jeder Vorgänger über einen Zeiger erreicht werden kann. Welche Veränderungen ergeben sich für die Funktionen ''insert'' und ''remove''?
-==== 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.