Blog z materiałami z przedmiotu Teoria Informacji prowadzonego w roku akademickim 2014/15 na Uniwersytecie Warszawskim.
Wednesday, December 17, 2014
10.12.14: Ćwiczenia (DM)
Tuesday, December 16, 2014
10.12.14: Ćwiczenia (SD)
- Omówiliśmy kody Reeda-Solomona (wykazaliśmy liniowość kodu, oraz pokazaliśmy jaki jest jego dystans, ale nie pokazaliśmy algorytmu odkodowywania). Informacje na temat tego kodu można znaleźć np. tu.
- Zrobiliśmy Ćwiczenia 7.4, 7.7
10.12.14 Wykład: "Kody liniowe - cd "
Kontynuowaliśmy tematykę kodów liniowych według książki [JJ]. Zrobiliśmy:
- kody Hamminga (Rozdział 4.4, bez ćwiczeń, przykładów i tego co jest na stronie 136),
- macierz standardową (Rozdział 7.6)
- odkodowywanie syndromem (Rozdział 7.7 bez Przykładu 7.45 i Ćwiczenia 7.9)
Tuesday, December 9, 2014
3.12.14: Ćwiczenia (SD)
- pokazaliśmy, że kody Hamminga są linowe jeśli n jest podzielne przez 4,
- Exercise 7.2, Twierdzenia 7.23 i 7.27, wyprowadzenie Eq. (7.3) z [JJ]
3.12.14: Wykład "Kody linowe"
Kontynowaliśmy temat konstrukcji kodów. Omówiliśmy następujące zagadnienia:
- macierze Hadamarda (Rozdział 6.6 książki [JJ] bez ćwiczeń 6.14 i 6.15
- kody liniowe: Rozdziały 7.1 - 7.3 ksiązki [JJ]
Thursday, December 4, 2014
03.12.14: Ćwiczenia (DM)
- Przypomnienie różnych podstawowych faktów z algebry liniowej
- Macierze i kody Hadamarda:
- dlaczego H_n+1 = (H_n H_n | H_n -H_n) to m.h. dla H_n - m.h.
- H_0= (1). Dlaczego H_n daje kody liniowe?
- dlaczego dla m != 2^k, to H - hadamarda m x m daje kody, które są liniowe?
- Zadania 6.4, 7.1, 7.2 z [JJ]
- Jak powstaje macierz parzystości z macierzy generującej w postaci systematycznej [JJ str. 129]
Wednesday, November 26, 2014
26.11.14: Ćwiczenia (DM)
- Omówienie zadania "Do przemyślenia" z poprzednich ćwiczeń
- E.x. 5.9, 6.18, 6.20, 6.21 z [JJ]
- Dowód, że 1/n * log(n po t) zbiega do H(t/n) dla n -> inf, t/n stałe (str 110 w [JJ])
26.11.14: Ćwiczenia (SD)
Policzyliśmy wyprowadzenie granicy ze strony 110 książki [JJ] (używając wzoru Stirlinga).
Exercises 6.18, 6.20 i 6.21.
Exercises 6.18, 6.20 i 6.21.
26.11.14: Wykład "Optymalność Twierdzenia Shannona, ograniczenia Hamminga i Gilberta-Varshamova"
Pokazaliśmy dowód optymalności Twierdzenia Shannona (Rozdział 5.5 z książki [JJ]).
Następnie pokazaliśmy ograniczenie Hamminga (Rozdział 6.4 z [JJ]) i ograniczenie Gilberta-Varshamova (Rozdział 6.5 z [JJ]).
Rozpoczęliśmy też wstęp do macierzy Hadamarda (Rozdział 6.6 z [JJ])
Wednesday, November 19, 2014
19.11.14: Wykład "Odległość Hamminga i Twierdzenie Shannona"
Wprowadziliśmy pojęcie odległości Hamminga (Rozdział 5.3 z [JJ]) i udowodniliśmy Drugie Twierdzenie Shannona (Rozdział 5.4 z [JJ]).
19.11.14: Ćwiczenia (DM)
- Dokończone e.x. 4.17 z [JJ] (pojemność sumy kanałów)
- Obliczyć pojemność kanału (średnik oddziela wiersze, przecinek liczby): (1, 0; 1/2, 1/2)
- e.x. zad 4.10 z [JJ] (pojemność iloczynu kanałów)
- E.x. 5.4 i 5.6 (odległość Hamminga), E.x. 5.8 z [JJ]
- Obliczyć pojemność:
(1, 0, 0, 0, 0; 1/2, 1/2, 0, 0, 0; 0, 0, 1/2, 0, 1/2; 0, 0, 1/2, 1/2, 0; 0, 0, 0, 1/2, 1/2) - Do przemyślenia: Kanał dostaje na wejściu x \in {0,1}^n, a na wyjściu ten sam ciąg z pominiętym jednym jednostajnie losowo wybranym bitem (czyli ciąg y \in {0,1}^(n-1)). Pokazać, że pojemność tego kanału to przynajmniej (N - log N - 1).
12.11.14: Ćwiczenia (DM)
- Przypomnienie pojemności kanału BSC
- Dokończenie Zad 1 z [NSW]
- 4.13, 4.15, 4.18 z [JJ]
- 4.17 z [JJ] - niedokończone
Wednesday, November 12, 2014
12.11.14: Wykład "Przepustowość i reguły decyzyjne"
Wprowadziliśmy pojęcie przepustowości kanału i pokazaliśmy, że jest to pojęcie dobrze zdefiniowane (Rozdział 4.8 z [JJ]).
Potem mówiliśmy o regułach decyzyjnych (Rozdziały 5.1 - 5.2 z [JJ]).
Potem mówiliśmy o regułach decyzyjnych (Rozdziały 5.1 - 5.2 z [JJ]).
5.11.14: Ćwiczenia (DM)
- Example 3.18, Exercise 3.5 z [JJ]
- Obliczanie Q_{ij} - str 59-60 w [JJ], Example 4.5
- Exercise 4.1 z [JJ]
- Ćw 2 z [NSW] (bez przepustowości)
- Częściowo: Zad 1 z [NSW]
Wednesday, November 5, 2014
5.11.14: Ćwiczenia (SD)
- Example 3.18, Exercise 3.5 z [JJ]
- Obliczanie Q_{ij} - str 59-60 w [JJ],
- Exercise 4.1 z [JJ]
- Ćw 1 i 2 z [NSW] (bez przepustowości)
- Do domu zostało Zad 1 z [NSW]
5.11.14: Wykład "Kody Shannona-Fano, Pierwsze Twierdzenie Shannona, wstęp do kanałów"
Pokazaliśmy kodowanie Shannona-Fano (Rozdział 3.4 z książki [JJ]) i Pierwsze Twierdzenie Shannona (Rozdział 3.6 z [JJ]).
Zaczęliśmy też mówić o kanałach informacyjnych (Rozdziały 4.1 - 4.7 z [JJ], przy czym zagadnienia związane z entropią i informacją wzajemną potraktowaliśmy pobieżnie, bo to już było).
Zaczęliśmy też mówić o kanałach informacyjnych (Rozdziały 4.1 - 4.7 z [JJ], przy czym zagadnienia związane z entropią i informacją wzajemną potraktowaliśmy pobieżnie, bo to już było).
Monday, November 3, 2014
29.10.14: Ćwiczenia (wspólne)
- ćw 3 z ćwiczeń 3 z [NSW],
- Jak kodować pary ciągów binarnych (elementów {0,1}^*x{0,1}^*)?
- Ex 2.10, 2.13, 2.14 z [JJ]
- Ex 2.12 (Nie zostało do końca formalnie udowodnione)
- Porównać optymalne kody dla źródeł o prawdopodobieństwach:
- 1/3, 2/3
- 0, 1/3, 2/3
29.10.14: Wykład "Kody Huffmana"
Wykład prowadzony był według następujących fragmentów książki [JJ]:
- Rozdział 2 (bez 2.5): Średnia długość kodu, (binarne) Kody Huffmana z dowodem optymalności, kodowanie kilku znaków na raz
- Rozdział 3.3: Średnia długość kodu jest nie większa niż entropia źródła. Definicja Wydajności oraz Redundancji kodu.
Wednesday, October 22, 2014
22.10.14: Ćwiczenia (wspólne)
- ćw 1, ćw 2, ćw 3, ćw 4 z [NSW]
- konstrukcja kodu o długościach słów kodowych: 1, 2, 2, 2, 2, 2, 3, 3, 3 dla alfabetu {0,1,2}
- przykład kodu jednoznacznie dekodowalnego i nieskończonego słowa, które można zdekodować na 2 sposoby
Tuesday, October 21, 2014
15.10.14: Ćwiczenia (DM)
- ćw 3 [NSW] (TI Ćwiczenia 5)
- przykład zmiennej losowej o dużej entropii, ale małej min entropii
- Przykład zmiennych losowych X i Y, dla których warunkowa min entropia H_inf(X|Y) (jeżeli ją zdefiniujemy analogicznie jak dla zwykłej entropii) jest większa niż min entropia H_inf(X)
- Zadania 2.5, 2.14, 2.15, 2.16, 2.29 c, d, 2.32 z [CT]
- do przemyślenia w domu: jak za pomocą nieuczciwej monety (reszka wypada z prawdopodobieństwem p \in (0, 1)) wylosować wartość z prawdopodobieństwem równym (dokładnie) 1/2?
8.10.14: Ćwiczenia (DM)
- ćw 3, 4, zad 3 z [NSW] (TI Ćwiczenia 2)
- reguła łańcuchowa dla informacji wzajemnej (Tw. 2.5.2 z [CT])
- zad 3 z [NSW] (TI Ćwiczenia 2) (Entropia Kolizji i Min Entropia)
- Przykład 2.3.1 z [CT]
1.10.14: Ćwiczenia (DM)
- ćw 1, ćw 2 z [NSW] (TI Ćwiczenia 2)
- nierówność Jensena
- minimalna i maksymalna wartość entropii zmiennej losowej o n wartościach
- Entropia pary, Entropia warunkowa - definicja, chain rule, przypadek zmiennych niezależnych
- przykład, że H(x|y) != H(y|x)
Friday, October 17, 2014
15.10.14: Wykład "Łańcuchy Markowa, nierówność Fano"
Wykład prowadzony był według następujących fragmentów książki [CT]:
- Rozdział 2.8 (cały) -- definicja łańcuchów Markowa, nierówność o przetwarzaniu danych i dwa proste wnioski płynące z niej,
- Rozdział 2.10 (do połowy strony 40) -- nierówność Fano i jej optymalność.
8.10.14: Ćwiczenia (SD)
- reguła łańcuchowa dla informacji wzajemnej (Tw. 2.5.2 z [CT])
- ograniczenie na entropię ciągu zmiennych losowych (Tw. 2.6.6 z [CT])
- Ćwiczenie 4 i Zadanie 2 z [NSW]
8.10.14: Wykład "Entropia i informacja wzajemna"
Dokończyliśmy wyprowadzanie pojęcia entropii z aksjomatów, wg. Rozdziału 1.2 skryptu [BT] (krok 5 na stronie 7).
Reszta wykładu była prowadzona według następujących fragmentów książki [CT].
- Rozdział 2.3 (cały) -- dywergencja Kullbacka i Leiblera, informacja wzajemna,
- Rozdział 2.4 (cały) -- związki między entropią i informacją wzajemną,
- Rozdział 2.5 (do strony 23 włącznie) -- reguła łańcuchowa dla entropii, warunkowa informacja wzajemna,
- Rozdział 2.6 (cały, z tym, że nierówność Jensena potraktowaliśmy pobieżnie):
- nierówność Jensena, nieujemność dywergencji Kullbacka i Leiblera (Tw. 2.6.3),
- nieujemność informacji wzajemnej (wniosek z Tw. 2.6.3),
- Tw. 2.6.4 o tym, że entropia jest ograniczona przez logarytm z rozmiaru przeciwdziedziny zmiennej losowej,
- Tw. 2.6.5 o tym, że warunkowanie nie może zwiększyć entropii,
1.10.14: Ćwiczenia (SD)
1.10.14: Wykład "Wprowadzenie do pojęcia entropii"
Dokonaliśmy wstępu do pojęcia entropii i wyprowadziliśmy wzór na entropię z aksjomatów entropii. Wykład był prowadzony według Rozdziału 1.2 skryptu [BT] (oprócz kroku 5 na stronie 7, którego nie zdążyliśmy pokazać).
Pokazaliśmy też wykres entropii binarnej:
Pokazaliśmy też wykres entropii binarnej:
Subscribe to:
Posts (Atom)