Klausur 25 Juli Sommersemester 2018, Fragen und Antworten PDF

Preview

Summary

Lehrstuhl Informatikanwendungen in der Medizin Augmented Reality Informatik Technische vo rs ch la g Hinweise zur Personalisierung: Ihre wird bei der Anwesenheitskontrolle durch Aufkleben eines Codes personalisiert. Dieser lediglich eine fortlaufende Nummer, welche auch auf der Anwesenheitsliste neb...

Description

Lehrstuhl für Informatikanwendungen in der Medizin & Augmented Reality Fakultät für Informatik Technische Universität München

ag

Hinweise zur Personalisierung: • Ihre Prüfung wird bei der Anwesenheitskontrolle durch Aufkleben eines Codes personalisiert. • Dieser enthält lediglich eine fortlaufende Nummer, welche auch auf der Anwesenheitsliste neben dem Unterschriftenfeld vermerkt ist. • Diese wird als Pseudonym verwendet, um eine eindeutige Zuordnung Ihrer Prüfung zu ermöglichen.

Grundlagen: Algorithmen und Datenstrukturen Prüfer: A1

A2

I II

IN0007 / Endterm

Datum:

Mittwoch, 25. Juli 2018

PD Dr. Tobias Lasser

Uhrzeit:

08:00 – 10:30

gs vo rs ch l

Klausur:

A3

A4

A5

A6

A7

A8

A9

A 10

Bearbeitungshinweise • Diese Klausur umfasst

– 16 Seiten mit insgesamt 10 Aufgaben

Bitte kontrollieren Sie jetzt, dass Sie eine vollständige Angabe erhalten haben. • Das Heraustrennen von Seiten aus der Prüfung ist untersagt.

su n

• Mit * gekennzeichnete Teilaufgaben sind ohne Kenntnis der Ergebnisse vorheriger Teilaufgaben lösbar. • Es werden nur solche Ergebnisse gewertet, bei denen der Lösungsweg erkennbar ist. Auch Textaufgaben sind grundsätzlich zu begründen, sofern es in der jeweiligen Teilaufgabe nicht ausdrücklich anders vermerkt ist. • Schreiben Sie weder mit roter / grüner Farbe noch mit Bleistift. • Die Gesamtpunktzahl in dieser Prüfung beträgt 160 Punkte.

Lö

• Als Hilfsmittel sind zugelassen: – ein selbst-beschriebenes Hilfsblatt (A4 doppelseitig nicht kopiert oder bedruckt) – ein analoges Wörterbuch Deutsch ↔ Muttersprache ohne Anmerkungen

• Schalten Sie alle mitgeführten elektronischen Geräte vollständig aus, verstauen Sie diese in Ihrer Tasche und verschließen Sie diese.

✓ Ankreuzen Kreuz streichen Wieder ankreuzen

✗

✗ Kreuze nicht nachfahren Feld ausmalen aber nicht durchdrücken keine autom. Erkennung → Einsicht

– Seite 1 / 16 –

Aufgabe 1

Wissensfragen (13 Punkte)

Bei jeder der folgenden Teilaufgaben ist genau eine Antwort korrekt. Kreuzen Sie jeweils nur die richtige Aussage an. Alle Teilfragen lassen sich unabhängig voneinander beantworten. a)* Für Stacks gilt: First in, First out

× Last in, First out

ag

Last in, Last out b)* Bei der amortisierten Analyse wird die durchschnittliche Laufzeit einer Operation in einer . . . (bitte ankreuzen) Folge von Operationen berechnet.

best möglichen

gs vo rs ch l

durchschnittlichen

× schlechtest möglichen

c)* Welche Datenstruktur eignet sich am besten für Hashing mit Verkettung?

× verkettete Liste Binärbaum zirkuläres Array

d)* Welcher Ansatz zur Kollisionsbehandlung bei Hashing hat die beste Cache-Effizienz? Verkettung

Quadratisches Sondieren

× Lineares Sondieren

e)* Wie viele Vergleiche sind bei einer Binärsuche maximal notwendig?

su n

⌊log(n)⌋ − 1

× ⌊log(n)⌋ + 1 ⌈log(n)⌉

Lö

f)* Welche Laufzeit hat Radixsort auf einer Folge vonn Zahlen aus der Menge {i : i ≤ n c }, wenn c eine Konstante ist? exponentiell konstant

× linear

g)* Welcher Sortieralgorithmus liefert die beste Laufzeit, wenn der Input bereits sortiert ist? Merge Sort Quick Sort

