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: 5. Übung am 28.4.2009 
Autor Nachricht

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag SS09: 5. Übung am 28.4.2009
Zu Beispiel 1: Was ist bitte eine binäre DMS?

Bei Beispiel 3 haben wir den Code heute in der Vorlesung gemacht... Der schwierigere (oder zumindest zeitaufwändigere) Teil ist aber eher das Programm zu schreiben.

Beispiel 5 aus dem Bauch heraus: Ein Code ist genau dann Suffix-frei, wenn der "Umdrehcode" Präfix-frei ist. Die Umdrehabbildung ist bijektiv. (Wer kein theoretische Informatik hat ist im Nachteil!)

Ich bin nicht sicher, ob es überhaupt sinnvoll ist, da viel rumzuargumentieren. Der Unterschied zwischen präfix- und suffix-frei ist doch einfach der, ob man von links nach rechts oder von rechts nach links schreibt. Da darf sich an der dahinterliegenden Logik nichts ändern.
Es bleibt noch zu zeigen, dass ein Suffix-Code endlich eindeutig entzifferbar ist... (d.h. wir schreiben jedes einzelne codewort von rechts nach links und lesen aber von links nach rechts.)


Zuletzt geändert von kater am So 26-04-2009 14:17:39, insgesamt 1-mal geändert.



Mi 22-04-2009 17:17:53
Diesen Beitrag melden
Profil
Benutzeravatar

Registriert: 10/2007
Beiträge: 27 + 109
Studium: (alt) Master Computerwissenschaften
Mit Zitat antworten
Beitrag Re: 5. Übung am 28.4.2009
Definition 2.1.1 Unter einer (diskreten) Nachrichtenquelle (kurz: Quelle) versteht man eine
Folge von (diskreten) Zufallsvariablen X1,X2, . . . . Sind die Xi unabhängig, so sagt man, die
Quelle ist gedächtnislos.
Hier betrachten wir ausschließlich diskrete gedächtnislose Quellen (kurz: DMS - discrete memoryless
source
). Weiters seien die Xi identisch verteilt


Mi 22-04-2009 20:00:53
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 107
Mit Zitat antworten
Beitrag Re: 5. Übung am 28.4.2009
kann es sein, dass beim 4.beispiel der einfachste ausdruck I(X1,X2) ist oder gibt es einen noch einfacheren?


Sa 25-04-2009 17:56:01
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: 5. Übung am 28.4.2009
zu Beispiel 4:
also I(X1,X2) weiter zu vereinfachen dürfte schwierig werden um nicht zu sagen unmöglich. noch "einfacher" wäre nur noch H(Xi) für irgendein i=1..n. dann müsste H(Xi) = I(X1,X2) gelten. dagegen findet man aber ein gegenbeispiel, nämlich (unabhängig identisch verteiltes) n-maliges münzewerfen: H(Xi)=1, I(X1,X2)=0

I(X1,(X2,...,Xn)) = H(X1) - H(X1|X2,...Xn)
weil MK: = H(X1) - H(X1|X2)
vereinfacht: I(X1,X2)

passt das dann so? hast du das genauso gemacht?


Zuletzt geändert von kater am Sa 25-04-2009 21:46:59, insgesamt 1-mal geändert.



Sa 25-04-2009 21:22:05
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: 5. Übung am 28.4.2009
hat irgendwer eine idee zu beispiel 1 oder beispiel 2?

und was meint unser prof mit $$\max_{P^n}$$ in beispiel 1? P^n wird ja auf der rechten seite garnicht verwendet also ist es streng formal genommen humbug. diese ungenauen notationen von unserem prof nerven mich manchmal schon.


Sa 25-04-2009 21:40:44
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 107
Mit Zitat antworten
Beitrag Re: 5. Übung am 28.4.2009
ja beispiel 4 hab ich genauso gemacht!


Sa 25-04-2009 21:42:50
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
Ich hab Beispiel 3 gemacht. Das Programm hat 75 Zeilen, wenn man Kommentare und Leerzeilen nicht mitrechnet. Das Programm beweist weiters, dass Perl6 mittlerweile in einem benutzbaren Zustand ist - das Thema Performance soll verschwiegen bleiben. Das Motto der neuen Major-Version lautet: "Gut Ding braucht Weile." Hoffentlich schaffen sie es in unter 10 Jahren Entwicklungszeit die Sprache fertigzukriegen.

Benutzter Interpreter:
This is Rakudo Perl 6, revision 37980 built on parrot 1.0.0-devel
for i486-linux-gnu-thread-multi.

Code:
Allgemeiner Huffman-Algorithmus
  implementiert in Perl 6 fuer die Codierungstheorie UE #5
  v1.0 / 2009-04-26

Original Knoten:
1 0.2
2 0.17
3 0.16
4 0.14
5 0.12
6 0.1
7 0.09
8 0.02
9 0
A 0

Berechneter Baum:
1 0.2
2 0.17
3 0.16
Y 0.47
  4 0.14
  5 0.12
  X 0.11
    7 0.09
    8 0.02
    9 0
    A 0
  6 0.1

