46
Teile und Herrsche (Divide and Conquer) Entwurfsmethode f¨ ur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. ose rekursiv die entstehenden Unterprobleme (Conquer) 3. Setze die L¨ osungen zusammen. Instanzen : Mergesort Quicksort Intervallhalbierung (kein Zusammensetzen) schnelle Berechnung ganzzahliger Potenzen P raktische Informatik 1, WS 2004/05, F olien Div+Conq-1, (4. F ebruar2005) Seite 1

Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Embed Size (px)

Citation preview

Page 1: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Teile und Herrsche (Divide and Conquer)

Entwurfsmethode fur Algorithmen

1. Teile das Problem in kleinere Unterprobleme (Divide)2. Lose rekursiv die entstehenden Unterprobleme (Conquer)3. Setze die Losungen zusammen.

Instanzen :

• Mergesort• Quicksort• Intervallhalbierung (kein Zusammensetzen)• schnelle Berechnung ganzzahliger Potenzen

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 1

Page 2: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Divide-and-Conquer: Laufzeiten

Oft ergibt sich der Effekt:

O(n) Laufzeitanteil verbesserbar zu O(log(n))

Notwendig dazu:

Summe der Großen der Teilprobleme ≤ Große des Problems

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 2

Page 3: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Turme von Hanoi

Gegeben Stapel von verschieden großen Scheibenvon oben nach unten großer werdend

Aufgabe: Umstapeln auf einen anderen Stapel.Erlaubt ist ein weiterer HilfsstapelBedingung: Es darf niemals eine Scheibe auf einer kleineren

liegen

Losung: mittels Teile-und-Herrsche:

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 3

Page 4: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

n

n-1

n

n-1

n-1n

1

2

3

Page 5: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Turme von Hanoi (2)

Notwendige Bewegungen fur n:

1. n − 1 Scheiben von 1 nach 3 mit 2 als Hilfsstapel

2. Scheibe n von 1 nach 2

3. n − 1 Scheiben von 3 nach 2 mit 1 als Hilfsstapel

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 5

Page 6: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Turme von Hanoi (2)

Haskell-Algorithmus zum Ermitteln der Bewegungen.

Die Nr. der Stapel wird als Argument mitubergeben.

-- hanoi: Stapel, Stapelnr, Zielstapelnr Hilfstapelnr:

hanoi xs a b c = hanoiw (reverse xs) a b c

hanoiw [] _ _ _ = []

hanoiw xa a b c =

(hanoiw (tail xa) a c b)

++

((head xa ,(a,b)): (hanoiw (tail xa) c b a))

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 6

Page 7: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Hanoi: Testaufruf

-- hanoi [1,2,3] 1 2 3 ergibt

-- [(1,(1,2)), (2,(1,3)), (1,(2,3)), (3,(1,2)), \\

--- (1,(3,1)), (2,(3,2)), (1,(1,2))]

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 7

Page 8: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Turme von Hanoi (3)

hanoi-Resultat Liste von Bewegungen:Zum Beispiel eine Bewegung (2, (1,3))Scheibe 2 von Stapel 1 nach 3

Lange der Resultatliste = 2n − 1

wenn n die Anzahl der Scheiben ist.

Die Funktionen hanoiexec und hanoiexecl

interpretieren die Ausgabeliste und fuhren die Bewegungen aus.

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 8

Page 9: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Such-Algorithmen: Suche mit Backtracking

Beispiel Handlungsreisenden-Problem (travelling salesman problem)

Gegeben: Landkarte, Stadte, Wege und Entfernungen

Gesucht: optimaler Weg durch alle Stadte.

Weitere Beispiele:

• optimaler Zug in Spielen (Dame, Schach, Tictactoe, Go)• erfullende Belegung einer aussagenlogischen Formel

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 9

Page 10: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Suche

Abstrakte Sichtweise:

Suche = Durchmusterung eines implizit gegebenenSuchbaumes (Suchraumes)

