6. Uebungsblatt (Loesungsvorschlag) PDF

Preview

Summary

Algorithmen und Datenstrukturen
SS 2020 Sabine Storandt...

Description

Algorithmen und Datenstrukturen Sommersemester 2020

6. Übungsblatt (Lösungsvorschlag) Abgabe (optional in Zweiergruppen) bis 09.06.20, 12:00 Uhr über ILIAS. Verwenden Sie die in ILIAS bereitgestellte LATEX-Vorlage und benennen Sie Ihre Abgabe nach dem Schema ads6_nachname1_nachname2.pdf (bzw. ads6_nachname.pdf, falls Sie alleine abgeben). Begründen Sie alle Ihre Behauptungen und kommentieren Sie Ihren Pseudocode. Aufgabe 1 - Stringtheorien (10 Punkte) Prüfen Sie, ob folgende Aussagen wahr oder falsch sind und begründen Sie Ihre Aussage. Gegeben sind immer zwei Wörter s und s′ mit Längen n und m, sowie m ≥ n. Falls nicht anders angegeben, nehmen wir bei der Editierdistanz Operationskosten von 1 für alle Operationen an. 1. ED(s, s′ ) ≥ m − |LGT S(s, s′ )| 2. Wenn Löschen 0 kostet und Einfügen 1, dann erhält man die minimale Editierdistanz, indem man zunächst alle Zeichen von s löscht und dann die Zeichen von s′ einfügt. 3. Wenn LGT S(s, s′ ) = LGT W (s, s′ ) gilt, dann haben s und s′ außerhalb von LGT W (s, s′ ) keine gemeinsamen Zeichen. 4. Wenn LGT S(s, s′ ) = si für ein i ∈ {1, . . . , n} gilt,1 dann haben s und s′ außerhalb von LGT S(s, s′ ) keine gemeinsamen Zeichen. 5. Falls in s′ genau m verschiedene Zeichen vorkommen und s das Wort s′ rückwärts ist, dann gilt ED(s, s′ ) = m. Lösungsvorschlag: 1. Die Aussage ist wahr. Überführt man das Wort s mit der minimalen Anzahl Operationen in das Wort s′ , so werden genau die Zeichen aus LGT S(s, s′ ) nicht verändert. Das Wort s′ hat somit genau m − |LGT S(s, s′ )| viele Zeichen, die beim Überführen erzeugt werden müssen, entweder durch Einfügen oder Ersetzen von Zeichen. Deshalb benötigt man mindestens m − |LGT S(s, s′ )| viele Operationen um s in s′ zu überführen. 2. Die Aussage ist falsch. Sei s = WERTPAPIERDIENSTLEISTUNGSRICHTLINIE und s′ = WOHNUNGSBAUFINANZIERUNGSGESELLSCHAFT. Löscht man alle Zeichen von s und fügt alle Zeichen von s′ ein, so hat dies Kosten 36. Löscht man hingegen alle Zeichen von s mit Ausnahme des ersten Zeichens und fügt nur die letzten 35 Zeichen von s′ hinzu, so kostet dies 35, also weniger. 3. Die Aussage ist falsch. Sei s = INSEL und s′ = LINSE. Es gilt LGT S(s, s′ ) = LGT W (s, s′ ) = INSE, allerdings haben s und s′ den Buchstaben L außerhalb von LGT W (s, s′ ) gemeinsam. 4. Die Aussage ist falsch. Sei s = AMPEL und s′ = LAMPE. Es gilt LGT S(s, s′ ) = AMPE = s4 , allerdings haben s und s′ den Buchstaben L außerhalb von LGT S(s, s′ ) gemeinsam. 5. Die Aussage ist falsch: Betrachtet man etwa die Wörter s = LAGER und s′ = REGAL, so ist s gleich dem Wort s′ rückwärts, aber es gilt ED(s, s′ ) = 4 6= m. Falls die Wortlänge m gerade ist, so ist die Aussage hingegen korrekt, da sich in diesem Fall an jeder Stelle die Buchstaben von s und s′ unterscheiden.

1

wie in der Vorlesung definiert sei si = s[1 . . . i] also das Teilwort von s bestehend aus den ersten i Zeichen

