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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
 
Linia 9: Linia 9:
  
 
{{rozwiazanie|||  
 
{{rozwiazanie|||  
 +
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Linia 15: Linia 16:
 
: c) <math>H(X)=\frac{1}{2} \log 2 + \frac{1}{4} \log 4 + \ldots = \sum_{i=1}^{\infty} i2^{-i} = \sum_{i=1}^{\infty} 2^{-i} + \sum_{i=2}^{\infty} 2^{-i} + \ldots = \sum_{i=0}^{\infty} 2^{-i} = 2</math>
 
: c) <math>H(X)=\frac{1}{2} \log 2 + \frac{1}{4} \log 4 + \ldots = \sum_{i=1}^{\infty} i2^{-i} = \sum_{i=1}^{\infty} 2^{-i} + \sum_{i=2}^{\infty} 2^{-i} + \ldots = \sum_{i=0}^{\infty} 2^{-i} = 2</math>
 
</div>
 
</div>
</div>}}
+
</div>
  
  
Linia 25: Linia 26:
  
 
{{rozwiazanie|||  
 
{{rozwiazanie|||  
 +
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Linia 30: Linia 32:
 
: b) <math>\sin X</math> nie jest funkcją różnowartościową. W ogólności Y może przyjmować takie same wartości dla różnych X. <math>H(Y)\le H(X)</math>
 
: b) <math>\sin X</math> nie jest funkcją różnowartościową. W ogólności Y może przyjmować takie same wartości dla różnych X. <math>H(Y)\le H(X)</math>
 
</div>
 
</div>
</div>}}
+
</div>
  
  
Linia 36: Linia 38:
 
Urna zawiera <math>z</math> zielonych kul, <math>c</math> czerwonych i <math>n</math> niebieskich. Które losowanie da wynik o większej entropii: losowanie <math>k\ge 2</math> kul ze zwracaniem czy bez zwracania?}}
 
Urna zawiera <math>z</math> zielonych kul, <math>c</math> czerwonych i <math>n</math> niebieskich. Które losowanie da wynik o większej entropii: losowanie <math>k\ge 2</math> kul ze zwracaniem czy bez zwracania?}}
  
{{rozwiazanie|||  
+
{{rozwiazanie|||
 +
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Linia 43: Linia 46:
 
</div>
 
</div>
 
</div>
 
</div>
}}
+
 
  
  
Linia 51: Linia 54:
 
Jaka jest entropia wyniku takiej procedury?}}
 
Jaka jest entropia wyniku takiej procedury?}}
  
{{rozwiazanie|||  
+
{{rozwiazanie|||
 +
}}
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Linia 68: Linia 72:
 
</div>
 
</div>
 
</div>
 
</div>
}}
 
  
 
== Zadania domowe ==
 
== Zadania domowe ==

Aktualna wersja na dzień 20:47, 27 wrz 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


Ć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


Ć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


Ć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

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.