Teoria informacji

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

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

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.