Praes 07Loes - SoSe19 PDF

Preview

Summary

SoSe19...

Description

SoSe 2019

M. Buchin D. Rohde, L. Pfahler, M. Bommert

DAP2 – Präsenzübung 7 Besprechung: 22.05.2019 — 24.05.2019 Abgabe: Präsenzübungen müssen nicht zu Hause bearbeitet werden, sondern werden unter Anleitung während der Übung erarbeitet. Präsenzaufgabe 7.1: (Gierige Algorithmen: Abdeckung durch Sendemasten) An einer Landstraße stehen mehrere Wohnhäuser, die durch Sendemasten mit Mobilfunkempfang versorgt werden sollen. Die zu verwendenden Sendemasten haben jeweils eine Reichweite von 3 Längeneinheiten und die Länge der Landstraße ist mit n Längeneinheiten gegeben. In einem Array A sind die Positionen der Wohnhäuser gegeben. Genauer gilt A[i] = 1 genau dann, wenn an Position i ein Wohnhaus steht. Ein Wohnhaus an Position k, 1 ≤ k ≤ n, ist versorgt, wenn ein Sendemast auf einer Position i platziert wird mit |k − i| ≤ 3. Steht also beispielsweise ein Wohnhaus an der Position 7, so muss an mindestens einer der Positionen von 7 − 3 = 4 bis 7 + 3 = 10 ein Sendemast errichtet werden. Gesucht ist eine kleinste Menge T von Positionen, sodass alle Wohnhäuser an der Landstraße mit Mobilfunkempfang versorgt sind, wenn auf jeder Position aus T ein Sendemast errichtet wird. a) Formulieren Sie – mit eigenen Worten und als Pseudocode – einen gierigen Algorithmus, der bei Eingabe eines Arrays A[1..n] eine kleinste Menge T von Positionen gemäß den Anforderungen der Aufgabenstellung ausgibt. b) Analysieren Sie die Laufzeit Ihres Algorithmus. c) Beweisen Sie, dass Ihr Algorithmus eine optimale Lösung berechnet. Lösung: a) Wir werden mit dem folgenden Pseudocode die Idee verfolgen, wiederholt ein noch nicht versorgtes Wohnhaus an Position k, 1 ≤ k ≤ n, durch einen Sendemasten an der Position k + 3 zu versorgen. (Wir werden später sehen, dass es für eine optimale Positionierung der Sendemasten nicht nötig ist, ein Haus an der Position n durch einen Sendemasten an der Position n − 2, obwohl dies intuitiv natürlich mehr Sinn machen würde). GreedyRoadCover(A[1..n]): i=1 2. last = −3 3. T = ∅ 4. for i ≤ 1 to n do 5. if |last − i| > 3 und A[i] = 1 then 6. last ← i + 3 7. T ← T ∪ last 8. return T 1.

1