1

Aufgabe 2 - Duden-Editierdistanz (10 Punkte) Wir wandeln die Editierdistanz wie folgt ab: Es sind noch dieselben Operationen wie vorher erlaubt (Einfügen, Löschen und Ersetzen von einzelnen Zeichen), aber nun muss nach jeder Operation ein korrektes deutsches Wort entstehen (siehe Duden, inklusive Mehrzahl und gebeugter Formen); Beispiel von HAUS zu AAL: HAUS, AUS, AAS, AAL. Wandeln Sie folgende Wortpaare mit möglichst wenig Operationen ineinander um (Optimalität muss hier natürlich nicht gezeigt werden, aber es geht immer in weniger als zehn Schritten): OST zu WEST, RAST zu LOS, ZUNGE zu MAGEN, BODEN zu SEE, EINS zu ZEHN. Lösungsvorschlag: Wir verwenden im folgenden nur die Grundformen, die im Duden stehen, auch wenn Plural- und gebeugte Formen zulässig waren. • OST → POST → PEST → WEST • RAST → LAST → LOST2 → LOS • ZUNGE → ZANGE → MANGE3 → MAGE4 → MAGEN • BODEN → BOGEN → WOGEN5 → WEGEN → FEGEN → FEGE6 → FEE → SEE • EINS → EIN → FEIN → FEHN7 → ZEHN Aufgabe 3 - Meditierdistanz (10 Punkte) a)

(8 Punkte) Beweisen Sie, dass die Editierdistanz eine Metrik darstellt, wenn alle Operationen (Löschen, Einfügen, Ersetzen) die gleichen positiven Kosten haben. Zur Erinnerung: Eine Metrik d : M × M → R auf einer Menge M erfüllt für beliebige Elemente a, b, c aus M folgende Axiome: • positiv definit, d.h. d(a, b) ≥ 0 und d(a, b) = 0 gdw. a = b, • symmetrisch, d.h. d(a, b) = d(b, a), • erfüllt Dreiecksungleichung, d.h. d (a, b) + d (b, c) ≥ d(a, c). Geben Sie ein Beispiel für positive Kosten von Löschen, Einfügen und Ersetzen an, sodass die dadurch definierte Editierdistanz keine Metrik mehr darstellt. Geben Sie explizit an, welche Eigenschaften verletzt sind und warum.

b)

(2 Punkte) Sind die Länge des längsten gemeinsamen Teilwortes oder die Länge der längsten gemeinsamen Teilsequenz Metriken? Begründen Sie!

2

Lost, der (militärisch): Senfgas, nach den Chemikern Lommel und Steinkopff benannt. https://www.duden. de/rechtschreibung/Lost 3 Mange, die (süddeutsch, schweizerisch): größeres Gerät, in dem Wäsche zwischen zwei rollenden Walzen geglättet wird. https://www.duden.de/rechtschreibung/Mange 4 Mage, der (Rechtssprache veraltet): Blutsverwandter. https://www.duden.de/rechtschreibung/Mage 5 wogen (gehoben): sich in Wogen [gleichmäßig] auf und nieder bewegen. https://www.duden.de/ rechtschreibung/wogen 6 Fege, die: Werkzeug zum Getreidereinigen. https://www.duden.de/rechtschreibung/Fege 7 Fehn, das (norddeutsch): Moor, Sumpfland. https://www.duden.de/rechtschreibung/Fehn

2

Lösungsvorschlag: a)

