Algorithmen und Programmierung 3, WS 2015/2016 | 1. …alp3.pdf · 2016-04-12 · Zusatzaufgabe (0 Punkte): Bestimmen Sie jeweils die Anzahl der mehrfach vorkom-menden Werte:

Algorithmen und Programmierung 3, WS 2015/2016 — 1. Ubungsblatt

Abgabe bis Freitag, 23. Oktober 2015, 12:00 Uhr, in die Facher der TutorenAbzugeben sind diesmal die Aufgaben 1, 2, und 6. Null-Punkte-Aufgaben sind zur

freiwilligen Vertiefung gedacht und werden nicht abgegeben.

1. (i) Vorubung: Wachstum von Laufzeiten, 4 Punkte

Sortieren Sie die folgenden Laufzeiten aufsteigend: Wenn f(n) = O(g(n)) ist,aber nicht g(n) = O(f(n)), dann soll f(n) vor g(n) kommen.

(a) n3 (b) log2 n (c) 1,8n (d) n (e) 3n (f)√n (g) n(log2 n)2 (h) n2

(ii) Beschleunigung der Hardware, 4 Punkte

Wenn ein Programm eine Laufzeit f(n) aus Aufgabe (i) hat und die Computerin zehn Jahren um den Faktor 1000 schneller werden, dann kann man Problemewelcher Große in derselben Zeit losen, in der man heute Probleme der Große(1) n = 20, (2) n = 1000 losen kann?

2. (2 Punkte) Die Computer werden immer schneller, die Speicherelemente immer billi-ger. Wird der Entwurf von effizienten Algorithmen angesichts dieser Entwicklung inZukunft an Bedeutung verlieren? Bei welchen Computeranwendungen werden Effizi-enzfragen eine großere/kleinere Rolle spielen?

Diskutieren Sie diese Fragen. (mindestens 5–10 Zeilen)

3. Korrektheit von Programmen, 0 Punkte

Das folgende Programmstuck ist ein Versuch, Sortieren durch Einfugen zu implemen-tieren.

void insertionSort(float[] a)

{ float x;

for (int i = 0; i<a.length; i++)

{ † x = a[i];

// Sortiere x zwischen a[0..i-1] ein// Bestimme zunachst die richtige Position j:

(∗) int j=i-1; † while (j>=0 && a[j-1]>x) j-- † ;

// Nun verschiebe einen Teil des Feldes und fuge x an dieser Stelle ein:† for (int k = i-1; k>=j; k--) a[k+1]=a[k];

a[j]=x; †

}

}

Stellen Sie dieses Programm richtig und fugen Sie an den durch † bezeichneten Stellenin Ihrem Programm Schleifeninvarianten in der Form vom Zusicherungen (assertions)ein, aus denen die Korrektheit des Programmes hervorgeht. (Ein formaler Beweis istnicht erforderlich, aber die Zusicherungen mussen aussagekraftig sein und vor allemzutreffen.)

4. (0 Punkte) Kann man Sortieren durch Einfugen schneller machen, indem man dieEinfugestelle j schneller findet als oben in Zeile (∗), zum Beispiel durch binare Suche?Wie ist es im besten und im schlechtesten Fall?

1

5. (0 Punkte) Was passiert bei (i) Sortieren durch Einfugen, (ii) Sortieren durch Aus-wahl, wenn die gegebene Folge bereits (a) aufsteigend oder (b) absteigend sortiertist? (c) Was passiert, wenn alle Elemente gleich sind? Ist es moglich, dass man bloßO(n) Zeit benotigt?

6. Programmierexperiment zum Sortieren, 10 Punkte

Schreiben Sie ein Programm in Java zum Sortieren von Zahlen, und testen Sie es mit20 Millionen zufallig erzeugten Gleitkommazahlen einfacher Genauigkeit (float).

• Programmieren Sie das Verfahren Quicksort. Wenn die Lange der zu sortieren-den Teilfolge in der Rekursion unter eine Schranke b sinkt, dann soll aber aufeine einfacheres Sortierverfahren ihrer Wahl umgeschaltet werden (z. B. Sortie-ren durch Einfugen, Sortieren durch Auswahl, Bubblesort).

• Das Pivotelement, das bei Quicksort zum Zerlegen der Folge verwendet wird,soll in jeder Teilfolge zufallig ausgewahlt werden.

• Messen Sie die Laufzeit. Zahlen Sie auch die Anzahl der Vergleiche zwischen denEingabezahlen mit und geben Sie sie aus.

• Experimentieren Sie mit mindestens drei verschiedenen Werten von b, und ver-suchen Sie experimentell, den besten Wert zu finden.

• Die Eingabewerte sollen gleichverteilt im Intervall [0, 1] erzeugt werden.

• Machen Sie jeweils (mindestens) zehn Durchlaufe mit verschiedenen Datensatzen,und dokumentieren Sie die Ergebnisse. Geben Sie auch die DurchschnittswerteIhrer Programmlaufe an.

Zusatzaufgabe (0 Punkte): Bestimmen Sie jeweils die Anzahl der mehrfach vorkom-menden Werte: Wieviele Zahlen kommen mindestens zweimal in der Eingabe vor?

Anleitung zur Abgabe der Programmieraufgabe: Laden Sie die dokumentierten Quell-texte (zum Beispiel als zip-komprimierten Ordner) auf der KVV-Seite der Veran-staltung1 bis zum Abgabetermin (Freitag, 23. Oktober 2015, 12:00 Uhr) hoch. FugenSie eventuell eine README-Datei hinzu, wenn der Aufruf des Programmes und dieBenutzung nicht selbsterklarend ist.

Geben Sie zusatzlich den ausgedruckten Quellcode und die Ergebnisse der Testlaufeauf Papier ab.

7. Vergleich von asymptotischen Laufzeiten, 0 Punkte

Welche der beiden folgenden Laufzeiten f(n) und g(n) ist fur große Werte von nschneller, und welche fur kleine n? Bei welchem Wert von n andert sich die Antwort?

(a) f(n) = 10n(log2 n)2, g(n) = 2n3/2

(b) f(n) = 5 · 2n, g(n) = 100n2 log2 n

8. Wiederholung der O-Notation, 0 Punkte

(a) Beweisen Sie: Wenn f(n) = O(g(n)) ist, dann ist f(n) + g(n) = O(g(n)).

(b) Beweisen Sie: max{f(n), g(n)} = Θ(f(n) + g(n)) fur f(n), g(n) > 0.

(c) Welche der folgenden Aussagen sind richtig (Begrunden Sie Ihre Antworten):n√n = O(n(log n)2); n(log n)2 = O(n

√n); n log n · (log log n) = O(n2);

n2 = O(n log n ·(log log n)); n2 ·2n = O(2n+2); n2 ·2n = O(3n); 3n = O(n2 ·2n);

1http://kvv.imp.fu-berlin.de

2


Abgabe bis Freitag, 30. Oktober 2015, 12:00 Uhr, in die Facher der Tutoren

9. Topologisches Sortieren, 5 Punkte

Geben Sie alle moglichen topologischen Sortierungen fur folgende Eingabe an:Es gibt n = 6 Knoten, und die Kanten sind {(6, 4), (3, 5), (4, 2), (3, 4), (5, 4), (1, 2),(1, 6), (3, 6)}.


(a) Was passiert beim in der Vorlesung angegebenen Algorithmus fur topologischesSortieren, wenn ein Paar (i, j) in der Eingabe mehrfach auftritt? Was passiert,wenn ein Paar (i, i) auftritt?

(b) Untersuchen Sie verschiedene Moglichkeiten, wie man die Liste der freien Ele-mente beim topologischen Sortieren verwalten kann, im Hinblick auf ihre Effizi-enz. Kann man auf diese Liste auch ganzlich verzichten?

(c) Welche Variablen oder Attribute im Programm aus der Vorlesung1 konnte manohne Nachteil einsparen?

11. Zirkulare Abhangigkeit, 9 Punkte

Erweitern Sie den Algorithmus zum topologischen Sortieren aus der Vorlesung, sodassbei der Existenz eines gerichteten Kreises nicht einfach mit einer Meldung abgebro-chen wird, sondern auch ein Kreis (als

”Beweis“) ausgegeben wird.

Beschreiben Sie Ihren erweiterten Algorithmus in Pseudo-Code. (Zum Beispiel konnenSie eine Schleife “fur alle Elemente x . . . ” schreiben.)

Erklaren Sie Ihren Algorithmus in Worten, ohne notwendigerweise auf Details derImplementierung einzugehen. (Sie mussen nur das erklaren, was gegenuber dem ur-sprunglichen Algorithms neu ist. Ein Korrektheitsbeweis ist nicht verlangt.)

