Példamegoldás: InfElm 2x45percben forrásának megtekintése

{{GlobalTemplate|Infoalap|InfelmZhFeladatok}}


'''thx to Soos Balazs (B.Joe)'''

__TOC__

Györfi László- Győri Sándor - Vajda István: '''Információ- és kódelmélet''',<br/>
Második bővített kiadás (TypoTex Kiadó, 2002): oldalszámok: '''54-59'''

==1.4 (Rossz kódok)==

A következő bináris kódok melyike nem lehet semmilyen eloszlás Huffmann-kódja? Mindegyik válaszát indokolja meg, azaz ha nincs ilyen eloszlás, akkor magyarázza meg miért, ha pedig van, akkor adjon meg egy olyat!

===a) 0, 10, 111, 101===
mo.: nem lehet, mert 10,101 nem prefix

===b) 00, 010, 011, 10, 110===
mo.: nem lehet, mert ha ábrázoljuk a fát, akkor az 110 kód feleslegesen hosszú, hisz 11 is elég lenne helyette -> ez a kód nem lehet optimális, nem huffman-kód.

===c) 1, 000, 001, 010, 011===
mo.: OK Pl.: 1/2, 1/8, 1/8, 1/8, 1/8

==1.6==

Legyen az X={x<sub>1</sub>, ..., x<sub>n</sub>} forrásábécé ötelemű, a következő valószínűségekkel: 0.4; 0.35; 0.1; 0.1; 0.05 Mennyi az eloszlás entrópiaja?<br/>
Konstruálja meg a bináris Shannon-Fano-kódot erre az eloszlásra, illetve konstruáljon bináris prefix kódot az li = felkerekít[-logp(xi)] kódszóhosszakkal az 1.2. lemma bizonyítása szerint (a kód bináris fával való reprezentálásával). <br/>
Mennyi az átlagos kódszóhossz?

===Bináris Shannon-Fano kódok===
Először csökkenő sorba rendezzük a valószínüségeket. <br/>
mo.: <br/>
<math> p_{1} = 0.4 </math> <br/>
<math> p_{2} = 0.35 </math> <br/>
<math> p_{3} = 0.1 </math> <br/>
<math> p_{4} = 0.1 </math> <br/>
<math> p_{5} = 0.05 </math> <br/>

<math> w_{1}:=  0 </math> <br/>

<math>w_{i}:=  \sum\limits_{n=1}^{i-1} p_{i}</math> <br/>
<br/>
azaz <br/>
<br/>
<math> w_{1} = 0 </math> <br/>
<math> w_{2} = 0,4 </math> <br/>
<math> w_{3} = 0,75 </math> <br/>
<math> w_{4} = 0,85 </math> <br/>
<math> w_{5} = 0,95 </math> <br/>

A bináris Shannon-Fano kódok:<br/>
<pre>
		  .5	.25  .125	.0625
w1=0	 0  +  0
w2=0.4  0  +  1
w3=0.75 1  +  1  +  0  +  0
w4=0.85 1  +  1  +  0  +  1
w5=0.95 1  +  1  +  1
</pre>
Ezek prefix kódok. Mindegyik annyi bitből áll, amennyi már megkülönbözteti a többitől.<br/>
Ezeket felírjuk 2-es számrendszerben.<br/>

===Entrópia===
<math>H = -\sum\limits_{n=1}^{5}(p_{i} \cdot \log(p_i))=...= 1.94</math><br/>

===Átlagos kódszóhossz ===
<math>E|f(x)|= +\sum\limits_{n=1}^{5} p_{i} \cdot l_{i} = 2.45</math><br/>

===Bináris prefix kód l<sub>i</sub> alapján===
<math>l_{i}=\lceil -\log(p_{i})\rceil=\{2,2,4,4,5\}</math><br/>

<math> w_{1} = 0 </math> <br/>
<math> w_{2} = 1 </math> <br/>
<math> w_{3} = 8 </math> <br/>
<math> w_{4} = 9 </math> <br/>
<math> w_{5} = 20 </math> <br/>

