Teoria informacji/TI Ćwiczenia 3: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
== Ćwiczenia == | |||
{{cwiczenie|[Sfałszowana moneta]|mdt| | |||
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?}} | |||
{{cwiczenie|[Moneta dla trzech]|mdt| | |||
W jaki sposób można przy pomocy monety przeprowadzić losowanie wśród trzech osób?}} | |||
{{cwiczenie|[Magiczna sztuczka]|ms| | |||
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.}} | |||
{{cwiczenie|[Entropia jako metryka]|ejm| | |||
Dla rozkładów X i Y definiujemy funkcję <math>d(X,Y)=H(X|Y)+H(Y|X)</math>. Pokaż że funkcja ta spełnia warunki metryki: | |||
:a) <math>d(X,Y)\ge 0</math> | |||
:b) <math>d(X,Y)=d(Y,X)</math> | |||
:c) <math>d(X,Y)=0 \Leftrightarrow</math> istnieje bijekcja między X a Y | |||
:d) <math>d(X,Y)+d(Y,Z) \ge d(X,Z)</math>}} | |||
== Zadania domowe == | |||
=== 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. | |||
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 <math>p=0,01</math> i <math>N=300</math> i policz oczekiwaną liczbę testów. | |||
Wersja z 17:39, 23 sie 2006
Ćwiczenia
Ćwiczenie [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 [Moneta dla trzech]
Ćwiczenie [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 [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.