Berechneter Code:
1: 0
2: 1
3: 2
4: 30
5: 31
6: 33
7: 320
8: 321
9: 322
A: 323


PS: Perl6 ist die Zukunft!

EDIT: wusste nicht, dass man noch 2 leere knoten anhängen muss. hier die korregierte version...


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


Zuletzt geändert von kater am Mo 27-04-2009 18:00:42, insgesamt 2-mal geändert.



So 26-04-2009 14:34:43
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 107
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
zu beispiel 1: vielleicht meint er ja maximum über P=(1-p,p), also dass p im intervall [0,1] läuft???


So 26-04-2009 16:12:17
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
ich glaube ja, dass $$\max_{P^n}$$ eine art redewendung ist, die soviel wie "man darf noch ein positives C (das affin von n abhängt) dazuaddieren" bedeutet. Wähle C=n und das Beispiel ist gelöst :P
ich geb zu, deine variante erscheint mir realistischer allerdings ist das sicher keine standardnotation. implizite dynamisch gebundene argumente gibts vielleicht in lisp ('declare special') oder in perl5 ('local') aber in einem mathematischen zusammenhang hab ich sowas noch nie gesehen. das wär für meinen geschmack fast noch schlimmer als das wertzsche "+0" als abkürzung für den limes.

ich hab ihm mal eine mail geschrieben:
Zitat:
...
Ich komme leider beim Beispiel 1 der Übung 5 nicht weiter und die Kollegen die ich gefragt habe wissen auch nicht weiter...
Die Frage lautet: Was bedeutet max_{P^n}? P ist nach meinem Verständnis eine vorgegebene Wahrscheinlichkeitsverteilung. Weiters weiß ich nicht, was es bedeutet, wenn die Schleifenvariable (P^n) im Ausdruck garnicht vorkommt. Nach meinem Verständnis ist das im Falle eines Maximums so, wie wenn ich das Maximum weglasse, vgl.
$\max_{x\in P} c = c \forall c$.
Liegt da vielleicht ein Angabefehler vor?
...


So 26-04-2009 16:44:55
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
zum bsp5: die eindeutige entzifferbarkeit lässt sich doch genauso wie bei präfixcodes beweisen. einziger unterschied ist, dass ich den code von hinten nach vorne durchlaufe(möglich, da endlich).
das wars doch schon, oder?


So 26-04-2009 17:48:07
Diesen Beitrag melden
Profil ICQ

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
nein nein, der unterschied hat es in sich. "möglich da endlich" musst du außerdem noch ein bissl begründen, so einfach ist das nicht! man kann sogar ein programm angeben, dass die entzifferung vornimmt und man kann zeigen, dass der look-ahead-buffer eines solchen parsers nicht größer als die maximale codewortlänge sein muss! kann sein dass es einen unkonstruktiven beweis gibt der schneller geht...


So 26-04-2009 17:55:44
Diesen Beitrag melden
Profil

Registriert: 10/2007
Beiträge: 27 + 52
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
hhm, mir fällt grad auf, dass die symmetrie zwischen präfix und suffix ist nicht vollständig ist. seh ich das richtig, dass wenn man den eingabetext (mit hilfe eines suffixcodes) von hinten nach vorne verschlüsselt, man dann die endliche entzifferbarkeit analog derer des präfixcodes zeigen könnte?.


So 26-04-2009 18:03:18
Diesen Beitrag melden
Profil ICQ

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
naja die entzifferbarkeit eines präfixcodes ist im grunde trivial: einfach solange lesen bis man ein gültiges codewort hat. dann mit dem nächsten codewort zum lesen beginnen. ein fall für einen LL(0) parser. bei einem suffix-code geht das aber nicht, da braucht man einen LL(k)-parser mit k=(maximale codewortlänge). sorry, ich hab leider keine mathematische erklärung!


So 26-04-2009 18:27:32
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
alex du hast recht, das funktioniert so! hab grad nachgelesen was "e.e.e." bedeutet. damit hab ich das 5. beispiel jetzt.

ich hab wieder ein pdf gemacht. diesmal aber nur mit den beispielen 3,4,5.


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


So 26-04-2009 20:09:34
Diesen Beitrag melden
Profil

Registriert: 03/2008
Beiträge: 26 + 32
Wohnort: 1230 Wien
Mit Zitat antworten
Beitrag Re: SS09: 5. Übung am 28.4.2009
hier die antwort von unserem prof zu meiner frage zu bsp 1.
Zitat:
P^n ist die Produktverteilung von (X_1,...,X_n), also das Produkt der
Bernoulliverteilung P=(p, 1-p). Man muss allerdings voraussetzen, dass
die Z unabhaengig von den X sind ( aber nicht unabhaengig
untereinander).

jetzt hab ich 2 dinge gelernt die ich mir vorher auch schon gedacht habe. meine eigentliche frage blieb leider unbeantwortet :(


Mo 27-04-2009 12:54:52
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