AD18 Uebung 1 - Prof. Dr. Falk Schreiber Übungsblatt PDF

Preview

Summary

Prof. Dr. Falk Schreiber
Übungsblatt...

Description

Universität Konstanz Algorithmen und Datenstrukturen Fachbereich Informatik & Informationswissenschaft WS 2018/2019 Prof. Dr. Falk Schreiber / Dr. Karsten Klein / Dr. Björn Sommer / Michael Aichem

1. Übungsblatt Ausgabe: 23. Oktober 2018 - Abgabe: 30. Oktober 2018, 12:00 Uhr - Tutorium: 6./7. November 2018

Aufgabe 1: Organisation

Voraussetzung zur Übungsteilnahme

Registrieren Sie sich im ZEuS System für die Übungen, da sonst keine Punkte verbucht werden können. Registrieren Sie sich für die Abholung der Übungsblätter und die Abgabe Ihrer Lösungen auch im Ilias System in Ihrer Gruppe. Das aktuelle Übungsblatt ist jeweils Dienstags im ILIAS System zu finden. Die Abgabefrist ist Dienstags 23:59 Uhr in der darauffolgenden Woche. In der Woche vom 29.10 finden keine Übungs-Veranstaltungen statt. Gruppen Die Bearbeitung in Zweiergruppen ist ausdrücklich erwünscht. Die Teamzuordnung erfolgt in Eigenverantwortung im Ilias System. Zur Registrierung Ihres Teams fügen Sie bei der ersten Abgabe Ihren Übungspartner im Team hinzu. Für alle weiteren Übungen sind dann dieselben Teams gesetzt (maximal zwei Studierende pro Team). Abgabe der theoretischen Aufgaben Die Abgabe der theoretischen Aufgaben erfolgt über das Ilias System als eine PDF-Datei im DIN A4-Format (keine Office- oder Bilddateien), benannt nach dem Schema 01_nachname1_nachname2.pdf. Ersetzen Sie jeweils 01 mit der Nummer des entsprechenden Übungsblattes. Bitte geben Sie auf den Lösungen die Namen aller Gruppenmitglieder an, damit wir eine Punktezuordnung machen können. Bitte schreiben Sie auch auf die Lösungen, an welchem Übungstermin Sie teilnehmen (Gruppe 1 Mo 17:00 P602 / 2 Die 8:15 P602 / 3 Die 8:15 L602 / 4 Die 17:00 P602) das erleichtert die Rückgabe der korrigierten Blätter. Bei falscher Benennung von Dateien oder falscher Angabe des Betreff besteht die Gefahr, dass Abgaben übersehen und nicht bewertet werden können. Abgabe der praktischen Aufgaben Die Abgabe der praktischen Aufgaben erfolgt getrennt von der Abgabe der theoretischen Aufgaben. Bitte geben Sie auf der Abgabe in Ilias auf Ihrem Lösungszettel nur an, dass / ob Sie eine praktische Aufgabe bearbeitet haben. Wir empfehlen Eclipse als Entwicklungsumgebung. Stellen Sie sicher, dass Ihre Abgabe kompiliert. Abgaben die nicht kompilieren werden nicht bewertet. Genaue Angaben zur Abgabe des Codes erhalten Sie auf dem nächsten Übungsblatt.

Aufgabe 2: Minimums- und Maximumssuche

5 Punkte

Die gleichzeitige Minimums- und Maximumssuche auf einem unsortierten Array M ist beschrieben durch Algorithmus 1: Gleichzeitige Minimums- und Maximumssuche begin min ← M [1] max ← M [1] for i = 2, . . . , n do if M [i] < min then min ← M [i] if M [i] > max then max ← M [i] return min, max (a) Führen Sie für das Array mit folgenden Zahlen eine gleichzeitige Minimums- und eine Maximumssuche mit Algorithmus 1 durch: 4

10

2

16

7

9

1

12

5

19

Dokumentieren Sie alle Zwischenschritte und geben Sie die Anzahl der nötigen Vergleiche an. (b) Wieviele Vergleiche werden bei dieser Strategie für eine Menge von n Zahlen durchgeführt? (c) Entwickeln Sie eine Strategie für eine gleichzeitige Minimums- und Maximumssuche, welche mit weniger Vergleichen auskommt, als die einfache Minimums- und Maximumssuche aus Algorithmus 1. Die Anzahl der Vergleiche sollte hierbei nicht nur um eine konstante Zahl reduziert werden (z.B. um 3), sondern um eine Zahl in Abhängigkeit der Eingabegröße n 1 n). (z.B. um 23 Hinweis: Betrachten Sie die spezielle Struktur des Eingabearrays aus Aufgabe 2(a) um auf einen Algorithmus zu kommen, der zu jeder Eingabe eine korrekte Lösung liefert. Beschreiben Sie Ihre Strategie in Pseudocode, und zeigen Sie, wie viele Vergleiche benötigt werden.

Aufgabe 3: Asymptotische Notation

5 Punkte

Gegeben sei die Funktion f : N0 → N mit f (n) = n2 . Betrachten Sie die folgende Darstellung der Mengen o(f ), O(f ), Θ(f ), Ω(f ), und ω(f ):

Ω(f ) ω(f )

Θ(f )

O(f ) o(f )

Benennen Sie alle notwendigen Aussagen, welche die Korrektheit der Darstellung beweisen. Zu betrachten sind Teil- und Schnittmengenrelationen, und die Existenz von Elementen in Teilmengen, Schnittmengen und Komplementmengen. Führen Sie einen Beweis für eine der Aussagen durch.

Aufgabe 4: Asymptotisches Wachstum

4 Punkte

Beweisen Sie die folgende Aussage: (f (n) + g(n)) ∈ O(max{f (n), g(n)})

Aufgabe 5: Asymptotisches Wachstum von Polynomen

2 Punkte

∑d i Gegeben sei ein Polynom p(n) = i=0 ai n d-ten Grades in n mit ad > 0 und eine Konstante k. Benutzen Sie die Definitionen der asymptotischen Notation, um die folgenden Eigenschaften zu beweisen. (a) Ist k ≥ d, dann gilt p(n) = O(nk ) (b) Ist k = d, dann gilt p(n) = Θ(nk ) (c) Ist k > d, dann gilt p(n) = o(nk )

Aufgabe 6: Asymptotisches Wachstum

4 Punkte

Ergänzen Sie eines der Zeichen O, Ω, Θ, o, ω, um eine möglichst präzise, wahre Aussage zu erhalten. Begründen Sie! (a) nlog2 c ∈ (b) n! ∈

(clog2 n ) für ein festes c > 1 (nn )

Aufgabe 7: Induktion Zeigen Sie durch vollständige Induktion 23n − 5n ist durch 3 teilbar (n sei eine natürliche Zahl).

5 Punkte...