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 by Gareth A. Jones and J. Mary Jones, Springer, 2000.
2. Elements of Information Theory by Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
3. An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitanyi, Springer, 1997.

Moduły

1. Notacja i kody (Ćwiczenia)