Differences

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

--- repds15:hausaufgaben [2015/08/28 13:39] – [Hashing] 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}$ (Tipp: $\int_1^n ... di$)
-  - 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)
-    else
-        return 0
-</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.
-===== Tag 2 =====
-==== Bäume ====
-  * Was ist ein Baum?
-  * Was ist ein (vollständig) binärer, ternärer, k-ärer Baum?
-  * Kann die Datenstruktur Liste auch als Baum aufgefasst werden? Ist ein Baum nur eine verzweigte Liste?
-  * Welche Datenstrukturen für allgemeine Bäume kennen wir?
-  * Entwerfe eine Datenstruktur für einen ternären Baum. Wieso sind Eltern-Arrays nicht geeignet?
-  * Gib eine rekursive Definition für Bäume an: Wie sieht ein Baum im Basisfall (Rekursionsanfang) aus? Wie sieht der Rekursionsfall (Rekursionsschritt) aus?
-==== Graphen ====
-  * Welche Datenstrukturen kennen wir für Graphen?
-  * Nenne Vor- und Nachteile dieser Datenstrukturen.
-==== Tiefensuche, Breitensuche, Prä-/In-/Postorder, Topologisches Sortieren ====
-  * Führe Tiefen- und Breitensuche an einem selbst gewählten Beispiel aus. Dabei soll jeder Knoten seine Nachbarn in aufsteigender Reihenfolge speichern.
-  * Wieso müssen wir uns bei der Tiefen- und Breitensuche in allgemeinen Graphen merken, welche Knoten wir schon besucht haben?
-  * Führe Prä-/In-/Postorder auf einem selbst gewählten Baum aus.
-  * Finde einen Baum, bei dem alle drei Traversierungen das gleiche Ergebnis liefern.
-  * Gib eine rekursive Implementierung der Postorder-Traversierung an. Orientiere dich an Algorithmus 4.1 (S. 96 im Skript).
-  * Was hat die Tiefensuche auf Bäumen mit Prä-/In-/Postorder zu tun?
-  * Welche Laufzeit hätten die Tiefen- und die Breitensuche, wenn der Graph als Adjazenzmatrix statt als Adjazenzliste vorliegen würde?
-  * Benutzt die (nicht rekursive) Tiefensuche einen Stack oder eine Queue? Wie sieht es mit der Breitensuche aus?
-  * Unter welchen Voraussetzungen kann ein Graph topologisch sortiert werden?
-  * Ist diese Sortierung immer eindeutig?
-  * Gib eine topologische Sortierung an einem selbst gewählten Beispiel an.
-==== Heaps ====
-  * Was ist ein Heap?
-  * Was ist der Unterschied zwischen Min- und Max-Heaps?
-  * In welcher Laufzeit kann bei einem Min-Heap (Max-Heap) auf das kleinste Element zugriffen werden?
-  * Was ist die Heap-Ordnung?
-  * Richtig oder falsch: Ein Heap ist ein binärer Suchbaum?
-  * Gib ein Beispiel für einen Heap an, der ein binärer Suchbaum ist.
-  * Füge eine selbst gewählte Folge von acht Zahlen in einen Min-Heap ein.
-  * Entferne alle Zahlen mit ''delete_min()'' und gib die Reihenfolge an. Was fällt dir auf?
-  * Benutze diese Beobachtung für folgendes: Schreibe ein Programm in Pseudocode, das ein Array A[1,...,n] als Eingabe erhält und dessen Elemente in aufsteigender Reihenfolge ausgibt.
-  * Wahr oder falsch: Wenn wir die Folge der einzufügenden Zahlen schon vorher kennen, kann das Einfügen aller Zahlen in den Heap in linearer Laufzeit realisiert werden.
-  * Entwerfe einen Heap, der als ternärer Baum aufgefasst werden kann.
-==== Binäre Suchbäume ====
-  * Was ist ein binärer Suchbaum?
-  * Können auch Buchstaben in einem binären Suchbaum verwaltet werden?
-  * Welche Tiefe hat ein binärer Suchbaum mit n Schlüsseln im besten und im schlechtesten Fall?
-  * Was passiert bei ''remove(5)'', wenn der Baum den Schlüssel 5 gar nicht enthält?
-  * Was passiert bei ''insert(5)'', wenn der Baum den Schlüssel 5 bereits enthält?
-  * Gib einen binären Suchbaum mit zehn Knoten an.
-  * Entferne die Wurzel.
-  * Entferne einen weiteren inneren Knoten
-      * mit einem Kind.
-      * mit zwei Kindern.
-  * Entferne ein Blatt.
-  * In welcher Laufzeit kann die Folge 1,2,...,n/2 in einen binären Suchbaum eingefügt werden?
-  * Gib eine Folge an, die in möglichst geringer Laufzeit eingefügt werden kann. Tipp: Breitensuche auf Bäumen.
-==== AVL-Bäume ====
-  * Was ist ein AVL-Baum?
-  * Wahr oder falsch: Jeder AVL-Baum ist ein binärer Suchbaum.
-  * Wahr oder falsch: Jeder binäre Suchbaum ist ein AVL-Baum.
-  * Wozu dienen die Rotationen?
-  * Was ist die Tiefe eines AVL-Baums mit n Knoten im besten und im schlechtesten Fall?
-  * Welche Nachteile hat die Verwendung von AVL-Bäumen gegenüber üblichen binären Suchbäumen?
-  * Füge die Zahlen 1,2,...,15 in einen anfangs leeren AVL-Baum ein. Gib bei Balance-Grad-Verletzungen außerdem an, ob es sich um einen ZickZick, ZickZack, ZackZick oder ZackZack-Fall handelt.
-==== (a,b)-Bäume ====
-  * Was ist ein (a,b)-Baum?
-  * Was bedeutet das a?
-  * Was bedeutet das b?
-  * Wie viele Kinder hat ein innerer Knoten, der 3 Schlüssel speichert?
-  * Füge die folgenden Zahlen in einen anfangs leeren (2,3)-Baum ein: 1, 4, 6, 9, 5, 11, 2, 3, 12, 10, 7, 8. Lösche anschließend wieder alle Schlüssel in der gleichen Reihenfolge.
-===== Tag 3 =====
-==== Hashing ====
-  * Was ist Hashing?
-  * Was ist eine Kollision?
-  * Welche Laufzeit haben ''insert(x)'', ''remove(x)'' und ''lookup(x)'' im besten und im schlechtesten Fall?
-  * Berechne $3x \mod 5$ für alle $x \in \{0, 1, 4, 5, 10, 12\}$.
-  * Fülle eine Wertetabelle für $f(x) := 3x \mod 11$
-  * Füge die Schlüssel 9, 20, 31, 42, 53 in eine Hash-Tabelle ein und gib jeweils die Reihenfolge der getesteten Zellen an:
-    * Hashing mit Verkettung
-    * Hashing mit linearem Austesten
-    * doppeltes Hashing mit $h(x) := f(x) + i\cdot g(x) \mod 11$, wobei $g(x) := 5 - (x \mod 5)$.
-    * Was ist der Auslastungfaktor $\lambda$ bei den beiden letzten Verfahren? Hängt er davon ob, ob linear ausgetestet oder doppelt gehasht wurde?
-^ x   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
-^ f(x)|   |   |   |   |   |   |   |   |   |   |    |
-^ x   | 0 | 1 | 2 | 3 | 4 |
-^ g(x)|   |   |   |   |   |
-==== Rekursive Programmierung ====
-==== Datenstrukturen entwerfen ====