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)
- Podaj przykład trzech zdarzeń losowych, które są parami niezależne, ale wszystkie trzy razem są zależne.
- 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?
- 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}$.
- 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
- 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$.
- 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.).
- 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?
- 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}$)