<pre>  
  / \ 
 /\ /\
	/  \	  
  /\	\
		  \
</pre>

Eredeti megoldás, ami szerintem rossz: Tehát a kódok: 00, 01, 1000, 1001, 11111. <br/>
Nekem jónak tűnő megoldás: 00, 01, 1000, 1001, 10100. <br/> Aki biztos a dolgában, javítson!<br/>
-- [[KornaiTamas|Yaman]] - 2005.12.01.<br/>
Rohadtul tök mindegy. :) A lényeg, hogy 5 hosszú legyen az utolsó kód. Ennyi. Ha fán tudod ábrázolni, akkor prefix is.<br/>
-- [[SzentimreyHarrachDanielMatyas|Đani]] - 2005.12.01.<br/>
Szerintem azért nem mindegy, mert az 1.2 lemma bizonyítása szerint kéri a kódot, akkor pedig szerintem w<sub>5</sub>-re 10100 lesz a kód.<br/>
-- [[KornaiTamas|Yaman]] - 2005.12.01.<br/>
Hehe, ha te mondod. Átnéztem azt a bizonyítást, mondjuk nem olyan nagyon-nagyon, de számomra nem derült ki, hogy miért az 10100 lesz a nyerő megoldás. Persze ez csak engem minősít...<br/>
-- [[SzentimreyHarrachDanielMatyas|Đani]] - 2005.12.01.<br/>
10100 a jó kód (és nem írom ide, hogy szerintem), mert w<sub>5</sub>=20-nak a kettesszámrendszerbeli alakja ennyi (és nem 11111).<br/>
-- Tomee<br/>

<math>E(f(x))= 2 \cdot 0,4 + 2 \cdot 0,35 + 2\cdot 4 \cdot 0,1 + 5 \cdot 0,05 = 0,8 + 0,7 + 0,8 + 0,25 = 2,55</math>

==1.7==

Egy pénzérmét addig dobunk fel, amíg írást nem kapunk. 
Jelölje az X valószínűségi változó a dobások számát. Mennyi az X 
entrópiája?<br/>

===Entrópia===
mo.:<br/>
<math>H(x)=-\sum\limits_{n=1}^{\infty} p_{i} \cdot \log p_{i} =
- \sum\limits_{n=1}^{\infty} (0,5^{i} \cdot \log(0,5)^{i})=
+ \sum\limits_{n=1}^{\infty} i \cdot (0,5)^{i} =
\frac{1}{1-0.5} = 
2
</math> <br/>
Az entrópia igy 2.<br/>
<pre>
  /\
 /\ elsore bejott
/  masodikra jott csak be
..
</pre>

==1.8 (Egyenletes eloszlás entropiája nagyobb)==

Mutassa meg, hogy a (p<sub>1</sub>, ..., p<sub>i</sub>, ..., p<sub>j</sub>, ..., p<sub>n</sub>) eloszlás entrópiája nem lehet nagyobb, mint a (p<sub>1</sub>, ..., p<sub>i</sub>/2+p<sub>j</sub>/2, ..., p<sub>i</sub>/2+p<sub>j</sub>/2, ..., p<sub>n</sub>)<br/>

{| border="1"
|p1||...||pi||...||pj||...||pn
|-
|p1||...||pi/2+pj/2||...||pi/2+pj/2||...||pn
|}

<math>-\sum\limits_{i=1}^{n}p_{i} \cdot \log p_{i} <= -\sum\limits_{i=1}^{n} q_{i} \cdot \log q_{i}</math><br/>

mo.:<br/>
<math> H(P):  \{p_{1}, \dots, p_{i}, \dots, p_{j}, \dots, p_{n}\} </math> <br/>
<math> H(Q):  \{p1, \dots, \frac{p_{i} + p_{j}}{2}, \dots, \frac{p_{i} + p_{j}}{2}, \dots, p_{n}\} </math> <br/>