Die Variable last bezeichnet die letzte Position, an der wir entschieden haben, einen Sendemasten zu errichten. Ihre Initialisierung mit last ← −3 stellt sicher, dass ein Haus auf der Position 1 nicht fälschlicherweise als versorgt erkannt wird. Mit der Laufvariable i prüfen wir nacheinander für jede Position, ob sich ein noch nicht versorgtes Wohnhaus an der Position i befindet. Befindet sich ein Wohnhaus an Position i (A[i] = 1) und ist dieses nicht durch den letzten Sendemasten versorgt (|last − i| > 3), fügen wir unserer Lösung entsprechend der obigen Überlegung einen Sendemasten auf der Position i + 3 hinzu. Für die Schleife gilt als Invariante für 1 ≤ i ≤ n + 1: Jedes Haus auf einer der Positionen 1, . . . , i − 1 ist durch einen Sendemasten in T versorgt. b) Die ersten drei Zeilen ergeben eine konstante Laufzeit. Die For-Schleife wird n mal iteriert (+1 für die zusätzliche abbrechende Ausführung des Schleifenkopfes) und im Rumpf der For-Schleife trägt jede Zeile eine konstante Laufzeit bei. Insgesamt ergibt sich also eine Laufzeit von O(n). c) Die in der Lösung zu Teilaufgabe a) erwähnte Invariante lässt sich per Induktion beweisen und liefert uns die Gültigkeit der durch unseren Algorithmus gelieferten Lösung. Wir zeigen nun die Optimalität nach dem Prinzip „greedy bleibt vorn“. Sei A[1..n] eine Eingabe, sei T = {t1 , t2 , . . . , tk } mit t1 ≤ t2 ≤ · · · ≤ tk unsere gierige Lösung für die Eingabe A und sei T ′ = {t1′ , t′2 , . . . , tk′ ′ } mit t1′ ≤ t′2 ≤ · · · ≤ tk′ ′ eine optimale Lösung mit k′ < k. Wir zeigen für 1 ≤ i ≤ k′ via Induktion: Sendemasten auf den Positionen t1′ , . . . , ti′ versorgen nicht alle Wohnhäuser bis zur Position ti + 3, oder es gilt ti′ ≤ ti . I.A. Sei s die erste Position des Hauses, also s = min{1 ≤ ℓ ≤ n | A[ℓ] = 1}. Dann gilt t1 = s + 3 und die gierige Lösung versorgt das Wohnhaus auf s mit einem Masten auf t1 . Gilt t′ > t, so folgt t′ − s > t − s = 3, also versorgt t1 das Wohnhaus auf s nicht. Unsere Behauptung gilt also für i = 1. I.V. Sei 1 < i ≤ k′ . Die Behauptung gilt für alle i′ < i. I.S. Sei 1 < i ≤ k′ . Sei ti′ > ti . Zu zeigen ist, dass Sendemasten auf t1′ , . . . , t′i nicht alle Wohnhauser auf den Positionen 1, . . . , ti + 3 versorgen. Sei s = ti − 3. Da ti durch den gierigen Algorithmus gewählt wurde, muss ein Wohnhaus auf Position s stehen. Wegen ti′ > ti gilt ti′ − s > ti − s = 3, das Wohnhaus auf s wird also nicht durch einen Sendemasten auf ti′ versorgt. Nach I.V. (mit i − 1) gilt eine der beiden Aussagen: ′ – ti−1 ≤ ti−1 . Das Wohnhaus auf Position s wurde nicht durch ti−1 versorgt (sonst ′ ≤ ti−1 < s − 3 und s wäre ti kein Element der gierigen Lösung). Es gilt also ti−1 ′ versorgt. wird auch nicht durch einen Masten auf einer der Positionen t1′ , . . . , ti−1 ′ , . . . , t′ – Die Positionen t1 i−1 versorgen nicht alle Wohnhäuser bis zur Position ti−1 + 3. Da der Sendemasten auf Position ti−1 die Positionen bis ti−1 + 3 versorgt, gilt s > ti−1 + 3 für die Position s des ersten durch ti versorgen Wohnhauses (s wird erst durch ti versorgt). Nach Definition gilt s = ti − 3 > ti−1 + 3 und nach Annahme ti′ > ti , insgesamt also ti′ − 3 > ti−1 + 3. Die Position ti′ versorgt also keine der Positionen bis ti−1 + 3, jedes nicht durch die Positionen t1′ , . . . , t′i−1 versorgte Haus bleibt also unversorgt.

Mit k′ < k gibt es eine Position tk′ +1 , die von unserem Algorithmus zur Lösung T hinzugefügt wurde, weil das Wohnhaus an Position s = tk′ +1 − 3 nicht abgedeckt war. Aus 2

der Hilfsaussage folgt, dass die Lösung T ′ das Element s nicht abgedeckt (B[tk′′ ] ≤ B[tk′ ]) Sk′ oder nicht alle Elemente aus ℓ=1 Stℓ , ein Widerspruch zur Annahme, dass T ′ eine Lösung ist mit |T ′ | < |T |. Präsenzaufgabe 7.2: (Dynamische Programmierung) In Budapest gibt es n Brücken an der Donau. Alice möchte die Strecke zwischen Brücken 1 und n am Ufer entlang spazieren, wobei sie zwischen zwei nacheinanderliegenden Brücken entweder am rechten Ufer (in Buda) oder am linken Ufer (in Pest) spazieren kann. Während sie zwischen Brücken i und i + 1 spaziert, 1 ≤ i < n, kriegt sie Brezeln, und zwar A[i] Brezeln in Buda, und B[i] Brezeln in Pest. Wenn sie die Donau über die i-te Brücke überqueren möchte, muss sie C[i] Brezeln abgeben, wobei sie nie weniger als 0 Brezeln haben kann. Alice beginnt mit 0 Brezeln in Buda bei der Brücke 1. Alle Werte A[i] und B[i] (1 ≤ i ≤ n − 1), sowie C[i] (1 ≤ i ≤ n) sind nicht negativ, und es gilt C[1] = C[n] = 0. Alice darf nicht in Gegenrichtung laufen (z.B. von Brücke i+1 nach Brücke i) und will die Anzahl der gesammelten Brezeln bei der n-ten Brücke in Buda maximieren.

