PSI

Z OI wiki

(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(→Písemka z 1. 2. 2011)
(→Studijní materiály)
Řádka 25: Řádka 25:
<br />
<br />
 +
 +
 +
<math>\left(\, \sum_{k=1}^n a_k b_k \right)^2 \le
 +
\left(\, \sum_{k=1}^n a_k^2 \right) \left(\, \sum_{k=1}^n b_k^2 \right)</math>
== Zkoušky ==
== Zkoušky ==

Verze z 14. 12. 2011, 18:41

Obsah

1. semestr 2. semestr 3. semestr 4. semestr 5. semestr 6. semestr
Povinné předměty DMA ¤ LAG
PR1 ¤ RPH		 ALG ¤ BP1 ¤ LGR
MA2 ¤ PR2		 JAG ¤ PSI ¤ SPS APO ¤ BP2 ¤ FYZ OPT SZZ - LS 2012
Inf. a poč. vědy NUM ¤ OSS DS ¤ FLP ¤ ZUI RPZ
Počítačové syst. EAM ¤ EM DSP ¤ OSD PKS ¤PSR ¤NVS
Softwarové syst. OSS ¤ SI ASS ¤ DS ¤ TUR WA1
Volitelné předměty ACM ¤ EPD ¤ ET1 ¤ FI1 ¤ HI1 ¤ HSD ¤ HT1 ¤ IA+AZK ¤ MME ¤ MMP ¤ MPS ¤ PAP ¤ PPR ¤ PRS ¤ RET ¤ SOJ ¤ UFI
Grafický minor

PGR ¤ MVR ¤ KMA ¤ MGA ¤ GRT

Info o předmětu

  • Cvičící: M. Petrík, L. Nentvich, T. Kroupa


Pravidla předmětu

Stránky předmětu


Studijní materiály

Závěrečné konzultační cvičení s prof. Navarou - poznámky (20. 12. 2010 14:30, bez záruky)



LaTeX: \left(\, \sum_{k=1}^n a_k b_k \right)^2 \le \left(\, \sum_{k=1}^n a_k^2 \right) \left(\, \sum_{k=1}^n b_k^2 \right)

Zkoušky

Pisemka z 4.1. 2011 

1) V populaci je infikovana 1/4 jedincu, ale jen u 2/3 se nakazka projevuje (a u zadnych neinfikovanych).
   Jaka je pravdepodobnost, ze jedinec bez priznaku neni infikovany? 
  
   Řešení: 
     výsledek je 9/10