<math> H(P) = -p_{1} \cdot \log p_{1} - \dots - p_{i} \cdot \log p_{i} - \dots - p_{j} \cdot \log p_{j} - \cdot - p_{n} \cdot \log p_{n} </math> <br/>
<math> H(Q) = -p_{1} \cdot \log p_{1} - \dots - \frac{p_{i} + p_{j}}{2} \log\frac{p_{i} + p_{j}}{2} - \dots - \frac{p_{i} + p_{j}}{2} \log\frac{p_{i} + p_{j}}{2} - \dots - p_{n} \cdot \log p_{n} </math> <br/>
<br/>

Kell:
<math>H(Q)-H(P) >= 0</math><br/><br/>

<math>-2 \cdot \frac{p_{i} + p_{j}}{2} \cdot \log\frac{p_{i} + p_{j}}{2} + p_{i} \cdot \log p_{i} + p_{j} \cdot \log p_{j} >= 0</math> <br/>
... balra-jobbra teszegetve, (-1)gyel megszorozva-megkeverve :) kijön, hogy:<br/>
<math> p_{i} \cdot \log \frac{1}{p_{i}} + p_{j} \cdot \log \frac{1}{p_{j}} <= (p_{i} + p_{j}) \cdot \log\frac{2}{p_{i} + p_{j}}</math> <br/><br/>

Jensen egyenlőtlenségből következik az állítás: <br/>
felhasználva, hogy: <br/>
a = p<sub>i</sub> + p<sub>j</sub> (a<sub>1</sub> = p<sub>i</sub>, a<sub>2</sub> = p</sub>j</sub>) és b = 2 (b<sub>1</sub> = 1, b<sub>2</sub> = 1).

==1.10 (Információs divergencia)==

Definicó alkalmazásával egyértelmű a megoldás...

==1.13 (Huffman-kód kószóhosszai) ==

Tegyük fel, hogy a (p<sub>1</sub>, ..., p<sub>n</sub>) eloszláshoz készítünk optimális bináris prefix kódot, ahol p<sub>1</sub> > p<sub>2</sub> > ... > p<sub>n</sub> > 0. Bizonyítsa be, hogy<br/>
a) ha p<sub>1</sub> > 2/5, akkor a hozzá tartozó kódszó 1 hosszúságú<br/>
b) ha p<sub>1</sub> < 1/3, akkor a hozzá tartozó kódszó legalább 2 hosszú<br/>

mo.: ???<br/>
annyit tudok, hogy {1 2 3 3} vagy {2 2 2 2} Hosszúságok mindegyik egy
optimális Huffmankodot ad.<br/>

Én itt arra jöttem rá, hogyha p1 = 0.4, akkor pont meg lehet csinálni, hogy az utolsó összeadásnál ezt adjuk hozzá valami máshoz, így a hozzá tartozó kódszó kettő hosszú lesz. Viszont ha ennél nagyobb, mondjuk 0.41, akkor ahhoz, hogy őt adjuk hozzá valamihez, az kell, hogy az előző összadás során kapott eredmény nála nagyobb legyen. Példának okáért 0.42. Ekkor a maradék valószínűség 0.17. Ezt adnánk hozzá a 0.41-hez. Azonban ez a helyzet nem állhat elő, mert a 0.42-t csak úgy kaphattuk meg, ha az egyik valószínűség legalább 0.21 volt. Nem kaphatjuk meg úgy a 0.42-t, hogy mindkét valószínűség kisebb, mint 0.17, ezért ezt vettük volna az összeadás egyik tagjának.<br/>
Nem tudom, hogy érthető volt-e, remélem igen.<br/>
A b) részhez ugyanilyen megfontolás szükséges. Ha p1 = 1/3-ad, akkor az utolsó összeadásnál előfordulhat olyan helyzet, hogy 3 1/3-ad valószínűségű elem közül kell választanunk. Tehát ekkor még megoldható, hogy p1-hez 1 hosszú kódszó tartozzon. Ám ha p1 < 1/3, mondjuk 0.3, akkor az utolsó előtti összeadásban szükségszerűen kapunk egy nála nagyobb eredményt, viszont a harmadik tag szükségszerűen kevesebb lesz nála. Így muszáj őket összeadnunk.<br/>
Na, ez még zavarosabb volt. :)<br/> -- [[SzentimreyHarrachDanielMatyas|Đani]] - 2005.11.27.

