Teoria informacji: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania (→Moduły) |
|||
Linia 51: | Linia 51: | ||
# [[Teoria_informacji/TI Wykład 13|Złożoność informacyjna Kołmogorowa]] ([[Teoria_informacji/TI Ćwiczenia 13|Ćwiczenia]]) | # [[Teoria_informacji/TI Wykład 13|Złożoność informacyjna Kołmogorowa]] ([[Teoria_informacji/TI Ćwiczenia 13|Ćwiczenia]]) | ||
# [[Teoria_informacji/TI Wykład 14|Stała Chaitina]] ([[Teoria_informacji/TI Ćwiczenia 14|Ćwiczenia]]) | # [[Teoria_informacji/TI Wykład 14|Stała Chaitina]] ([[Teoria_informacji/TI Ćwiczenia 14|Ćwiczenia]]) | ||
− |
Aktualna wersja na dzień 08:18, 24 sie 2006
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
- Information and Coding Theory, Gareth A. Jones and J. Mary Jones, Springer, 2000.
- Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
- An Introduction to Kolmogorov Complexity and Its Applications, Ming Li and Paul Vitanyi, Springer, 1997.
- Information Theory, Inference, and Learning Algorithms, David J.C. MacKay, Cambridge University Press, 2003.
Moduły
- Notacja i kody (Ćwiczenia)
- Pojęcie entropii (Ćwiczenia)
- Optymalne kodowanie - kod Huffmana (Ćwiczenia)
- Optymalne kodowanie - kod Shannona-Fano (Ćwiczenia)
- Entropia zmiennej losowej i wzajemna informacja (Ćwiczenia)
- Doskonale bezpieczne szyfrowanie (Ćwiczenia)
- Kanały transmisji i ich przepustowość (Ćwiczenia)
- Odczytywanie przesłanej wiadomości (Ćwiczenia)
- Poprawa wydajności kanału (Ćwiczenia)
- Efektywne kodowanie wiadomości (Ćwiczenia)
- Twierdzenie Shannona o kodach (Ćwiczenia)
- Dowód Twierdzenia Shannona (Ćwiczenia)
- Złożoność informacyjna Kołmogorowa (Ćwiczenia)
- Stała Chaitina (Ćwiczenia)