heute ist der Geburtstag von
Gabriel Cramer (31.07.1704 - 04.01.1752)


Auf das Thema antworten  [ 22 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Alle Beiträge anzeigen 
SS09: 2. Übung 
Autor Nachricht

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag SS09: 2. Übung
Ich hab das Programm zu Beispiel 1 geschrieben. Es ist ein Python-Programm. Die Endung sollte .py lauten, aber die Extension .py ist gesperrt drum hab ichs ue2b1.txt genannt.

Der Output ist:
Code:
03/2009: Codierungstheorie UE #2, Beispiel 1
Baum erzeugen:
D 0.30  A 0.25  E 0.20  B 0.15  C 0.10
D 0.30  A 0.25  f!0.25  E 0.20
g!0.45  D 0.30  A 0.25
h!0.55  g 0.45

Erzeugter Baum:
h 0.55
  D 0.30
  A 0.25
g 0.45
  f 0.25
    B 0.15
    C 0.10
  E 0.20

03/2009: Codierungstheorie UE #2, Beispiel 6a
Baum erzeugen:
A 0.33  B 0.20  C 0.20  D 0.13  E 0.13
A 0.33  f!0.27  B 0.20  C 0.20
g!0.40  A 0.33  f 0.27
h!0.60  g 0.40

Erzeugter Baum:
h 0.60
  A 0.33
  f 0.27
    D 0.13
    E 0.13
g 0.40
  B 0.20
  C 0.20

03/2009: Codierungstheorie UE #2, Beispiel 6b
Baum erzeugen:
A 1.00  B 1.00  C 1.00  D 1.00  E 1.00
f!2.00  A 1.00  B 1.00  C 1.00
f 2.00  g!2.00  A 1.00
h!3.00  f 2.00

Erzeugter Baum:
h 3.00
  g 2.00
    B 1.00
    C 1.00
  A 1.00
f 2.00
  D 1.00
  E 1.00

Zur Erklärung:

Nach "Baum erzeugen:" werden die Wahrscheinlichkeiten geordnet angegeben. Die beiden unwahrscheinlichsten Fälle werden jeweils zusammengefasst und der Name des neuen Knotens ist in der nächsten Zeile mit einem "!" gekennzeichnet.

Bei Beispiel 6 sieht man, dass in beiden Fällen der gleiche Baum aufgebaut wird. Daraus folgt, dass die binären Codes gleich sein müssen. Bei der Gleichverteilung gibt es natürlich mehrere Möglichkeiten eines binären Codes, aber die sind alle gleich gut.
Binärer Code:
00 - A
010 - D
011 - E
10 - B
11 - C


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.


Fr 20-03-2009 19:40:30
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Beispiel 2
Beispiel 2:

0, 10, 11 ist gültig

00, 01, 10, 110 ist ungültig,
weil man nach 11 schon weiß, wie es weitergeht. die 0 von 110 liefert keine ZUSÄTZLICHE information

01, 10 ist ungültig,
die 2. ziffer liefert jeweils keine zusätzliche information. 0, 1 wäre sinnvoller.

--
hat wer beispiel 3? das schaut nach sehr viel schreibarbeit aus...
und wie siehts aus mit beispiel 4 und 5?


Fr 20-03-2009 19:47:57
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
ich habs in lisp programmiert. der code ist im anhang(falls jemand an funktionaler programmierung interessiert ist).
Code:
CL-USER> (build-huffman-tree '((a 0.25) (b 0.15) (c 0.1) (d 0.3) (e 0.2)))
(((#:G2075
   (((#:G2074 ((D 0.3) (A 0.25))) 0.55)
    ((#:G2073 (((#:G2072 ((B 0.15) (C 0.1))) 0.25) (E 0.2))) 0.45)))
  1.0))

CL-USER> (build-huffman-tree '((a 1/3) (b 1/5) (c 1/5) (d 2/15) (e 2/15)))
(((#:G2079
   (((#:G2078 ((A 1/3) ((#:G2076 ((D 2/15) (E 2/15))) 4/15))) 3/5)
    ((#:G2077 ((B 1/5) (C 1/5))) 2/5)))
  1))

CL-USER> (build-huffman-tree '((a 1/5) (b 1/5) (c 1/5) (d 1/5) (e 1/5)))
(((#:G2083
   (((#:G2082 (((#:G2081 ((B 1/5) (C 1/5))) 2/5) (A 1/5))) 3/5)
    ((#:G2080 ((D 1/5) (E 1/5))) 2/5)))
  1))


Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.


Sa 21-03-2009 14:54:28
Diesen Beitrag melden
Profil ICQ
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
Beispiel 4 und 5 habe ich beide mit Induktion nach m bewiesen:
Beispiel 4:
(IA): m=1,2 trivial
(IS): Beim erzeugen des Huffman-Codes werden $p_m$ und $p_{m+1}$ vereinigt.
1.Fall: $p_1 \geq p_m+p_{m+1}$
Hier lässt sich die Induktionsvorraussetzung anwenden, denn man erzeugt den Huffman-Code für
$P=(p_1,p_2,...,p_{m-1},p_m+p_{m+1})$, wobei laut IV $p_1$ ein Wort
der Länge 1 erhält. Dieses Wort ändert sich nicht, wenn man $p_m$ und $p_{m+1}$ wieder aufspaltet.

2.Fall: $p_m+p_{m+1} > p_1 \Rightarrow p_m+p_{m+1} > \frac{2}{5} \Rightarrow p_m > \frac{1}{5}$
Daraus folgt einerseits dass $p_2+\dots+p_{m-1} =1-(p_1+p_m+p_{m+1}) < \frac{1}{5}$,
andererseits dass $p_2, ..., p_{m-1} > p_m > \frac{1}{5}$
Dieser Fall kann also nur auftreten, falls m=3, woraus aber ebenfalls folgt, dass das kürzeste Wort Länge 1 hat.


Beispiel 5:
(IA): m=4 (kleinere m sind unmöglich)
$p_1 < \frac{1}{3} \Rightarrow p_2 < \frac{1}{3} \Rightarrow p_3+p_4 = 1-p_1-p_2 > \frac{1}{3}$
Also werden zuerst 3 und 4 vereinigt, danach 1 und 2, wodurch alle Wörter Länge 2 haben.

(IS): Es werden wieder die letzen beiden Wahrscheinlichkeiten addiert, und die Fälle wie in Bsp 4 unterschieden:
1.Fall: Hier kann wieder die IV angewendet werden.
2.Fall: $p_m+p_{m+1} > p_1 $
Hier werden die letzen beiden nach dem Vereinigen immer ganz nach vorne gestellt (Die p's werden ja immer größer).
Vor dem Vereinigen mit p_1 steht folgendes da:
$(p_2+p_3,p_4+p_5,...,p_m+p_{m+1},p_1)$ (Falls m+1 gerade, beginnt das ganze mit p_3+p_4)
Da wir davon ausgehen können, dass m+1 > 4, stehen vor p_1 mind. 2 Werte, also ist man nach der Vereinigung von
$p_m+p_{m+1}$ mit $p_1$ noch nicht fertig, was bedeutet, das jedes Wort min. Länge 2 hat!

Ich hoffe, es ist nicht zu kompliziert formuliert. Bin für legliche (konstruktive) Kritik offen!


Mo 23-03-2009 17:19:30
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 28 + 204
Wohnort: 1040 Wien // Waldviertel
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
diesmal sollten wir ja wirklich alle per internet schon vorkreuzen, aber:
Zitat:
Zu diesem Zeitpunkt ist noch keine Eintragung erlaubt!

hat schon jemand gekreuzt?

_________________
Why do Computer Scientists get Halloween and Christmas mixed up?
Because: oct 31 = dec 25


I wish to complain about this parrot that I purchased not half an hour ago from Fachschaft TM.


Mo 23-03-2009 18:40:31
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
@highstick: danke fürs online stellen!
edit: kreuzen geht bei mir auch noch nicht.


Mo 23-03-2009 19:07:56
Diesen Beitrag melden
Profil ICQ

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
ich wollte gestern schon kreuzen. da gings aber noch nicht. und jetzt gehts auch noch immer nicht (Mo, 19:25)!

wie war das mit dem "cron-job"?
cron t=-3 AUFMACHEN
cron t=-2 ZUMACHEN
:x


Mo 23-03-2009 20:26:56
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 26 + 29
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
hat jemand etwas zum 3.?


Mo 23-03-2009 20:35:23
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
wenn jemand was dazu hat... ich denke nicht, dass dieser jemand so verrückt ist, dass er das alles bei m=5 eintippen würde :mrgreen:

Beim Code hätte ich eine Frage, ich hab das alles in matlab implementiert. Zu meiner Frage:
Wie kann ich bei einer Zuweisung einen '0'er bzw einen '1'er einfach an die zugewiesene Zahl "picken" bzw. "dranhängen"?

Mein code:
Code:
function X = huffman(P)
n=size(P,2);
G=zeros(2,n);
L=zeros(n); R=zeros(n);
c=zeros(n);
G(1,1:n)= P(1:n);
G(2,1:n)=1:n;

G(1,:)=sort(G(1,:),'descend');

for i= 1:n-1
    G(1,n-i)=G(1,n-i)+G(1,n-i+1);
    L(i)=G(2,n-i);
    R(i)=G(2,n-i+1);
    G(2,n-i)=n+i;
    G(:,n-i+1)=[];
    G(1,:)=sort(G(1,:),'ascend');
end
c(L(n-1))=0;
c(R(n-1))=1;

for j=n-2:-1:1
    c(L(j))=c(j+n)0; %muss noch überlegen, wie man hier einfach so einen 0'er bzw. einen 1'er dranhängt.
    c(R(j))=c(j+n)1;
end


hab mich jetzt lange damit beschäftigt, sollte doch nicht so schwer sein, bekomm aber bei jedem meiner Versuche eine Fehlermeldung :roll:


Mo 23-03-2009 21:22:10
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Matlab
aa = [2,3]
-> aa = [2 3]

[aa,5]
-> [2 3 5]

bzw ";" wenn du spalten willst

in deinem fall [c(j+n),0] oder [c(j+n);0]


Mo 23-03-2009 21:38:06
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
hatte es so ganz am anfang probiert!! ging jedoch nicht bei matlab.. :(
aber danke für die Hilfe!! :wink:


Mo 23-03-2009 22:01:52
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 26 + 29
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
x='010';
x(4)='0' liefert x='0100'


Mo 23-03-2009 22:24:48
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
naja, das beispiel von mir funktioniert bei mir aber. das problem ist vielleicht, dass c(j+n) schon keinen sinn macht... oder was ist z.B. das ergebnis von c(4)? meines wissens nach ist c() einfach eine art von ersatz für eckige klammern?

vielleicht liegts auch daran, dass ich octave hab und kein matlab. aber ich weiß grad nicht, was du mit c(j+n) meinst also wunderts mich nicht, wenns der computer nicht versteht...

@s.e.: viele wege führen nach rom 8) praktisch, dass die listen von selber wachsen


Mo 23-03-2009 22:29:51
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 05/2008
Beiträge: 27 + 12
Wohnort: Wien West
Studium: (alt) Bachelor Computerwissenschaften
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
kater hat geschrieben:
aber ich weiß grad nicht, was du mit c(j+n) meinst also wunderts mich nicht, wenns der computer nicht versteht...


Unter der Annahme, dass du gescheiter bist als der Computer.. Was natürlich nicht immer der Fall sein wird. :wink:


Mo 23-03-2009 22:44:46
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 2. Übung
probiers doch einfach mal mit
c(j+n,0)
:mrgreen:

aber wenn du mir sagst, was die c()-funktion macht, was in L(j) drin ist (zeile oder spalte und welche dimension), dann sag ich dir, wie man eine 0 dranhängt 8)

mfg


Mo 23-03-2009 23:08:53
Diesen Beitrag melden
Profil
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Auf das Thema antworten   [ 22 Beiträge ]  Gehe zu Seite 1, 2  Nächste
Alle Beiträge anzeigen 


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast


Du darfst neue Themen in diesem Forum erstellen.
Du darfst Antworten zu Themen in diesem Forum erstellen.
Du darfst deine Beiträge in diesem Forum nicht ändern.
Du darfst deine Beiträge in diesem Forum nicht löschen.
Du darfst keine Dateianhänge in diesem Forum erstellen.

Suche nach:
Gehe zu:  
cron
Powered by phpBB © phpBB Group.  |  Designed by STSoftware for PTF  |  © Czechnology 2007 - 2021  |  Deutsche Übersetzung durch phpBB.de