× Insertion Sort – Seite 2 / 16 –

h)* Welche der   folgenden Voraussetzungen sind jeweils hinreichend, um das kleinste vonn Elementen in Zeit O log(n ) finden zu können? (a) Die Elemente sind in einer doppelt verketteten sortierten Liste enthalten. (b) Die Elemente sind in einem AVL-Suchbaum enthalten. (c) Die Elemente sind in einem Binomial-Min-Heap enthalten. (b) und (c) (a) und (c)

ag

(b)

× (a), (b) und (c)

gs vo rs ch l

keine, es ist nicht möglich, das kleinste von n Element in Zeit O (log(n)) zu finden.

i)* Wie kann in ungewichteten Graphen das SSSP Problem am effizientesten gelöst werden? Dijkstra Algorithmus

× Breitensuche Kruskal Algorithmus

j)* Für welches Problem ist der Ansatz der Tiefensuche nicht geeignet? Erkennung von Kreisen in Graphen.

× Berechnung von kürzesten Wegen in Graphen.

Bestimmung von starken Zusammenhangskomponenten in gerichteten Graphen. Bestimmung von Zusammenhangskomponenten in ungerichteten Graphen.

k)* Welche der folgenden Voraussetzungen ist hinreichend, damit der Dijkstra-Algorithmus das korrekte Resultat liefert?

× Alle Kantengewichte des Eingabegraphen sind nicht-negativ.

su n

Der Eingabegraph ist ein DAG.

Der Eingabegraph enthält keinen negativen Kreis. Der Eingabegraph enthält einen negativen Kreis.

l)* Was ist der eigentliche Rand des Wortes "xyyzzxyzxyyzzx"?

Lö

yzzx x

× xyyzzx ǫ

m)* Bei der Muster-Suche in einem Text nutzt man sichere Shifts um zu erkennen, ob ein Vorkommen bereits übersprungen wurde. um zu verhindern, dass Sicherheitslücken ausgenutzt werden können.

× um zu verhindern, dass ein Vorkommen des Musters im Text übersprungen wird. um im Vergleich zum naiven Verfahren keine Vorverarbeitung durchführen zu müssen.

– Seite 3 / 16 –

Aufgabe 2

a)* Kreuzen Sie für die folgenden Funktionen das jeweils stärkste passende Landau-Symbol anstelle von ∆ an (pro Funktion nur ein Kreuz!). Begründen Sie im Textfeld für jeden Fall Ihre Entscheidung mit einer entsprechenden Rechnung. n

∈ ∆(n 2 )

⊠o

O

ω

Ω

Θ

(1)

n2

∈ ∆(n 2 + 2n)

o

O

ω

Ω

⊠ Θ

(2)

n

∈ ∆ (1 + n + (−1)n · n)

o

O

ω

⊠ Ω

Θ

(3)

4

∈ ∆(3)

o

O

ω

Ω

⊠ Θ

(4)

2ln n ∈ ∆(2n )

⊠ o

O

ω

Ω

Θ

(5)

n2

∈ ∆(2n )

⊠ o

O

ω

Ω

Θ

(6)

1 ln n

∈ ∆( n1 )

o

O

⊠ ω

Ω

Θ

(1) lim

n →∞ n 2

n2 1 =1 = lim + 2n n→∞ 1 + 2/n

(2) Es gilt c · n ≥ 1 + 2n ≥ 1 + n + (−1)n · n für c = 3 und für alle n ≥ n0 := 1. (3) lim

n →∞

(4) lim

n →∞

4 4 = 3 3 2ln n 2n 2

(5) lim

n →∞

= lim

e (ln 2)(ln n)

n →∞

n

= lim

n →∞

n ln 2 n

(ln 2)−1 =0 = lim n n →∞

n L .H. 2 2n L .H. =0 = lim n = lim n n n →∞ n →∞ 2 · ln 2 · ln 2 2 · ln 2 2

1 ln n n →∞ 1 n

= lim

n →∞

1 n L .H. = lim 1 = ∞ n →∞ ln n n

Lö

su n

(6) lim

ag

Beispiel:

gs vo rs ch l

0 1 2 3 4 5 6 7 8 9 10 11 12

Landau Symbole (28 Punkte)

– Seite 4 / 16 –

b)* Gegegeben seien die folgenden drei Algorithmen f1, f2, und f3. • Berechnen Sie zuerst die Ausgaben der drei Algorithmen für die Werten = 0, ... , 5 in der dafür vorgesehenen Tabelle. • Erklären Sie dann, was die jeweiligen Algorithmen berechnen. • Bestimmen Sie für jeden der drei Algorithmen die Laufzeitklasse in Landau-Notation. Begründen Sie Ihre Aussagen.

int f2(int n) if (n == 0) or (n == 1) return n; else return f2(n-1) + f2(n-2);

Eingabe n 0

f1(n) 0

1

1

2

1

3

2

4

3

5

5

static int[] c; // initialisiert auf -1

int f3(int n) if (c[n] < 0) if (n == 0) c[n] = 0; else if (n == 1) c[n] = 1; else if (n == 2) c[n] = 1; else int d = floor(n/2); int a = f3(d); int b = f3(d+1); if (n % 2 == 0) c[n] = 2 * a * b - a * a; else c[n] = b * b + a * a; return c[n];

gs vo rs ch l

int f1(int n) if (n == 0) or (n == 1) return n; int a = 1; int b = 0; for (int i = 2; i

√

0 1

2 · 10.

c)* Wählen Sie nun für die erste Stufe die Hashfunktionh1 . Führen Sie damit das aus der Vorlesung bekannte Verfahren durch und wählen Sie für die zweite Stufe jeweils eine geeignete Hashfunktionen aus. Geben Sie für jedes Element an, in welchem Bucket (der ersten Stufe) es landet, welche Position im Bucket es gegebenenfalls bekommt (zweite Stufe) und welche Hashfunktion dafür zuständig ist. Bucket

Position im Bucket

Hashfunktion

2

6

2

h3

4

2

4

h2

7

1

-

-

11

2

1

h2

12

5

2

h2

18

3

-

-

19

6

4

h3

22

4

-

-

26

6

11

h3

29

5

4

h2

su n

Element

Lö

0 1 2 3

d)* Weshalb müssen beim perfekten statischen Hashing die Hashfunktionen der zweiten Stufe injektiv sein? Injektive Hashfunktionen bilden nie zwei verschiedene Elemente auf denselben Wert ab und gewährleisten damit Kollisionsfreiheit.

– Seite 7 / 16 –

0 1 2 3 4 5 6 7 8 9 10

0 1

Aufgabe 5 0 1 2 3 4 5 6 7

QuickSort (15 Punkte)

a)* Gegeben sei die Zahlenfolge: 11, 17, 6, 7, 5, 16, 8, 10

Sortieren Sie die Zahlenfolge mit QuickSort, wobei immer das letzte Element einer Teilsequenz als Pivot zu verwenden ist. Eine Teilsequenz von maximal 2 Elementen soll in einem einzigen Schritt direkt sortiert werden. Geben Sie jeweils für jede Rekursionsebene einen Zwischenschritt an. Gerne kann das Schema aus der Übung verwendet werden.

Schritt 2, Pivot 7: 6, 5 | 7 | 8 | 10 | 16, 11, 17 Schritt 3, Pivot 17: 6, 5 | 7 | 8 | 10 | 16, 11 | 17

0 1

gs vo rs ch l

Schritt 4, Zweiergruppen sortieren, fertig: 5, 6, 7, 8, 10, 11, 16, 17

ag

Schritt 1, Pivot 10: 8, 5, 6, 7 | 10 | 16, 11, 17

b)* Wie ist die asymptotische Laufzeit des QuickSort-Algorithmus mit unbekannter Pivot-Strategie? O (n 2 ) Hinweis: O (n log n) gilt nur für die mittlere Laufzeit, nicht die asymptotische!

0 1 2

c)* Konstruieren Sie eine Beispiel-Eingabe mit 7 Elementen für den QuickSort Algorithmus wie in a) beschrieben, die zur best-case Laufzeit führt. Beispiel: 3, 7, 5, 14, 12, 16, 10

d)* Der QuickSelect-Algorithmus kann so modifiziert werden, dass die worst-case Laufzeit bei einer Eingabe der Länge n die wie folgt rekursiv formulierte obere Schranke T (n) besitzt:  n

su n

0 1 2 3 4 5

T (n) = T

2

+ 10n

T (1) = 10

Zeigen Sie durch vollständige Induktion, dass T (n) ≤ 20n für alle Zweierpotenzen n = 2k mit k ∈ N0 gilt.

Lö

Induktion über k !

Induktionsanfang: Für k = 0 ist n = 1 und es gilt T (1) = 10 ≤ 20 · 1.

