Teoria informacji

http://warsztatywww.wikidot.com/www6:teoria-informacji

Prowadzący

Marcin Kotowski
Michał Kotowski

Opis

Dlaczego porysowana płyta CD działa (czasami)? Jak wydajnie skompresować plik? Czy można porozumiewać się bezbłędnie przez zaszumiony kanał? Które liczby są mniej, a które bardziej losowe? Na te i na inne pytania odpowiada stworzona w latach 40. XX wieku przez Claude'a Shannona teoria informacji. Oprócz tego, że dostarcza ona ciekawych problemów matematycznych, znalazła praktyczne zastosowanie w przetwarzaniu sygnałów, kryptografii, sztucznej inteligencji czy kompresji plików.

Warszaty będą poświęcone omówieniu podstaw tej teorii - zarówno warstwy teoretycznej, jak i przykładowych zastosowań.

Program zajęć

Tematem pierwszych zajęć będą: entropia Shannona ($H(X)=-\sum p_i\log p_i$) i jej podstawowe własności, pojęcie kodu. Potem omówimy różne interpretacje entropii i jej związki z kodowaniem i kompresją (np. jak entropia wiąże się z możliwością optymalnej kompresji danych). Przewidziane będzie dużo zadań, łatwych i trudnych. Następnie, zależnie od zainteresowań uczestników i własnej decyzji, zahaczymy o jeden lub więcej z następujących tematów:

• złożoność Kołmogorowa (czyli co to znaczy, że ciąg znaków jest "losowy")
• zastosowania entropii we wnioskowaniu statystycznym
• kanały (wbrew pozorom nie chodzi tu o "Kanał" A. Wajdy)
• kwantowa teoria informacji (wyłącznie w ramach tzw. deseru, bo solidne wprowadzenie do tematu przekracza ramy czasowe warsztatów)

Zajęcia będą miały formę wykłado-ćwiczeń, czyli prezentacja teorii przeplatana zadaniami do samodzielnego rozwiązania. Będą też dla chętnych zadania do zakodowania (z gatunku - napisać program, który coś liczy, i omówić wyniki wraz z interpretacją).

Wymagania

• pojęcia: funkcja wykładnicza, logarytm, funkcja wypukła
• elementarna znajomość rachunku prawdopodobieństwa (wiedzieć, co to wartość oczekiwana, zdarzenie losowe, co to znaczy, że dwa zdarzenia są niezależne)
• (opcjonalnie) umiejętność programowania w czymkolwiek

Zadania kwalifikacyjne

Poniższe zadania mają zróżnicowany stopień trudności. Nie trzeba zrobić wszystkich, by się zakwalifikować, ale oczywiście im więcej, tym lepiej - oczekujemy, że chętny uczestnik zrobi co najmniej 5 zadań. W razie pytań, wątpliwości itd. - nie wahaj się napisać: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim.

Zadania należy przesyłać na adres: moc.liamg|1ikswotok.lahcim#moc.liamg|1ikswotok.lahcim (można na raty)

1. Podaj przykład trzech zdarzeń losowych, które są parami niezależne, ale wszystkie trzy razem są zależne.
2. Mamy monetę, na której orzeł wypada z nieznanym prawdopodobieństwem $p$. Rzuciliśmy 1000 razy i wypadło 500 orłów. Co możemy stąd wywnioskować na temat prawdopodobieństwa, że moneta jest uczciwa ($p=\frac{1}{2}$)? Czy trzeba przyjąć jakieś dodatkowe założenia?
3. Urna zawiera $b$ kul białych i $c$ kul czarnych. Wykonujemy kolejno następujące doświadczenie: losujemy z urny kulę, a następnie wkładamy ją z powrotem do urny, a wraz z nią dokładamy do urny kulę tego samego koloru. Udowodnij, że prawdopodobieństwo wylosowania w n-tym losowaniu kuli białej jest $\frac{b}{b+c}$.
4. Oblicz maksimum funkcji: $f(x) = -x\log x - (1-x)\log(1-x) + Ax + B(1-x)$, gdzie $\log$ oznacza logarytm dwójkowy, a $A, B$ - liczby rzeczywiste. taka funkcja pojawia się przy obliczaniu przepustowości pewnego kanału
5. Mamy $n \geq 3$ monet, z których jedna jest fałszywa (może być lżejsza lub cięższa od reszty). Do dyspozycji mamy wagę szalkową, na szalki której możemy kłaść monety. Waga wskazuje zawsze jedną z trzech możliwości: lewa szalka cięższa, prawa szalka cięższa lub równowaga. Jakie jest maksymalne $n$, dla którego możemy rozpoznać fałszywą monetę (i stwierdzić, czy jest cięższa, czy lżejsza od reszty) przy pomocy co najwyżej $k$ ważeń? Podać strategię ważenia monet dla $k=3$ i $n=12$.
6. Rozważmy następującą sztuczkę karcianą: sztukmistrz prosi ochotnika o wylosowanie 5 kart z talii 52-kartowej. Następnie wybiera jedną z nich i zakrywa ją, a pozostałe układa w określonym porządku od lewej do prawej. Pomocnik sztukmistrza, który przez cały czas stał za drzwiami, wchodzi, ogląda 4 odkryte karty i natychmiast zgaduje, jaka jest zakryta karta. Wyjaśnić, jak to możliwe (matematycznie, tj. bez odwoływania się do telepatii itd.).
7. W urnie są 1 kula biała i 1 czarna. Rzucamy kostką i dokładamy do urny tyle kul czarnych ile wypadło oczek, a następnie losujemy z urny bez zwracania dwie kule. Jakie jest prawdopodobieństwo, że wylosowane kule mają ten sam kolor? Jakie jest prawdopodobieństwo, że na kostce wypadła jedynka, jeśli wiemy, że wylosowano kule różnokolorowe?
8. Alicja i Bob mogą przesyłać sobie (oboje jednocześnie) k-bitowe ciągi przez wadliwy kabel. Kabel działa tak, że jeśli na danej pozycji ciągu oboje wysłali 0, to obie strony dostają na wyjściu 0, a jeśli którakolwiek wysłała 1, to obie dostają 1. Alicja i Bob chcą przesyłać sobie określone znaki (np. liczby ze zbioru 1..N), każdy znak kodując jako ciąg k bitów. Oczywisty protokół pozwala na komunikację z prędkością "2 znaki/2 bity" (tj. N=2, k=2). Wymyśl protokół, który pozwoli osiągnąć lepszą prędkość (czyli dla pewnych N, k mieć $\frac{N}{2^k} > \frac{1}{2}$)