Buda1 C [1] = 0 Pest1

A[1] = 5

Buda2

C [2] = 2 B [1] = 3

Pest2

A[2] = 1

Buda3

C [3] = 7 Pest3

B [2] = 4

A[3] = 0

Buda4

C [4] = 5 B [3] = 5

Pest4

A[4] = 8

Buda5

C[5] = 0 B [4] = 1

Pest5

In diesem Beispiel wäre es optimal, bei den Brücken 2 und 4 das Ufer zu wechseln. In diesem Fall kommt man mit 15(= 5 − 2 + 4 + 5 − 5 + 8) Brezeln am Ziel in Buda an. a) Geben Sie die Rekursionsgleichungen für die maximalen Anzahlen p(i) und q(i) von Brezeln an, die Alice bei Erreichen der i-ten Brücke in Buda bzw. Pest sammeln kann. b) Geben Sie einen Algorithmus in Pseudocode an, der auf dem Prinzip der dynamischen Programmierung beruht und die maximale Anzahl gesammelter Brezeln beim Erreichen der Brücke n in Buda zurückgibt. c) Analysieren Sie die Laufzeit Ihres Algorithmus. d) Beweisen Sie die Korrektheit Ihrer Rekursionsgleichungen aus Teilaufgabe a) mittels Induktion.

Lösung: a) Die rekursiven Formen für p(i) bzw. q(i) werden aufeinander referenzieren. Die Abbruchbedingungen sind offensichtlich p(1) = 0 und q(1) = 0, da man bei der ersten Brücke in 3

Buda keinen Brezel hat, bzw. mit C[1] = 0 ohne Abgaben die erste Brücke nach Pest überqueren kann. Für die weiteren Brücken (i > 1), kann die i-te Brücke in Buda entweder von der i − 1-ten Brücke in Buda, oder über die i-te Brücke aus Pest erreicht werden. Ähnliches gilt für die i-te Brücke in Pest. Dabei müssen wir darauf achten, dass man keinen Kreis in die rekursive Form einbaut (z.B. p(i) referenziert auf q(i), und q(i) auf p(i)). Deswegen haben wir folgende rekursiven Formen: ( 0 falls i = 1 p [i] = max{p(i − 1) + A[i − 1], q(i − 1) + B[i − 1] − C[i]} falls i > 1 ( 0 falls i = 1 q [i] = max{q(i − 1) + B[i − 1], p(i) − C[i]} falls j > 1 b) In Pseudocode erhalten wir folgenden Algorithmus. Wir geben den größeren Wert von P [n] und Q[n] zurück, da man kostenlos aus Pest über die n-te Brücke nach Buda kommen kann (C[n] = 0). Brezeln (Array A[1..n − 1], Array B[1..n − 1], Array C[1..n]): 1. P ← new Array [1..n ] 2. Q ← new Array [1..n ] 3. P [1] ← 0 4. Q[1] ← 0 5. for i ← 2 to n do 6. P [i] ← max{P [i − 1] + A[i − 1], Q[i − 1] + B[i − 1] − C[i]} 7. Q[i] ← max{Q[i − 1] + B[i − 1], P [i] − C[i]} 8. return max{P [ n ], Q[ n ]} c) Die Laufzeit T (n) des Algorithmus ist O(n), weil wir die Zeit O(n) für die Zeilen 1, 2, 5, 6 und 7 benötigen, und die restliche Zeilen (3, 4 und 8) konstante Zeit benötigen. d) Behauptung: p(i) und q(i) enthalten die maximale Anzahl der Brezeln beim Erreichen der i-ten Brücke in Buda bzw. Pest, für alle i ∈ N. IA. Für i = 1 ist p(1) = 0 korrekt, da Alice am Anfang in Buda ist, und somit keine Brezeln hat, und q(1) = 0 korrekt, da sie kostenlos die erste Brücke überqueren kann (C[1] = 0) und damit höchstens 0 Brezeln in Pest am Anfang haben kann. IV. Seien p(i − 1) und q(i − 1) die maximale Anzahl an Brezeln bei der i − 1-ten Brücke, für beliebiges aber festes i. IS. Wir zeigen zuerst die Korrektheit von p(i). Nehmen wir an, es gäbe eine bessere Summe u > p(i) = max{p(i − 1) + A[i − 1], q(i − 1) + B[i − 1] − C[i]}, sodass Alice u Brezeln bei der i-ten Brücke in Buda haben kann. Die i-te Brücke in Buda für u kann entweder durch Buda von der i − 1-ten Brücke, oder aus Pest über die i-te Brücke erreicht werden (es ist nicht erlaubt, in Gegenrichtung zu laufen). Fall 1: Sie kam durch Buda. Dann ist u > p(i − 1) + A[i − 1], und also u − A[i − 1] > p(i −1). u−A[i −1] ist die Anzahl der Brezeln, die Alice in Buda bei der i −1-ten Brücke haben müsste. Das widerspricht der I.V. für p(i − 1). 4

