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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Nie podano opisu zmian
Dorota (dyskusja | edycje)
376 edycji
 
(Nie pokazano 13 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
== Zadanie 1: kompresja danych ==
== Ćwiczenia ==


=== Treść ===
{{cwiczenie|1 [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?}}


# Przygotuj trzy pliki, zawierające tekst w trzech różnych językach: polskim, angielskim i trzecim dowolnie wybranym. Każdy plik powinien zawierać przynajmniej 50000 znaków. Duży wybór tekstów w różnych językach można znaleźć na przykład na stronie [http://gutenberg.org Projektu Gutenberg].
# Napisz program <tt>litery</tt>, który czyta plik tekstowy o podanej nazwie (przekazanej jako parametr wywołania programu) i wypisuje wszystkie symbole występujące w pliku wraz z ich częstością, w formie: '''A 0.134 <nowa_linia> b 0.126 ...''' Nie musi poprawnie wypisywać znaków narodowych. Program powinien wypisać też entropię binarną <!--link--> obliczonego rozkładu prawdopodobieństwa. Uruchom program dla trzech przygotowanych wcześniej plików, porównaj otrzymane wyniki.
# Napisz program <tt>huffman</tt>, który czyta plik tekstowy o podanej nazwie i oblicza kod Huffmana <!--link--> dla rozkładu symboli występujących w tym pliku. Program powinien wypisać otrzymany kod w formie: '''A 001 <nowa_linia> b 0001010 ...''' <br/> Napisz program <tt>shannon</tt>, który oblicza kod Shannona-Fano. <!--link--> Uwaga: aby otrzymać poprawny kod Shannona-Fano, nie można korzystać w obliczeniach z liczb zmiennoprzecinkowych (dlaczego?), jedynie z liczb całkowitych. Prawdopodobieństwo danego symbolu można pomnożyć przez ustaloną liczbę całkowitą (najlepiej potęgę 2, np. 65536) i zaokrąglić, otrzymując w ten sposób reprezentację całkowitoliczbową.
<!-- Uwaga: czy na wykladzie jest konstruktywna metoda obliczania kodu S-F? -->
# Napisz program <tt>kompresuj</tt>, który koduje podany plik tekstowy '''plik.txt''' za pomocą kodu Huffmana i Shannona-Fano. Wynik kodowania powinien zostać zapisany do plików '''plik.huf''' i '''plik.sf'''. Dla ułatwienia można każdy bit wynikowego kodu zapisywać na oddzielnym bajcie, jako znak "0" lub "1".
# Uruchom program <tt>kompresuj</tt> dla trzech przygotowanych plików tekstowych. Dla każdego z nich porównaj następujące wielkości:
#* liczbę bitów oryginalnego pliku,
#* liczbę znaków "0" i "1" w plikach '''.huf''' i '''.sf''',
#* entropię rozkładu prawdopodobieństwa symboli w oryginalnym pliku. <br/> Czy te wielkości zależą od języka kompresowanego tekstu?
# Napisz program <tt>kompresujbloki</tt>, który kompresuje podany plik metodą Huffmana i Shannona-Fano, zastosowanymi do bloków długości 2, 3, 4 lub więcej (tzn. kod jest generowany nie dla pojedynczych symboli, lecz dla par, trójek, czwórek ... sąsiednich symboli). Porównaj efektywność kompresji pojedynczych symboli i bloków, pod względem:
#* rozmiaru zakodowanego pliku,
#* rozmiaru kodu (aby móc wykonać dekompresję, kod musi być zapisany razem z zakodowaną informacją),
#* złożoności czasowej i pamięciowej algorytmu.


<!-- Prowadzący laboratorium może zrezygnować z fragmentów zadań, np. zrobić tylko kodowanie Huffmana, bez Shannona-Fano -->
{{cwiczenie|2 [Moneta dla trzech]|mdt|
W jaki sposób można przy pomocy monety przeprowadzić losowanie wśród trzech osób?}}


=== Rozwiązanie ===


Rozwiązanie zadania powinno zawierać:
{{cwiczenie|3 [Magiczna sztuczka]|ms|
* wykonywalne programy,  
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.
* kody źródłowe programów,
* pliki tekstowe wykorzystane do eksperymentów,
* raport z analizą otrzymanych wyników i odpowiedziami na postawione wyżej pytania.
Pliki źródłowe i raport należy ''podpisać'' imieniem i nazwiskiem autora.


Ocenie podlegać będzie poprawność implementacji oraz umiejętność analizy i interpretacji wyników eksperymentalnych. Dodatkowe programy, eksperymenty, komentarze będą mile widziane. Nie będzie natomiast brana pod uwagę efektywność czasowa i pamięciowa programów.
Wyjaśnij jak ta sztuczka działa.}}


== Zadanie 2 ==


Rozważmy trzy warianty kompresji pliku tekstowego, które wykorzystują korelację między sąsiednimi symbolami do osiągnięcia większego stopnia kompresji:
{{cwiczenie|4 [Entropia jako metryka]|ejm|
# Kodowanie Huffmana zastosowane do bloków 2 symboli.
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:
# Kodowanie kolejnego symbolu pliku, <math>a_{n+1}</math>, za pomocą kodu Huffmana, który zależy od symbolu poprzedniego, <math>a_n</math>. W algorytmie tym, dla każdego symbolu <math>a</math> występującego w pliku, obliczany jest warunkowy rozkład prawdopodobieństwa następnego symbolu <math>b</math>, pod warunkiem <math>a</math>: <math>p(b|a)</math>. Dla takiego rozkładu obliczany jest kod Huffmana.
: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 ==
Różne warianty kompresji:
 
* blokami o długości 2
=== Zadanie 1 - Efektywne testy przesiewowe ===
* przewidywanie kolejnego symbolu na podstawie poprzedniego
 
* od końca: przewidywanie poprzedniego na podstawie następnego
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.
Który wariant powinien być najlepszy? Porównaj (stopień kompresji, złożoność pamięciowa), udowodnij, skomentuj, zaimplementuj.
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.
Przeprowadź rozumowanie dla dwóch sytuacji: słowa kodowe muszą mieć długość całkowitą lub nie muszą. (dla zainteresowanych: zob. kodowanie arytmetyczne)
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.
 
 
=== 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?

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ę d(X,Y)=H(X|Y)+H(Y|X). Pokaż, że funkcja ta spełnia warunki metryki:

a) d(X,Y)≥0
b) d(X,Y)=d(Y,X)
c) d(X,Y)=0⇔ istnieje bijekcja między X a Y
d) d(X,Y)+d(Y,Z)≥d(X,Z)

Zadania domowe

Zadanie 1 - Efektywne testy przesiewowe

Załóżmy, że mamy do przebadania pod kątem obecności jakiegoś wirusa N próbek krwi. Prawdopodobieństwo pozytywnego wyniku p dla każdej próbki jest niewielkie (np. p=0,01), 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 p=0,01 i N=300 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?

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_3&oldid=51704”