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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 27: Linia 27:
 
=== Zadanie 1 - Efektywne testy przesiewowe ===
 
=== Zadanie 1 - Efektywne testy przesiewowe ===
  
Załóżmy że mamy do przebadania pod kątem obecności jakiegoś wirusa <math>N</math> próbek krwi. Prawdopodobieństwo pozytywnego wyniku <math>p</math> dla każdej próbki jest niewielkie (np. <math>p=0,01</math>), a każdy test jest kosztowny.
+
Załóżmy, że mamy do przebadania pod kątem obecności jakiegoś wirusa <math>N</math> próbek krwi. Prawdopodobieństwo pozytywnego wyniku <math>p</math> dla każdej próbki jest niewielkie (np. <math>p=0,01</math>), a każdy test jest kosztowny.
Zamiast badać każdą próbkę osobno, możemy badać zmieszane fragmenty próbek. Zakładamy wtedy że wynik jest pozytywny jeśli choć jedna z wymieszanych próbek zawierała wirusa. Zakładamy też że każdą próbkę możemy podzielić na wystarczająco wiele fragmentów. Ostatecznie musimy jednak dla każdej próbki wiedzieć bez wątpliwości czy zawiera wirusa czy nie.
+
Zamiast badać każdą próbkę osobno, możemy badać zmieszane fragmenty próbek. Zakładamy wtedy, że wynik jest pozytywny jeśli choć jedna z wymieszanych próbek zawierała wirusa. Zakładamy też, że każdą próbkę możemy podzielić na wystarczająco wiele fragmentów. Ostatecznie musimy jednak dla każdej próbki wiedzieć bez wątpliwości czy zawiera wirusa, czy nie.
 
O ile możemy zmniejszyć oczekiwaną liczbę testów do wykonania?
 
O ile możemy zmniejszyć oczekiwaną liczbę testów do wykonania?
 
Zaprojektuj efektywne badanie dla <math>p=0,01</math> i <math>N=300</math> i policz oczekiwaną liczbę testów.
 
Zaprojektuj efektywne badanie dla <math>p=0,01</math> i <math>N=300</math> i policz oczekiwaną liczbę testów.
Linia 35: Linia 35:
 
=== Zadanie 2 - Optymalność kodu Huffmana ===
 
=== Zadanie 2 - Optymalność kodu Huffmana ===
  
Udowodnij że kod Huffmana dla źródeł binarnych ma optymalną długość. Zacznij od udowodnienia że każde źródło ma kod optymalny w którym dwa najdłuższe słowa kodowe są rodzeństwem (różnią się tylko ostatnim bitem).
+
Udowodnij, że kod Huffmana dla źródeł binarnych ma optymalną długość. Zacznij od udowodnienia, że każde źródło ma kod optymalny, w którym dwa najdłuższe słowa kodowe są rodzeństwem (różnią się tylko ostatnim bitem).
 
Uogólnij to rozumowanie na źródła o dowolnej ilości symboli i udowodnij optymalność kodu Huffmana w ogólnym przypadku.
 
Uogólnij to rozumowanie na źródła o dowolnej ilości symboli i udowodnij optymalność kodu Huffmana w ogólnym przypadku.
  
Jeśli kod Huffmana jest optymalny, to dlaczego używa się wielu różnych metod kompresji?
+
Jeśli kod Huffmana jest optymalny, dlaczego używa się wielu różnych metod kompresji?

Aktualna wersja na dzień 18:48, 17 wrz 2006

Ćwiczenia

Ćwiczenie 1 [Sfałszowana moneta]

Monetę nazywamy sfałszowaną, jeśli prawdopodobieństwo wypadnięcia orła jest inne niż reszki.

Jak przy pomocy sfałszowanej monety dokonać sprawiedliwego losowania między dwiema osobami?


Ćwiczenie 2 [Moneta dla trzech]

W jaki sposób można przy pomocy monety przeprowadzić losowanie wśród trzech osób?


Ćwiczenie 3 [Magiczna sztuczka]

W pewnej magicznej sztuczce bierze udział magik, jego asystent i ochotnik z widowni. Asystent, którego nadnaturalne zdolności mają być pokazane, jest zamykany w dźwiękoszczelnym pomieszczeniu. Magik daje ochotnikowi 6 pustych kart: 5 białych i jedną zieloną. Ochotnik ma na każdej z kart napisać inną liczbę naturalną pomiędzy 1 a 100. Ochotnik zatrzymuje zieloną kartę, i oddaje pozostałe karty magikowi. Magik, który widział wszystkie pisane liczby, ustawia białe karty w jakiejś kolejności i przekazuje je asystentowi. Asystent po obejrzeniu kart ogłasza jaki numer został napisany na zielonej karcie.

Wyjaśnij jak ta sztuczka działa.


Ćwiczenie 4 [Entropia jako metryka]

Dla rozkładów X i Y definiujemy funkcję . Pokaż, że funkcja ta spełnia warunki metryki:

a)
b)
c) istnieje bijekcja między X a Y
d)

Zadania domowe

Zadanie 1 - Efektywne testy przesiewowe

Załóżmy, że mamy do przebadania pod kątem obecności jakiegoś wirusa próbek krwi. Prawdopodobieństwo pozytywnego wyniku dla każdej próbki jest niewielkie (np. ), a każdy test jest kosztowny. Zamiast badać każdą próbkę osobno, możemy badać zmieszane fragmenty próbek. Zakładamy wtedy, że wynik jest pozytywny jeśli choć jedna z wymieszanych próbek zawierała wirusa. Zakładamy też, że każdą próbkę możemy podzielić na wystarczająco wiele fragmentów. Ostatecznie musimy jednak dla każdej próbki wiedzieć bez wątpliwości czy zawiera wirusa, czy nie. O ile możemy zmniejszyć oczekiwaną liczbę testów do wykonania? Zaprojektuj efektywne badanie dla i i policz oczekiwaną liczbę testów.


Zadanie 2 - Optymalność kodu Huffmana

Udowodnij, że kod Huffmana dla źródeł binarnych ma optymalną długość. Zacznij od udowodnienia, że każde źródło ma kod optymalny, w którym dwa najdłuższe słowa kodowe są rodzeństwem (różnią się tylko ostatnim bitem). Uogólnij to rozumowanie na źródła o dowolnej ilości symboli i udowodnij optymalność kodu Huffmana w ogólnym przypadku.

Jeśli kod Huffmana jest optymalny, dlaczego używa się wielu różnych metod kompresji?