PSI

Z OI wiki

Přejít na: navigace, hledání

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

Nové PSI - Počítačové sítě

Lehkým úvodem může být komiks The Manga Guide to Statistics | No Starch Press. V době psaní dostupný zde a zde.

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

Teorie a příklady na pochopení základů (15.1.2013 bez záruky)


Semestrální testy a zápočtová práce

Google drive

Zkoušky akademický rok 2010/2011

Pisemka z 4.1. 2011 

1) V populaci je infikovana 1/4 jedincu, ale jen u 2/3 se nakaza 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), nikoli 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.

Zkoušky akademický rok 2011/2012

Pisemka z 3.1.2012. 

1) Když něco měřime, přesná vzdálenost je LaTeX: \mu; LaTeX: \sigma^2=16. Kolikrát musíme měřit, aby se na hladině významnosti
   96% chyba aritmetického průmeru lišila max 1.5. Použivá se centralní limitní věta.

2) Dána jsou data a četnosti:
 
   x       0  1  2  3  4  5  6  7  8
   cetnost 3  2  4  7  3  5  5  1  2

  spočitat EX, DX.

3) Je dan Markovův řetězec:

   LaTeX: $$\left( \begin{array}{cc@{\ }r}
   1-p & p \\
   q & 1-q \\
   \end{array} \right)$$

   a) Pozorované jsou následující stavy: (1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1). Odhadněte dané pravděpodobnosti.
   b) Spočítat LaTeX: (1,0)\cdot \textbf{P}^2
   c) Najit limitní vektor a spočítat, jestli řetězec k němu konverguje.

4) Zjistit jestli jsou tohle Huffmanovy kódy: (stačí kreslit stromečky)

   a) 0010, 01, 10, 110 (neni, stredni delka neni optimalni)
   b) 010, 01, 10, 110 (neni instantni)
   c) 00, 01, 10, 111, 110 (je)
   d) 10, 010, 011 (delka neni optimalni)
   e) 0, 10, 111, 110 (je)

Pisemka z 12.1. 2012 

1) Mějme 300 čísel zaokrouhlených na jedno desetinné místo. Určete, o kolik se maximálně liší jejich
   aritmetický průměr od aritmetického průměru skutečných, nezaokrouhlených hodnot s pravděpodobností 0.95.
      
   Řešení:
      Nejprve pro jedno zaokrouhlení, LaTeX: EX_{i}=0, DX_{i}=\frac{1}{1200} , DX z funkce rovnoměrného rozložení
      LaTeX: f(x) = \begin{cases} 10 & x \geq -0.05 \or x \leq 0.05 \\
      0  & jinak
      \end{cases}
      LaTeX: DX_{i}=EX_{i}^{2}=10\int_{-0.05}^{0.05}x^{2}dx=\frac{1}{1200}
      LaTeX: ES_{300}=\sum_{i=1}^{300}EX_{i}=0
      LaTeX: DS_{300}=\sum_{i=1}^{300}DX_{i}=300 \cdot \frac{1}{1200}=\frac{1}{4}
      Zbytek jsem vyrobil pomocí intervalového odhadu, ale to je špatně, poznámka zněla, že nás zajímá průměr a ne střední hodnota, 
      pokud někdo doplní, budu rád... 

2) Exponenciální rozložení má pro LaTeX: t \ge 0 hustotu LaTeX: f_{X}(t) = we^{-wt}.
   Na základě náhodného výběru
                0.42600148; 0.87249437; 0.14744007; 0.01452009; 1.44667089
   najděte maximálně věrohodný odhad parametru LaTeX: w

   Řešení:
      Řešeno pomocí MLE. Je třeba funkci dosadit do LaTeX: M(w)=\prod_{i=1}^{n}{we^{-wt_i}}, zlogaritmovat
      LaTeX: m(w)=\ln\left(\prod_{i=1}^{n}{we^{-wt_i}}\right)=n\ln{w}-w\sum_{i=1}^{n}t_{i}, zderivuji
      LaTeX: 0=\frac{n}{w}-\sum_{i=1}^{n}t_{i}, upravím
      LaTeX: w=\frac{n}{\sum_{i=1}^{n}t_{i}}\doteq1.72

