Entropija (informatika)
Entropija ali Shannonova entropija je v informatiki količina, ki meri negotovost izida poskusa povezanega s slučajno spremenljivko. Ta vrsta entropije določa za pričakovano vrednost količino informacije, ki jo pridobimo takrat, ko izvedemo poskus, in dobimo njeno vrednost. Ta entropija je torej merilo za količino informacije, ki jo dobimo s poznavanjem vrednosti slučajne spremenljivke.
Označimo jo s . Merimo pa jo v bitih.
Primer: met kovanca ima entropijo enega bita. Seveda v primeru, da kovanec ni pravilen, je negotovost manjša in s tem tudi entropija nižja.
Uvedel jo je ameriški elektrotehnik in matematik Claude Elwood Shannon (1916 – 2001) v letu 1948.
Če je X slučajna spremenljivka, ki lahko zavzame diskretne vrednosti x1, x2, x3,…. xn, potem je Shannonova entropija zanjo enaka
kjer je b osnova logaritma (kadar je enota za entropijo bit, je b enak 2).
Primer meta kovanca
[uredi | uredi kodo]Pri metu kovanca sta enako verjetna dva izida glava in številka. Če je entropija merilo za negotovost, potem je očitno, da mora graf entropije imeti tudi maksimum.
Za posamezne poskuse velja P(X=x0) = ½ (glava) oziroma p0 in P(X=x1) = ½ (številka) oziroma p1 Iz tega dobimo po definiciji entropije zanjo vrednost H = 1 bit. To pomeni, da nam vsak izid meta kovanca da 1 bit informacije.
Primer je popolnoma drugačen, če kovanec ni pravilen (vsak izid poskusa ni enako verjeten). Recimo, da je verjetnost 60% (p 0) da pade glava in 40% (p1) da pade številka. Velja p 0 + p 1 = 1. Entropija se izračuna po zgornjem obrazcu na naslednji način
kjer je q enak 1-p. V tem primeru imamo večjo nesigurnost v izid poskusa. S tem pa tudi zmanjšano entropijo oziroma vsak met kovanca nam da manj kot 1 bit informacije. Če pa bi imel kovanec na obeh straneh glavo (popolnoma nepravilni kovanec), bi bila entropija nič. izid meta kovanca nam ne bi dal nobene informacije, ker je izid poskusa vedno znan oziroma enak.
Za vsako verjetnost lahko izračunamo entropijo iz zgornjega izraza. Problem nastopi pri vrednosti p = 0, kjer dobimo za entropijo vrednost nič. V ostalem delu pa je graf funkcije entropija/verjetnost simetrična.
Če vržemo kovanec dvakrat, imamo štiri možne izida poskusa. Verjetnost vsakega izida pa je 0,25. Pri 20 zaporednih metih je verjetnost 20 bitov.
Zunanje povezave
[uredi | uredi kodo]- Entropija in informacija (rusko)
- Opis entropije v informatiki Arhivirano 2011-05-15 na Wayback Machine. (angleško)
- Informatika in entropija Arhivirano 2009-05-21 na Wayback Machine. (angleško)