Wir beweisen zunächst die drei Eigenschaften, wenn alle Operationen die gleichen positiven Kosten c haben. Wir beobachten, dass in diesem Fall eine Operationssequenz σ1 , . . . , σk der Länge k mit Kosten k · c verbunden ist. • positiv definit: Gilt a = b, so gilt ED(a, b) = 0, da wir a mit der leeren Operationssequenz in b überführen können, welche Kosten 0 hat. Gilt a 6= b, so gibt es eine Operationssequenz der Länge k > 0, die a in b überführt. Beispielsweise kann man alle Zeichen von a löschen und anschließend alle Zeichen von b einfügen. Allerdings gibt es keine Sequenz der Länge 0, die a in b überführt. Somit gilt ED(a, b) > 0. • symmetrisch: Sei S eine optimal Operationssequenz, die a in b überführt, und sei k die Länge von S. Wir konstruieren eine zweite Operationssequenz S ′ , indem wir jede Löschoperation in S durch eine Einfügeoperation ersetzen und umgekehrt. Außerdem vertauschen wir die beiden Zeichen jeder Ersetzungsoperation. Die entstehende Sequenz S ′ hat ebenfalls Länge k (und somit gleiche Kosten wie S) und überführt b in a. Es kann außerdem keine kürzere Sequenz der Länge k ′ < k geben, welche b in a überführt, da wir sonst auf die gleiche Art und Weise eine Sequenz der Länge k ′ konstruieren könnten, welche a in b überführt. Somit gilt ED(a, b) = ED (b, a). • Dreiecksungleichung: Sei S eine Operationssequenz der Länge k, welche a in b überführt und S ′ eine Operationssequenz der Länge k ′ , welche b in c überführt. Dann können wir a in c überführen, indem wir zunächst S und dann S ′ ausführen, was Kosten k · c + k ′ · c hat. Es folgt ED(a, b) + ED(b, c) ≥ ED(a, c).

b)

Wir betrachten nun den Fall, dass Löschen und Ersetzen Kosten 1 haben, Einfügen aber Kosten 2. Die resultierende Editierdistanz ist positiv definit und erfüllt die Dreiecksungleichung, allerdings ist sie nicht symmetrisch, da z.B. ED(PILOT, PI) = 3 und ED(PI, PILOT) = 6 gilt. Beides sind keine Metriken, da sie nicht positiv definit sind. So gilt etwa für s = CHRISTBAUM und s′ = LÖWENKOPF, dass |LGT S(s, s′ )| = |LGT W (s, s′ )| = 0, aber s 6= s′ . Aufgabe 4 - Amortisierte Analyse (10 Punkte)

a)

(4 Punkte) In der Vorlesung haben wir für 1-dimensionale Felder bzw. Tabellen besprochen, wie man diese dynamisch vergrößern kann und dabei amortisiert konstante Kosten erhält. Wir betrachten nun 2-dimensionale Felder. Es gilt wiederum, dass das Feld verdoppelt wird, sobald es gefüllt ist, und zwar nun in jeder Dimension. Hat das Feld also gerade Größe 2 × 2 und wir fügen das 5. Element ein, stocken wir das Feld auf eine Größe von 4 × 4 auf. Beim 17. Element vergrößern wir das Feld dann auf 8 × 8, usw. Analysieren Sie die amortisierten Kosten, sowohl mit der Aggregationsmethode als auch mit der Bankkonto/Buchhaltermethode.

b)

(6 Punkte) Auf dem 4. Übungsblatt hatten wir in Aufgabe 3a) die Operation betrachtet, die für einen gegebenen Knoten x in einem balancierten Binärsuchbaum den Knoten mit nächstgrößeren Schlüssel (den sogenannten Successor) zurückgibt, oder zertifiziert, dass x der Knoten mit dem größten Schlüssel ist. Die Worst-Case-Laufzeit dieser Operation liegt in O(log n). Wir betrachten nun den Fall, dass wir diese Operation für jeden der n Schlüssel genau ein Mal aufrufen. Die Gesamtlaufzeit können wir dann naiv mit O(n log n) abschätzen. Zeigen Sie, dass die amortisierten Kosten der Einzeloperation jedoch in O(1) liegen. Lösungsvorschlag:

a)

Aggregationsmethode: Seien ci die Kosten für die i-te Einfügung. Das Feld ist nach jeder (2j )2 = 4j -ten Einfügung voll. Deshalb muss bei jeder (4j + 1)-ten Einfüge-Operation ein Feld

3

der Größe (2j+1)2 = 4j+1 angelegt werden, das alte Feld der Größe 4j kopiert werden und die eigentliche Einfügeoperation durchgeführt werden. In diesem Fall gilt also ci = 4j+1 + 4j + 1 = 5 · 4j + 1. In allen anderen Fällen gilt ci = 1, da nur eingefügt werden muss. Wir erhalten amortisierte Kosten von n X i=1