3) Pohybujeme se ve čtvercové síti o 2 řádcích a 3 sloupcích. Z každého uzlu můžeme pouze do sousedního vlevo, vpravo
   nebo dolů (pokud tam nějaký je). Z každého uzlu jsou pravděpodobnosti přechodu do všech povolených sousedních uzlů stejné.
   A. Klasifikujte všechny stavy
   B. Najděte všechny uzavřené množiny stavů
   C. Najděte všechna stacionární rozdělení pravděpodobností a posuďte, zda řetezec k některému z nich konverguje.
   
   Řešení:
      Situace vypadá nějak takhle:
      1 <--> 2 <--> 3
      |      |      |
      V      V      V
      4 <--> 5 <--> 6
      
      A. 4,5,6 trvalé neperiodické, 1,2,3 přechodné
      B. LaTeX: \{4,5,6\}, \o
      C. Matice přechodu:
         LaTeX: $$\left( \begin{array}{cccccc@{\ }r}
         0 & 1/2 & 0 & 1/2 & 0 & 0  \\
         1/3 & 0 & 1/3 & 0 & 1/3 & 0  \\
         0 & 1/2 & 0 & 0 & 0 & 1/2  \\
         0 & 0 & 0 & 0 & 1 & 0 \\
         0 & 0 & 0 & 1/2 & 0 & 1/2 \\
         0 & 0 & 0 & 0 & 1 & 0 \\
         \end{array} \right)$$
  
         Definice: Pro každý vektor p stacionárního rozdělení platí, že p*P=p, kde P je matice přechodu.
         Výsledek přenásobení matice vektorem LaTeX: (a,b,c,d,e,f) zleva musí být roven LaTeX: (a,b,c,d,e,f)
         
         LaTeX: (a,b,c,d,e,f)\left( \begin{array}{cccccc@{\ }r}
         0 & 1/2 & 0 & 1/2 & 0 & 0  \\
         1/3 & 0 & 1/3 & 0 & 1/3 & 0  \\
         0 & 1/2 & 0 & 0 & 0 & 1/2  \\
         0 & 0 & 0 & 0 & 1 & 0 \\
         0 & 0 & 0 & 1/2 & 0 & 1/2 \\
         0 & 0 & 0 & 0 & 1 & 0 \\
         \end{array} \right) = (a,b,c,d,e,f)
         
         Po přenásobení matice vektorem:
         LaTeX: \left(\frac{b}{3}, \frac{a}{2} + \frac{c}{2}, \frac{b}{3}, \frac{a}{2} + \frac{e}{2}, \frac{b}{3} + e + f, \frac{c}{2} + \frac{e}{2}\right) = \left(a,b,c,d,e,f\right)
         
         Z toho soustava rovnic do které ještě přidáme podmínku LaTeX: a+b+c+d+e+f=1
         LaTeX: 
         a = \frac{b}{3}; 
         b = \frac{a}{2} + \frac{c}{2};   
         c = \frac{b}{3};   
         d = \frac{a}{2} + \frac{e}{2};   
         e =  \frac{b}{3} + e + f;   
         f = \frac{c}{2} + \frac{e}{2};   
         a + b + c + d + e + f = 1
         
         
         Nějak tu soustavu umlátíme a vyjde nám jediné řešení LaTeX: \left(0,0,0,\frac{1}{4},\frac{1}{2},\frac{1}{4}\right). Toto je jediné rozdělení a řetězec k němu konverguje vždy, 
         jelikož množina trvalých stavů je jen jedna.


   /* Nestačilo by rovnici LaTeX: p*P=p řešit jen pro stavy LaTeX: 4,5,6, protože víme, že ve stacionárním rozdělení musí být
      pravděpodobnosti přechodných stavů nulové? --dobriric

4) Informační zdroj nad abeceou LaTeX: \{a,b,c,d\} je popsán pravděpodobností LaTeX: p(a)=0.1, p(b)=0.6,
   p(c)=p(d)=0.15.
   Nalzeněte Huffmanův binární kód i Shannonův kód pro tento zdroj a popište jejich efektivitu vůči
   teoretickému optimu.
   
   Řešení
      Vyrobil jsem Huffmanův kód B = 1, A = 000, C=001, D= 01, střední délka 1.6
      Pak jsem vypočítal délky jednotlivých slov pro Shannonův kód, ty mi vyšli 1,3,3,4 střední délka 1.9, vyrobit nějaký kód,
      nepřišli jsme na to, jestli je na to nějaký jednotný algoritmus, vytvořili jsem instantní kód s vypočítanými délkami a zdá se,
      že to prošlo...
      A pak dovysvětlit, střední délky, entropie...

Pisemka z 16.1.2012

--Richard Dobřichovský 16.1.2012, 12:45 (UTC) 

1) V první krabici je 10 bílých a 15 červených koulí. V druhé krabici je 15 bílých a 5 červených koulí. Třetí krabice
   je prázdná. Z první a druhé krabice vytáhneme po jedné kouli a dáme do třetí krabice. Z třetí krabice vytáhneme kouli. Jaká je pravděpodobnost, že
   z třetí krabice vytáhneme bílou kouli?

   Řešení:
      
      Po tažení z první a druhé krabice mohou v třetí krabici nastat tři stavy:
      1) Jsou v ní dvě bílé koule, s pravděpodobností LaTeX: \frac{10}{25}\cdot\frac{15}{20}=\frac{3}{10}.
      2) Jsou v ní dvě různé koule, červená a bílá, s pravděpodobností LaTeX: \frac{10}{25}\cdot\frac{5}{20}+\frac{15}{25}\cdot\frac{15}{20}=\frac{11}{20}.
      3) Jsou v ní dvě červené koule, s pravděpodobností LaTeX: \frac{15}{25}\cdot\frac{5}{20}=\frac{3}{20}.

      Nyní táhneme z třetí krabice:
      1) Nastal-li první stav, vytáhneme bílou kouli s pravděpodobností LaTeX: 1.
      2) Nastal-li druhý stav, vytáhneme bílou kouli s pravděpodobností LaTeX: \frac{1}{2}.
      3) Nastal-li třetí stav, vytáhneme bílou kouli s pravděpodobností LaTeX: 0.

      Celkem tedy pravděpodobnost, že vytáhneme z třetí krabice bílou kouli je LaTeX: \frac{3}{10}\cdot1+\frac{11}{20}\cdot\frac{1}{2}+\frac{3}{20}\cdot0=\frac{23}{40}.

2) Určete maximální věrohodný odhad parametru LaTeX: \lambda pro náhodný výběr LaTeX: x_1,x_2,\dots,x_n z rozdělení s hustotou:

   LaTeX: f_X(t) = \begin{cases}
      \frac{\lambda^3}{2}t^2e^{-\lambda t} & 0 \leq t \\
      0  & t<0
      \end{cases}

   Řešení: LaTeX: \lambda=\frac{3n}{\sum\limits_{j=1}^n t_j}, postup viz písemku z 12.1.2012, příklad 2.

3) Alice a Bob hrají hru. Hráč, co je na řadě, hodí kostkou. Padne-li 6, vyhrává, a hra končí. Padne-li liché číslo, pokračuje stejný hráč.
   Padne-li jiné sudé číslo než 6, pokračuje druhý. Alice začíná. Jaké jsou pravděpodobnosti výsledků?

   Řešení: Alice vyhrává s pravděpodobností LaTeX: \frac{3}{5}, Bob s pravděpodobností LaTeX: \frac{2}{5}. Postup viz Příklady na Markovovy řetězce, příklad 14. Jen jsou jiné
           pravděpodobnosti přechodů mezi  přechodnými stavy.

4) Informační zdroj je popsán pravděpodobnostmi LaTeX: p(a)=\frac{1}{10},\,p(b)=\frac{2}{10},\,p(c)=\frac{7}{10}. Sestrojte blokový 
   Huffmanův kód pro dvojice znaků.

   Řešení: Určíme pravděpodobnosti všech možných zřetězení dvou znaků z abecedy (LaTeX: aa, ab, ac, ba \dots celkem 9), LaTeX: p(ab)=p(a)\cdot p(b).
           Tyto zřetězení pak jednotlivě tvoří množiny LaTeX: S_1,\dots,S_9 a postupujeme standardně podle algoritmu pro Huffmanovo kódování
           (slidy z přednášek teorie informace, strana 92-93).


Písemka 19.1. 2012

--Pavel Lieberzeit 19.1.2012, 16:47 (UTC+1) 

1) Dílna vypaluje keramické výrobky, při vypalování se poškodí zhruba 20% z nich a ty jsou potom neprodejné. Určete pravděpodobnost s 
   jakou ze 400 džbánků daných na vypálení zbyde 340 nepoškozených.
   Dále určete cenu, za kterou se má jeden džbánek prodávat, jestli s pravděpodobností 95% chci 400 nevypálených džbánků (takže část se
   rozbije) prodat za aspoň 20000.
   
   (oboje se dá řešit centrální limitní větou, rozdělení je binomické)

2) Máme četnosti známek z testu A=2, B=0, C=5, D=10, E=8, F=56 (přesná čísla si nepamatuju, ale nějak takhle byly). Proveďte test
   hypotézy, že rozložení známek odpovídá binomickému rozdělení Bi(5, p) kde EX = 4. Jako ocislovani znamek pouzije X(A) = 0, X(B) = 1,...
   X(F)=5.
   
   (nejprve zjistit pravděpodobnost pro binomické rozdělení (EX = m*q, kde Bi(m, q)), pak spočítat teoretické četnosti a provést chi kvadrát
   test dobré shody. Například.)

3) Vypočítat pravděpodobnostní rozdělení pro čtvrtý krok pro Markovovův řetězec daný maticí přechodu {[1,0,0],[0,1,0],[1/6,1/2,1/3]}.
   Počáteční pravděpodobnostní rozdělení je rovnoměrné, tj p(0) = (1/3,1/3,1/3)
   
   (využije se rovnice p(4) = p(0)*P^4 => je potřeba udělat čtvrtou mocninu matice přechodů a tu zleva vynásobit počátečním pravděpodob.
   rozdělením)

4)Určete rychlost entropie pro markovský zdroj informace, který je zadán matici přechodu

// Pokud si pamatuju správně, tak matice vypadala následovně. --Tomáš Hnídek

// Opravené zadanie. --Noskoja1 19. 1. 2012, 16:40 (UTC) 

         LaTeX: $$\left( \begin{array}{cccccc@{\ }r}
         0,2 & 0 & 0 & 0,8 \\
         0 & 0,25 & 0,75 & 0 \\
         0 & 1 & 0 & 0   \\
         0,5 & 0 & 0 & 0,5  \\
         \end{array} \right)$$

// Zadania by mali byť OK --Noskoja1 19. 1. 2012, 16:40 (UTC)

Pisemka z 7.2.2012.

vyfocená písemka

Zkoušky akademický rok 2012/2013

Pisemka z 4.1.2013.

--Filip Šrajer 5.1.2012, 9:47 (UTC+1) 

1) Je zadána náhodná veličina X s rovnoměrným rozdělením na <2,7>. Určete distribuční funkci náhodné veličiny Y, která je dána předpisem:
   
   LaTeX: Y = \begin{cases}
      3  & X<3 \\
      X  & 3 \leq X \leq 5 \\
      5  & 5<X
      \end{cases}
   Dále vyjádřete Y jako směs (diskrétní a spojitá složka).

2) Naměřené hodnoty {182, 183, 179, 189, 185, 180} //hodnoty už přesně nevím
   Na hladině významnosti 0,05 otestujte nulovou hypotézu, že střední hodnota je rovna 182.

3) Markovovův řetězec je daný maticí přechodu:
         LaTeX: $$\left( \begin{array}{cccccc@{\ }r}
         0 & 1 & 0 & 0 & 0 \\
         0 & 0 & 0 & 1 & 0 \\
         0 & 1/4 & 1/4 & 1/4 & 1/4   \\
         1 & 0 & 0 & 0 & 0  \\
         0 & 0 & 1/4 & 1/2 & 1/4  \\
         \end{array} \right)$$
   a) Klasifikujte všechny stavy.
   b) Určete všechny uzavřené množiny stavů.
   c) Najděte stacionární rozdělení.

4)Pro dané množiny kódových slov určete, zda mohly být vytvořeny pomocí Shannonova kódování a Huffmanova kódování.
   V kladném případě najděte původní informační zdroj. Odpovědi zdůvodněte.
   a)0000,11        
   b)0000,0
   c)10,11,00,010,011
   d)00,01,11

vyfocená písemka

Písemka z 9.1.2013 

1) Máme veličinu X se zadanou funkcí hustoty:
      LaTeX: f_x = \begin{cases}
      \frac{t}{8}  & X \in  <0,4>\\
      0  & jinak
      \end{cases}
      Určete její distribuční funkci LaTeX: F_x a funkce LaTeX: 1-F_x, F_{x}^{2}, 2F_x. Pokud jsou funkce distribuční, tak určete jejich hustotu.

2) Máme hodnoty normální veličiny {65,71,...} (bylo jich 5). Ověřte na hladině významnosti LaTeX: \alpha=0,05 hypotézu LaTeX: H_0: \sigma^2=120 a hypotézu LaTeX: H_1: \sigma^2\neq120.

3) Markovovův řetězec je daný maticí přechodu -> nevim jak přesně vypadala.. psti mají rovnoměrné rozdělení, napište jaké mají rozdělení po 4 krocích.

4)Bezpaměťový informační zdroj; znaky a,b,c; psti : LaTeX: p(a)=\frac{1}{6},\,p(b)=\frac{2}{6},\,p(c)=\frac{3}{6}; sestrojit blokový Huffmanův kód pro dvojice znaků.

Písemka z 16.1.2013 

1) Tabulka náhodných veličin X a Y a) spočítat LaTeX: cov(X,Y) b) závislost/nezávislost c) určit pravděpodobnostní funkci veličiny LaTeX: Z = X + Y

2) Počet bodů z testu {15,16,...26} (bylo jich 20). Ověřte na hladině významnosti LaTeX: \alpha=0,05 hypotézu a)LaTeX: H_0: body z testu mají rovnoměrné rozdělení na intervalu <15;26> b)hypotézu LaTeX: H_1: nemají rovnoměrné rozdělení.

3) Markovovův řetězec je daný maticí přechodu -> nevim jak přesně vypadala.. a) klasifikovat stavy b) určit uzavřené množiny trvalých stavů c) najít všechna stacionární rozdělení a napsat jestli k nějakému ten řetězec konverguje

4) Jsou zadané veličiny LaTeX: X ~ Bi(1,2/3); Y ~ Bi(1,1/100); Z = X @ Y; @ je součet modulo 2 zjistěte vzájemnou informaci X a Z.
Citováno z „http://oi.hanx.cz/wiki/index.php/PSI“
Events Upcoming
More »