Induktionsvoraussetzung: Aussage ist gültig für k , zu zeigen: auch gültig für k + 1.

Def.

Induktionsschritt: Angenommen, für n = 2k gilt also T (n) ≤ 20n. Für 2k +1 = 2n gilt dann T (2n) = I.V.

T (n) + 10 · 2n ≤ 20n + 20n = 20 · 2n . Damit ist die Aussage gezeigt.

– Seite 8 / 16 –

Aufgabe 6

BucketSort (15 Punkte)

int[] bucketSort(int[] array, int n): // n ist Laenge von array list[] buckets ← new array of n empty lists; for i = 0 to n-1 do int bucket = computeBucket(array[i]); buckets[bucket].pushBack(array[i]); for i = 0 to n-1 do sort(buckets[i]); // aus der Standard-Bibliothek return concatenation of buckets[0],...,buckets[n-1]

ag

Wir betrachten im Folgenden eine Variante des kSort Algorithmus aus der Vorlesung, wir nennen ihn bucketSort:

a)* Sortieren Sie die folgende Zahlenfolge mit dem oben angegebenen Algorithmus bucketSort: 3, 7, 5, 9, 5, 1, 4, 2, 6, 0

0 1 2

su n

gs vo rs ch l

Hierbei sei computeBucket die Funktion, die die führende Ziffer zurückliefert. Verwenden Sie zur Veranschaulichung folgende Struktur, wobei die erste Zeile die Buckets repräsentiert, mit den dazu assoziierten Listen, die nach unten erweitert werden sollen.

Lö

b)* Ist bucketSort ein stabiler Sortieralgorithmus? Wie ist die Laufzeit vonbucketSort? Begründen Sie Ihre Anworten. bucketSort ist stabil, sofern sort stabil ist.  P −1  Die Laufzeit von bucketSort ist O n + ni=0 Ti , wobei Ti die jeweilige Laufzeit vonsort für den i -ten Bucket ist.

c)* Der AlgorithmusbucketSort in der Variante aus a) ist in seiner Funktionsweise eng verwandt mit Hashing. Geben Sie die dazu passende Hashfunktion an. h(x) = x mod 10

– Seite 9 / 16 –

0 1 2 3

0 1

Im Folgenden betrachten wir avlBucketSort, einen modifizierten bucketSort für das Sortieren von Floats mit Werten im Intervall [0, 1) . In jedem Bucket befindet sich nun anstelle einer Liste ein AVL-Baum. Der Algorithmus, nachfolgend in Pseudocode beschrieben, verwendet einecomputeBucket Funktion, welche die erste Dezimalstelle nach dem Komma zurückliefert.

d)* Sortieren Sie die folgende Zahlenfolge mit avlBucketSort. 0.102, 0.201, 0.77, 0.354, 0.715, 0.5, 0.72

gs vo rs ch l

Verwenden Sie zur Veranschaulichung die gleiche Struktur wie in a), nur mit AVL-Bäumen. Zeichnen Sie für jede insert-Operation den jeweiligen AVL-Baum und erläutern Sie, falls notwendig, die durchgeführten Rotationen.

Lö

su n

0 1 2 3 4 5 6 7

ag

float[] avlBucketSort(float[] array, int n) { // n ist Laenge von array avlTree[] buckets ← new array of n empty AVL-Trees; for i = 0 to n-1 do int bucket = computeBucket(array[i]); buckets[bucket].insert(array[i]); // insert in AVL Baum return concatenation of buckets[0].getInOrderTraverse(),...,buckets[n-1].getInOrderTraverse()

0 1 2

e)* Bestimmen Sie die worst-case Laufzeit von avlBucketSort. Bitte begründen Sie Ihre Antwort. worst-case Laufzeit: O (n log n) , da jedes insert O (log n) benötigt.

– Seite 10 / 16 –

Aufgabe 7

Heaps (15 Punkte)

a)* Gegeben seien die folgenden Zahlen: 12, 1, 5, 8, 4, 7, 10, 11, 3, 2, 9, 6 Erstellen Sie daraus einen binären Heap, der durch ein Array repräsentiert wird. Dokumentieren Sie dazu alle relevanten Schritte der effizientenbuildHeap Operation durch verständlichen Text bzw. Zeichnungen. Zeichnen Sie abschliessend den resultierenden binären Heap als Baum.

gs vo rs ch l

ag

Anfang von buildHeap :

0 1 2 3 4 5 6 7 8

