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 10:23] – 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: | ||
- | * log2(8) | ||
- | * log3(1) | ||
- | * log2(n4) | ||
- | * log10(1n2) | ||
- | * 2log4(n) | ||
- | * logn(n) | ||
- | * loga(b)⋅logb(n) | ||
- | * log2(4n3) | ||
- | * log2(√n) | ||
- | * log2(∑ni=0i) | ||
- | * log3(∏ni=13i) | ||
- | * ∑ni=1n⋅i | ||
- | * ∑nk=02−k | ||
- | * ∑n2k=14−k | ||
- | * ∑ni=12i<_ | ||
- | - Wahr oder falsch? Begründe deine Antwort. | ||
- | * 1=Θ(3) | ||
- | * 2=Ω(1) | ||
- | * 3=ω(2) | ||
- | * n=ω(1) | ||
- | * f=O(g) und g=O(f)⟺f=Θ(g) | ||
- | * ∑nk=02−k=O(1) | ||
- | * log2(n)=Θ(log8(n)) | ||
- | * 2log2(2n)=O(n2) | ||
- | * f1=Ω(g1) und f2=Ω(g2)⟹f1+f2=Ω(g1+g2) | ||
- | * f=o(g)⟺f=O(g) | ||
- | * f(n)=g(n2)⟹f=Ω(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 | ||
- | </ | ||
- | - < | ||
- | k = 1 | ||
- | for i=sqrt(n), 2sqrt(n), | ||
- | k = k + 1 | ||
- | </ | ||
- | |||
- | Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten: | ||
- | - Θ(1) | ||
- | - Θ(n) | ||
- | - Θ(n3) | ||
- | - Θ(2n) | ||
- | - Θ(√n) | ||
- | - Θ(logn) | ||
- | - Θ(logn3) | ||
- | - Θ(n!) | ||
- | |||
- | Was tut der folgende Pseudocode? Angenommen n=2k für ein beliebiges k∈N. | ||
- | < | ||
- | function raetsel(Array A[0, | ||
- | { | ||
- | 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 | ||
- | } | ||
- | } | ||
- | } | ||
- | </ | ||
- | Welche Ausgabe liefert raetsel(A, 0, 7) für A = [1, | ||
- | ==== 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) | ||
- | else | ||
- | return 0 | ||
- | </ | ||
- | |||
- | Lösen: | ||
- | - T(1)=0 und T(n)=2T(n2)+n2 für n>1 | ||
- | - T(2)=1 und T(n)=T(n2)+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, | ||
- | ==== 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 '' | ||
- | ==== 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. | ||
- | * Erweitere die Datenstruktur Stack um die Funktion '' | ||
- | * 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 ==== | ||
- | |||
- | ==== Graphen ==== | ||
- | |||
- | ==== Tiefensuche, | ||
- | |||
- | ==== Heaps ==== | ||
- | |||
- | ==== Binäre Suchbäume ==== | ||
- | |||
- | ==== AVL-Bäume ==== | ||
- | |||
- | ==== (a, | ||
- | |||
- | ===== Tag 3 ===== | ||
- | |||
- | ==== Hashing ==== | ||
- | |||
- | ==== Rekursive Programmierung ==== | ||
- | |||
- | ==== Datenstrukturen entwerfen ==== | ||
- | |||