geordnete Aufzahlung der moglichen Losungen

Suchstrategien: Tiefensuche (depth-first)Breitensuche (breadth-first)

Zurucksetzen bei Fehlschlag: Backtracking

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 10

Page 11: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Zusammensetzen eines Wertes

Gegeben : Satz von (ganzzahligen, positiven ) GewichtenGesucht : Zielgewicht

Vereinfachtes Modell:

Gegeben : Multimenge von positiven ganzen ZahlenGesucht : Untermultimenge, deren Summe genau

das Zielgewicht (die gewunschte Zahl) ergibt.

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 11

Page 12: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Gewichtsproblem (2)

Erste Methode

Konstruiere die Liste aller Unterlisten, berechne deren Summe und

vergleiche mit der gewunschten Zahl:

Funktion gewichtx:

Argument 1: Liste der verfugbaren GewichteArgument 2: Zielzahl

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 12

Page 13: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Gewichtsproblem (3)

data Maybe a = Nothing | Just a

gewichtx xs ziel =

let ulisten = unterlisten xs

wertuliste = zip (map sum ulisten) ulisten

okliste = filter (\(w,xs) -> w == ziel) wertuliste

in head okliste

unterlisten [x] = [[x]]

unterlisten (x:xs) =

let unterl = unterlisten xs

in ([x]: (map (\ul -> x:ul) unterl)) ++ unterl

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 13

Page 14: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Methode 1: Eigenschaften

Die Funktion gewichtx ist ineffizient

Die Konstruktion aller Unterlisten erfordert exponentiellen Platz

lazy Auswertung ergibt: linearen Platzbedarf, exponentielle Zeit

gewichtx sucht weiter, auch wenn es keine Erfolgsaussichten mehr gibt

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 14

Page 15: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Suche mit Backtracking

Backtracking, wenn die Summe der Gewichte schon zu groß ist.

gewichtxbt xs ziel =

case gewichtxbtw xs ziel []

of Nothing -> Nothing

Just res -> Just (sum res, res)

gewichtxbtw xs 0 res = Just res

gewichtxbtw [] ziel res = Nothing

gewichtxbtw (x:xs) ziel res =

if ziel < 0 then Nothing

else

let versuch1 = gewichtxbtw xs (ziel-x) (x:res)

versuch2 = gewichtxbtw xs ziel res

in case versuch1 of

Just x -> Just x

Nothing -> versuch2

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 15

Page 16: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Testlauf Gewichtsproblem

Testeingabe = [5,5,3,3,3,3], gewunschtes Ergebnis ist 12.

(Just (12,[3, 3, 3, 3]),

[[5], [5, 5], [5, 5, 3], [5, 5, 3], [5, 5, 3], [5, 5, 3],

[5, 3], [5, 3, 3], [5, 3, 3, 3], [5, 3, 3, 3], [5, 3, 3],

[5, 3, 3, 3], [5, 3, 3], [5, 3], [5, 3, 3], [5, 3, 3, 3],

[5, 3, 3], [5, 3], [5, 3, 3], [5, 3], [5], [5, 3], [5, 3, 3],

[5, 3, 3, 3], [5, 3, 3, 3], [5, 3, 3], [5, 3, 3, 3],

[5, 3, 3], [5, 3], [5, 3, 3], [5, 3, 3, 3], [5, 3, 3],

[5, 3], [5, 3, 3], [5, 3],

[3], [3, 3], [3, 3, 3], [3, 3, 3, 3]])

Weitere Verbesserungsmoglichkeiten: Symmetrien ausnutzen

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 16

Page 17: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Allgemeine Suchfunktion mit Tiefensuche und

Abschneiden

suchbtdf :: a -> (a->[a]) -> (a-> Bool) -> (a-> Bool) -> Maybe a

anf: aktuelles Objekt (Zustand)toechter: Direkte Nachfolgezustandeziel: Pradikat: ist der aktuelle Zustand ein Zielzustand?cut: Wenn ja, dann keine Nachfolgezustande untersuchen

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 17

