Teoria informacji

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Wprowadzenie w teorię przydatną w wielu zastosowaniach informatyki, jak m.in. w kryptografii, w modelowaniu języka naturalnego, czy w bio-informatyce. Teoria ta okresla ilościowo informację zawartą w zmiennej losowej lub w ciągu bitów, a także kryteria optymalnego przesyłania zakodowanej wiadomości przez zaszumiony kanał.

Sylabus

Autorzy

• Damian Niwiński
• Michał Strojnowski
• Marcin Wojnarski

Wymagania wstępne

• Matematyka dyskretna
• Rachunek prawdopodobieństwa i statystyka
• Języki, automaty i obliczenia

Zawartość

• Od gry w 20 pytań do pojęcia entropii. Nierówność Krafta.
• Kody Huffmana i Shannona-Fano.
• Entropia warunkowa, pojęcie informacji.
• Pierwsze twierdzenie Shannona o optymalnym kodowaniu.
• Przesyłanie wiadomości przez zaszumiony kanał, przepustowość kanału.
• Poprawa wydajności kanału, stopa kodu.
• Główne twierdzenie Shannona o optymalnym przesyłaniu informacji.
• Kody korygujące błędy.
• Złożoność informacyjna Kołmogorowa i jej własności. Liczba Chaitina.
• Złożoność informacyjna Kołmogorowa a entropia Shannona - uniwersalny test Martina Loffa.

Literatura

1. Information and Coding Theory, Gareth A. Jones and J. Mary Jones, Springer, 2000.
2. Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
3. An Introduction to Kolmogorov Complexity and Its Applications, Ming Li and Paul Vitanyi, Springer, 1997.
4. Information Theory, Inference, and Learning Algorithms, David J.C. MacKay, Cambridge University Press, 2003.

Moduły

1. Notacja i kody (Ćwiczenia)
2. Pojęcie entropii (Ćwiczenia)
3. Optymalne kodowanie - kod Huffmana (Ćwiczenia)
4. Optymalne kodowanie - kod Shannona-Fano (Ćwiczenia)
5. Entropia zmiennej losowej i wzajemna informacja (Ćwiczenia)
6. Doskonale bezpieczne szyfrowanie (Ćwiczenia)
7. Kanały transmisji i ich przepustowość (Ćwiczenia)
8. Odczytywanie przesłanej wiadomości (Ćwiczenia)
9. Poprawa wydajności kanału (Ćwiczenia)
10. Efektywne kodowanie wiadomości (Ćwiczenia)
11. Twierdzenie Shannona o kodach (Ćwiczenia)
12. Dowód Twierdzenia Shannona (Ćwiczenia)
13. Złożoność informacyjna Kołmogorowa (Ćwiczenia)
14. Stała Chaitina (Ćwiczenia)