a)
p<sub>1</sub> > p<sub>2</sub> > ... > p<sub>m</sub> > 0 (*)
Teljes indukcióval bizonyítunk. n = 1, 2, 3-ra arcpirítóan triviális.
Légyen igaz n-ig, hogy ha p<sub>1</sub> > 2/5, akkor a hozzá tartozó kódszó 1 hosszúságú
n+1-re p1,p2,....,p(n), p(n+1)
A két legkisebb p(n) és p(n+1) (ld. *). Innen két eset van.

  1. Az új, p1,p2,....,p(n-2),p(n)+p(n+1)-ben továbbra is p1 a legnagyobb.Ekkor visszavezettük n-re, azaz az indukciós feltevés miatt  igaz, hogy ha p1>2/5, akkor a hozzá tartozó kódszó 1 hosszú.

  2. Nem p1 a legnagyobb. Ekkor láthatóan p(n)+p(n+1) lenne a legnagyobb. De p(n)+p(n+1)<2*(1-2/5)/n<2*(3/5)/3=2/5. Tehát 2. eset nem is lehet.
Ezzel az állítást béláttuk.

b)
n=1,2,3 nem lehet, mert p1 szigorúan a legnagyobb.
n=4-re igaz, p1<1/3 és p1>p2>p3>p4 -> p3+p3+p4>2/3 -> p1+p2<2/3 -> p3+p4>1/3 ezek plusz 1.5 tétel -> optimális bináris prefix kód {2,2,2,2} hosszú.

Innen ismét indukció, stb...

-- [[GelencserGabor]] - 2005.12.01.

==1.14 (Titkosítás)==

Legyenek X és Z bináris független valószínűségi változók úgy, hogy 
P{X=1}=p és P{Z=1}=0.5  Legyen Y=X mod2 Z
X felfogható, mint titkosítandó üzenet, Z a titkos kulcs és Y a rejtjelezett
üzenet. Számítsa ki a következő mennyiségeket és magyarázza meg jelentésüket
a titkosítás szempontjából:<br/>
mo.:<br/>
<math> H(X) = -p \cdot \log p - (1-p) \cdot \log(1-p) = h(p)</math><br/>
<math> H(X|Z) = H(X) = h(p)</math>, mert X, és Z független<br/>
<math> H(X|Y,Z) = H(f(Y,Z)|Y,Z) = 0</math>, mert X függ Y, és Z-től<br/>
<math> H(X|Y) = </math> <br/>
<pre>
			X  Z  Y
(1-p)/2  0  0  0
  p/2	 1  0  1	==>	 p(Y=0)=.5	p(Y=1)=.5	fuggetlen mindentol
(1-p)/2  0  1  1
  p/2	 1  1  0
</pre>
<math>H(X|Y) = H(X) = h(p)</math><br/>

==1.17 (Futamhossz kódolás)==

Legyenek X<sub>1</sub>, ..., X<sub>n</sub> bináris valószínűségi változók. Jelölje R = (R<sub>1</sub>, R<sub>2</sub>, ...) az egyes szimbólumok előfordulásainak futamhosszait. Tehát pl. az 1110010001111 sorozathoz R=(3,2,1,3,4) tartozik. Hogyan viszonyul egymáshoz H(X<sub>1</sub>, ..., X<sub>n</sub>), H(R) és H(R, X<sub>n</sub>)?<br/>

mo.:<br/>
X=(x1,...xn)<br/>
R=(R1,R2,...)<br/>
X=00101110  ==> R={3 2 2 3 1}<br/>

R=f(x1,...xn)<br/>
H(x)>=H(f(x))	Megj.: ha f() invertálható akkor pont =<br/>
H(x1,...xn)>=H(R), mert nem tudjuk mivel kezdődik a kód 0/1 ?<br/>
H(x1,...xn)>=H(R,Xn)<br/>

==1.18 (Markov-lánc entrópiája)==

Legyen XX (<-duppla_vastagX) =X1,X2,... egy bináris, stacionárius
Markov-lánc, amelynek állapotátmenetei a következők:<br/>
P(X2=0|X1=0} = p,<br/>
P(X2=1|X1=0} = 1-p,<br/>
P(X2=0|X1=1} = (1-p)/2,<br/>
P(X2=1|X1=1} = (1+p)/2<br/>
Mennyi P(X1=0)=? Mennyi a forrás entropiája?<br/>

mo.:<br/>
	  {{InLineImageLink|Infoalap|InfelmZhFeladatok|1_18.JPG}}<br/>
[p0 p1] 

{| border="1"
|[p0 p1]||p||1-p
|-
|||(1-p)/2||(1+p)/2
|}

p0+p1 =1<br/>
p0= p0*p+(1-p)/2*p1<br/>
p1= (1-p)*p0+(1+p)p1<br/>
____________________<br/><br/>
p0(1-p) = (1-p)/2*p1<br/>
p0= p1/2<br/>
p0+ 2p0 = 1<br/>
p0=1/3<br/><br/>


<math> \sum\limits_{x1} \sum\limits_{x2}	p(x1)* p(x2|x1)*log (p((x2|x1))) = </math> <br/>
<math> -\lgroup 1/3[p*log(p)+(1-p*log(1-p))]+2/3*[(1-p)/2*log((1-p)/2)+(1+p)/2*log((1+p)/2)]\rgroup = </math> <br/>
<br/>
Defínició szerint:<br/>
<math>\frac{1}{3} \cdot h(p) + \frac{2}{3} \cdot h(\frac{1-p}{2}) </math>

===Általános stacionárius eset===

{| border="1"
|<math>1-\alpha</math>||<math>\alpha</math>
|-
|<math>\beta</math>||<math>1-\beta</math>
|}

mátrix esetén a <math> p0= \beta /(\alpha+\beta) </math> és <math> p1 =\alpha /(\alpha+\beta) </math>

stacionárius eloszlás esetén.

<math>H(XX) =p0* h(\alpha) + p1 * h(\beta))</math> .


==1.20 (Vissza a jövőbe)==

<math>H(X_0 | X_{-1}, X_{-2}, ..., X_{-n}) = H(X_0 | X_1,X_2, ..., X_n)</math> 

segédtudomány:<br/>
<math>H(X, Y) = H(X) +H(Y|X) => H(Y|X)= H(X, Y)- H(X)</math> 

<math>H(X_0, X_{-1}, X_{-2}, ..., X_{-n}) - H(X_{-1}, X_{-2}, ..., X_{-n})</math>  =
<math>H(X_0, X_1,X_2, ..., X_n) - H(X_1,X_2, ..., X_n)</math> 

Mivel <math>H(X_0, X_1,X_2, ..., X_n)</math>  '''stacionárius''' valószínűségi változó sorozat (folyamat, információforrás) ezért a  <math>(X_{i+0}, X_{i+1}, X_{i+2}, ... , X_{i+n})</math> együttes eloszlása egyezik <math>(X_{j+0}, X_{j+1}, X_{j+2}, ... , X_{j+n})</math> együttes eloszlásával, minden i-re és j-re, vagyis elmozoghatunk a sorozat mentén. Ha az eloszlás egyezik, az entrópia is.  thx to Main.BergmannGabor.
<br/><br/>
 (i+n eltolással, ahol i=0... -n)
<math>P(X_0 ,X_{-1}, X_{-2}, ..., X_{-n}) = P(X_0 ,X_1,X_2, ..., X_n)</math> 

Tehát a vizsgált összegekben a tagok külön külön egyenlőek:

<math>H(X_0 ,X_{-1}, X_{-2}, ..., X_{-n}) =  H(X_0 ,X_1,X_2, ..., X_n)</math> 

és (i+n+1 es eltolás)
<math>H(X_{-1}, X_{-2}, ..., X_{-n}) =  H(X_1,X_2, ..., X_n)</math> 