Page 18: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Allgemeine Suchfunktion mit Tiefensuche und

Abschneiden

suchbtdf anf toechter ziel cut =

if ziel anf then Just anf

else if cut anf

then Nothing

else let nexts = toechter anf

in suchbtdfl nexts toechter ziel cut

suchbtdfl [] toechter ziel cut = Nothing

suchbtdfl (x:xs) toechter ziel cut =

let result1 = suchbtdf x toechter ziel cut

result2 = suchbtdfl xs toechter ziel cut

in case result1 of

Nothing -> result2

Just x -> Just x

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 18

Page 19: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Anwendung und Testlauf

testgewicht_allgem = suchbtdftr ([],[5,5,3,3,3,3])

(\(xs,ys) -> if ys == [] then []

else [(head ys:xs,tail ys),(xs,tail ys)] )

(\(xs,_) -> (sum xs) == 12)

(\(xs,_) -> (sum xs) > 12)

--- (75 Schritte)

testgewicht_allgemmv =

suchbtdftr ([],[(5,2),(3,4)])

(\(xs,ys) -> if ys == [] then []

else let (yh1,yh2):yr = ys

in if yh2 == 1

then [(yh1:xs,yr),(xs,yr)]

else [(yh1:xs,(yh1,yh2-1):yr),(xs,yr)])

(\(xs,_) -> (sum xs) == 12)

(\(xs,_) -> (sum xs) > 12)

--- ( 17 Schritte)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 19

Page 20: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Greedy Algorithmen, lokal optimale Schritte

greedy == gierig, gefraßig

Idee der Suche

Bevorzuge den jeweils lokal optimalsten Schritt

Ergibt meist nur suboptimale Losung

Bei manchen Problemklassen: optimale Losung.

Paketproblem: Abwandlung des Gewichtsbeispiels

Gegeben einige Teile, die in Pakete verpackt werden sollenund eine Obergrenze des Paketgewichts.

Gesucht optimale Zusammenstellung der Teile fur das erste Paket

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 20

Page 21: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Greedy Algorithmen, lokal optimale Schritte

Vereinfachung: Liste von Zahlen.

lokal optimal: Immer das jeweils schwerste ubrige Teil nehmen

Ergibt suboptimale Werte, aber nicht optimale.

postgreedy xs max = postgreedyw xs max []

postgreedyw [] max res = (sum res,res)

postgreedyw _ 0 res = (sum res,res)

postgreedyw xs max res =

let ls = filter (<= max) xs

m = maximum ls

in case ls of

[] -> (sum res,res)

_ -> postgreedyw (delete m xs) (max - m) (m:res)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 21

Page 22: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Greedy Algorithmus: Testlaufe

-- Beispiele:

--- postgreedy [1,2,3,4,5] 12 ---> (12,[3, 4, 5])

-- nicht optimal, aber nahe dran:

-- postgreedy [5,5,3,3,3,3] 12 ---> (10,[5, 5])

-- postmin1 [5,5,3,3,3,3] 12 ---> (12,[3, 3, 3, 3])

-- postgreedy [5,5,3,3,3,3] 14 ---> (13,[3, 5, 5])

-- postmin1 [5,5,3,3,3,3] 14 ---> (14,[5, 3, 3, 3])

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 22

Page 23: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman-Kodierung von Nachrichten

Nachrichtenubertragung, Kompression von Dateien

Analog zum Morsecode:

Gegeben: lange Nachricht uber Alphabet A,

die relativen Haufigkeiten p(a) der einzelnen Zeichen sind bekannt

Ubertragung der Nachricht mit anderem Alphabet B

Gesucht: Kodierungsfunktion c so dass:

Ubermittlungsaufwand der kodierten Nachricht minimal

Lange der kodierten Nachricht

Lange der Original-Nachricht

≈ mittlere Lange des Kodes C := {c(a) | a ∈ A},= Σ{a∈A}p(a) ∗ c(a)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 23