2) Gen se vyskytuje ve 4 variantach A, B, C, D. Model predpoklada, ze B se vyskytuje 3x casteji nez A a D 3x casteji nez C.
   Odhadnete jejich pravdepodobnost na zaklade zjistenych cetnosti v tabulce.

   LaTeX: \begin{tabular}{|r|r|r|r|r|}
   \hline 
   \bf varianta & \bf A & \bf B & \bf C & \bf D \\
   \hline
   \bf cetnost & 10 & 15 & 15 & 40 \\
   \hline
   \end{tabular}

     (nesmi se resit pomoci momentu (nenumericka data))
  
   Řešení: 
     Urci se, kolik by mely ty pravdepodobnosti teoreticky byt, tedy: LaTeX: P(A)=a, LaTeX: P(B)=3a, LaTeX: P(C)=c a LaTeX: P(D)=3c

     Jelikoz soucet pravdepodobnosti ma byt jedna, tak se muze spocitat treba c - vyjde to myslim LaTeX: c=\frac{(1-4a)}{4}
     a pak se sestavi ta verohodnost tj. LaTeX: L = a^{10} \cdot (3a)^{15} \cdot \left ( \frac{(1-4a)}{4} \right )^{15} \cdot  \left ( 3\cdot\frac{(1-4a)}{4} \right )^{40}

     to se zlogaritmuje jelikoz se s tim lip pocita:

     LaTeX: l = 10\cdot log(a) + 15\cdot log(3a) + 15\cdot log\left (\frac{(1-4a)}{4}\right ) + 40\cdot log\left (3\cdot\frac{(1-4a)}{4}\right )

     zderivujeme, položíme rovno nule (hleda se maximum) a vyjde hodnota parametru 'a' (myslim ze to vyjde 5),
     dosadi se do tech teoretickych pravdepodobnosti a to je vysledek.

       /* Mne vyslo A=0,078125 B=0,234375 C=0,171875 a D=0,515625   Jeste nekomu to vyslo takhle? (souhlas, Venca H)

       /* tak zaprvé myslim, že je špatná úvaha a zadruhé P(A)=P(D)=P(B/3), nikoly P(D)=3c ??? pokud nesouhlasite tak prosim vysvětlit..

       /* Asi te zmatla formulace ulohy. Máš to chápat jako: Model predpoklada, ze B se vyskytuje 3x casteji nez A a dale model predpoklada, 
             ze D se vyskytuje 3x casteji nez C. (Ondra J.)

3) Uvazujte Markovuv retezec se stavy LaTeX: \chi = \lbrace 0,1,2 \rbrace  a matici prechodu

   LaTeX: $$\left( \begin{array}{cc@{\ }r}
   0 & 1/4 & 3/4 \\
   1 & 0 & 0 \\
   0 & 1 & 0 \\
   \end{array} \right)$$

   Urcete odpovidajici markovsky zdroj informace nad abecedou LaTeX: \chi a stanovte jeho rychlost entropie.
  
   Řešení: 
     /* vyšlo mi 0,3788804571 */ 
       // Zvlastni, mne vyslo 0,295 a pocatecni rozdeleni p=(4/11;4/11;3/11) no a stredni podminena entropie (coz je ta rychlost entropie)
          se rovna pouze 4/11*H(1/4,3/4) pac ty ostatni radky jsou diracovo rozdeleni. Jeste nekomu to tak vyslo? (souhlas s 0,295, Venca H)

4) Bonus: Jak by mohl vypadat popis poctu obeti dopravnich nehod pomovci Markovova retezce a klasifikace jeho stavu?
  
   Řešení:

Pisemka z 13.1. 2011 

