Hausaufgaben SS2016 - Sommersemester PDF

Preview

Summary

Sommersemester...

Description

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, F. Land M. Rau

14. April 2016

Hausaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 1

Hausaufgabe 1.1 (O-Notation (2 Punkte)) Ordnen Sie die über die folgenden Ausdrücke definierten Funktionen fi : N>0 → R≥0 , i = 3 1, . . . , 13 der Größe nach im Sinne der O-Notation: f1 (n) := n 2 , f2 (n) := loglogn, f3 (n) := nn , √ f4 (n) := 3n , f5 (n) := n, f6 (n) := n3 , f7 (n) := n log n, f8 (n) := n, f9 (n) := n2 , f10(n) := log2 n, f11(n) := 2n , f12 (n) := nε , für 0 < ε < 21 , f13(n) := logn. Hausaufgabe 1.2 (O-Notation (2 Punkte)) Beweisen oder widerlegen Sie die folgenden Aussagen: 1. n2 ∈ O(n), 2. n · log n ∈ O(n2 ), 3. n2 + n ∈ O(n2 ), 4. 3n ∈ O(2n )

Hausaufgabe 1.3 (Vollständige Induktion (3 Punkte)) Sei n ∈ N \ {0}. Beweisen Sie per Induktion: n

∑ i · (i + 1) = i=1

n · (n + 1) · (n + 2) . 3

Hausaufgabe 1.4 (O-Notation (3 Punkte)) Geben Sie für den folgenden Algorithmus die maximale Anzahl der Operationen an und bestimmen Sie die Worst-Case Laufzeit gemäß der O -Notation. Algorithmus O DD E VEN S ORT (A) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

integer n=length(A); for k=0 to n-1 do integer i=1; while iA[i+1] then integer temp=A[i]; A[i]=A[i+1]; A[i+1]=temp; fi i=i+2; od i=0; while iA[i+1] then integer temp=A[i]; A[i]=A[i+1]; A[i+1]=temp; fi i=i+2; od od

Abgabe der theoretischen Aufgaben Donnerstag, den 21. April, bis spätestens 14 Uhr im Schrein.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, F. Land M. Rau

21. April 2016

Hausaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 2

Hausaufgabe 2.1 (Sortieren (3 Punkte)) Sortieren Sie die Sequenz [7, 3, 5, 4, 1, 2, 8, 6] mittels Bubble Sort. Hausaufgabe 2.2 (Induktion (3 Punkte)) Zeigen Sie, dass für alle n ∈ N \ {0, 1} Fn ≥

 1 + √5 n−2 2

.

Hausaufgabe 2.3 (Induktion (4 Punkte)) Zeigen Sie, dass der Algorithmus von Euclid zum Berechnen des größten gemeinsamen Teilers von zwei Zahlen a, b ∈ N eine Laufzeit von O(log(a + b)) besitzt. Verwenden und beweisen Sie dabei die folgende Aussage: Falls die Prozedur E UCLID k mal aufgerufen wird und a > b ist, so gilt a ≥ Fk und b ≥ Fk−1 , wobei Fk die k-te Fibonacci Zahl ist. Hinweis: Ist a > b so gilt: a = (a div b) · b + (a mod b) Programmieraufgabe 2.4 Implementieren Sie (a) die lineare Suche und (b) die binäre Suche zum Finden der Position (beginnend bei 0) einer Zahl in einem Array. Falls das Array die gesuchte Zahl nicht enthält, soll -1 zurückgegeben werden. Sie können davon ausgehen, dass das Array aufsteigend sortiert ist. (c) Die Testfälle enthalten Instanzen mit Listen der Längen 125.000, 250.000, 500.000 und 1.000.000. Erklären Sie das unterschiedliche Laufzeitverhalten der beiden Algorithmen.

Abgabe der theoretischen Aufgaben sowie der Programmieraufgaben Donnerstag, den 28. April, bis spätestens 14 Uhr. Die Abgabe der theoretischen Aufgaben erfolgt im Schrein, die Abgabe der Programmieraufgaben im iLearn.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, F. Land M. Rau

28. April 2016

Hausaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 3

Hausaufgabe 3.1 (Mergesort (2 Punkte)) Sortieren Sie die Sequenz [7, 3, 5, 4, 1, 2, 8, 6] mittels Mergesort. Hausaufgabe 3.2 (Induktion (2 Punkte)) Beweisen Sie, dass

n

∑ i2i ∈ Θ(n2n) i=1