Page 24: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman-Kodierung von Nachrichten

Wir nehmen B = {0,1}.

Kodierung c so, dass C := {c(a) | a ∈ A} prafixfrei ist,

d.h. kein Wort in C ist Prafix eines anderen in C.

Zur prafixfreien Kodierung kann ein binarer Baum aufgebaut werden,

der die Dekodierung sehr einfach macht:

Die Kodeworte sind die Adressen der Blatter

(0: nach links, 1: nach rechts),

die Markierungen der Blatter sind die gesuchten Kode-Buchstaben.

Dekodierung ist eindeutig und schnell

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 24

Page 25: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Morse-Kode

a ·− a · − ·− b − · ·· c − · −·ch −−−− d − · · e · f · · −·g −− · h · · ·· i ·· j · − −−. . .

ist kein Huffman-Kode, denn nicht prafixfrei

Nimmt man die Pause dazu, dann prafixfrei.

Die Lange der Kodierungen der Buchstaben beim Morsekode

entspricht der relativen Haufigkeit der Buchstaben in englischen Texten

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 25

Page 26: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Erzeugung eines Huffman-Kodes

Seien a1, . . . , an die zu kodierenden Zeichen

und p1, . . . , pn die relativen Haufigkeiten (u.a.n∑

i=1pi = 1)

Gesucht: Kode c uber {0,1}

n∑i=1

|c(ai)| ∗ pi, die mittlere Kodewortlange, soll minimal werden.

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 26

Page 27: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Algorithmus zur Erzeugung eines

Huffman-Kodes

Greedy-Algorithmus zum Aufbau eines Code-Baumes:

Start mit Liste von Baumen, die nur aus einem Blatt bestehen.

Schritt des Algorithmus:

Nehme die beiden Baume mit der geringsten Haufigkeit

Erzeuge neuen Baum (Knoten B1 B2) zu 0,1

Am Ende ergibt sich der gesuchte Kode-Baum.

Dieser Greedy-Algorithmus erzeugt immer einen optimalen Huffman-

Kode !

Der Baum ist nicht eindeutig

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 27

Page 28: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman in Haskell

data Hufftree a = Hleaf a Float

| Hnode (Hufftree a) (Hufftree a) Float

huffle :: Hufftree a -> Hufftree a -> Bool

huffle htr1 htr2 = (huffrh htr1) <= (huffrh htr2)

huffrh (Hleaf _ x) = x

huffrh (Hnode _ _ x) = x

huffgreedy xs = huffgreedyw (map (\(x,p)->(Hleaf x p)) xs)

huffgreedyw [x] = x

huffgreedyw xs@(_:_) =

let y1:(y2:yr) = mischsortg xs huffle

in huffgreedyw ((Hnode y1 y2 ((huffrh y1) + (huffrh y2))):yr)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 28

Page 29: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman in Haskell

huffextractcode ht =

mischsortg (map (\(x,y) -> (x,reverse y)) (huffxcw "" ht))

(\(x1,_) (x2,_) -> x1 <= x2)

huffxcw prefix (Hleaf x _) = [(x,prefix)]

huffxcw prefix (Hnode tl tr _) =

(huffxcw (’0’:prefix) tl) ++ (huffxcw (’1’:prefix) tr)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 29

Page 30: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman in Haskell

testhuffgreedy =

let probs =

[(’a’,0.45),(’b’, 0.13),(’c’,0.12),

(’d’,0.16),(’e’,0.09),(’f’,0.05)]

tr = huffgreedy probs

in (mittlere_codewortlaenge tr, huffextractcode tr)

mittlere_codewortlaenge tr = mitt_cwl tr 0.0

mitt_cwl (Hleaf _ x) tiefe = x*tiefe

mitt_cwl (Hnode tl tr x) tiefe =

(mitt_cwl tl (tiefe + 1.0)) + (mitt_cwl tr (tiefe + 1.0))

> testhuffgreedy