1) Máme tři modely rozdělení X,Y,Z dané tabulkou:
   
   LaTeX: \begin{tabular}{|r|r|r|r|r|}
   \hline 
   \bf & \bf 1 & \bf 2 & \bf 3 & \bf 4 \\
   \hline
   \bf X & 1/2 & 1/4 & 1/8 & 1/8 \\
   \hline
   \bf Y & 1/3 & 1/3 & 1/6 & 1/6 \\
   \hline
   \bf Z & 2/5 & 3/10 & 1/5 & 1/10 \\
   \hline
   \end{tabular}
   
   Určete, který z modelů je nejlepší podle realizace:
   
   LaTeX: \begin{tabular}{|r|r|r|r|r|}
   \hline 
   \bf & \bf 1 & \bf 2 & \bf 3 & \bf 4 \\
   \hline
   \bf cetnost & 43 & 30 & 15 & 12 \\
   \hline
   \end{tabular}
   
   Řešení: 
     Tohle jsem nemel, ale co jsem koukal jinam tak se spocitala cetnost podle pravdepodobnosti
     a pak se porovnavala(nejak) s cetnosti z realizace. Mam pocit ze Z vychazi nejlip (souhlas se Z)

     /* Co pouzit metodu (maximalni) verohodnosti? Nejvic bude sedet rozdeleni s nejvetsi verohodnosti. Nekomu takovyhle postup Navara uznal?
         --Jelinond 23. 1. 2011, 23:25 (UTC)
     // Při zkoušce jsem ji zkoušel, ale nemohl jsem se dopočítat (asi chyba v postupu). Možná by se dal použít 'selský rozum' typu:
       SUMA[ (četnost/pravděpodobnost) ]/4, která musí být co nejblíže součtu četností (100)
         --Hanx 25. 1. 2011, 20:33 (UTC)
     // no viděl bych to na LaTeX: $$X^2 $$ test dobré shody. --Michal Zajačík 30. 1. 2011, 16:53 (UTC)

2) Zda bude pršet zítra je dané pouze tím,zda prší dnes. Dána matice přechodu:
   
   LaTeX: $$\left( \begin{array}{cc@{\ }r}
   0.7 & 0.3 \\
   0.4 & 0.6 \\
   \end{array} \right)$$
  
   kde 0.7 je pravděpodobnost, že bude pršet zítra pokud pršelo dnes
     a 0.4 je pravděpodobnost, že bude pršet zítra pokud dnes nepršelo.
   
   Vypočítejte pravděpodobnost, že bude pršet za 4 dny pokud dnes pršelo
   
   Řešení: 
     nasobit matici (1,0) 4x matici pravdepodobnosti
     nebo rozkreslit jako strom (také uznáno :)) )
     výsledek: 0,5749

3) Bakterie 1 má pravděpodobnosti v DNA:
     P1(C)=P1(G)=0.355 P1(A)=P1(T)=0.145
   Bakterie 2: 
     P2(C)=P2(G)=P2(A)=P2(T)=0.25
   
   Rozhodněte, která bakterie je složitější (z hlediska informace na stejně dlouhém úseku DNA)
   
   Řešení: 
     Pres entropii, zase si nejsem vysledky jist, ale ta s mensi entropii je slozitejsi (nebo tak nejak to vysvetloval pri predavani vysledku)
     // Zde si dovolím nesouhlasit: složitější je ta s větší entropíí (ta druhá), neboť nám poskytne větší míru informace.

4) Bonus: X je náh.veličina, platí EX^2 < nekonečno. Dokažte, že pro každé a z R platí E(X - EX)^2 je menší nebo rovno E(X - a)^2

   Řešení: 
     Jednoduche upravy ze skript nakonec vyjde Neco^2 vetsi, rovno nez 0 coz plati

Pisemka z 20.1. 2011 

1) Házíme mincí na čáru; náhodná veličina X udává vzdálenost hozené mince od čáry. Její rozdělení pravděpodobnosti je dáno hustotou:
   f(x) = 1-(x/2) pokud x patří do <0;2>,
             0    pokud x>2.
   Náhodná veličina Y = 1/x udává výhru (zisk) z jednoho hodu. Jaké je rozdělení (střední hodnota, rozptyl) náhodné veličiny Y?
   
   Řešení: 
     Na tehle pisemce jsem sice nebyl, ale zkusim nastinit reseni(snad i spravny:D).
     Nejpve zintegrujeme hustotu, cimz ziskame distribucni funkci. K te nasledne vytvorime funkci inverzni, tedy funkci kvantilovou.
     Tu zobrazime funkci h(u) = 1/u. Integralem dopocitame stredni hodnotu.(radeji to nekdo overte)
     -> tento postup teoreticky funguje, ale je v něm mnoho prostoru na to udělat chyby, o čemž jsem se
     přesvědčil když mi střední hodnota začala vycházet jako arcus tangens .. proto bych spíš doporučil využít
     vztahu ze skript, kdy posléze lze nekonečna omezit na ten interval <0,2>:
     LaTeX: $$E(h(X))=\int_{-\infty}^{\infty}h(u)f_X(u) du$$ --Michal Zajačík 30. 1. 2011, 19:19 (UTC)
   

2) V cyklu délky 4 (viz obrázek) v každém rohu nezávisle vybereme postup po směru hod. ručiček s pravděpodobností 2/3,
   v opačném směru s pravděpodobností 1/3. Stanovte pravděpodobnosti stavů po 4 krocích, jestliže počáteční stav je 1.
   (obrázek byly 4 prázdný kolečka spojený čarama tak, že tvořily čtverec)
   
   Řešení: 
     matici (1,0,0,0) jsem 4x násobil maticí přechodu, vyšlo mi (41/81,0,40/81,0) (Pavel S.)

3) Morseova abeceda používá 3 znaky: "tečka", "čárka", "mezera". Předpokládejme, že pravděpodobnosti jejich výskytu ve
   zprávě jsou po řadě 0.4, 0.4, 0.2 a jsou nezávislé. Navrhněte binární Huffmanův kód a jeho střední délku pro:
   a) znaky "tečka", "čárka", "mezera",
   b) dvojice těchto znaků.
   Zhodnoťte výsledné délky.
   
   Řešení: 
     a) střední hodnota mi vyšla 1.6 (Pavel S.)
     b) střední hodnota mi vyšla 3.12 (Pavel S.)

4) Bonus: Předvolební průzkum předpověděl dvěma stranám 30%, resp. 5% hlasů. Co dovedete říct o srovnání absolutních
   nebo relativních chyb těchto odhadů?
   
   Řešení:

Písemka z 25. 1. 2011

--Michal Zajačík 26. 1. 2011, 11:05 (UTC) 

1) Profesor zapomíná v kavárně deštník s pravděpodobností 1/4 (za podmínky, že s ním dorazí). Po návštěvě tří kaváren zjistil,
   že nemá deštník. Určete pravděpodobnost, že profesor deštník zapomněl právě v i-té kavárně, kde i = 1,2,3.
   
   Řešení: 
     P(a1)=1/4 * 1 = 1/4 -> pravděpodobnost, že ho ztratil v první kavárně, podmíněná tím, že jej tam donesl,
     ale protože je to první kavárna, donesl ho tam s pravděpodobností 1.
     P(a2)=(1-1/4)*1/4 -> pravděpodobnost, že ho ztratí v druhé podmíněná tím, že ho neztratil v první.
     P(a3)=(1-1/4)*(1-1/4)*1/4 -> pravděpodobnost, že ho ztratil v třetí podmíněná tím, že ho neztratil v první ani v druhé.
     P(a)=P(a1)+P(a2)+P(a3) -> pravděpodobnost, že ho vůbec někde zapomněl, nás zajímají podmíněné pravděpodobnosti:
     LaTeX: $$P(a1|a)=P(a1\cap a)/P(a)=P(a1)/P(a)$$ -> pravděpodobnost, že ho nechal v první za podmínky, že ho vůbec zapomněl,
     za využití toho, že LaTeX: $$a1\subset a$$.
     LaTeX: $$P(a2|a)=P(a2\cap a)/P(a)=P(a2)/P(a)$$ -> pravděpodobnost, že ho nechal v druhé za podmínky, že ho vůbec zapomněl
     LaTeX: $$P(a3|a)=P(a3\cap a)/P(a)=P(a3)/P(a)$$ -> pravděpodobnost, že ho nechal v třetí za podmínky, že ho vůbec zapomněl
  

2) Každý den jezdíte do školy i zpět metrem. Váš příchod na stanici je vždy náhodný a doba čekání na příjezd
   vlaku se pohybuje v rozmezí 0 až 3 minuty. Jaká je pravděpodobnost, že Vaše celková doba čekání během 23 dnů bude kratší než 80 minut?
   Uveďte použité předpoklady a výsledek vyjádřete ve tvaru F(x) pro nějakou distribuční funkci F.
  
   Opravené Řešení: 
     Veličina X: čekání jedné jízdy, má rovnoměrné rozdělení na <0,3>. Veličina Y
     je součet 23*2 rovnoměrných rozdělení X, takže dle centrální limitní věty konverguje k normovanému normálnímu
     rozdělení. Odhadneme DY a EY (za pomocí vzorců pro rovnoměrné rozdělení veličiny X),
     dále pracujeme dle CLV a distribuční funkce normovaného normálního rozdělení:

     LaTeX: $$EY=(23*2)*EX=46*1,5=69$$
     LaTeX: DY=46*DX=46*1/12(3-0)^2=34,5$$
     LaTeX: $$\Phi((80-EY)/\sqrt{DY})=\Phi((80-69)/\sqrt{34.5})=\Phi(1.872)$$

  --------------------------------------------------------------------------------------------------------------------------------------------

   Chybné Řešení: 
     Každý den jezdíte tam i zpět, takže denně čekáte 0-6 minut. Předpokládejme, že veličina X (čekání jeden den),
     má rovnomerné spojité rozdělení na <0,6>. Veličina Y (čekání za 23 dnů) má tedy také rovnoměrné spojité rozdělení, ale na <0,138>.
     Dále se odhadne odchylka a střední hodnota veličiny Y (podle vzorečků k rovnoměrnému rozdělení).
     Protože veličina Y je součet 23 rovnoměrných rozdělení, pak podle centrální limitní věty konverguje k normálnímu rozdělení.
     Takže vezmete vzorec distribuční funkce obecného normálního rozdělení,
     do něj dáte hodnoty průměru a rozptylu a vypočítáte hodnotu v bodě 80.

    /* Neni tu nahodou chyba? Prece soucet 23 rovnomernych rozdeleni X neni rozvomerne rozdeleni, 
       ale Normalni = N(23m,23s^2). Takze zadne Y na <0,138> tam nevznikne. Nebo se mylim? (Dima)
       
       -> Je to rovnoměrné, představ si to jako rovnoměrné rozdělení zobrazené funkcí h(x)=23x. Dostal jsem za to bod.
          Dále postupuješ podle CLV, jak jsem psal. --Michal Zajačík 27. 1. 2011, 13:37 (UTC)
       
    /* Možná by stálo za úvahu se zamyslet nad tím, jestli pravděpodobnost čekání za 23 dní není menší
       u Y=0, než u Y=69. Určitě Y=69 mohu dostat více způsoby než Y=0 (nikdy nečekám). Je jasné, že
       čekání u jednoho příchodu je rovnoměrné rozdělení, ale u dvou tomu tak není. Tzn. předpoklad,
       že X má rovnoměrné rozdělení mi úplně nesedí. X a Y mají normální rozdělení. Jirka Blecha
       
       -> Nemyslím si, neboť veličina X (čekání jeden den) je součtem dvou veličin s rovnoměrným rozdělením.
          Veličina Y jakožto součet 23 rovnoměrných skutečně má normální rozdělení, ale ve smyslu konvergence
          dle centrální limitní věty. Na odhad střední hodnoty a rozptylu potřebuješ využít ono rovnoměrné.
          Opakuji, že tato část je nejspíše dobře, neb mi to opravující neškrtl, ale bodově ohodnotil.
           --Michal Zajačík 27. 1. 2011, 21:31 (UTC)

    /* Navara pise na svych strankach: "Součet (resp. výběrový průměr) z rovnoměrného rozdělení má rovnoměrné rozdělení." - 
       Doufám, že takové hlouposti jste v kursu nepotkali, a pokud ano, upozorněte mě. MN" 
       PROOF:http://cmp.felk.cvut.cz/~navara/psi/ -> aktuality (Dima)
       
       -> máte pravdu, moje chyba. Stačí si představit součet hustot dvou rovnoměrných rozdělení.
       Ten pak není rovnoměrný ani náhodou. Opravil jsem řešení, tak, jak by to mělo vypadat. --Michal Zajačík 28. 1. 2011, 11:28 (UTC)

    /*Díky, tady na té stránce je toho víc o součtu(konvoluci) náhodných veličin.
      http://www.kmt.zcu.cz/person/Kohout/info_soubory/zimnisemestr/SS/pravd5.pdf Pro dumavé hlavy. Pro dvě náhodné veličiny dává
      součet 2 náhodných veličin s rovnoměrným rozdělením nějaké Simpsonovo rozdělení - trojúhelník. Pro více to jde k normálnímu.
      Jirka Blecha

3) Určete rychlost entropie markovského zdroje informace popsaného uvedeným diagramem, kde entropii uvažujte v podobě
   LaTeX: $$H_e(p)= -\sum_{i=1}^n p_iln(p_i)$$
   Nalezněte, jaká hodnota parametru LaTeX: \alpha maximalizuje rychlost entropie.
   Dále byl diagram, ze kterého se vytvořila matice přechodu
          LaTeX: $$\left( \begin{array}{ccc@{\ }r}
          0 & 1 & 0 \\
          \alpha & 0 & 1-\alpha \\
          1 & 0 & 0 \\
         \end{array} \right)$$
   
   Řešení: 
     Nalezl se stabilní stav, kde hodnoty ve vektoru byly závislé na LaTeX: $$\alpha$$. Z toho se spočítala rychlost entropie,
     díky prvnímu a poslednímu řádku (při počítání entropie vyjdou nuly - diracovo rozdělení) to nějak hezky vyšlo, dostali jste 
     funkci rychlosti zdroje na parametru LaTeX: $$\alpha$$. Zderivovat podle LaTeX: $$\alpha$$, položit rovno 0, hledat maximum.

4) (Bonus) Dokažte následující tvrzení: jsou-li A1,...,An nezávislé jevy, pak
                 LaTeX: $$P(\bigcup_{i=1}^n A_i) = 1 - \prod_{i=1}^n (1 - P(A_i)).$$           
  
   Řešení: 
     Jevy nezávislé, tudíž LaTeX: $$P(\bigcap_{i=1}^n A_i) = \prod_{i=1}^n P(A_i).$$
     Dále: LaTeX: $$P(\bigcup_{i=1}^n A_i) = \overline{P(\bigcap_{i=1}^n \overline{A_i})}=1 - P(\bigcap_{i=1}^n \overline{A_i})=1 - \prod_{i=1}^n P(\overline{A_i})=1 - \prod_{i=1}^n (1 - P(A_i)).$$ Q.E.D.

Písemka z 1. 2. 2011 

1) Finanční korporace se skládá z 50 menších firem. Pravděpodobnost, že firma zkrachuje, se odhaduje na 0.1. Jaká je
   pravděpodobnost, že zkrachují minimálně tři firmy této korporace? Uveďte použité předpoklady. Výsledek stačí vyjádřit 
   ve tvaru LaTeX: F(x), kde LaTeX: F je distribuční funkce.
   
   Řešení: 
       např. LaTeX: Bi(50, 0.1) -> výpočet EX, DX ze vzorečku -> normování -> konverguje k normálnímu rozdělení (centrální limitní věta)
   
   Moje řešení: Veličina F ... firma zkrachuje. Veličina K ... zkrachují alespoň 3 firmy korporace.
   LaTeX: $$P(F)=0.1$$ LaTeX: $$P(\overline{F})=0.9$$
   Že zkrachují minimálně 3 firmy lze přeložit jako že nezkrachuje žádná, jedna, nebo dvě firmy.
   Vyjdeme z binomického rozdělení:
   P(K) = 1 - P(zkrachuje 1) - P(zkrachují 2) - P(nezkrachuje žádná)
   LaTeX: $$P(K) = 1 - 50*P(F)*P(\overline{F})^{49} - \left( \begin{array}{c@{\ }r}
   50 \\
   2 \\
   \end{array} \right)*P(F)^2*P(\overline{F})^{48} - P(\overline{F})^{50}\doteq0.8886$$
   A to vše za předpokladu, že firmy budou krachovat nezávisle na sobě. --Michal Zajačík 1. 2. 2011, 14:23 (UTC)

2) Uvažujme posloupnost nezávislých hodů kostkou. Nechť LaTeX: X_n značí maximální počet ok dosažených do LaTeX: n-tého
   hodu včetně. Stanovte matici přechodu pro takto zadaný Markovův řetězec a rozhodněte, zda v něm existuje absorpční stav.
   
   Řešení: 
     Počet ok = počet teček co hodíme, malinko matoucí. Jinak:
     P(1) = P(2) = P(3) = P(4) = P(5) = P(6) = 1/6. První řádek je rovnoměrné diskrétní rozdělení, zkrátka co padne.
     Druhý řádek: když jsme předtím hodili dvojku, pravděpodobnost přechodu do 1 je nula, protože 1<2. Pravděpodobnost,
     že zůstaneme ve dvojce je 1 - že v ní nezůstaneme, tedy že hodíme číslo větší než 2, čili 1 - 4/6. Takto se udělal každý řádek.
     Sestavíme tedy matici:
     LaTeX: $$\left( \begin{array}{cccccc@{\ }r}
          1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6  \\
          0 & 2/6 & 1/6 & 1/6 & 1/6 & 1/6  \\
          0 & 0 & 3/6 & 1/6 & 1/6 & 1/6  \\
          0 & 0 & 0 & 4/6 & 1/6 & 1/6 \\
          0 & 0 & 0 & 0 & 5/6 & 1/6 \\
          0 & 0 & 0 & 0 & 0 & 1 \\
         \end{array} \right)$$
     Absorpční stav v tomto řetězci je, je jím stav 6: když padne šestka, je jasné, že víc už padnout nemůže (na šestistěnné kostce),
     takže naše maximum se nemění a zůstáváme v daném stavu s pravděpodobností 1. --Michal Zajačík 1. 2. 2011, 14:23 (UTC)

3) Kompresní program Zabalím tě! zakóduje jednotlivé znaky řetězce
   
   bcccddadda     (1)
   
   pomocí binárního kódu jako bitový řetězec délky 25. Posuďte efektivitu algoritmu použitého v tomto kompresním programu.
   Reklama na jiný program Stlačím tě! tvrdí, že její program využívající binární kódování jednotlivých znaků umí
   zakódovat řetězec (1) pomocí 17 bitů. Lze tomu věřit?
   
   Řešení: 
      Řešení je více - entropie jako dolní odhad, srovnání s Huffmanovým kódem, který vytvoříme atd. Zabalím tě! je značně
      neefektivní, protože optimálnímu kódu stačí pro zakódování (1) 19 bitů. Reklamě na program Stlačím tě! věřit nelze... 
      ... 17 < 10*entropie_zdroje (10* protože máme 10 znaků).
      
     Moje řešení: Abeceda X={a,b,c,d}. Délka (1) = 10.
     Počet 'a' v (1): 2 -> P(a)=2/10
     Počet 'b' v (1): 1 -> P(b)=1/10
     Počet 'c' v (1): 3 -> P(c)=3/10
     Počet 'd' v (1): 4 -> P(c)=4/10
     Půjdeme na to jak jinak než přes entropii:
     LaTeX: $$H(a,b,c,d)=-\sum_{i=1}^{4}P(x_i)*log_2(P(x_i))\doteq1.8$$, kde x znamená písmenko a P(x) jeho pravděpodobnost.
     Entropie nám tu udává nejoptimálnější počet kódových znaků na zakódování jednoho písmena.
     Nyní s ní porovnáme střední délky kódů:
     L(Z)=25/10=2.5 pro Zabalím tě. Protože L(Z)>H(a,b,c,d), tak je jasné, že daný kód sice funguje, ale není optimální.
     L(S)=17/10=1.7 pro Stlačím tě. Protože L(S)<H(a,b,c,d), je jasné že daný kód slovo nemůže zakódovat (je ještě menší než optimum). --Michal Zajačík 1. 2. 2011, 14:23 (UTC)

4) Bonus: Ukažte, že pro libovolné jevy LaTeX: A_1,...,A_n platí
         
         LaTeX: $$P\left(\bigcap_{i=1}^n A_i\right) \geq \sum_{i=1}^n P(A_i) - (n-1)$$.
  
   Opravené Řešení:
    LaTeX: $$P(\bigcap_{i=1}^nA_i)=\overline{P(\bigcup_{i=1}^n\overline{A_i})}=1-P(\bigcup_{i=1}^n\overline{A_i})=1 - \sum_{i=1}^nP(\overline{A_i}) + \prod_{i=1}^nP(\overline{A_i})=1 - \sum_{i=1}^n(1- P(A_i)) + \prod_{i=1}^n(1-P(A_i))=1-\sum_{i=1}^n1 + \sum_{i=1}^nP(A_i)+ \prod_{i=1}^n(1-P(A_i)).$$
   LaTeX: $$= 1 - n + \sum_{i=1}^nP(A_i)+ \prod_{i=1}^n(1-P(A_i))=\sum_{i=1}^nP(A_i)+ \prod_{i=1}^n(1-P(A_i)) - (n-1).$$ Vzhledem k tomu že LaTeX: $$\prod_{i=1}^n(1-P(A_i))\leq1$$, platí jistě
   LaTeX: $$P\left(\bigcap_{i=1}^n A_i\right) \geq \sum_{i=1}^n P(A_i) - (n-1)$$. Rovnost pro produkt roven nule, tedy například je-li jeden jev
   jistý, P(A)=1, 1-P(A)=0, celý produkt roven nule. Q.E.D. --Michal Zajačík 13. 2. 2011, 13:12 (UTC)
   
   Chybné: LaTeX: $$P(\bigcap_{i=1}^nA_i)=\overline{P(\bigcup_{i=1}^n\overline{A_i})}=1-P(\bigcup_{i=1}^n\overline{A_i})=1 - \sum_{i=1}^nP(\overline{A_i}) - \prod_{i=1}^nP(\overline{A_i})=1 - \sum_{i=1}^n(1- P(A_i)) - \prod_{i=1}^n(1-P(A_i))=1-\sum_{i=1}^n1 + \sum_{i=1}^nP(A_i) - \prod_{i=1}^n1 + \prod_{i=1}^nP(A_i).$$
   LaTeX: $$= 1 - n + \sum_{i=1}^nP(A_i)-1+ \prod_{i=1}^nP(A_i).$$ Vzhledem k tomu že LaTeX: $$\prod_{i=1}^nP(A_i)\leq1$$, nerovnost platí.
   Dosadíme ten produkt (ono pí):
   LaTeX: $$P(\bigcap_{i=1}^nA_i)\geq -n + \sum_{i=1}^nP(A_i) + 1$$, tedy po lehké úpravě:
   LaTeX: $$P(\bigcap_{i=1}^nA_i)\geq \sum_{i=1}^nP(A_i) - (n-1)$$ Q.E.D. --Michal Zajačík 1. 2. 2011, 14:23 (UTC)
   
   /*Myslím si, že tento důkaz má v sobě několik nepřesností. První je u třetího rovnítka. Měla by tam být nerovnost a před "pí"
     by mělo být +. Dále u pátého rovnítka. To pravidlo na rozepsání platí pouze pro sumu, stačí si zkusit pro n=2 a už to
     nevychází. V předposledním řádku důkazu, by měla být opačně nerovnost. Zde uvádím svoje řešení. Jirka Blecha

     LaTeX: $$P(\bigcap_{i=1}^nA_i)=P(\overline{\bigcup_{i=1}^n\overline{A_i}})}=1-P(\bigcup_{i=1}^n\overline{A_i})\geq1 - \sum_{i=1}^nP(\overline{A_i}) =1 - \sum_{i=1}^n(1- P(A_i))=1-\sum_{i=1}^n1 + \sum_{i=1}^nP(A_i)= 1 - n + \sum_{i=1}^nP(A_i)= \sum_{i=1}^nP(A_i)-(n-1).$$
     
     -> pravdu díž, trhání produktu je kardinální blbost, tudíž i nerovnosti na konci, nicméně při opravě testu mi to museli přehlédnout :)
     Díky. Opraveno. Jinak třetí rovnítko je správně, neboť je tam právě ten produkt.
Citováno z „http://oi.hanx.cz/wiki/index.php/PSI“
Events Upcoming
More »