Hausaufgabe 3.3 (Dynamische Programmierung (3 Punkte)) Überlegen Sie sich die Rekursionsvorschrift für ein dynamisches Programm und geben Sie den Algorithmus in Pseudocode an um folgendes Problem zu lösen. Stellen Sie sich vor Sie arbeiten in einer Behörde und haben ein bestimmtes Budget B ∈ N das Sie ausgeben müssen. Dabei ist ein Kursangebot K1 , . . . , Kn gegeben wobei jeder Kurs Ki gewisse Kosten Ci ∈ N hat und einen gewissen Organisationsaufwand Ai ∈ N benötigt. Gesucht ist eine Auswahl von Kursen, so dass mindestens das Budget B ausgegeben wird und der gesamte Organisationsaufwand minimal ist. Hausaufgabe 3.4 (Rekurrenz (3 Punkte)) Seien a, b ∈ N>0 gegeben und sei T : N>0 → N>0 eine Abbildung mit ( a falls n = 1 T (n) ≤ b + T (⌊n/2⌋) sonst für alle n ∈ N>0 . Zeigen Sie, dass T (n) ≤ a + b⌊log2 (n)⌋ für alle n ∈ N>0 gilt.

Abgabe der theoretischen Aufgaben Freitag, den 06. Mai, bis spätestens 9 Uhr. Die Abgabe der theoretischen Aufgaben erfolgt im Schrein.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, F. Land M. Rau

04. Mai 2016

Hausaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 4

Hausaufgabe 4.1 (Rekurrenz (3 Punkte)) Gegeben seien die folgenden Rekurrenzgleichungen für a, b ∈ N: 1. T (0) = a, T (n) = T (n − 1) + b für alle n ∈ N\{0} 2. T (1) = 1, T (n) = T ( n2 ) + n für alle n ∈ N derart, dass es ein k ∈ N\{0} gibt mit n = 2k , T (n) = T (2k ) mit k = ⌊log2 (n)⌋ in den restichen Fällen. Zeigen Sie, dass in beiden Fällen T (n) ∈ O (n) gilt. Hausaufgabe 4.2 (Laufzeit (4 Punkte)) Die binäre Suche teilt einen Suchbereich sukzessive in zwei gleichgroße Teile auf. Dieses Verfahren funktioniert auch, wenn der Suchbereich sukzessive in drei gleichgroße Teile aufgeteilt wird. Dieses Verfahren heißt ternäre Suche. Ermitteln Sie die Anzahl der Rechenoperationen im folgenden Algorithmus. Gehen Sie davon aus, dass pro Zeile eine Rechenoperation benötigt wird. Geben Sie anschließend die Gesamtlaufzeit des Algorithmus gemäß der O-Notation an. Algorithmus SEARCH (A, x) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int a = 0, b=n; int n = A.length; int k1,k2; while a0 und T : N>0 → N>0 mit ( a falls n = 1 T (n) ≤ b + T (⌊n/k⌋) sonst gilt, dass T (n) ≤ a + b⌊logk (n)⌋ für alle n ∈ N>0 ist (vgl. Hausaufgabe 3.4). Hausaufgabe 4.3 (Hanoi (3 Punkte)) Zeigen Sie, dass der in der Vorlesung präsentierte rekursive Algorithmus für die Türme von Hanoi die minimale Anzahl an Zügen berechnet, um einen Turm der Höhe n von Position 1 auf Position 2 über 3 zu verschieben. Hinweis: Sie können diese Aussage mittels Induktion zeigen. Programmieraufgabe 4.4 (Rucksack Problem) Implementieren Sie das in der Vorlesung vorgestellte dynamische Programm, um das RucksackProblem zu lösen. Erweitern Sie das dynamische Programm so, dass eine entsprechende Teilmenge von Items bestimmt und zurückgegeben wird.

Abgabe der theoretischen und praktischen Aufgaben Donnerstag, den 12. Mai, bis spätestens 14 Uhr. Die Abgabe der theoretischen Aufgaben erfolgt im Schrein. Die Abgabe der praktischen Aufgaben erfolgt im iLearn.

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, F. Land M. Rau

12. Mai 2016

Hausaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 5

Hausaufgabe 5.1 (Quicksort (2 Punkte)) Modifizieren Sie den angegebenen Algorithmus so, dass er die Elemente eines gegebenen Feldes in absteigender Reihenfolge anordnet. Algorithmus QUICKSORT (A,l,r) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

integer x,i,j,temp; if (l < r) then x = A[l]; i = l+1; j = r; while (i...