> (2.24,[(’a’,"0"), (’b’,"101"), (’c’,"100"),

(’d’,"111"), (’e’,"1101"), (’f’,"1100")])

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 30

Page 31: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman in Haskell

a

c b

f ed

0 1

0 1

01 0

1

0 1

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 31

Page 32: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman: Kodieren und Dekodieren

huffkodiere xs tr = huffcode xs (huffextractcode tr)

huffcode [] tr = []

huffcode (x:xs) tr = (kodiere x tr) ++ huffcode xs tr

kodiere x ((a,ca):xs) = if x == a then ca else kodiere x xs

huffdekodiere xs tr = huffdecode xs tr tr

huffdecode [] (Hleaf a _) _ = [a]

huffdecode xs (Hleaf a _) tr = a : (huffdecode xs tr tr)

huffdecode (’0’:xs) (Hnode trl trr _) tr = huffdecode xs trl tr

huffdecode (’1’:xs) (Hnode trl trr _) tr = huffdecode xs trr tr

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 32

Page 33: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Huffman: Kodieren und Dekodieren

testkodiere =

let wort = "badfadcade"

tr = huffgreedy hufftestprobs

kodiertes_wort = huffkodiere wort tr

dekodiertes_wort = huffdekodiere kodiertes_wort tr

in (kodiertes_wort, dekodiertes_wort,wort, dekodiertes_wort == wort)

> testkodiere

> ("10101111100011110001111101","badfadcade","badfadcade",True)

Kompressionsverfahren: Kodieren (kurze) Worte statt Zeichen.

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 33

Page 34: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Scan: lineare Algorithmen

Ziel: Konstruktion von linearen Algorithmen (d.h. O(n))

Verfahren: Durchlaufen (Scan) einer Folge / ListeVerwendung von O(1)- Zeit und Speicherpro Folgenelement.Auch mehrfaches Scannen ist erlaubt.

Wesentlich: Minimierung der Anzahl der Durchlaufe.

Bester Fall: 1 DurchlaufFile-, Stream-Verarbeitung

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 34

Page 35: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Scan in Haskell

Beispiele filter p (map q xs)) ein Durchlauf

map q (reverse xs) ungunstig,da ganze Liste gleichzeitig im Speicher

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 35

Page 36: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel

Maximum einer Liste von Zahlen:

Verfahren 1: sortieren, dann erstes Element auswahlenO(n ∗ log(n))

Verfahren 2: Scannen der Liste mit aktuellem maximalen ElementO(n)

minim (x:xs) = minimr x xs

minimu x [] = x

minimr x (y:ys) = if x <= y then minimr x ys

else minimr y ys

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 36

Page 37: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Minimum mit Verfahren 2

Minimumberechnung:

minim_sort xs = head (mischsort xs)

naive Analyse: O(n ∗ log(n))genauere Analyse in Haskell: Aufwand: O(n)

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 37

Page 38: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiele fur Scan-Algorithmen

Suche eines gegebenen Wortes in einem Textfile

Erzeugung eines optimalen Huffman-Kodes:1. Scan zur Ermittlung der Haufigkeiten der Zeichen2. Erzeugung des Huffman Baumes3. Kodierung: Scan

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 38

Page 39: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel fur lineare Algorithmen

Finden des Medians einer Liste:

Median: Element, so dass die Anzahl der kleinerenund die Anzahl der großerenmoglichst nah an der Halfte liegt.

Es gibt O(n)-Algorithmus

vermutlich gibt es keinen Scan- Algorithmus!

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 39

Page 40: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: Summe von Teilfolgen

Aufgabe: Finde die maximale Summe einer zusammenhangenden

Teilfolge einer endlichen Folge von ganzen Zahlen.

bei der alle Elemente nichtnegativ sind

(mcv: maximal contiguous subvector).

Beispiel

Bei [1,2,−5,3,4,−1,1,2,5,−10] ergibt sich 8.

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 40

Page 41: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: mcv: verschiedenen Methoden

