Teoria informacji/TI Ćwiczenia 2: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\endaligned" na "\end{align}")
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
Linia 56: Linia 56:
 
Rozpisujemy:
 
Rozpisujemy:
 
<center><math>
 
<center><math>
\aligned
+
\begin{align}
 
H & = - \sum_{s \in S} p(s) \cdot \log {p(s)} \\
 
H & = - \sum_{s \in S} p(s) \cdot \log {p(s)} \\
 
& = - \sum_{s \in X} p \cdot p(s|X) \log (p \cdot p(s|X))
 
& = - \sum_{s \in X} p \cdot p(s|X) \log (p \cdot p(s|X))
Linia 81: Linia 81:
  
  
(c) <math>\aligned
+
(c) <math>\begin{align}
 
H(\langle p_1, \ldots, p_m \rangle)& =H(\langle p_1 + \ldots + p_k, p_{k+1} + \ldots + p_m\rangle)\\
 
H(\langle p_1, \ldots, p_m \rangle)& =H(\langle p_1 + \ldots + p_k, p_{k+1} + \ldots + p_m\rangle)\\
 
& + (p_1 + \ldots + p_k)H(\langle\frac{p_1}{\sum_{i=1}^k p_i}, \ldots, \frac{p_k}{\sum_{i=1}^k p_i}\rangle)\\
 
& + (p_1 + \ldots + p_k)H(\langle\frac{p_1}{\sum_{i=1}^k p_i}, \ldots, \frac{p_k}{\sum_{i=1}^k p_i}\rangle)\\

Wersja z 12:43, 9 cze 2020

Ćwiczenia

Ćwiczenie 1 [Obliczanie entropii]

Oblicz entropię wyniku w następujących eksperymentach:

a) Rzucamy jedną kostką sześcienną,
b) Rzucamy dwiema kostkami sześciennymi i sumujemy liczbę oczek,
c) Rzucamy symetryczną monetą do uzyskania pierwszego orła. Wynikiem jest liczba wykonanych rzutów.

Rozwiązanie

{{{3}}}


Ćwiczenie 2 [Entropia funkcji]

Niech X będzie zmienną losową przyjmującą skończoną liczbę wartości. Jaka będzie zależność między entropią X a entropią Y, jeśli:

a)
b) ?

Rozwiązanie

{{{3}}}


Ćwiczenie 3 [Losowanie ze zwracaniem i bez]

Urna zawiera zielonych kul, czerwonych i niebieskich. Które losowanie da wynik o większej entropii: losowanie kul ze zwracaniem czy bez zwracania?

Rozwiązanie

{{{3}}}


Ćwiczenie 4 [Kombinacja entropii]

Załóżmy, że mamy dwa źródła i o entropiach i , takie że zbiory ich symboli są rozłączne. Przeprowadzamy losowanie i z prawdopodobieństwem podajemy symbol ze źródła , a z prawdopodobieństwem ze źródła .

Jaka jest entropia wyniku takiej procedury?

Rozwiązanie

{{{3}}}

Zadania domowe

Zadanie 1 - Aksjomatyzacja entropii

Niech będzie funkcją rzeczywistą określoną na rozkładach prawdopodobieństwa, spełniającą warunki:

(a) jest ciągłą funkcją p

(b)


(c)

Udowodnij, że H jest miarą entropii Shannona. Innymi słowy, że z dokładnością do wyboru podstawy logarytmu, jedyną funkcją spełniającą podane warunki jest


Zadanie 2 - Inne miary entropii

W kryptografii używa się często innych miar entropii. Przykładami są:

Definicja [Entropia kolizji]

Entropia kolizji mierzy prawdopodobieństwo, że dwie zmienne z danego rozkładu będą sobie równe

Definicja [Entropia minimum]

Entropia minimum mierzy prawdopodobieństwo odgadnięcia wartości zmiennej pochodzącej z danego rozkładu

Udowodnij następujące nierówności:


Zadanie 3 - Nieskończona entropia

W szczególnych przypadkach wartość entropii zmiennej losowej może być nieskończona. Niech dla . jest tu stałą normalizującą: . Pokaż, że ma skończoną wartość (np. przez ograniczenie jej z góry przez całkę funkcji ), a więc definicja jest sensowna. Pokaż, że entropia tak zdefiniowanej zmiennej losowej jest nieskończona.