Entropia (teoria informacji) – Gry

Entropia (teoria informacji)

Z Wikipedii

Skocz do: nawigacji, szukaj
Ujednoznacznienie Ten artykuł dotyczy pojęcia z dziedziny teorii informacji. Zobacz też: inne znaczenia tego terminu.

Entropia – w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypadająca na znak symbolizujący zajście zdarzenia z pewnego zbioru. Zdarzenia w tym zbiorze mają przypisane prawdopodobieństwa wystąpienia.

Wzór na entropię:

H(x)=\sum_{i=1}^np(i)\log_r \frac{1}{p(i)}= - \sum_{i=1}^np(i)\log_r {p(i)}\,\!

gdzie p(i) – prawdopodobieństwo zajścia zdarzenia i, a n – liczba wszystkich zdarzeń danej przestrzeni. W przypadku kodowania ciągu znaków jest to prawdopodobieństwo wystąpienia i-tego znaku. W teorii informacji najczęściej stosuje się logarytm o podstawie r=2, wówczas jednostką entropii jest bit. Dla r= e jednostka ta nazywa się nat (nit), natomiast dla r=10 – dit lub hartley.

Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego w następnej chwili. Jeżeli następujące zdarzenie występuje z prawdopodobieństwem równym 1, to z prostego podstawienia wynika, że entropia wynosi 0, gdyż z góry wiadomo, co się stanie – nie ma niepewności.

Własności entropii:

  • jest nieujemna
  • jest maksymalna, gdy prawdopodobieństwa zajść zdarzeń są takie same
  • jest równa 0, gdy stany systemu przyjmują wartości 0 albo 1
  • własność superpozycji – gdy dwa systemy są niezależne, to entropia sumy systemów równa się sumie entropii.
  • jeśli ze źródła danych pobierane są k-literowe ciągi, wówczas entropia wynosi H(x(k)) = kH(x)

Definicja informacyjna była pierwotnie próbą ujęcia tradycyjnego pojęcia entropii znanego z termodynamiki w kategoriach teorii informacji. Okazała się jednak, że definicja ta jest przydatna w ramach samej teorii informacji.

Pojęcie entropii jest bardzo przydatne w np. dziedzinie kompresji danych. Entropię zerowego rzędu można obliczyć znając histogram ciągu symboli. Jest to iloczyn entropii i liczby znaków w ciągu. Osiągi kodowania Huffmana są często zbliżone do tej granicy, jednak lepszą efektywnością charakteryzuje się kodowanie arytmetyczne.

Przyjęcie modelu, w którym uwzględnia się kontekst znaku, pozwala zwykle na bardzo duże obniżenie entropii.

[edytuj] Przykład

W przypadku, gdy prawdopodobieństwa poszczególnych zdarzeń w zbiorze są równe, powyższy wzór można stosować w postaci uproszczonej:

H(x) = log2(n)

gdzie n oznacza wielkość zbioru. Przykładowo dla zbioru 26 liter alfabetu (n=26) entropia każdej z nich wynosi około 4,7, więc ośmioznakowy ciąg liter wykorzystywany np. jako hasło będzie miał entropię 37,6.

Moneta, która wyrzuca z takim samym prawdopodobieństwem orły i reszki, ma 1 bit entropii na rzut:

- p_{O} \log_2 p_{O} - p_{R} \log_2 p_{R} = - \frac 1 2 \log_2 \frac 1 2 - \frac 1 2 \log_2 \frac 1 2 = \frac 1 2 + \frac 1 2 = 1

Ogólniej każde źródło dające N równie prawdopodobnych wyników ma log2N bitów na symbol entropii:

- \sum_{i=1}^N \frac 1 N \log_2 \frac 1 N = - N \frac 1 N \log_2 \frac 1 N = -\log_2 \frac 1 N = \log_2 N

[edytuj] Zobacz też

Wikisłownik
Zobacz hasło entropia w Wikisłowniku





Notice: Undefined offset: 203 in /home/plu21/domains/kompedium.net/public_html/gry/richFeeds.php on line 26

Notice: Undefined offset: 203 in /home/plu21/domains/kompedium.net/public_html/gry/richFeeds.php on line 91
Unable to open RSS Feed sample-template_SAFE.html, exiting