12. Programmieraufgabe, 6 Punkte, hochzuladen auf der KVV-Seite der Veranstaltung

Schreiben Sie ein Java-Programm fur die vorige Aufgabe. Sie konnen das Programmaus der Vorlesung1 erweitern. Ihr Programm soll nicht mehr als O(m+n) zusatzlicheZeit und nicht mehr als O(n) zusatzlichen Speicher brauchen.

13. Binarbaume, 0 Punkte

Ein vollstandiger binarer Baum der Hohe h ist ein binarer Baum, bei dem jederKnoten mit Tiefe ≤ h− 2 genau zwei Kinder hat.

(a) Zeichnen Sie vollstandige binare Baume mit 12 und mit 15 Knoten.

(b) Wieviele Knoten kann ein vollstandiger binarer Baum der Hohe h mindestensund hochstens haben?

(c) Welche Hohe kann ein vollstandiger binarer Baum mit n Knoten haben?

14. Asymptotisches Wachstum, 0 Punkte

Finden Sie moglichst einfache Ausdrucke der Form Θ(·) fur folgende Funktionen:

(a) 3n2 − 4n + 23 + 27n · dlog2 ne/2 (c) 22n+dlog2 ne (e) 2blog4 nc

(b) max{ndlog2 ne, (dlog2 ne)4} (d) 1.82dlog2 ne (f) 2blog3 nc+dlog4 ne

1http://www.inf.fu-berlin.de/lehre/WS15/ALP3/TopoSort.java

3


Abgabe bis Freitag, 6. November 2015, 12:00 Uhr, in die Facher der Tutoren

15. algebraischen Spezifikation fur Mengen, 7 Punkte

Leiten Sie aus der algebraischen Spezifikation fur Mengen

istenthalten(x, leereMenge) = False

istenthalten(x, einfuge(x,m)) = Trueistenthalten(x, einfuge(y,m)) = istenthalten(x,m), fur x 6= y

istenthalten(x, losche(x,m)) = Falseistenthalten(x, losche(y,m)) = istenthalten(x,m), fur x 6= y

(mit den Signaturen von einfuge, losche, leereMenge, und istenthalten wie in derVorlesung) durch Umformungen folgende Identitat her: Fur x 6= y gilt

istenthalten(u, losche(x, einfuge(y,m))) = istenthalten(u, einfuge(y, losche(x,m))).

16. Vereinigung und Durchschnitt, 0 Punkte

Erweitern Sie die algebraische Spezifikation von Mengenoperationen aus der vorigenAufgabe um die Funktionen Vereinigung und Durchschnitt (von je zwei Mengen).

17. Stuckweise konstante Funktionen, 0 Punkte

Wie wird die stuckweise konstante Funktion h(x) = bx/2c−d(1−x)/3e, definiert fur0 ≤ x < 10 in dem Format, das in der Vorlesung vorgestellt wurde, dargestellt?

18. Verschieben von Funktionen, 6 Punkte, Programmieraufgabe

(a) Schreiben Sie eine Python-Funktion, die eine stuckweise konstante Funktion Fum einen Parameter b ∈ R verschiebt:

H = verschiebe(F,b)

Es soll H(x) = F (x + b) sein uberall dort, wo F (x + b) definiert ist.

(b) Zusatzfrage, 0 Punkte

Wie entsteht der Graph von H aus dem Graphen von F , wenn b = 1 ist?

19. Fallunterscheidung, 7 Punkte, Programmieraufgabe

Schreiben Sie eine Python-Funktion

H = fallunterscheidung(b,F,G)

die bei Eingabe von zwei stuckweise konstanten Funktion F und G und einem Para-meter b ∈ R die Funktion H erzeugt, die folgendermaßen definiert ist:

H(x) =

