Teoria informacji
Z Studia Informatyczne
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, informacja.
- Pierwsze twierdzenie Shannona o optymalnym kodowaniu.
- Kanały, utrata informacji, poprawa wydajności, przepustowość.
- Główne twierdzenie Shannona o optymalnym przesyłaniu informacji.
- Złożoność informacyjna Kołmogorowa. Liczba Chaitina.
- Złożoność informacyjna Kołmogorowa a entropia Shannona - uniwersalny test Martina Loffa.
Literatura
- "Information and Coding Theory" by Gareth A. Jones and J. Mary Jones, Springer, 2000.
- "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
