Kodowanie i teoria informacji 2008

Środa 15¹⁵ - 16⁵⁵ A-1/204 wykład

Kolokwium zaliczeniowe odbędzie się na wykładzie 11 czerwca.

Kolokwium poprawkowe odbędzie się 17 czerwca o godz. 7³⁰ w sali C-11/P.01.

Poprawka kolokwium poprawkowego odbędzie się 24 czerwca o godz. 7³⁰ w sali C-11/P.01.

Ostatnia szansa - 26 czerwca o godz. 13¹⁵ w sali A-5/312.

Literatura

1. T.M.Cover, J.A.Thomas, Elements of Information Theory, Wiley, 2006 (ISBN-13 978-0-471-24195-9)
2. D.J.C.MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003
3. D.Niwiski, M.Strojnowski, M.Wojnarski, Studia informatyczne - Teoria informacji (http://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji)
4. N.Abramson, Teoria informacji i kodowania, PWN, 1969

Tematy wykładów (w przybliżeniu)

1. Wprowadzenie. (27-02-2008)
   [Zasady zaliczenia kursu. Opis tematyki kursu.]
2. Entropia, entropia warunkowa, wzajemna informacja. (5-03-2008)
   [Podstawowe pojęcia; relacje między entropią a wzajemną informacją.]
3. Entropia, entropia warunkowa, wzajemna informacja (cd). (12-03-2008)
   [Nierówność Jensen'a i jej konsekwencje; łańcuchy Markowa.]
4. AEP (asymptotic equipartition property) i jej konsekwencje. (19-03-2008)
   []
5. Entropia w procesach stochastycznych. (26-03-2008)
   [Procesy stochastyczne; procesy Markowa; drugie prawo termodynamiki.]
6. Kompresja danych. (2-04-2008)
   [Pojęcie kodu; kody jednoznacznie dekodowalne; nierówność Krafta i twierdzenie McMillana; kod Shannona.]
7. Kompresja danych (cd). (9-04-2008)
   [Kod Fano; kod Huffmanna; kod Fano-Shannon-Elias.]
8. Dyskretne kanały. (16-04-2008)
   [Definicja kanału; przykłady kanałów; kanały symetryczne; pojemność kanału.]
9. Szybkość kodu dla kanału. (23-04-2008)
   [Rozszerzenie dyskretnego kanału; warunkowe prawdopodobieństwo błędu; szybkość kodu.]
10. Join AEP. Channel Coding Theory. (30-04-2008)
    [Join AEP; Channel Coding Theory; Source-Channel Theory.]
11. Złożoność Kołmogorowa. (7-05-2008)
    [Definicja złożonosci Kołmogorowa; złożoność Kołmogorowa a entropia; złożoność Kołmogorowa dla liczb naturalnych; ciągi niekompresowalne i algorytmicznie losowe.]
12. Złożoność Kołmogorowa (cd). (14-05-2008)
    [Uniwersalne prawdopodobieństwo; nieobliczalność złożoności Kołmogorowa; liczba Chaitina.]
13. Doskonale bezpieczne szyfrowanie. (28-05-2008)
    []
14. Podsumowanie wykładu. Omówienie niektórych zadań. (4-06-2008)
    []
15. Kolokwium zaliczeniowe. (11-06-2008)
    []

Listy zadań

• Lista zadań nr 1 (termin oddania zadań: 2 kwietnia 2008)
• Lista zadań nr 2 (termin oddania zadań: 23 kwietnia 2008)
• Lista zadań nr 3 (termin oddania zadań: 14 maja 2008)
• Lista zadań nr 4 (termin oddania zadań: 4 czerwca 2008)

Zasady zaliczenia kursu

Kurs będzie zaliczany na podstawie kolokwium końcowego. Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4, wyraźnie podpisana. Ocena z kursu może być podwyższona w przypadku wykazania się aktywnością w dziedzinach związanych z tematyką wykładu.

Dodatkowym warunkiem zaliczenia jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych przez wykładowcę zadań. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty.