Példamegoldás: InfElm 2x45percben
Ez az oldal a korábbi SCH wikiről lett áthozva.
Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!
Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.
thx to Soos Balazs (B.Joe)
Györfi László- Győri Sándor - Vajda István: Információ- és kódelmélet,
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={x1, ..., xn} 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?
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).
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.
mo.:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p_{5} = 0.05 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{1}:= 0 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{i}:= \sum\limits_{n=1}^{i-1} p_{i}}
azaz
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{1} = 0 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{2} = 0,4 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{3} = 0,75 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{4} = 0,85 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{5} = 0,95 }
A bináris Shannon-Fano kódok:
.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
Ezek prefix kódok. Mindegyik annyi bitből áll, amennyi már megkülönbözteti a többitől.
Ezeket felírjuk 2-es számrendszerben.
Entrópia
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H = -\sum\limits_{n=1}^{5}(p_{i} \cdot \log(p_i))=...= 1.94}
Átlagos kódszóhossz
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle E|f(x)|= +\sum\limits_{n=1}^{5} p_{i} \cdot l_{i} = 2.45}
Bináris prefix kód li alapján
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle l_{i}=\lceil -\log(p_{i})\rceil=\{2,2,4,4,5\}}
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{1} = 0 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{2} = 1 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{3} = 8 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{4} = 9 }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle w_{5} = 20 }
/ \ /\ /\ / \ /\ \ \
Eredeti megoldás, ami szerintem rossz: Tehát a kódok: 00, 01, 1000, 1001, 11111.
Nekem jónak tűnő megoldás: 00, 01, 1000, 1001, 10100.
Aki biztos a dolgában, javítson!
-- Yaman - 2005.12.01.
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.
-- Đani - 2005.12.01.
Szerintem azért nem mindegy, mert az 1.2 lemma bizonyítása szerint kéri a kódot, akkor pedig szerintem w5-re 10100 lesz a kód.
-- Yaman - 2005.12.01.
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...
-- Đani - 2005.12.01.
10100 a jó kód (és nem írom ide, hogy szerintem), mert w5=20-nak a kettesszámrendszerbeli alakja ennyi (és nem 11111).
-- Tomee
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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}
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?
Entrópia
mo.:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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 }
Az entrópia igy 2.
/\ /\ elsore bejott / masodikra jott csak be ..
1.8 (Egyenletes eloszlás entropiája nagyobb)
Mutassa meg, hogy a (p1, ..., pi, ..., pj, ..., pn) eloszlás entrópiája nem lehet nagyobb, mint a (p1, ..., pi/2+pj/2, ..., pi/2+pj/2, ..., pn)
| p1 | ... | pi | ... | pj | ... | pn |
| p1 | ... | pi/2+pj/2 | ... | pi/2+pj/2 | ... | pn |
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle -\sum\limits_{i=1}^{n}p_{i} \cdot \log p_{i} <= -\sum\limits_{i=1}^{n} q_{i} \cdot \log q_{i}}
mo.:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(P): \{p_{1}, \dots, p_{i}, \dots, p_{j}, \dots, p_{n}\} }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(Q): \{p1, \dots, \frac{p_{i} + p_{j}}{2}, \dots, \frac{p_{i} + p_{j}}{2}, \dots, p_{n}\} }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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} }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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} }
Kell:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(Q)-H(P) >= 0}
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle -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}
... balra-jobbra teszegetve, (-1)gyel megszorozva-megkeverve :) kijön, hogy:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 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}}}
Jensen egyenlőtlenségből következik az állítás:
felhasználva, hogy:
a = pi + pj (a1 = pi, a2 = pj) és b = 2 (b1 = 1, b2 = 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 (p1, ..., pn) eloszláshoz készítünk optimális bináris prefix kódot, ahol p1 > p2 > ... > pn > 0. Bizonyítsa be, hogy
a) ha p1 > 2/5, akkor a hozzá tartozó kódszó 1 hosszúságú
b) ha p1 < 1/3, akkor a hozzá tartozó kódszó legalább 2 hosszú
mo.: ???
annyit tudok, hogy {1 2 3 3} vagy {2 2 2 2} Hosszúságok mindegyik egy
optimális Huffmankodot ad.
É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.
Nem tudom, hogy érthető volt-e, remélem igen.
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.
Na, ez még zavarosabb volt. :)
-- Đani - 2005.11.27.
a) p1 > p2 > ... > pm > 0 (*) Teljes indukcióval bizonyítunk. n = 1, 2, 3-ra arcpirítóan triviális. Légyen igaz n-ig, hogy ha p1 > 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:
mo.:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X) = -p \cdot \log p - (1-p) \cdot \log(1-p) = h(p)}
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X|Z) = H(X) = h(p)}
, mert X, és Z független
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X|Y,Z) = H(f(Y,Z)|Y,Z) = 0}
, mert X függ Y, és Z-től
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X|Y) = }
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
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X|Y) = H(X) = h(p)}
1.17 (Futamhossz kódolás)
Legyenek X1, ..., Xn bináris valószínűségi változók. Jelölje R = (R1, R2, ...) 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(X1, ..., Xn), H(R) és H(R, Xn)?
mo.:
X=(x1,...xn)
R=(R1,R2,...)
X=00101110 ==> R={3 2 2 3 1}
R=f(x1,...xn)
H(x)>=H(f(x)) Megj.: ha f() invertálható akkor pont =
H(x1,...xn)>=H(R), mert nem tudjuk mivel kezdődik a kód 0/1 ?
H(x1,...xn)>=H(R,Xn)
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:
P(X2=0|X1=0} = p,
P(X2=1|X1=0} = 1-p,
P(X2=0|X1=1} = (1-p)/2,
P(X2=1|X1=1} = (1+p)/2
Mennyi P(X1=0)=? Mennyi a forrás entropiája?
mo.:
[p0 p1]
| [p0 p1] | p | 1-p |
| (1-p)/2 | (1+p)/2 |
p0+p1 =1
p0= p0*p+(1-p)/2*p1
p1= (1-p)*p0+(1+p)p1
____________________
p0(1-p) = (1-p)/2*p1
p0= p1/2
p0+ 2p0 = 1
p0=1/3
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \sum\limits_{x1} \sum\limits_{x2} p(x1)* p(x2|x1)*log (p((x2|x1))) = }
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle -\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 = }
Defínició szerint:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \frac{1}{3} \cdot h(p) + \frac{2}{3} \cdot h(\frac{1-p}{2}) }
Általános stacionárius eset
| Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 1-\alpha} | Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \alpha} |
| Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \beta} | Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 1-\beta} |
mátrix esetén a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p0= \beta /(\alpha+\beta) } és Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle p1 =\alpha /(\alpha+\beta) }
stacionárius eloszlás esetén.
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(XX) =p0* h(\alpha) + p1 * h(\beta))} .
1.20 (Vissza a jövőbe)
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X_0 | X_{-1}, X_{-2}, ..., X_{-n}) = H(X_0 | X_1,X_2, ..., X_n)}
segédtudomány:
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X, Y) = H(X) +H(Y|X) => H(Y|X)= H(X, Y)- H(X)}
Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X_0, X_{-1}, X_{-2}, ..., X_{-n}) - H(X_{-1}, X_{-2}, ..., X_{-n})} = Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X_0, X_1,X_2, ..., X_n) - H(X_1,X_2, ..., X_n)}
Mivel Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle H(X_0, X_1,X_2, ..., X_n)}
stacionárius valószínűségi változó sorozat (folyamat, információforrás) ezért a együttes eloszlása egyezik 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.
(i+n eltolással, ahol i=0... -n)
Tehát a vizsgált összegekben a tagok külön külön egyenlőek:
és (i+n+1 es eltolás)
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
mátrixszal adottak (a mátrix i-edik sorának j-edik oszlopában a P{Z2=j|Z1=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!
mo.:
/\ marad /\ 1-t 2-t jobbra balra
pl: 0 0 2 3 5 5 6 ==> 0111011010
E|f(x)=summa pi*li=.5*1+ 2*.25*2 = 1.5
pi=1/256
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
Tehát a kódunk tökéletes volt.
1.22
Az alábbi ábra egy ZZ=Z1, Z2, ... 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.
Legyen továbbá Y1,Y2, ... független azonos eloszlásu bináris valószínűségi változok sorozata, ahol P(Yi=0) =1/3. Definiáljuk az XX=X1, X2, ... forrást az Xi=2Zi+Yi egyenlettel. Mennyi XX forrás entrópiája feltéve, ha Z1,Z2 független Y1, Y2, ...-tól?
mo.:
![{\displaystyle lim[n->inf]1/n*H(Z_{1}...Z_{n}|X_{1}...X_{n})=lim1/n*H(f(x_{1}..x_{n})|X_{1}..X_{n}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aed992770c510d78884a06f5c7d76ea8fb5d0227)
1.23. LZ78
Adjunk meg a 36 darab nullából álló sztring LZ78-kódját.
0 00 000 0000 00000 ...
1+2+3+4+5...+ ? =36
Sorozat összege: n*(n+1)/2 =36 => n=8. Tehát nyolc darab index kerül bele a szótárba
| 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 |