Nun wird für die ersten ⌊n /2⌋ Elemente in umgekehrter Reihenfolge ein siftDown durchführt: siftDown 7: 6 und 7 vertauschen siftDown 4: 2 und 4 vertauschen siftDown 8: 3 und 8 vertauschen siftDown 5: unverändert siftDown 1: unverändert siftDown 12: 1 und 12 vertauschen, 2 und 12 vertauschen, 4 und 12 vertauschen Der fertige Binary Heap sieht wie folgt aus:

su n

b)* Betrachten Sie nun folgenden Binomial Heap:

Lö

Führen Sie die deleteMin-Operation für diesen Heap durch. Beschreiben Sie alle relevanten Schritte, die während dieser Operation ausgeführt werden. Benutzen Sie hierzu die Binärdarstellung (1 bzw. 0 Bit für Existenz von Binomialbaum vom entsprechenden Rang) für den Zustand des Heaps vor, während, und nach der deleteMin Operation. Zeichnen Sie abschliessend den resultierenden Heap. Nach deleteMin wird die ’1’ aus dem Heap entfernt , anschließend müssen die Knoten neu verknüft werden. Dies lässt sich über die Binärdarstellung des Heaps durchführen: Binärdarstellung vor deleteMin: 1111 Binärdarstellung direkt nach dem Löschen der ’1’: 0100 + 0010 + 0001 + 0111 Binärdarstellung nach merge: 1110 Der fertige Heap sieht wie folgt aus:

– Seite 11 / 16 –

0 1 2 3 4 5 6 7

Aufgabe 8 0 1 2

(a-b)-Bäume (15 Punkte)

a)* Welches Problem lösen (a,b)-Bäume im Bezug auf allgemeine binäre Suchbäume hinsichtlich Laufzeit bzw. Speicherzugriffe?

ag

Allgemeine binäre Suchbäume können zur Liste entarten, wodurch die locate-Operation ineffizient wird. Durch die Grad-Invariante bleibt der Baum flach, was während der Suche zu weniger Speicherzugriffen und kürzerer Laufzeit (worst case O (log n)) führt.

Gegeben sei folgender (a,b)-Baum mit a = 2, b = 4: 11, 18

gs vo rs ch l 1, 6, 8

1

6

A

13

B

8

11

13

19, 22

C

18

19

22

D

∞

Der Wurzelknoten sowie die inneren Knoten des Baumes sind mit blauer Farbe von oben nach unten und von links nach rechts alphabetisch gekennzeichnet. 0 1 2

b)* Entfernen Sie das Element 11. Welchen Grad haben Knoten A und Knoten B nach der Operation jeweils? Beschreiben Sie kurz (als Text oder Zeichnung), was passiert. Blatt mit Schlüssel 11 entfernen. Das größte Element des Vaterknotens (d.h. die 8) wandert nun in den Rootknoten und ersetzt die 11. Knoten A hat Grad 3 nach der Operation Knoten B hat Grad 3 nach der Operation 8, 18

1, 6

13

B

C

su n 1

6

13

8

18

19

19, 22

D

22

∞

c)* Gehen Sie nun wieder vom Ausgangsbaum aus. Entfernen Sie das Element 13. Welchen Grad haben Knoten B, C und D jeweils nach Ausführen aller notwendigen Operationen? Welche Operationen sind notwendig? Beschreiben Sie kurz (als Text oder Zeichnung), was passiert.

Lö

0 1 2 3

A

Blatt 13 und sein Handle werden zunächst entfernt. Damit ist Knoten C nun leer und hat Grad < 2. Fall 1: Betrachte Nachbar D mit d(D) > 2 . Dessen kleinstes Element 19 wandert in den Root-Knoten A. Knoten C hat nun 2 Kinder, nämlich 18 und 19. Damit ist d(B) = 4 (unverändert), d(C) = 2 und d(D) = 2

Fall 2: Betrachte Nachbar B mit d(B) > 2 : Dessen größtes Element 8 wandert in den Root-Knoten A, 11 somit nach C. Damit ist d(B) = 3, d(C) = 2 und d(D) = 3 (unverändert) 11, 19

1, 6, 8

1

6

B

8

A

18

11

18

22

C

19

22

D

∞

– Seite 12 / 16 –

Gegeben seien folgende Bäume. Handelt es sich um gültige (a,b)-Bäume? Begründen Sie Ihre Antwort unter Verwendung der korrekten Terminologie. Beschreiben Sie gegebenenfalls wie der Baum in einen gültigen (a,b)-Baum trans...