Teoria Informatiei si a codarii

download Teoria Informatiei si a codarii

of 190

  • date post

    08-Oct-2015
  • Category

    Documents

  • view

    60
  • download

    2

Embed Size (px)

description

Culegere Probleme

Transcript of Teoria Informatiei si a codarii

  • 1

    Cap. 1 Probabiliti. Informaia

    Dicionar: - aposteriori (a posteriori) -locuiune latin: din ceea ce urmeaz, dup experien, pornind de la datele ei; - apriori (a priori) - locuiune latin: din ceea ce precede, anterior experienei; - binar -1.care este constituit din dou elemente; 2.a crui baz este numrul 2; - bit/bii -1. Unitate de msur a informaiei; 2.simbol binar; - discret -care este alctuit din elemente distincte; care variaz n salturi; cuantificat; discontinuu; - echiprobabil(e) -de egal probabilitate; - informaie -necesarul/rezultatul cunoaterii; - probabilitate -1.nsuirea de a fi probabil; 2.msur (funcie) definit pe un cmp de evenimente, p : [0,1].

    Definiii: - surs de informaie (sau experiment probabilistic) = un mecanism (un experiment) prin care se selecteaz un mesaj

    (un eveniment) dintre n posibile dup o lege arbitrar (sau cel puin necunoscut); - mesaj (eveniment) = realizarea produs n urma efecturii experimentului; - 1 bit = cantitatea de informaie furnizat de o surs de informaie binar, fr memorie, echiprobabil, printr-un mesaj

    al ei; - eveniment elementar = un eveniment ce nu poate fi definit ca o reuniune de dou evenimente distincte ntre ele i de

    primul.

    Breviar teoretic: 1. Probabilitate Determinarea experimental a probabilitii de realizare a unui mesaj (eveniment) A se face dup relaia:

    2. Probabilitate condiionat Determinarea experimental a probabilitii de realizare a evenimentului (mesajului) B atunci cnd s-a realizat evenimentul (mesajul) A se face dup relaia:

    3. Formula fundamental a probabilitilor evenimentelor elementare Dac Ai, i = 1n sunt evenimentele elementare ale unui experiment probabilistic (mesajele unei surse de informaie) atunci: ( )

    =

    =

    n

    1ii 1Ap (1.3)

    4. Relaia lui Bayes Dac A i B sunt dou evenimente atunci:

    ( ) ( ) ( ) ( ) ( )A/BpBpB/ApApBA,p == (1.4) unde p(A, B) = probabilitatea de a se realiza i A i B. 5. Formula probabilitii totale Dac Ai cu i = 1, n sunt evenimentele elementare ale unui experiment probabilistic i B un eveniment oarecare pentru acelai experiment atunci:

    ( ) ( ) ( )=

    =

    n

    1iii B/ApApBp (1.5)

    6. Evenimente independente Setul de evenimente Ai, i I, sunt independente dac i numai dac pentru J I

    ( ) ( )iiii Ap Ap JJ = (1.6) n particular, A i B sunt dou evenimente independente dac i numai dac:

  • 2

    ( ) ( ) ( ) ( )BpApBApBA,p == (1.7) i utiliznd relaia (1.4)

    ( ) ( )( ) ( )B/ApBp

    A/BpAp=

    =

    (1.8) 7. Informaia Cantitatea de informaie necesar ridicrii nedeterminrii asupra evenimentului A este egal cu cea furnizat de realizarea evenimentului A i egal cu :

    ( ) ( ) Ap1logAi 2= [bii] (1.9)

    1.1 Zece mingi sunt puse n trei cutii C1, C2, C3. Care este probabilitatea ca n C1 s fie 3 mingi?

    Rezolvare: Fiecare minge poate fi aezat n oricare din cele trei cutii; astfel c fiecare minge tripleaz numrul de variante de aezare a mingilor n cutii. Aadar numrul de variante de aezare a mingilor n cutii este:

    N = 333 ..... 3 = 310 = 59.049 (1.1.1)

    Pentru a avea trei mingi n C1 trebuie ca celelalte apte s fie aezate n C2 i C3. Numrul de variante cu trei mingi n C1 va fi:

    15.3601281202CN 73103C1 === (1.1.2)

    unde 310C reprezint numrul de moduri de alegere a 3 mingi din 10 posibile (considernd mingile distincte); iar 27 reprezint numrul de posibiliti de aezare a apte mingi n dou cutii, C2 i C3. Probabilitatea cerut este:

    26%3

    2CP 10

    7310

    3C1

    = (1.1.3)

    1.2. Trei trgtori trag simultan asupra aceleiai inte. Probabilitatea ca fiecare trgtor s nimereasc inta este p1 = 0,4; p2 = 0,5; p3 = 0,7. Notnd cu A evenimentul ca inta s fie lovit, B evenimentul ca inta s fie lovit exact o dat s se afle: a) p(A); b) p(B); c) dac cele dou evenimente A i B sunt independente.

  • 3

    Rezolvare: a) Calculnd probabilitatea evenimentului contrar lui A:

    ( ) ( ) ( )( ) 9%p1p1p1Ap 321 == (1.2.1) rezult c:

    ( ) ( ) 91%Ap1Ap == (1.2.2)

    b) Avem c:

    ( ) ( ) ( )( ) ( )( )

    ( ) ( ) ( )( ) 36%pp1p1p1pp1 p1p1pAAAp

    AAApAAApBp

    321321

    321321

    321321

    =++

    +=+

    ++=

    (1.2.3)

    unde cu Ai s-a notat evenimentul ca trgtorul i s nimereasc inta. c) Pentru ca cele dou evenimente s fie independente este necesar ca:

    p(A/B) = p(A) (1.2.4)

    dar cum:

    p(A/B) = 100% (1.2.5)

    rezult c cele dou evenimente nu sunt independente.

    1.3. Fie dou urne, U1 (ce conine 2 bile albe i 3 bile negre) i U2 (ce conine o bil alb i 5 bile negre). Se extrage o bil din U1 i se introduce n U2, apoi se extrage o bil din U2. Care este probabilitatea ca bila transferat s fi fost alb dac bila extras din U2 este: a) alb; b) neagr?

    Rezolvare: Fie evenimentele A bila transferat este alb; B bila extras din U2 este alb; a) Pentru a calcula p(A/B) aplicm formula lui Bayes:

    ( ) ( ) ( ) ( )A/BpBpB/ApAp = (1.3.1)

    Probabilitile ( ) ( ) Ap si Ap se calculeaz simplu:

    ( )52Ap = i ( )

    53Ap = (1.3.2)

    Probabilitatea condiionat p(B/A) este:

    p(B/A) =2/7 (1.3.3)

  • 4

    iar p(B) se poate calcula cu formula probabilitii totale:

    ( ) ( ) ( ) ( ) ( )51

    71

    53

    72

    52AB/pApB/ApApBp =+=+= (1.3.4)

    Astfel:

    ( ) ( ) ( )( ) 74

    51

    72

    52

    BpB/ApApA/Bp =

    =

    = (1.3.5)

    b) n mod analog

    ( ) ( ) ( ) ( ) ( ) ( )54

    76

    53

    75

    52

    A/BpAp/ABpApBp;75/ABp

    =+=

    =+== (1.3.6)

    ( ) ( ) ( )( ) ( )A/Bp72,514554

    75

    52

    Bp/ABpApBA/p

  • 5

    adic p(A) = p(B) cum era de ateptat.

    Obs: - cele dou probabiliti p(A) i p(B) sunt probabiliti apriori (dinainte de producerea evenimentelor). nainte ca primul student s extrag un subiect, toi studenii, indiferent de ordinea lor, au anse egale la a extrage un subiect uor.

    1.5. Un tetraedru regulat are feele colorate, una n rou, una n galben, una n verde, iar cea de-a treia conine pe toate trei culorile. Se las s cad tetraedrul pe una din fee. Fie evenimentele: R - faa pe care a czut tetraedrul conine rou; G - faa pe care a czut tetraedrul conine galben; V - faa pe care a czut tetraedrul conine verde. a) ct este probabilitatea evenimentului rou, p(R)? b) ct este probabilitatea condiionat p(R/G)? c) sunt evenimentele R, G i V independente?

    Rezolvare: a) Probabilitatea evenimentului rou este:

    b) Probabilitatea de a se realiza evenimentului rou dac s-a realizat galben este:

    ( )21R/Gp = (1.5.2)

    deoarece una din dou fee ce conin galben conine i rou. c) Pentru ca evenimentele R, G i V s fie independente trebuie s fie ndeplinite relaiile:

    ( ) ( ) ( )( ) ( ) ( )( ) ( ) ( )( ) ( ) ( ) ( )

    =

    =

    =

    =

    VpRpGpVRGpVpGpVGpVpRpVRpGpRpGRp

    (1.5.3)

    Aplicnd relaia (1.1), gsim c:

    ( ) ( ) ( ) ( ) ( ) ( )( )

    41VRGp

    41VGpVRpGRp

    21VpGpRp

    =

    ======

    (1.5.4)

    Cum ultima relaie din (1.5.3) nu este verificat evenimentele R, G i V nu sunt independente.

  • 6

    1.6. Pot fi simultan dou evenimente i incompatibile i independente?

    Rezolvare: Fie A i B dou evenimente. Incompatibilitatea lor presupune ca:

    ( ) 0BAp = (1.6.1) iar independena:

    ( ) ( ) ( )BpApBAp = (1.6.2)

    Din cele dou relaii rezult c cele dou evenimente pot fi independente, fiind incompatibile, doar dac unul este de probabilitate nul. Altfel spus, dou evenimente de probabiliti nenule pot fi independente doar dac sunt compatibile.

    1.7. O imagine alb negru se compune din 1024 x 256 pixeli. Fiecare pixel poate avea un nivel de gri dintre 64 posibile. Aflai informaia furnizat de: a) un pixel; b) ntreaga imagine.

    Rezolvare: a) Considernd egal probabile nivelele de gri, conform definiiei informaiei unui eveniment:

    ( ) ( ) 6641loggri nivelplogpixeli 22 === bii (1.7.1)

    c) ntreaga imagine furnizeaz de 1024 x 256 ori mai mult informaie:

    ( ) ( ) 101,5pixeli2561024imaginei 6= bii (1.7.2)

    1.8. a) Care este numrul de ntrebri minime necesare pentru a afla un numr necunoscut Nx cuprins ntre 1 i 1000? ntrebrile pot fi de genul :

    Numrul Nx este mai mare dect Np (nominalizat)? b) Ct este primul prag Np1 i ct este informaia coninut de rspunsul la ntrebarea: Numrul Nx este mai mare dect 348?

    Rezolvare: a) Informaia necesar pentru a afla numrul Nx necunoscut este:

    ( ) 1000 log1/10001log

    Np1logi 22

    x

    2N === bii (1.8.1)

    Informaia obinut prin rspunsul la o ntrebare este:

  • 7

    ( ) ( ) ( ) ( )p

    p

    p

    pP

    N2N

    N2NN Ap

    1logApAp1logApi += (1.8.2)

    unde ANp este evenimentul prin care numrul Nx este mai mare dect pragul Np. Evident:

    ( ) ( ) 1ApAppp NN

    =+ (1.8.3)

    i putem scrie: ( ) ( )

    pp NNAp1Apx == (1.8.4)

    de unde

    ( ) ( ) [ ]0,1cu x x1

    1logx1x

    1xlogxii 22Np

    +== (1.8.5)

    Funcia i(x) i atinge maximul dac

    21

    x = (1.8.6)

    Valoarea maximului este:

    bit 1im = (1.8.7)

    i corespunde unui prag:

    499N pm = (1.8.8)

    Aadar, dac pragul este ales la jumtatea intervalului n care se cunoate c se afl Nx informaia obinut prin rspunsul la ntrebare (n cazul cel mai defavorabil) este maxim i egal cu 1 bit. Cert, numrul minim de ntrebri este:

    unde [y]sup denot nu