{F (x), wenn x < b

G(x), wenn x ≥ b

Erganzen Sie diese Spezifikation, falls Sie es fur erforderlich halten, zum Beispieldurch Angabe von passenden Vorbedingungen.

4

20. Erzeugen stuckweise konstanter Funktionen, 0 Punkte

In der Vorlesung wurden gar nicht spezifiziert, wie man eine stuckweise konstanteFunktion erzeugen kann. Ohne diese Moglichkeit sind stuckweise konstante Funk-tionen als abstrakter Datentyp aber gar nicht brauchbar. Spezifizieren Sie eine odermehrere Operationen fur einen abstrakten Datentyp

”stuckweise konstante Funkti-

on“, die es ermoglichen, beliebige stuckweise konstante Funktionen zu erzeugen (even-tuell unter Zuhilfenahme der in den vorigen Aufgaben definierten Operationen).

21. Stuckweise lineare stetige Funktionen, 0 Punkte

Statt stuckweise konstanten Funktionen wollen wir stetige und stuckweise lineareFunktionen betrachten, die auf einem abgeschlossenen Intervall [a, b] definiert sind,wie die Funktion f(x) im folgenden Beispiel:

x

f(x)

1 2 3 5.5 7

1

2

3

4

(3x−1)/2

2(13− x)/5

17/2−x

(3; 4)

(5.5; 3)

(7; 1.5)

(1; 1)

Uberlegen Sie sich eine Datenstruktur (Haskell-Datentyp, Java-Klasse, oder Python-Klasse) zur Darstellung solcher Funktionen. Schreiben Sie eine Funktion/Methode,die den Wert einer solche Funktion f(x) an einer gegebenen Stelle x ausrechnet.

22. Generatorfunktionen, 0 Punkte

Schreiben Sie die Python-Funktion add(F,G) aus der Vorlesung mit einer Gene-ratorfunktion statt mit der Variablen ausgabe, auf der das Ergebnis akkumuliertwird.

23. Gleichheitstest, 0 Punkte

Schreiben Sie eine Funktion, die zwei stuckweise konstante Funktionen auf Gleichheittestet. Die Definition der Gleichheit ist dabei die ubliche Definition fur Funktionen:Zwei Funktionen sind gleich, wenn sie den gleichen Definitionsbereich haben undwenn sie an allen Stellen des Definitionsbereiches denselben Wert liefern.

24. Stuckweise konstante Funktionen in Java, 0 Punkte

(a) Schreiben Sie eine abstrakte Klasse oder ein Interface fur den abstrakten Daten-typ stuckweise konstante Funktion mit den Operationen aus der Vorlesungund aus den obigen Aufgaben.

(b) Implementieren Sie den Datentyp.

25. Stuckweise konstante Funktionen in Haskell, 0 Punkte

(a) Durch welche Merkmale der Sprache Haskell wird das Konzept der abstraktenDatentypen unterstutzt? (Typklassen? Module?)

(b) Implementieren Sie stuckweise konstante Funktionen in Haskell.

5


Abgabe bis Freitag, 13. November 2015, 12:00 Uhr, Aufgabe 29 korrigiert am 7.11.

26. Volle Binarbaume, 6 Punkte (zu unterscheiden von vollstandigen Binarbaumen)

(a) (0 Punkte) In einem vollen binaren Baum hat jeder innere Knoten zwei Kinder.Man kann einen beliebigen Binarbaum als vollen Binarbaum darstellen, indemman fur jedes fehlende Kind eines Knotens ein neues Blatt (einen externenKnoten) einsetzt. Alle ursprunglichen Knoten werden zu inneren Knoten, unddie neuen Blatter reprasentieren die null/Nil-Zeiger im ursprunglichen Baum.Zeigen Sie, dass ein voller binarer Baum mit n Blattern n−1 innere Knoten hat.

(b) (6 Punkte) Beweisen Sie, dass in einem vollen binaren Baum mit n Blattern aufTiefe l1, . . . , ln die folgende Gleichung gilt:

n∑

i=1

2−li = 1

(c) (0 Punkte) Fur jede Folge l1, . . . , ln ganzer Zahlen, die die obige Gleichungerfullt, gibt es einen vollen binaren Baum mit n Blattern auf Tiefe l1, . . . , ln.

27. Mittlere Weglange, 7 Punkte (Programmieraufgabe, eine ehemalige Klausuraufgabe)

Schreiben Sie ein Programm in Java oder Haskell, das fur einen gegebenen binarenSuchbaum die mittlere innere Weglange berechnet; sie ist um 1 kleiner als die erwar-tete Anzahl von Vergleichen, die zum Finden eines zufallig ausgewahlten Knotensin dem Baum im Durchschnitt erforderlich sind. (Jeder Knoten wird mit gleicherWahrscheinlichkeit gesucht.)

Ihr Programm muss ubersetzbar und laufffahig sein, aber nicht vollstandig in demSinn, dass Sie zum Beispiel das Suchen und alle notwendigen und nutzlichen Me-thoden fur eine Klasse Baum programmieren mussen. Beschranken Sie sich auf diegestellte Aufgabe. Man muss das Programm testen konnen.

28. Umwandeln einer Liste in einen Baum, 0 Punkte (eine ehemalige Klausuraufgabe)

Schreiben Sie ein Programm in Java oder Haskell, das eine sortierte Liste von nganzen Zahlen in einen binaren Suchbaum der kleinstmoglichen Hohe h umwandelt.

h = dlog2(n + 1)e − 1

29. AVL-Baume, 7 Punkte

Fugen Sie nacheinander die Schlussel 1, 20, 50, 40, 30, 35, 60, 70 in einen anfangsleeren AVL-Baum ein. Entfernen Sie dann die Schlussel 35 und 1. Zeichnen Sie denAVL-Baum nach jeder Operation auf.

30. Blatter mit unterschiedlicher Tiefe, 0 Punkte

Was ist die kleinste Tiefe, die ein Blatt in einem AVL-Baum der Hohe h haben kann?

31. Rotationen und Doppelrotationen, Programmierung, 0 Punkte

Schreiben Sie ein Programmstuck fur (a) eine Linksrotation, (b) eine Doppelrotation,die mit einer Linskrotation beginnt. Verwenden Sie dafur moglichst wenige Zuweisun-gen. Die Eingabe ist ein Zeiger auf die Wurzel des betroffenen Teilbaumes. KommenSie dabei ohne simultane Zuweisungen an mehrere Variablen gleichzeitig aus, wie essie zum Beispiel in Python gibt.

6


Abgabe bis Freitag, 20. November 2015, 12:00 Uhr, Aufgabe 33 korrigiert am 18.11.

32. Rotationen, 0 PunkteBeweisen Sie: Jeder Suchbaum fur n Schlussel kann durch einen Folge von Rotationenin jeden anderen Suchbaum fur diese Schlussel transformiert werden.Zusatzfrage (offen): Gilt diese Aussage auch fur AVL-Baume, wenn alle Zwischener-gebnisse ebenfalls AVL-Baume sein mussen?

33. Analyse von Skiplisten, 7 PunkteL sei eine Skipliste mit n Eintragen. Zeigen Sie:

(a) Die erwartete Anzahl von Knoten in L (ausgenommen die Listenkopfe) ist 2n.

(b) Die Wahrscheinlichkeit, dass L aus mehr als k Listen besteht, ist hochstensn/2k. Hinweis: Fur Ereignisse A1, . . . , An gilt die Vereinigungsschranke:Pr[A1 ∨ · · · ∨An] ≤∑n

i=1 Pr[Ai], wobei”Pr“ die Wahrscheinlichkeit bedeutet.

34. Erweiterte Suchanfragen fur binare Baume, 6 Punkte

Die Knoten x eines Suchbaumes enthalten neben den Kinderzeigern x.links undx.rechts auch den Schlussel x.s und einen ganzzahligen Wert x.w. Wir wollen nunfolgende Anfragen beantworten: Fur zwei gegebene Schranken a und b soll die Summealle Werte der Eintrage bestimmt werden, deren Schlussel s im Intervall a < s ≤ bliegt. Erwertern Sie die Baumknoten um geeignete Attribute, damit diese Anfragen inLaufzeit proportional zur Hohe des Baumes beantwortet werden konnen. SchreibenSie dazu eine Funktion in Pseudocode, die als Eingabe a und b und einen Zeigers tauf die Wurzel des Baumes bekommt. Erlautern Sie auch, wie die neuen Attributebeim Erstellen oder beim Umbau des Baumes rekursiv berechnet werden.

35. Integrieren, 7 PunkteDas Integral einer stuckweise konstanten Funktion g : [a, b) → R ist eine stuckweiselineare stetige Funktion f : [a, b]→ R, wie in Aufgabe 21 vom 3. Zettel definiert:

f(x) =

∫ x

u=ag(u) du

(a) (Vorbereitung, 0 Punkte) Denken Sie sich eine stuckweise konstante Funktion gmit mindestens drei Stucken aus, und berechnen Sie dann f . Fur welche Eingabeg ergibt sich die Beispielfunktion f , die bei Aufgabe 21 abgebildet ist?

(b) (Programmieraufgabe, 7 Punkte) Schreiben Sie ein Programm, um eine Dar-stellung von f aus g zu berechnen. Erlautern Sie, welche Darstellung von fSie gewahlt haben. Programmieren Sie auch die Auswertung einer stuckweiselinearen Funktion f(x) an der Stelle x.

(c) (Zusatzaufgabe, 0 Punkte) Wenn f : [a, b] → R eine stuckweise lineare stetige

Funktion ist, dann ist die rechtsseitige Ableitung f+(x) = limt→0+f(x+t)−f(x)

teine stuckweise konstante Funktion f+ : [a, b)→ R. Schreiben Sie ein Programmzur Berechnung von f+ aus f .

36. 2-3-Baume, 0 PunkteKonstruieren Sie fur jede Hohe h ≥ 1 einen 2-3-Baum mit Hohe h und folgenderEigenschaft: Man kann ein neues Element x einfugen, sodass man den gesamten Wegzur Wurzel durchlaufen muss und sich die Hohe um 1 erhoht. Beim anschließendenEntfernen dieses Elementes x wird der ursprungliche Zustand wiederhergestellt. (Bei2-4-Baumen kann das nicht passieren.)

7


Abgabe bis Freitag, 27. November 2015, 12:00 Uhr.

37. Suffixbaum und Verschiebefunktion, 7 Punkte

(a) (0 Punkte) Bestimmen Sie den Suffixbaum und

(b) (7 Punkte) die Verschiebefunktion fur folgende Zeichenkette:

a

a

b

b

b

c

c

c

a

b

b

c

c

c

a

a

a

b

c

c

a

a

a

b

b

b

c

b

b

c

c

c

a

a

a

b

38. Teilwortsuche mit Fingerabdrucken, 7 Punkte

Die Rabin-Karp-Methode mit dem Modul M soll zur Suche einer Teilfolge der Lange12 uber dem Alphabet Σ = {0, 1, . . . , 9} verwendet werden. Finden Sie zwei verschie-dene, aber moglichst ahnliche Worter u, v ∈ Σ12, die den gleichen Fingerabdruck ha-ben. Sie durfen sich fur einen der Moduln (a) M = 3163, (b) M = 1111, (c) M = 9876entscheiden.

39. Schnelle Teilwortsuche, 0 Punkte

Wir wollen ein Muster der Lange m in einem Text der Lange n suchen. Herr B. C.Dom hat ein neues Teilwortsuchverfahren entwickelt, und er preist es damit an, dass esnach einer Vorverarbeitung des Musters

”im gunstigsten Fall“ nur dn/me−1 Zeichen

des Textes anschauen muss, um zu entscheiden, ob das Muster im Text vorkommt.Beweisen Sie, dass das unmoglich ist.

40. Teilwortsuche, 6 Punkte

Wie kann man aus der Verschiebefunktion des Wortes xy ablesen, ob x ein Teilwortvon y ist, wenn man |x| = m und |y| = n kennt?

41. (0 Punkte) Fur zwei Worter x und y der Lange n ist x eine zyklische Verschiebungvon y, wenn man x = ab und y = ba fur zwei Worter a und b schreiben kann. Wiekann man in linearer Zeit feststellen, ob x eine zyklische Verschiebung von y ist?(Man kann diese Frage auf das Teilwortproblem zuruckfuhren.)

42. Verbesserung der Verschiebefunktion, 0 Punkte

Die verbesserte Verschiebefunktion f zum Suchen eines Musters b1b2 . . . bm ist furj = 2, . . . ,m folgendermaßen definiert:

f(j) := max({ k | 0 ≤ k < j − 1, b1 . . . bk = bj−k . . . bj−1 und bk+1 6= bj } ∪ {0}

)

Fur j = m+ 1 stimmt f(m+ 1) mit der ursprunglichen Verschiebefunktion f(m+ 1)aus der Vorlesung (ohne die Bedingung

”bk+1 6= bj“) uberein.

(a) Berechnen Sie die verbesserte Verschiebefunktion des Musters aus Aufgabe 37.

(b) Begrunden Sie, warum die Teilwortsuche mit der verbesserten Verschiebefunk-tion immer noch korrekt ist.

(c) Zeigen Sie, dass beim Suchen mit der verbesserten Verschiebefunktion auf kei-nen Fall mehr Vergleiche der Form ai = bj durchgefuhrt werden als mit derursprunglichen Verschiebefunktion f . Finden Sie ein Beispiel, bei dem echt we-niger Vergleiche notwendig sind.

(d) Auf der rechten Seite kann {0} sogar durch {−1} ersetzt werden; man mussdann allerdings die Suchprozedur anpassen.

(e) Schreiben Sie einen Algorithmus zum Berechnen von f in linearer Zeit.

8


Abgabe bis Freitag, 4. Dezember 2015, 12:00 Uhr.

43. Adjazenzlisten, 0 Punkte

Wie kann man auf einfache Art uberprufen, ob ein Graph, der mit Adjazenzlistengespeichert ist, ein einfacher Graph ist (keine mehrfachen Kanten enthalt)? VersuchenSie, mit O(m+n) Zeit und mit moglichst wenig zusatzlichem Speicher auszukommen.


Betrachten wir die Knoten u eines Graphen in der Reihenfolge, wie der rekursiveAufruf T (u) bei der Tiefensuche beendet wird. Das heißt, wir fugen am Ende desProgramms T (u) folgende Zeile ein:

num2 := num2+1; T2Nummer[u] := num2;

(a) (0 Punkte) Wenn der Vorganger f [v] von v gleich u ist, welche Beziehung bestehtdann zwischen T2Nummer[u] und T2Nummer[v]?

(b) (4 Punkte) Beweisen Sie: Wenn es eine Kante (u, v) mit

T2Nummer[v] > T2Nummer[u]

gibt, dann enthalt der Graph einen Kreis.

(c) (4 Punkte) Wie kann man diesen Kreis bestimmen? Schreiben Sie ein Pro-grammstuck in Pseudocode, das den Kreis aus u und v, den Vorgangerzeigernim Tiefensuchbaum und der T2Nummerierung bestimmt.

(d) (3 Punkte) Verwenden Sie Aufgabe (b), um aus der T2Nummerierung eineskreisfreien Graphen eine topologische Sortierung zu konstruieren. BeschreibenSie den Algorithmus in Worten.

45. Algorithms von Dijkstra, 5 Punkte

Wenden Sie den Algorithms von Dijkstra zur Bestimmung der kurzesten Wege im fol-genden gerichteten Graphen an: Die Knotenmenge V = {1, 2, . . . , 6}, und der Graphist vollstandig, das heißt, von jedem Knoten gibt es eine Kante zu jedem anderenKnoten. Die Kantenlangen sind cij = 3j−i fur i < j und cij = i − j fur i > j. DerStartknoten ist Knoten 2.

Geben Sie nach jeder Iteration die Werte der Zeiger und Markierungen an. (Dieinternen Daten der Prioritatswarteschlange brauchen Sie nicht anzugeben.)

46. Negative Kantenlangen, 4 Punkte

Konstruieren Sie einen Graphen, der auch Kanten mit negativer Lange enthalt, undbei dem der Algorithmus von Dijkstra die kurzesten Wege nicht richtig bestimmt.Der Graph darf keine Kreise negativer Lange enthalten.

47. Unterhaltungsaufgabe, 0 Punkte

Herr B. C. Dom hat die Definition eines Suchbaums missverstanden als ein Baum,in dem jeder Schlussel eines Knotens großer ist als der Schlussel im linken Kind undkleiner als der Schlussel im rechten Kind (sofern diese Kinder vorhanden sind). Erhat nun eine Methode zum Patent angemeldet, mit der er eine ungeordnete Liste vonn Schlusseln in O(n) Zeit in einen solchen

”Suchbaum“ umwandeln kann.

(a) Konnen Sie den Algorithmus von Herrn Dom erraten?

(b) Wie viel wurden Sie fur die Lizenz zur Benutzung dieses Patents zahlen?

9



48. Graphenalgorithmen in der kunstlichen Intelligenz, Programmieraufgabe, 13 Punkte

Die folgende Aufgabe findet sich in einer Sammlung von Rechenaufgaben mit demTitel Propositiones ad acuendos juvenes (Aufgaben zur Scharfung des Geistes derJugend), die wahrscheinlich um das Jahr 800 am Hof Karls des Großen entstandenist und Alkuin von York zugeschrieben wird:

Die Aufgabe vom Wolf, der Ziege und dem Kohlkopf. Ein Mann muss-te einen Wolf, eine Ziege und einen Kohlkopf uber einen Fluss uber-setzen; er konnte aber nur ein Boot auftreiben, das gerade zwei vonihnen tragen konnte. Wie konnte er alles unversehrt hinuberbringen?1

(a) Modellieren Sie diese Aufgabe durch einen Graphen. Die Knoten sollen denmoglichen Zustanden des Systems Mann–Ziege–Wolf–Kohlkopf–Boot–Fluss ent-sprechen, und die Kanten den erlaubten Ubergangen: Zum Beispiel wurde derWolf die Ziege oder die Ziege den Kohlkopf fressen, wenn sie ohne Aufsicht ge-lassen wurden; der Mann, der das Boot rudert, kann nur einen Gegenstand oderein Tier zusatzlich mitnehmen. Eine Losung soll einem Weg in diesem Graphenentsprechen.

(b) Schreiben Sie ein Programm in Python oder Java, das diesen Graphen erstellt.Wie viele Knoten und wie viele Kanten hat der Graph? Schreiben Sie eineProgramm, das mit Breitensuche einen Weg in diesem Graphen findet, der einerLosung des Problems entspricht.

(c) (0 Punkte) Ist die Losung eindeutig? Wie kann man feststellen, ob es in einemGraphen nur einen einzigen Weg von s nach t gibt?

49. Halden vom Grad d, 7 Punkte

Betrachten Sie die Variante einer Halde, bei der jeder innere Knoten d ≥ 2 Kinder hat.(Fur d = 2 ergeben sich die gewohnlichen Halden.) Wie verandert sich die Laufzeit furdie Operationen zugroß beziehungsweise zuklein in Abhangigkeit von d? (AndereBezeichnungen fur diese Operationen sind bubbledown und bubbleup.) Wie wirktsich das auf die Operationen einfugen, entferneMin und verkleinereSchlussel aus?

Wenn man eine solche d-Halde fur den Algorithmus von Dijkstra verwendet, wie mussman dann d in Abhangigkeit von m und n wahlen, dass man die beste asymptotischeLaufzeit erhalt? Welche Laufzeit ergibt sich dann fur das kurzeste-Wege-Problem?Was ergibt sich in den Extremfallen m = Θ(n) und m = Θ(n2)?

50. (0 Punkte) Denken Sie sich einen gierigen Algorithmus aus, der versucht, in einemGraphen einen kurzen Weg von einem Startknoten s zu einem Zielknoten t zu finden.Welche Probleme konnen dabei auftreten?

1PROPOSITIO DE LUPO ET CAPRA ET FASCICULO CAULI. Homo quidam debebat ultra fluviumtransferre lupum et capram et fasciculum cauli, et non potuit aliam navem invenire, nisi quae duos tantumex ipsis ferre valebat. Praeceptum itaque ei fuerat, ut omnia haec ultra omnino illaesa transferret. Dicat,qui potest, quomodo eos illaesos ultra transferre potuit. SOLUTIO. Simili namque tenore ducerem priuscapram et dimitterem foris lupum et caulum. Tum deinde venirem lupumque ultra transferrem, lupoqueforas misso rursus capram navi receptam ultra reducerem, capraque foras missa caulum transveheremultra, atque iterum remigassem, capramque assumptam ultra duxissem. Sicque faciente facta erit remigatiosalubris absque voragine lacerationis.

10



51. Kurzeste Spannbaume, 0 PunkteZeigen Sie, dass der folgende Algorithmus von Prim einen kurzesten Spannbaumberechnet:

Q := V ; d[s] := 0; d[v] :=∞ fur alle v ∈ V − {s}while Q 6= ∅:

entferne den Knoten u mit kleinstem Wert d[u] aus Qfur alle v ∈ E(u):

if cuv < d[v]:d[v] := cuvf [v] := u

Wie findet man am Ende die Kanten, aus denen der Baum besteht? Was ist der Un-terschied von diesem Algorithmus zum Algorithmus von Dijkstra fur kurzeste Wege?Wie muss der Startknoten s gewahlt werden? Welche Bedeutung hat d[v]?

52. Hashtabellen, 10 Punkte

(a) Fugen Sie nacheinander die Schlussel 5, 28, 19, 15, 20, 33, 12, 17, 10 in eineHashtabelle der Große 9 ein. Die Hashfunktion ist h(k) = k mod 9. Die Konfliktewerden mit Verkettung gelost.

(b) Fugen Sie nacheinander die Schlussel 10, 22, 31, 4, 15, 28, 17, 88, 59 in eine Hash-tabelle der Große 11 ein. Die Hashfunktion ist h(k) = k mod 11. Die Konfliktewerden durch offene Adressierung mit linearem Sondieren gelost.

(c) Fugen Sie nacheinander die Schlussel 10, 22, 31, 4, 15, 29, 17, 88, 59 in eineHashtabelle der Große 11 ein. Die Konflikte werden durch Kuckuck mit h1(k) =k mod 11 und h2(k) = (k mod 13) mod 11 behandelt.

Illustrieren Sie jeweils die einzelnen Schritte, insbesondere beim Kuckuckshashing.

53. Loschen mit linearem Sondieren, 10 Punkte

(a) In der Vorlesung wurde gezeigt, dass es bei offener Adressierung nicht reicht, furein entferntes Element bloß den Platz freizumachen, den es belegt. Zeigen Sie aneinem Beispiel, dass auch das folgende Verfahren zum Entfernen des Schlusselsx im Zusammenhang mit linearem Sondieren nicht funktioniert, weil spatereSuchoperationen einen vorhandenen Schlussel moglicherweise nicht finden.

p := h(x)while T [p] 6= x:

if T [p] = null: return “x nicht vorhanden”p := (p + 1) mod M

p0 := p // Position von xwhile T [(p + 1) mod M ] 6= null:

p := (p + 1) mod MT [p0] := T [p]; T [p] := null

(b) Schreiben Sie in Pseudocode ein korrektes Verfahren zum Entfernen, das wirk-lich einen Platz in der Tabelle freimacht, und argumentieren Sie, warum esfunktioniert.

11


Abgabe bis Freitag, 8. Januar 2016, 12:00 Uhr.

54. Der gierige Algorithmus, 0 Punkte

Die Jedi-Ritter wollen ihre Rebellenbasis auf dem Planeten Orbis Pictus gegen dasImperium verteidigen. Die Basis wird durch eine Mauer mit einer Lange von ` Meilengeschutzt, die zwei machtige Felsen verbindet. Die Jedi mussen die Tore in der Mauersichern. Die Positionen xi der n Tore sind gegeben: 0 ≤ x1 < x2 < · · · < xn ≤ `. EinRitter kann einen Bereich von m Meilen uberblicken, das heißt, ein Ritter, der anPosition y steht, kann alle Tore i im Bereich y −m ≤ xi ≤ y + m uberwachen undgegen Angriffe sichern. Konnen Sie den Jedi-Rittern helfen, die kleinste Zahl vonWachtern zu berechnen, die notwendig sind, um alle Tore zu uberwachen? GebenSie einen effizienten Algorithmus fur dieses Problem an, und erklaren Sie, warum erkorrekt ist.

55. Streckenschnitt, 10 Punkte

Bestimmen Sie mit dem Algorithmus aus der Vor-lesung alle Schnittpunkte der vier Strecken AiBi

mit (A1, . . . , A4) = ((2, 2), (3, 5), (9, 5), (5, 2)) und(B1, . . . , B4) = ((8, 6), (7, 3), (1, 6), (4, 5)) durchUberstreichen der Ebene. Geben Sie den Inhalt der vertikalen Struktur F und derhorizontalen Struktur (der Ereigniswarteschlange Q) vor jedem Ereignis an.

56. Orientierungstest mit Gleitkomma-Arithmetik, Programmieraufgabe, 10 Punkte

Wahlen Sie 10 Punkte Ai = (xi, yi) auf der Geraden g durch die Punkte B = (2.3, 3.2)und C = (9.3, 6.2), indem Sie x1 = 0.1 und x2 = 99.99 setzen und acht weiterex-Koordinaten zufallig aus einem geeigneten Bereich wahlen und die zugehorigen y-Koordinaten durch Einsetzen in die Geradengleichung ausrechnen. Fuhren Sie alleRechnungen in Gleitkommaarithmetik aus.

Bestimmen Sie fur jedes xi die Maschinengenauigkeit, εi = x′i − xi, wobei x′i diekleinste Gleitkommazahl großer als xi ist (εi ist immer eine Zweierpotenz). BerechnenSie dann jeweils fur die 41 Punkte A = (xi +kεi, yi), −20 ≤ k ≤ 20, die Orientierungdes Dreiecks ABC.

Sie durfen diese Aufgabe in einer beliebigen Programmiersprache losen, die dafurgeeignet ist. Dokumentieren Sie neben den Ergebnissen (einschließlich εi) auch dieSprache (Version, Compiler) und den verwendeten Prozessor, und mit welcher Genau-igkeit (einfache oder doppelte Genauigkeit) die Rechnungen durchgefuhrt wurden.

57. Suche nach Rang, 0 Punkte

Erweitern Sie folgende Worterbuch-Datenstrukturen (sofern das sinnvoll ist), so dasses effizient moglich ist, bei Eingabe von k den k-kleinsten Schlussel in der gespei-cherten Schlusselmenge zu finden. Beschreiben und analysieren Sie auch die notigenModifikationen fur die anderen Worterbuchoperationen:

(a) Skipliste

(b) Digitaler Suchbaum (trie, nicht komprimiert), mit lexikographischer Ordnung

(c) Hashtabelle

(d) 2-3-Baum

12

58. Rot-Schwarz-Baume, 0 Punkte

Rot-Schwarz-Baume sind binare Suchbaume mit folgenden Eigenschaften:1

(a) Jeder innere Knoten hat zwei Kinder.

(b) Jeder Knoten ist entweder als rot oder als schwarz gekennzeichnet.

(c) Die Wurzel und alle Blatter sind schwarz.

(d) Die Kinder eines roten Knotens sind schwarz.

(e) Alle Wege von der Wurzel zu den Blattern enthalten die gleiche Anzahl vonschwarzen Knoten.

Die schwarze Hohe h′ ist die um eins verminderte Anzahl der schwarzen Knoten aufjedem Weg von der Wurzel zu einem Blatt.

1. Welche Hohe kann ein Baum mit schwarzer Hohe h′ mindestens und hochstenshaben?

2. Wie viele rote Knoten kann ein Baum mit schwarzer Hohe h′ mindestens undhochstens haben?

3. Wie viele schwarze Knoten kann ein Baum mit schwarzer Hohe h′ mindestensund hochstens haben?

4. Zeichnen Sie Rot-Schwarz-Baume mit 5, 7 und 12 Blattern. Zeigen Sie, dass manaus jedem Rot-Schwarz-Baum einen 2-4-Baum machen kann, und umgekehrt.

Begrunden Sie Ihre Antworten. (Fragen 1–3 sind abgewandelte Klausuraufgaben.)

59. Munzwechseln, 0 Punkte

An der Supermarktkasse soll ein Betrag von n Cents herausgegeben werden, wobeidie minimale Anzahl an Munzen verwendet werden soll. (Zur Erinnerung: Es gibtEuro-Munzen zu 1, 2, 5, 10, 20, 50, 100 und 200 Cent.)

(a) Beschreiben Sie einen gierigen Algorithmus fur das Problem und implementierenSie ihn. Was ist die Laufzeit des Algorithmus?

(b) Beweisen Sie, dass Ihr Algorithmus aus (a) eine optimale Losung liefert.

Hinweis: Machen Sie sich Gedanken uber die Struktur einer optimalen Losung:Wie viele 1-Cent-Munzen kann eine optimale Losung hochstens enthalten? Wieviele 2-Cent-Munzen? usw?

(c) Geben Sie ein Beispiel von Munzwerten, so dass der gierige Algorithmus nichtoptimal ist. Dabei sollte es eine 1-Cent-Munze geben, damit sich jeder Betraggarantiert wechseln lasst.

(d) Beweisen Sie, dass der gierige Algorithmus fur Munzen mit Werten 1, c, c2, . . . , ck

die minimale Anzahl von Munzen verwendet, wenn c > 1 und c, k ∈ N ist.

60. Ausgeglichene Baume, 0 Punkte

Frau C. B. Daflich hat die Schwache des Verfahrens von Herrn Dom (Aufgabe 47vom 7. Ubungsblatt) erkannt: Die entstehenden Baume sind nicht ausgeglichen! Siehat daher eine Methode entwickelt, um in linearer Zeit einen

”Suchbaum“ im Sinn

von Aufgabe 47 herzustellen, der nur Hohe h = O(log n) hat. Konnen Sie auch einensolchen Algorithmus finden? Geht es sogar in der optimalen Hohe h = blog2 nc?

1Es gibt auch andere Versionen von Rot-Schwarz-Baumen. In der Regel enthalten die inneren Knotenauch Werte und nicht nur Schlussel (im Gegensatz zu den a-b-Baumen, wie sie in der Vorlesung besprochenwurden). Rot-Schwarz-Baume sind in der Klasse TreeMap im Java-Paket java.util implementiert.

13


Probeklausur. Bearbeitung bis Donnerstag, 17. Dezember 2015, 15:45 Uhr.

61. Spezifikation von Multimengen, 10 Punkte

Eine Multimenge (engl. multiset oder bag) ist etwas Ahnliches wie eine Menge, außerdass Elemente auch mehrfach vorkommen durfen. Die Reihenfolge spielt keine Rolle.Zum Beispiel ist {{a, b}} 6= {{a, a, b}} = {{a, b, a}} 6= {{a, a, a, b}}, fur a 6= b.

Schreiben Sie eine formale Spezifikation (modellierend oder algebraisch) fur einen ab-strakten Datentyp von Multimengen uber der Grundmenge der ganzen Zahlen (int),der folgende Operationen unterstutzt: Erzeugen einer leeren Multimenge; Einfugenund Streichen eines Elementes (dabei wird die Vielfachheit jeweils um 1 erhoht be-ziehungsweise erniedrigt); Bestimmen der Vielfachkeit eines Elementes.

62. Addition einer Konstante zu den Kantengewichten, 10 Punkte

(a) Kann sich der kurzeste Weg von s nach t in einem gerichteten Graphen G andern,wenn man eine Konstante C > 0 zu allen Kantengewichten des Graphen addiert?Begrunden Sie Ihre Aussage.

(b) Kann sich der kurzeste Spannbaum in einem ungerichteten Graphen G andern,wenn man eine Konstante C > 0 zu allen Kantengewichten des Graphen addiert?Begrunden Sie Ihre Aussage.

(c) Wir suchen den kurzesten zusammenhangenden Teilgraphen, der alle Knoteneines ungerichteten Graphen G enthalt. Beweisen Sie, dass der kurzeste Spann-baum dieses Problem lost, wenn alle Kantengewichte positiv sind.

(d) Wie lost man das Problem von Aufgabe (c), wenn der Graph G auch Kantenmit negativem Gewicht enthalt?

63. Komprimierte digitale Suchbaume, 10 Punkte

Fugen Sie nacheinander die acht Schlussel 00000, 11110, 1010, 0101, 110, 1100, 1101,und 1111 in einen leeren komprimierten digitalen Suchbaum uber dem Alphabet{0, 1} ein. Zeichnen Sie den Baum nach jeder Einfugeoperation.

64. Langste gemeinsame Teilfolge, dynamisches Programmieren, 10 Punkte

Entwerfen Sie einen effizienten Algorithmus fur folgendes Problem: Fur zwei Folgen(a1, . . . , am) und (b1, . . . , bn) soll die langste gemeinsame Teilfolge bestimmt werden.Eine Teilfolge besteht dabei aus einem Teil der Elemente in der ursprunglichen Rei-henfolge. Zum Beispiel ist in den Wortern

karamba-ole und maibowle-mit-banane

eine gemeinsame Teilfolge der Lange 4 durch unterstrichene Zeichen markiert. Einkurzeres Beispiel sind die Worter Graph und alpha.

Schreiben Sie ein Programm in Pseudocode, das die Lange der langsten Teilfolge aus-rechnet. (Die Folge selbst mussen Sie nicht bestimmen.) Analysieren Sie die Laufzeitund den Speicherbedarf Ihres Algorithmus.

14



65. Backtracking, 0 Punkte

Eine Halbdame kann sich wie eine Dame beim Schachspiel bewegen, außer dass sienur in einer Diagonalenrichtung (von links unten nach rechts oben) ziehen kann undnicht in der anderen Diagonalenrichtung.

(a) Wie viele Moglichkeiten gibt es, 8 Halbdamen auf das Schachbrett zu stellen,sodass sie sich nicht gegenseitig angreifen konnen?

(b) Wie viele verschiedene Moglichkeiten gibt es, wenn man gedrehte oder gespie-gelte Konfigurationen als gleich betrachtet?

(c) Zeigen Sie, dass man auf jedem n × n-Schachbrett n Halbdamen unterbringenkann.

66. Drachenschach, 10 Punkte, Programmieraufgabe

Der Drachen vereinigt die Bewegungsmoglichkeiten einer Dame und eines Springersim klassichen Schachspiel: Zusatzlich zu Zeilen, Spalten und Diagonalen kann einDrachen von Position (i, j) auf Position (i′, j′) ziehen, wenn {|i− i′|, |j− j′|} = {1, 2}ist.

(a) Wie viele Drachen, die sich nicht angreifen konnen, kann man auf dem 8 × 8Schachbrett maximal aufstellen?

(b) Was ist das kleinste (n × n)-Schachbrett mit n ≥ 2, auf dem man n Drachenaufstellen kann?

Schreiben Sie ein Backtracking-Programm fur diese Aufgaben. Zahlen Sie die rekur-siven Aufrufe insgesamt und auch getrennt fur jede Ebene des Losungsbaums.

67. Golomb-Maßstabe, 0 Punkte

Ein Golomb-Maßstab oder eine Sidon-Menge der Ordnung n besteht aus n naturli-chen Zahlen 0 = a1 < a2 < · · · < an, sodass alle paarweisen Differenzen aj − aiverschieden sind. Zum Beispiel ist 0, 1, 3, 7, 12 ein Golomb-Maßstabe der Ordnung 5.Golomb-Maßstabe werden zum Beispiel zur Anordnung der Empfanger in der Ront-genkristallographie verwendet.

Suchen Sie Golomb-Maßstabe mit moglichst kleinem an fur n = 4, 5, 6, 7, 8. Liefertder gierige Algorithmus immer eine optimale Losung?

68. Kurzester Weg mit negativen Kantengewichten, 10 Punkte

Das Problem A sei das Problem, in einem gerichteten Graphen mit beliebigen ganz-zahligen Kantengewichten einen kurzesten Weg von s nach t zu finden, der keinenKnoten mehrfach besucht. Das Problem B sei das Problem, zu uberprufen, ob einungerichteter Graph einen Hamilton-Kreis enthalt, das heißt, einen Kreis, der jedenKnoten genau einmal durchlauft.

Zeigen Sie, dass man das Problem B in polynomieller Zeit auf das Problem A redu-zieren kann.

15



69. Volladdierer, 0 Punkte

Ein Volladdierer berechnet aus drei Eingabebits x, y, c zwei Ausgabebits r und c′

nach folgender Formel, wobei ⊕ das exklusive Oder (XOR) ist:(r ≡ (x⊕ y ⊕ c)

)∧(c′ ≡ ((x ∧ y) ∨ (c ∧ (x ∨ y)))

)

Schreiben Sie eine dazu aquivalente Formel in konjunktiver Normalform.

70. Konjunktive Normalform, 4 Punkte

Schreiben Sie Boolesche Formeln in konjunktiver Normalform fur folgende Aussagen.Versuchen Sie, mit moglichst wenigen Klauseln auszukommen.

(a) Hochstens eine der Variablen x1, . . . , x5 ist wahr.

(b) Mindestens zwei der Variablen x1, . . . , x5 sind wahr.

(c) Keine zwei benachbarten Variablen xi und xi+1 von den Variablen x1, . . . , x5sind gleichzeitig falsch.

(d) Die durch die Bits (x4 . . . x0) gegebene Binarzahl ist kleiner als elf.

71. Erfullbarkeit (SAT), Programmieraufgabe, 10 Punkte

Eine Boolesche Formel φ(x1, ..., xn) in konjunktiver Normalform ist genau dann erfull-bar, wenn φ(1, x2, ..., xn) oder φ(0, x2, ..., xn) erfullbar ist. Dabei ensteht die Formelφ(1, x2, ..., xn) aus φ(x1, ..., xn), indem jedes Vorkommen von x1 durch 1 ersetzt wird.Das Ergebnis kann vereinfacht werden: Jede Klausel, die x1 enthalt, kann weggelassenwerden. Steht das Literal x1 in einer Klausel, kann man es streichen. Fur die Formel

φ(x1, x2, x3) = (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2) ∧ (x1 ∨ x2 ∨ x3) ∧ x3vereinfacht sich zum Beispiel φ(1, x2, x3) zu (x2 ∨ x3) ∧ x3.Analoges gilt fur φ(0, x2, ..., xn). Eine konjunktive Normalform, die keine Klauselnmehr enthalt (

”leere Konjunktion“) ist erfullbar; eine konjunktiver Normalform, die

eine leere Klausel enthalt (”leere Disjunktion“), ist nicht erfullbar.

Implementieren Sie einen entprechenden rekursiven Entscheidungsalgorithmus furSAT in Python oder Java, der auch gegebenfalls eine erfullende Belegung ausgibt.Zahlen Sie in geeigneter Form die Schritte des Programmes, zum Beispiel die Anzahlder rekursiven Aufrufe. Die Eingabeformel in konjunktiver Normalform soll wie imfolgenden Beispiel codiert sein: (x1∨x2∨ x3)∧ (x1∨x3)∧ x2 als 1 2 -3, -1 3, -2.

Testen Sie Ihr Programm zum Beispiel mit der Konjunktion aus Aufgabe 70b und 70d.

72. NP, 6 Punkte

Zeigen Sie, dass die folgenden Probleme in NP sind, und geben Sie jeweils das Zerti-fikatskriterium an.

(a) Eingabe: Eine naturliche Zahl k in BinardarstellungFrage: Ist k zusammengesetzt? (das heißt, keine Primzahl)Anmerkung: Die Mulitplikation oder Division zweier n-stelliger Zahlen nach derSchulmethode erfordert O(n2) Zeit.

(b) Eingabe: Eine Menge von n Paketen mit Gewichten w1, . . . , wn ∈ N und zweiZahlen k, v ∈ N.Frage: Lassen Sich die Pakete mit k Autos transportieren, wenn jedes Autohochstens Pakete mit Gesamtgewicht v laden kann?

16



73. Huffman-Baume, 0 Punkte

(a) Bestimmen Sie den Huffman-Baum fur die Haufigkeiten 1300, 1900, 2000, 2400,3000, 3300, 3400, 3900, 4900, 7000, 7200, 9900.

Zeigen Sie in einzelnen Schritten, wie der Algorithmus ablauft, und zeichnen Sieden optimalen CodeBaum.

(b) Ist der optimale binare Code fur diese Haufigkeiten eindeutig?


Zeigen Sie, dass man einen Huffman-Baum in O(n) Zeit bauen kann, wenn die Haufig-keiten h1 ≤ · · · ≤ hn in sortierter Reiehenfolge gegeben sind.

75. Datenkompression, Programmieraufgabe, 10 Punkte

(a) Implementieren Sie die Huffman-Codierung in Python oder Java. Dabei sollein Text byteweise gelesen werden. Zunachst werden in einem Durchlauf dieHaufigkeit der Zeichen bestimmt, danach ein Huffman-Baum konstruiert undschließlich die Codierung des Texts ausgegeben werden. Uberlegen Sie sich da-zu eine geeignete Codierung fur den Huffman-Baum. Um das Ende der Dateifestzulegen, muss man entweder die Lange der Datei separat ubermitteln, oderman muss ein zusatzliches Zeichen eof in das Eingabealphabet aufnehmen. Siekonnen selbst entscheiden, ob Sie die Ausgabe auf mehrere Dateien aufteilenoder in eine Datei zusammenpacken.

(b) Bestimmen Sie experimentell den Kompressionsfaktor fur die Texte Deutsch-land, ein Wintermarchen1 und Sternstunden der Menschheit2 im Vergleich zum8-Bit-ISO-Latin1-Code.

(c) Implementieren Sie auch die Decodierung. Die Eingabe besteht den im Schritt(a) produzierten Daten: aus dem Huffman-Code (das heißt, einem beliebigenprafixfreien Codes uber dem Alphabet {0, 1}) und dem codierten Text.

76. Adjazenzlisten, 5 Punkte

Gegeben ist ein Graph mit den Knoten V = {1, 2, . . . , n} und m Kanten in Adjazenz-listenspeicherung. Die Kanten (i, j) in den Adjazenzlisten sollen nach den Endknotenumsortiert werden; das heißt, in der Adjazenzliste von i soll die Kante (i, j) vor (i, k)kommen, wenn j < k ist.

Skizzieren Sie einen Algorithmus, der diese Sortieraufgabe in linearer Zeit, das heißt,in O(m + n) Zeit lost. (Hinweis: Denken Sie an Radix-Sort.)

77. Geometrische Verteilung, Vorubung, 0 Punkte

(a) Wie oft muss man (im Erwartungswert) mit einem einzelnen Wurfel wurfeln,bis man insgesamt drei Sechsen geworfen hat?

(b) Gegeben sind n verschiedene Zahlen. Wir wahlen zufallig eine Zahl a davon ausund bestimmen dann die Anzahl der n− der Zahlen < a und die Anzahl n+ derZahlen > a. Wir wiederholen diesen Versuch solange, bis n− ≥ 10 und n+ ≥ 10ist. Was ist der Erwartungswert fur die Anzahl der Versuche?

1http://www.inf.fu-berlin.de/lehre/WS15/ALP3/Deutschland.txt, 77550 Bytes. Die Originalquelleist http://www.gutenberg.org/files/6079/6079-8.txt, mit einem zusatzlichen Vor- und Nachspann.

2http://www.inf.fu-berlin.de/lehre/WS13/Datenkompression/Daten/buch1, 420.825 Bytes.

17


Freiwillige Abgabe bis Freitag, 5. Februar 2016, 12:00 Uhr.

78. Das Worterbuchproblem, 0 Punkte

Lassen Sie die Datenstrukturen, die Sie fur das Worterbuchproblem kennengelernthaben, Revue passieren.

Stellen Sie die Vor- und Nachteile gegenuber. Welche Operationen werden von wel-chen Datenstrukturen effizient unterstutzt?

79. Hashing, 0 Punkte

Welche Moglichkeiten der Kollisionsbehandlung gibt es bei Hashtabellen?

80. 1-IN-3-SAT, 6 Punkte

Beim 1-IN-3-SAT-Problem ist eine Menge von Klauseln gegeben, die aus je drei Li-teralen bestehen. Gesucht ist eine Belegung, in der in jeder Klausel genau ein Literalwahr ist (im Gegensatz zum gewohnlichen Erfullbarkeitsproblem SAT, wo in jederKlausel mindestens ein Literal wahr sein muss). Wir schreiben diese Klauseln in derForm l1 + l2 + l3 = 1.

Zeigen Sie, dass dieses Problem NP-schwer ist, indem Sie 3SAT darauf reduzieren.Die Reduktion ersetzt jede 3SAT-Klausel l1 ∨ l2 ∨ l3 durch 3 Klauseln

l1 + b1 + c1 = 1

l2 + b2 + c2 = 1

c1 + c2 + l3 = 1

mit neuen Variablen b1, c1, b2, c2, die sonst nirgends vorkommen. (3SAT ist der Spe-zialfall von SAT, in dem jede Klausel drei Literale enthalt.)

81. (0 Punkte) Liegt das Proplem 1-IN-3-SAT in NP?

82. Unabhangige Knotenmenge, 6 Punkte

Gegen ist ein ungerichteter Graph G. Gesucht ist eine moglichst große Teilmenge vonKnoten, in der keine zwei Knoten benachbart sind. Zeigen Sie dass dieses ProblemNP-schwer ist, indem Sie 3-Farbbarkeit darauf reduzieren.

Anleitung: Nehmen Sie drei disjunkte Kopien des Graphen, dessen 3-Farbbarkeit ge-testest werden soll, und verbinden je drei entsprechende Knoten in den verschiedenenKopien durch drei Kanten, die ein Dreieck bilden.

83. Entropie, 6 Punkte

Im Huffman-Baum fur die Haufigkeiten p1, . . . , pn mit p1 + · · · + pn = 1 seien dien Blatter auf Tiefe l1, . . . ln. Aus Aufgabe 26 vom 4. Ubungsblatt wissen wir, dass∑

2−li = 1 ist. Zeigen Sie, dass die mittlere Codewortlange∑

pili durch die Entropie

H(p1, . . . , pn) := p1 log21p1

+ p2 log21p2

+ · · ·+ pn log21pn

(1)

der Verteilung (p1, . . . , pn) von unten beschrankt ist.

Anleitung: Leiten Sie aus der Ungleichung ez ≥ 1 + z, die fur alle z ∈ R gilt, durchUmformung die Beziehung 2−li ≥ 2−Li(1 − ln 2 · (li − Li)) her. Setzen Sie dannLi := log2

1pi

, summieren Sie uber i, und verwenden Sie∑

2−li = 1 fur die linkeSeite.

18

84. Existenz eines guten Codes, 0 Punkte

Fur die Folge li := dlog21pie gilt

∑2−li ≤ 1. Wir konnen nun die Langen li schritt-

weise reduzieren, dass∑

2−li = 1 wird. Auf diese Weise erhalten wir einen Code,dessen mittlere Codewortlange

∑pili die Entropieschranke (1) um hochsten 1 Bit

uberschreitet.


Berechnen Sie die Entropie der Verteilung, die sich aus den Haufigkeiten von Auf-gabe 73 vom 14. Ubungsblatt ergibt. Vergleichen Sie sie mit der mittleren Code-wortlange des Huffman-Codes.

86. Radixsort, 0 Punkte

Die Fachverteilung bei einem Durchlauf von Radixsort kann durch verkettete Listenerfolgen. Eine andere Moglichkeit speichert die n Elemente direkt in ein Zielfeldz[0 . . . n−1]: Zunachst muss man zahlen, wieviele Elemente fur jedes Fach 0, . . . , B−1bestimmt sind. Anschließend bestimmt man den Beginn des Intervalls, das jedes Fachim Feld z einnimmt. Danach kann man die Elemente durchlaufen und direkt an dierichtige Stelle in z setzen.

Schreiben Sie ein Programm dafur in Pseudocode.1,

87. Korrektheit der Impementierung eines abstrakten Datentyps, 0 Punkte

Die folgende Klasse BitSet2 implementiert einen Menge von (nicht zu großen) ganzenZahlen als Bitvektor.

public class BitSet {

int maxvalue;

long A[];

BitSet(int maxv) {

maxvalue = maxv;

int size = 1+maxv/64;

A = new long[size];

}

public boolean contains(int i) {

if ((i>maxvalue) || (i<0)) return false;

int k = i/64;

int shift = i-k*64;

return ((A[k]>>shift) & 1)==1;

}. . .

(a) Erganzen Sie die Methoden add und remove, und definieren Sie einen passendenabstrakten Datentyp.

(b) Geben Sie die Abstraktionsfunktion und gegebenfalls die Darstellungsinvarian-ten und die Nebenbedingungen dieser Implementierung an.

(c) Beweisen Sie die Korrektheit der Implementierung.

1Zur Losung siehe das Unterprogramm RadixDurchlauf im Programm http://www.inf.fu-berlin.de/

lehre/WS13/Datenkompression/Suffixfeld-KS.py2http://www.inf.fu-berlin.de/lehre/WS15/ALP3/BitSet.java

19

Algorithmen und Programmierung 3, WS 2015/2016

Klausur, Bearbeitung bis Donnerstag, 18. Februar 2016, 10:00 Uhr.

1. Spezifikation von Mengen, 10 Punkte

In der Vorlesung wurden eine einfache Java-Implementierung des abstrakten Daten-typs Menge ganzer Zahlen mit der Abstraktionsfunktion

f(m,A) = M = {A[j] | 0 ≤ j < m }

besprochen, die so beginnt:

class SmallIntSet {

int m;

int A[];

SmallIntSet() {

m = 0;

A = new int[100];

}

...

Die Klasse soll Mengen M mit |M | ≤ 100 Elementen darstellen konnen. BetrachtenSie drei verschiedene Darstellungsinvarianten:

(1) Fur alle 0 ≤ j < k < m gilt A[j] 6= A[k].

(2) Fur alle 0 ≤ j < k < m gilt A[j] < A[k].

(3) (keine Bedingung).

(a) Erganzen Sie das obige Progammskelett fur jede dieser drei Moglichkeiten umdie Implementierung der Methode public void remove(int x) (mit der Spe-zifikation M := M \ {x}).

(b) Diskutieren Sie, wie sich die Wahl der Darstellungsinvariante (1), (2), oder (3)auf die Implementierung der beiden folgenden Operationen auswirkt:

public boolean contains(int x) (x ∈M?)public void add(int x) (M := M ∪ {x})

2. Skiplisten, 10 Punkte

(a) Fugen Sie nacheinander die Schlussel 1(2), 20(1), 50(1), 40(3), 30(2), 35(1) ineine anfangs leere Skipliste ein. Die Zahlen in Klammern geben dabei an, inwievielen Listen jedes Element enthalten ist (statt einer Zufallsentscheidung).Zeichnen Sie die Skipliste nach jeder Operation auf.

(b) Welche Vergleiche zwischen Schlusseln werden nun bei der Suche nach denSchlusseln 35 bzw. 45 durchgefuhrt?

(c) Entfernen Sie dann nacheinander die Schlussel 35 und 1. Zeichnen Sie die Ski-pliste nach jeder Operation auf.

20

3. Zusammenhangskomponenten, 10 Punkte

In einem ungerichteten Graphen G = (V,E) ist die Erreichbarkeitsrelation folgender-maßen definiert:

u ∼ v ⇐⇒ u = v oder es gibt einen Weg von u nach v

Diese Relation ist eine Aquivalenzrelation, und ihre Aquivalenzklassen heißen Zu-sammenhangskomponenten.

Schreiben Sie ein effizientes Programm in Pseudocode, das fur einen ungerichtetenGraphen G mit n ≥ 1 Knoten und m Kanten, der als Adjazenzlisten gespeichert ist,die Anzahl der Zusammenhangskomponenten ausrechnet.

Analysieren Sie die Laufzeit und den Speicherbedarf Ihres Algorithmus in Abhangig-keit von m und n.

Geben Sie eine kurze Begrundung fur die Korrektheit an.

4. Dynamisches Programmieren, 10 Punkte

Gegeben ist eine Folge (a0, a1, a2, . . . , an−1) von n verschiedenen Zahlen, z. B. (5, 28,19, 15, 20, 33, 12, 17, 10). Eine aufsteigende Teilfolge ist eine Teilfolge, die monotonwachsend ist, zum Beispiel (5, 19, 20, 33) oder die Teilfolge (19). (Jede einelementigeTeilfolge ist eine aufsteigende Teilfolge.)

Schreiben Sie ein effizientes Programm in Pseudocode, das die Anzahl aller aufstei-genden Teilfolgen (mit mindestens einem Element) berechnet. Die Folge (1, 2, 3) hatzum Beispiel 7 solche aufsteigenden Teilfolgen, die Folge (4, 3, 2, 1) hat nur 4.

Analysieren Sie die Laufzeit und den Speicherbedarf Ihres Algorithmus.


Hinweis: Es geht mit O(n) Speicher und O(n2) Zeit.

21

Algorithmen und Programmierung 3, WS 2015/2016

Klausur, Bearbeitung bis Dienstag, 12. April 2016, 16:00 Uhr.

1. Streckenschnitt, 10 Punkte

B1

B2

B3B4

A1

A2

A3

A4

C

D

E

F

Bestimmen Sie mit dem Algorithmus ausder Vorlesung alle Schnittpunkte der vierStrecken AiBi mit

A1, . . . , A4 = (4, 5), (1, 4), (2, 2), (6, 3) und

B1, . . . , B4 = (7, 3), (9, 2), (8, 6), (5, 6)

durch Uberstreichen der Ebene von links nach rechts. Geben Sie den Inhalt dervertikalen Struktur (der Fegegerade F ) und der horizontalen Struktur (der Ereignis-warteschlange Q) in jedem Schritt an.

2. Algebraische Spezifikation, 10 Punkte

Die Operationen einfuge, losche, leereMenge, und istenthalten fur Mengen von ganzenZahlen sind folgendermaßen spezifiziert (wie in der Vorlesung):

istenthalten(x, leereMenge) = False

istenthalten(x, einfuge(x,m)) = Trueistenthalten(x, einfuge(y,m)) = istenthalten(x,m), fur x 6= y

istenthalten(x, losche(x,m)) = Falseistenthalten(x, losche(y,m)) = istenthalten(x,m), fur x 6= y

Erweitern Sie die Spezifikation um eine neue Operation

aek : Z× (Menge Z)→ N.

Das Ergebnis von aek(x,m) soll die Anzahl der Elemente in m sein, die kleiner als xsind.

Begrunden Sie kurz die Korrektheit Ihrer Losung.

3. Dynamisches Programmieren, 10 Punkte

Gegeben ist eine Folge (a0, a1, a2, . . . , an−1) von n verschiedenen Zahlen, z. B. (5, 28,19, 15, 20, 33, 12, 17, 10). Eine absteigende Teilfolge ist eine Teilfolge, die monotonfallend ist, zum Beispiel (19, 12, 10) oder die Teilfolge (20). (Jede einelementigeTeilfolge ist eine absteigende Teilfolge.) Schreiben Sie ein effizientes Programm inPseudocode, das die langste absteigende Teilfolge berechnet.

Analysieren Sie die Laufzeit und den Speicherbedarf Ihres Algorithmus.


Hinweis: Es geht mit O(n) Speicher und O(n2) Zeit.Fur einen korrekten Algorithmus, der in O(n log n) Zeit lauft, gibt es 5 Zusatzpunkte.(Dieser Algorithmus ist aber eher kompliziert.)

4. 2-3-Baume, 10 Punkte

Fugen Sie die Schlussel DAVID, TENNIS, COUCH, HAND, PAPPE, MAUS, FISCH,YOGHURT, und ZEIT der Reihe nach in einem zunachst leeren 2-3-Baum ein, derdie Schlussel lexikographisch ordnet. Streichen Sie dann das Wort HAND. Zeigen Siealle Zwischenschritte. (Wie in der Vorlesung sind die Werte nur in den Blattern des2-3-Baumes gespeichert.)

22

Documents

Algorithmen und Programmierung 3, WS 2015/2016 | 1. …alp3.pdf · 2016-04-12 · Zusatzaufgabe (0 Punkte): Bestimmen Sie jeweils die Anzahl der mehrfach vorkom-menden Werte: