Informacje na temat egzaminu

Egzamin rozpocznie się we wtorek 10.02 o godz. 10:00 w sali 3320. Plan egzaminu jest następujący:

• godz. 10:00 -- 11:00 - teoria (nie wolno korzystać z notatek i innych materiałów)
• godz. 11:00 -- 11:15 - przerwa
• godz. 11:15 -- 12:45 - zadania (wolno korzystać z notatek i innych materiałów)

Na teorii można się spodziewać pytań podobnych jak na kolokwium ("podaj twierdzenie X", mogą też pojawić się pytania o proste dowody niektórych twierdzeń). Również część zadaniowa będzie podobna do tej z kolokwium.

W czasie egzaminu nie wolno wychodzić z sali (za wyjątkiem przerwy). Osoby które muszą wyjść z obiektywnych przyczyn (np. medycznych) proszone są o kontakt z prowadzącym przed rozpoczęciem egzaminu.

21.1.15 Wykład "Kryptografia oparta na szumach i kryptografia kwantowa"

• Modele Wynera, Csiszara i Kornera oraz Maurera (wg. tego)
  
• kryptografia kwantowa (wg. [NSW], Rozdział 6)

14.1.15: Ćwiczenia (SD)

Skończyliśmy dowód Lematu 2.2 stąd.

Powiedzieliśmy co to są ektraktory dwu-źródłowe i że iloczyn skalarny nad Z2 jest jednym z nich (patrz tu, Rozdział 1)

14.1.15 Wykład: "Ekstraktory losowości"

Wspomnieliśmy na temat zastosowań (np. w kryptografii odpornej na wycieki). Pokazaliśmy Lemat LHL z dowodem (patrz tu, Rozdział 3)

7.1.15: Ćwiczenia (SD)

• Punkt (iii) i (iv) z Lematu 2 stąd.
• Fakt, że Delta(A;B|C) = Delta((A,C),(B,C))
• Średnia min-entropia warunkowa (patrz Rozdział 2.4 tu) 

7.1.15 Wykład: "Schematy autentykacji i wstęp do ekstraktorów losowości"

• teorio-informacyjnie bezpieczne schematy autentykacji i ich związek z funkcjami haszująvymi (Rozdział 4.5 ze [Stinson] -- dość pobieżnie, bardziej szczegółowo Rozdział 4.5.1).
• odległość statystyczna (patrz np. tu Definition 1) oraz wstęp do ekstraktorów losowości (to samo miejsce, Rozdział 2)

17.12.14: Ćwiczenia (SD)

Dzielenie sekretu: n-out-of-n (patrz np. tu, Rozdział 6.1) oraz protokół Shamira. 

17.12.14 Wykład: "Szyfrowanie"

• Twierdzenie Shannona i one-time pad (wg. [NSW], Wykład 6 -- przy czym Tw Shannona bez drugiej części)
• Generatory pseudolosowe i szyfrowanie za ich pomocą (szyfry strumieniowe) -- wg mojego wykładu do którego slajdy są dostępne tu. (Wykład 1, slajdy 32-29 i Wykład 2 slajdy 16-19, 22-32).

21.1.15: Ćwiczenia (SD)

Twierdzenie 1 z stąd.

10.12.14: Ćwiczenia (DM)

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.

e.x. 7.3, 7.7 (pierwsza część), 7.9 z [JJ]

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)

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]

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]

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.

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])

19.11.14: Ćwiczenia (SD)

Exercises 4.10, 4.16, 4.18 z [JJ],

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
• 
  

12.11.14: Ćwiczenia (SD)

• Dokończenie Zad 1 z [NSW]
• Exercises 4.12, 4.13, 4.18 z [JJ]

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]).

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]

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).

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.

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

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)

15.10.14: Ćwiczenia (DM)

15.10.14: Ćwiczenia (SD)

• Zadania 2.14, 2.15, 2.17 z [CT]

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 (DM)

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,

Pokazaliśmy też diagram Venna dla entropii i informacji wzajemnej:

1.10.14: Ćwiczenia (DM)

1.10.14: Ćwiczenia (SD)

wprowadziliśmy pojęcie entropii warunkowej (strona 17 książki [CT])

pokazaliśmy regułę łańcuchową dla entropii w wersji tylko z dwiema zmiennymi XY (Tw. 2.2.1 z [CT])

zrobiliśmy Ćwiczenia 2,4 i Zadanie 3 z [NSW]

zadanie 2.5 z [CT] zostało do domu

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: