www.jammni.de

Logo - Kleiner Drache
Login
Username:

Passwort:

Daten merken
Auto-Login
Registrieren
 
Online
niemand
 
Forumsuche
Suche nach:

Logo - DracheHaskell-Forum

blizz

Gepostet:
21.06.2006 23:08

Algorithmus von Kruskal / Huffman Codierung  
Keine Ahnung wie ich das in haskell realisieren soll!

Haskell Greedy-Algorithmen

a) Benutzen Sie den folgenden Datenentyp Graph, um den Algorithmus von Kruskal zu implementieren.

newtype Node a = Node a deriving (Read,Show,Eq)
data Edge a b = Edge (Node a,Node a) b deriving (Read,Show,Eq)
data Graph a b = Graph [Edge a b] deriving (Read, Show)

b) Implementieren Sie zwei Funktionen, die einen String nach der Methode von Huffman komprimieren und dekomprimieren.
Als Alphabet sollen bei der Komprimierung die im Text vorkommenden Buchstaben verwendet werden. Das Ergebnis soll dann ein String über dem Ascii-Alphabet sein.

hofe ihr könnt miir helfen
danke schonmal im vorraus
Zum Seitenanfang    
 
Jacke

Gepostet:
22.06.2006 15:21

   
hier schon mal der anfang:
ich programmier heute abend weiter...vllt hilft es dir ja schon was :-)
newtype Node a = Node a deriving (Read,Show,Eq)
data Edge a b = Edge (Node a,Node a) b deriving (Read,Show,Eq)
data Graph a b = Graph [Edge a b] deriving (Read, Show)

--qsort:: Ord a => [a] -> [a]

qsort (Graph x)=(Graph (qsort2 x))
qsort2 []=[]
qsort2 ((Edge (Node c,Node d) x):xs) = ((qsort2 kleiner) ++[(Edge (Node c,Node d) x)] ++ (qsort2 groesser))
where kleiner = ([y|y <- xs, (getgewicht y)<x])
groesser= ([y|y <- xs, (getgewicht y)>x])
getgewicht (Edge (Node l,Node s) m)=m


test=(Graph ([(Edge (Node 'a',Node 'b') 7),(Edge (Node 'b',Node 'c') 3),(Edge (Node 'c',Node 'e') 6),(Edge (Node 'b',Node 'e') 2)]))

--kreisfrei prüft ob der graph immernoch kreisfrei ist wenn man einen knoten dazu nimmt
--suche ist eine unterfunktion die prüft ob auch der andere knoten drin ist
kreisfrei x (Graph []) =True
kreisfrei (Edge (Node c,Node d) k) (Graph ((Edge (Node e,Node f) x):xs))
| ((c == e)||(c==f))&&((d == e)||(d==f))=False --wenn diesselbe kante schon drin ist
| ((c == e)||(c==f)) =suche d xs
| ((d == e)||(d==f)) =suche e xs
| otherwise = kreisfrei (Edge (Node c,Node d) k) (Graph xs)
where
suche v []=True
suche v ((Edge (Node h,Node l) m):ms)
|((v == h)||(v==l))=False
|otherwise = suche v ms
Zum Seitenanfang    
 
Siracusa

Gepostet:
22.06.2006 16:35

   
@Jacke (paßt nur am Rande ins Thema, aber du hast leider keine ICQ-Nummer angegeben):

Sag mal, wieso postest du immer komplette Lösungen? Mir ist schon klar, daß der Fragende es dann natürlich sehr bequem hat und nur nochmal die Lösung zum Verständins durchgehen muß. Allerdings ist es ja nicht Sinn der Sache, die gestellten Aufgaben von anderen bearbeiten zu lassen. Das Programmieren (gerade in Haskell) lernt man m.E. so nicht, sondern nur, indem man selbst programmiert. Spätestens in der Prüfung zeigt sich dann, ob man es "nur" verstanden hat, oder ob man es wirklich kann.
Aus eigentlich allen anderen Foren kenne ich das so, daß der Threadersteller zunächst erstmal selbst geschriebenen Quellcode postet und dann gemeinsam auf Fehlersuche gegangen wird. Komplette Lösungen ohne Eigeninitiative gibt's dort also nicht.

Viele Grüße,

Siracusa
Zum Seitenanfang    
 
Jacke

Gepostet:
22.06.2006 17:28

   
hmm hast du recht eigentlich recht siracusa...ich sollte mehr tipps geben und weniger machen :-)

aufgabe a) in der kurskal funktion muß man erst den graphen der länge nach sortieren...
danach schnappt man sich immer das erste element aus der liste und fügt es in den spannbaum ein(ne zweite liste) mit der funktionkreisfrei prüft man ob dieses element hinzugefügt werden kann...kriegste hin blizz

falls du bei fehlermeldungen probleme hast helfe ich dir gerne weiter...

gruß jacke
ps:(202660243)
Zum Seitenanfang    
 
Jacke

Gepostet:
23.06.2006 09:35

   
noch ein paar tipps zu huffman:
die datentypen sehen so aus

data Bit=L|R deriving (Eq, Show)
type HCode =[Bit]
type Table=[(Char,HCode)]

data Tree =Leaf Char Int |Node Int Tree Tree


Codemessage könnte diesen typ haben
codeMesage::Table->[Char]->HCode

und
decodeMesage::Tree->HCode->Char

du mußt dir eine Tabelle erstellen dir die codierung der buchstaben angibt..tabelle=[(Char , HCode)]
diese tabelle erzuegst du aus einen baum dafür brauchst du ne funktion makeTree
der Baum erhält eine liste von häufigkeiten der buchstaben [('l',3),('a',2),('h',1),('z',1)] und gibt die oben genannte tabelle zurrück
um die häufigkeiten der buchstaben zu errechnen mußt du mal in deinen lösungen gucken...das hab ich schonmal für dich geproggt...

alles in allen eine sehr lange aufgabe
als tipp mach dir erstmal eine variable tabelle und schreib gleich die funktion codeMessage...(du brauchst auch noch ne funktion lookuptable um die werte aus der tabelle zu suchen...hab ich dir so in der art auch schonmal geschrieben bei der letzten lösung)
decodeMessage würde ich an deiner stelle auch gleich zu anfang schreiben(ist sehr stark an die aufgabe letzte woche angelegt)

gruß jacke
Zum Seitenanfang