direktes Verfahren

Bestimme alle Teilfolgen (ohne Lucken),

wahle die aus, die nur nichtnegative Elemente haben,

bilde die Summe und

bestimme das Maximum.

Dieses Verfahren ist kubisch O(n3):

i. Es gibt quadratisch viele dieser Teillisten,ii. Auswahl hat Zeitbedarf O(n3),iii. Summenbildung ist linear in einer Teilliste, also auch O(n ∗ n2)iv. Maximumsberechnung linear (d.h. quadratisch).

Zusammen O(n3).

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 41

Page 42: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: mcv: naives Verfahren

startsublists [] = []

startsublists [x] = [[x]]

startsublists (x:t) = [x] : (map (\y->(x:y)) (startsublists t))

nesublists [] = []

nesublists (x:t) = (startsublists (x:t)) ++ (nesublists t)

mcv_quadrat [] = 0

mcv_quadrat (x:xs) =

maximum (map sum

(filter (\ys -> all (>= 0) ys) (nesublists (x:xs))))

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 42

Page 43: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: mcv: Divide and Conquer

Halbiere die Liste in der Mitte, bestimme die mcv-Zahlen ml, mr rekursivberechne zusatzlich die rechte mcv-Zahl mlr der linken Teillistedie linke mcv-Zahl mrl der rechten Teilliste.Bilde das Maximum der Zahlen ml, mr, mrl + mlr.

Zeitbedarf ist O(n ∗ log(n))

mcv_dq [x] = if x <= 0 then 0 else x

mcv_dq (x:xs) = let len =length (x:xs)

xa = take (len ‘div‘ 2) (x:xs)

xb = drop (len ‘div‘ 2) (x:xs)

mca = mcv_dq xa

mcb = mcv_dq xb

mca_r = sum (takeWhile (>= 0) (reverse xa))

mcb_l = sum (takeWhile (>= 0) xb)

in maximum [mca,mcb,mca_r+mcb_l]

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 43

Page 44: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Beispiel: mcv: Scan-Verfahren

Der Scan benotigt zum Durchlauf der Liste eine Umgebung:• das bisher gefundene Maximum,• die Summe der aktuellen Teilliste• die Restliste.

Zeitbedarf ist O(n)

mcv_scan xs = mcv_scanr 0 0 xs

mcv_scanr gm lm [] = max gm lm

mcv_scanr gm lm (x:xs) =

if x < 0

then mcv_scanr (max gm lm) 0 xs

else mcv_scanr gm (lm+x) xs

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 44

Page 45: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Algorithmen fur mcv-Variante

Finde die maximale Summe einer zusammenhangenden Teilfolge

einer gegebenen endlichen Folge von ganzen Zahlen.

MNaiver Algorithmus:

startsublists [] = []

startsublists [x] = [[x]]

startsublists (x:t) = [x] : (map (\y->(x:y)) (startsublists t))

nesublists [] = []

nesublists (x:t) = (startsublists (x:t)) ++ (nesublists t)

mcv2_quadrat [] = 0

mcv2_quadrat (x:xs) =

maximum (map sum (nesublists (x:xs)))

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 45

Page 46: Teile und Herrsche (Divide and Conquer) · Teile und Herrsche (Divide and Conquer) Entwurfsmethode fur Algorithmen 1. Teile das Problem in kleinere Unterprobleme (Divide) 2. L¨ose

Scan-Algorithmus fur mcv-Variante

Umgebung:

• maximale Summe bisher• verwendbare Restsumme• Restfolge

mcv2_scan xs = mcv2_scanr 0 0 xs

mcv2_scanr gm lsum [] = max gm lsum

mcv2_scanr gm lsum (x:xs) =

if lsum < 0

then mcv2_scanr gm x xs

else mcv2_scanr (max gm lsum) (lsum+x) xs

Praktische Informatik 1, WS 2004/05, Folien Div+Conq−1, (4. F ebruar2005) Seite 46