ci =

log 4n X



j



5·4 +1 =n+5·

j=0

log 4n X j=0

5 4j = n + (4n − 1) ≤ 8n 3

für n sequentielle Einfügungen. Bankkontomethode: Wir setzen für jede Operation amortisierte Kosten c′i = 8 an. Bei billigen Einfügungen (also Operationen i 6= 4j + 1; siehe Überlegungen bei der Aggregationsmethode) sind die tatsächlichen Kosten ci = 1, wir können also 7 Währungseinheiten beiseite legen. Jede i = (4j +1)-te Operation hat tatsächliche Kosten ci = 5 · 4j +1 (siehe Aggregationsmethode). Bei einer solchen Operation haben die letzten 34 4j = 3·4j−1 Einfügungen jeweils 7 Währungseinheiten zurückgelegt. Des weiteren zahlen wir amortisierte Kosten c′i = 8 für die Operation selbst. Das Restguthaben nach der (4j + 1)-ten Einfügung ist deshalb   7 · 3 · 4j−1 + 8 − 5 · 4j + 1 = 7 + (21 − 20) · 4j−1 ≥ 7.

b)

Somit rutschen wir auch mit der i = (4j + 1)-ten Operation nicht ins Minus, sondern können weiterhin Kosten 7 zurücklegen. Algorithmus 1 zeigt eine mögliche Implementierung der angesprochenen Operation. Wir können Algorithmus 1 : next(Node x) 1 2 3 4 5 6 7 8 9 10 11 12

if x.right 6= null then x ← x.right while x.left 6= null do x ← x.left return x else while x.parent 6= null do c←x x ← x.parent if c = x.left then return x return null

beobachten, dass die Laufzeit eines einzelnen Aufrufs dadurch bestimmt wird, wie oft die beiden Schleifen durchlaufen werden. Somit lässt sich die asymptotische Laufzeit bestimmen, indem wir zählen, wie oft die Zeilen 4 (x ← x.left) und 9 (x ← x.parent) ausgeführt werden. Bildlich gesprochen laufen wir in den beiden Zeilen von einem Knoten x zu seinem linken Kind oder zum Elternknoten. Betrachten wir nun den Fall, dass die Operation für jeden Schlüssel genau ein mal aufgerufen wird und nehmen zur Illustration den folgenden Suchbaum: 4 2 1

6 3

5

4

7

Das Verhalten des Algorithmus lässt sich anhand der folgenden Suchpfade beschreiben: x←x.parent

• next(1): 1 −−−−−−−→ 2 x←x.right

• next(2): 2 −−−−−−→ 3 x←x.parent

x←x.parent

• next(3): 3 −−−−−−−→ 2 −−−−−−−→ 4 x←x.right

x←x.left

• next(4): 4 −−−−−−→ 6 −−−−−→ 5 x←x.parent

• next(5): 5 −−−−−−−→ 6 x←x.right

• next(6): 6 −−−−−−→ 7 x←x.parent

x←x.parent

x.parent=null

• next(7): 7 −−−−−−−→ 6 −−−−−−−→ 4 −−−−−−−−→ null Wir können beobachten, dass für jeden Knoten x die Anweisungen x ← x.left und x ← x.parent höchstens einmal ausgeführt wird. So geht man vom Knoten 6 etwa nur beim Aufruf von next(7) zum Elternknoten und nur beim Aufruf von next(4) nach links. Allgemein gilt, dass man von einem Knoten x nur dann nach links geht, wenn man sich in einem Aufruf next(y) befindet, wobei y der erste Knoten auf dem Weg von x zur Wurzel ist, in dessem rechten Teilbaum sich x befindet. Des weiteren geht man von einem Knoten x nur dann nach oben, wenn man sich in einem Aufruf next(y) befindet, wobei y der Knoten mit dem größten Wert im rechten Teilbaum von x ist. Somit werden die Zeilen 4 und 9 im Verlauf der n Aufrufe jeweils höchstens n mal aufgerufen. Die Gesamtlaufzeit beträgt also O(n) und die amortisierten Kosten einer Einzeloperation O(1).

5...