==1.21==

Legyenek a ZZ stacionárius Markov-lánc állapotai a 0, 1, ..., 255 számok, és tegyük fel, hogy az állapotátmenet valószínűségek az alábbi 256x256-os<br/>
	 {{InLineImageLink|Infoalap|InfelmZhFeladatok|256matrix.JPG}}<br/>
mátrixszal adottak (a mátrix i-edik sorának j-edik oszlopában a P{Z<sub>2</sub>=j|Z<sub>1</sub>=i} valószínűség található). Mi a Markov-lánc stacionárius eloszlása? Mennyi a forrás entropiája? Készítsen jó, egyertelműen dekódolható, változó szóhosszúságú blokk-kódot!<br/>
mo.:<br/>
<pre>
		 /\
  marad /\
	  1-t	2-t jobbra
	  balra
</pre>

pl: 0 0 2 3 5 5 6 ==> 0111011010<br/>
E|f(x)=summa pi*li=.5*1+ 2*.25*2 = 1.5<br/>
pi=1/256<br/>
H(ZZ)=H(Z2,Z1)=-summa[z1=...]P(Z1=z1)*summa[z2=...](Z2=z2|Z1=z1)logP(Z2=z2Z1=z1)=
=1/256)* (-256*.5*log.5 -512*.25*log.5) = .5log2+2/4*log4 = 1.5<br/>

Tehát a kódunk tökéletes volt.<br/>

==1.22==

Az alábbi ábra egy ZZ=Z<sub>1</sub>, Z<sub>2</sub>, ... Markov-lánc működését írja le. Tegyük fel, hogy a láncot a stacionárius eloszlásból indítjuk.<br/>
{{InLineImageLink|Infoalap|InfelmZhFeladatok|1_18.JPG}}<br/>

<math> P(X_1=0 | X_0=0)=p </math> <br/>
<math> P(X_1=1 | X_0=0)=1-p </math> <br/>
<math> P(X_1=0 | X_0=1)=\frac{1-p}{2} </math> <br/>
<math> P(X_1=1 | X_0=1)=\frac{1+p}{2} </math> <br/>

Legyen továbbá Y<sub>1</sub>,Y<sub>2</sub>, ... független azonos eloszlásu bináris valószínűségi változok sorozata, ahol P(Y<sub>i</sub>=0) =1/3. Definiáljuk az XX=X<sub>1</sub>, X<sub>2</sub>, ... forrást az X<sub>i</sub>=2Z<sub>i</sub>+Y<sub>i</sub> egyenlettel. Mennyi XX forrás entrópiája feltéve, ha Z<sub>1</sub>,Z<sub>2</sub> független Y<sub>1</sub>, Y<sub>2</sub>, ...-tól?

mo.:
<math>H(XX)= H(Z_2|Z_1)+H(X_1|Z_1)</math><br/>
<math>H(Z_2|Z_1) =1/3h(p) +2/3h(1/2-p/2)</math>
<math>H(X_1|Z_1)= -(1/3*(1/3*log(1/3)+2/3*log(2/3))+2/3*(1/3*log(1/3)+2/3*log(2/3)))=H(Y_1)= h(1/3)</math>
<math>lim[n->inf] 1/n*H(Z_1...Z_n|X_1...X_n)=lim 1/n*H(f(x_1..x_n)|X_1..X_n))</math>

==1.23. LZ78==

Adjunk meg a 36 darab nullából álló sztring LZ78-kódját.

0 00 000 0000 00000 ...<br/>
1+2+3+4+5...+ ? =36 <br/>
Sorozat összege: n*(n+1)/2 =36 => n=8. Tehát nyolc darab index kerül bele a szótárba

{| border="1"
|Kódoló üzenete||Szótár||
|-
|index,f{next char}||index||érték
|-
|0,f{0}||1||0
|-
|1,f{0}||2||00
|-
|...||...||...
|-
|7,f{0}||8||00000000
|}


[[Category:Infoalap]]