Fall 2: Sie kam aus Pest. Dann ist u > q(i − 1) + B[i − 1] − C[i]. u + C[i] wäre die Anzahl der Brezeln bei der i-ten Brücke in Pest, u + C[i] − B[i − 1] die Anzahl bei der i − 1-ten Brücke in Pest, und diese Anzahl u + C[i] − B[i − 1] > q(i − 1) . Das widerspricht der I.V. für q(i − 1). Somit ist auch p(i) die maximale Anzahl der Brezeln in Buda bei der i-ten Brücke. Jetzt zeigen wir die Optimalität von q(i). Nehmen wir an, sie ist nicht optimal und es gäbe ein besseres w > q(i) = max{q(i − 1) + B[i − 1], p(i) − C[i]}. Dieser Wert w kann entweder aus Buda über die i-te Brücke, oder durch Pest von der i − 1-ten Brücke erreicht werden. Fall 1: Sie kam aus Buda. Dann ist w > p(i) − C[i], also w + C[i] > p(i). w + C[i] wäre dann die Anzahl der Brezeln in Buda bei der i-ten Brücke, was nicht sein kann, weil wir gerade bewiesen haben, dass p(i) maximal ist. Fall 2: Sie kam aus Pest. Dann ist w > q(i − 1) + B[i − 1]. w − B[i − 1] wäre die Anzahl der Brezeln bei der i − 1-ten Brücke in Pest, was der I.V. für q(i − 1) widerspricht. Somit ist q(i) optimal und die Behauptung gilt für p(i) und q(i) für alle i ∈ N.

Präsenzaufgabe 7.3: (Dynamische Programmierung) Bob möchte für seine Kommilitonin Alice eine CD seiner Lieblingslieder zusammenstellen. Er hat bereits eine Auswahl von n Liedern der Längen d1 , . . . , dn (in Sekunden) getroffen und will mit diesen die CD mit einer Hördauer von p Sekunden exakt ausfüllen. Natürlich soll sich kein Lied auf der CD wiederholen. Er weiß, dass Alice längere Lieder mag, und enschließt sich, sein Ziel mit so wenigen Liedern wie möglich zu erreichen. a) Finden Sie eine rekursive Form für die kleinste Anzahl an Liedern, mit denen Bob die CD füllen kann. b) Geben Sie (in Pseudocode) einen auf dynamischer Programmierung beruhenden Algorithmus an, der die kleinste Anzahl von Liedern bestimmt, mit denen die CD restlos gefüllt werden kann, oder der anzeigt, falls keine Lösung existiert. c) Analysieren Sie die Laufzeit Ihres Algorithmus. d) Zeigen Sie die Korrektheit Ihrer rekursiven Form.

Lösung: a) Wir können die minimale Anzahl von Liedern M (i, z) für eine Hörzeit z, wobei nur die Lieder 1, . . . , i verwendet werden dürfen, in der folgenden Weise rekursiv berechnen:  ∞ falls i = 0, z 6= 0     0 falls z = 0 M (i, z) =  ∞ falls i > 0, z < 0    min {1 + M(i − 1, z − di ), M(i − 1, z)} falls i > 0, z > 0 5

b) Auf der Basis der rekursiven Definition ergibt sich das folgende dynamische Programm zur Berechnung von M für die Hörzeit z : 1 2 3 4 5 6 7 8 9 10 11 12 13

