Teoria informacji

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.