gCount(Array D, p) // D[1..n] enthält die Längen d1 , . . . , dn der Lieder: n ← length(D) Array M[0..n, 0..p] for z ← 1 to p do M[0, z] ← ∞ for i ← 0 to n do M[i, 0] ← 0 for i ← 1 to n do for z ← 1 to p do M [i, z] ← M [i − 1, z] if z − D[i] ≥ 0 then if M[i, z] > 1 + M [i − 1, z − D[i]] then M[i, z] ← 1 + M [i − 1, z − D[i]] return M[n, p] Existiert keine Lösung, gibt der hier angegebene Algorithmus das Symbol ∞ aus.

c) Wir zeigen durch Induktion über i, dass M(i, z) für alle Hörzeiten 0 ≤ z ≤ p die minimale Anzahl benötigter Liedlängen aus d1 , . . . , di angibt, um die Hörzeit z zusammenzusetzen. I.A. Wenn i = 0 ist (keine Lieder verfügbar), dann ist im Fall z = 0 (Länge 0) die minimale Anzahl der verwendeten Lieder M(0, 0) = 0. Ansonsten, also wenn z > 0, ist die Hörzeit z nicht realisierbar, was durch ∞ korrekt bezeichnet ist. I.V. Seien 0 < i ≤ n. Dann ist M(i′ , z) für alle 0 ≤ z ≤ p die minimale Anzahl benötigter Lieder, um die Hörzeit z mit Liedern aus d1 , . . . di zusammenzusetzen, für alle i′ < i. I.S. Sei 0 < i ≤ n. Zu zeigen ist die Korrektheit von M(i, z) für alle z. Nehmen wir an, dass für z > 0 der Wert M(i, z) nicht die minimale Anzahl benötigter Lieder ist. Dann gibt es ein v < M(i, z) = min{M(i − 1, z), 1 + M(i − 1, z − di )}, so dass mit v der Lieder 1, . . . , i die Hörzeit der Länge z realisierbar ist. Dafür gibt es zwei Möglichkeiten: ∗ Das Lied i wird nicht verwendet. Dann kann die Hörzeit z mit v Liedlängen aus d1 , . . . , di−1 erreicht werden. Es gilt v < M(i, z) = min{M(i − 1, z), 1 + M(i − 1, z − di )} ≤ M(i − 1, z). Dies ergibt einen Widerspruch zur Optimalität von M(i − 1, z) nach I.V. ∗ Das Lied i wird verwendet. Dann kann die Hörzeit z − di mit v − 1 Liedern aus d1 , . . . , di−1 erreicht werden. Es gilt v − 1 < M(i, z) − 1 = min{M(i − 1, z), 1 + M (i − 1, z − di )} − 1 ≤ M (i − 1, z − di ). Dies ergibt einen Widerspruch zur Optimalität von M(i − 1, z − di ) nach I.V. Somit kann kein 0 ≤ z ≤ p existieren, sodass M(i, z) nicht den korrekten Wert für die minimale Anzahl an Liedern für alle i und alle z angibt. 

6

Präsenzaufgabe 7.4: (Datenstrukturen) Betrachten Sie die Löschen-Operation in Binärbäumen aus der Vorlesung (Foliensatz 11, Datenstrukturen). Zur Erinnerung: In Fall (c) wird vorausgesetzt, dass das zu löschende Element z zwei Kinder hat. Des Weiteren wird vorausgesetzt, dass alle Schlüssel unterschiedlich sind. Der Nachfolger eines Elements z ist das Element x, für das key[x] > key[z] gilt und es kein Element y mit key[y] > key[z] und key[ y] < key[x] gibt. Zeigen Sie folgende Aussage aus der Vorlesung (Folie 202): Der Nachfolger von z hat höchstens ein Kind. Lösung: Da der rechte Unterbaum rc[z] von z nicht leer ist (Fall (c)), liegt der Nachfolger x von z in rc[z]. Anderenfalls gäbe es einen Widerspruch zur Sortiereigenschaft des Baums, da alle Elemente außerhalb von rc[z] entweder einen kleineren Schlüssel als z haben, oder einen größeren als alle Elemente in rc[z] (vergleiche auch Nachfolgersuche, Folie 154). Angenommen, x hat zwei Kinder. Dann gilt für den linken Teilbaum von x, dass es mindestens ein Element y enthält, für das gilt: • key[y] < key[x], da y im linken Teilbaum von x liegt, und • key[y] > key[z], da y im rechten Teilbaum von z liegt. Dies ist ein Widerspruch zur Nachfolgereigenschaft von x. Also war die Annahme falsch und x hat höchstens ein Kind.

7...