Teoria informacji bada zagadnienia takie jak:
* mierzenie ilości informacji w ciągu danych,
* ograniczenia na przetwarzanie danych
* ograniczenia komunikacji.
Powstała jako próba odpowiedzi na pytania typu:
* jaki jest optymalny kompresor dla danego typu danych?
* jak szybko możemy przesyłać informacje przez kanał komunikacji?
Pytania te dość szybko doprowadziły do dużo bardziej ogólnych pytań, typu:
* jak mierzyć jakość kompresora?
* jak mierzyć prędkość przesyłu danych przez kanał komunikacji?
Podejście oferowane przez teorię informacji różni się od tego oferowanego przez "analizę najgorszego przypadku": w dużo większym stopniu skupia się ona na analizie procesu losowego i działania na "losowych" danych. Podejście to okazuje się skuteczne w praktyce — narzędzia i pojęcia stworzone przez teorię informacji są powszechnie używane przy analizie praktycznie implementowanych rozwiązań: kompresory bezstratne, korekcja błędów, przetwarzanie sygnałów…
Przedmiot zaczniemy od przedstawienia klasycznych zagadnień teorii informacji. Następnie skupimy się na zastosowaniu tych zagadnień: pokażemy dolne i górne granice dla kompresji danych, co więcej pokażemy, że wiele współcześnie stosowanych metod kompresji, pomimo faktu, że wydają się tylko heurystykami, ma teoretyczne podstawy lub teoretyczne analizy (omówimy zarówno bezstratne jak i stratne algorytmy). Oprócz klasycznych wyników pokażemy też te bardziej współczesne oraz pokażemy zastosowania teorii informacji w innych działach informatyki.
Przedmiot jest niezależny (i rozłączny) od przedmiotu Kompresja Danych. W porównaniu do Kompresji Danych ten przedmiot jest nastawiony w o wiele większym stopniu na aspekty teoretyczne, np. gdy Kompresja Danych przedstawia szereg algorytmów kompresji i daje intuicje, dlaczego działają, my pokażemy twierdzenia mówiące o skuteczności niektórych z nich.
Przedmiot ma pewne niewielkie przecięcie z przedmiotem Kody korekcyjne, usunięcie go jest trudne w reżimie wybieralności przedmiotów.
### Zagadnienia:
* Miary informacji: entropia, dywergencja, informacja wspólna, łańcuchy Markowa, nierówność przetwarzania danych
* Kompresja bezstratna: kody o zmiennej długości, źródła ergodyczne, kodowanie uniwersalne
* Przykłady kompresji uniwersalnej: LZ77, kompresja gramatykowa.
* Kompresja stratna: kwantyzacja, kompresja dźwięku i obrazu, transformata Karhunen–Loève, dyskretna transformata kosinusowa (DCT)
* Przepustowość kanałów komunikacji: twierdzenie Shannona.
* Inne zastosowania teorii informacji: uczenie maszynowe, generatory pseudolosowe.
### Wymagania wstępne:
Rachunek prawdopodobieństwa, Algebra, mile widziane: Matematyka dyskretna, Algorytmy i struktury danych.
### Literatura:
1. Thomas M. Cover, Joy A. Thomas, Elements of Information Theory. Wiley Series in Telecommunications, 1991.
2. Gareth A. Jones, Mary J. Jones, Information and Coding Theory. Springer, 2000.
3. David Salomon, Data Compression: The Complete Reference, Springer, 1998
Przedmiot będzie realizował część materiału z kursów innych uczelni: [MIT](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-441-information-theory-spring-2016/lecture-notes/), [University of Chicago](https://home.ttic.edu/~madhurt/courses/infotheory2017/index.html), [Stanford](https://web.stanford.edu/class/ee376a/outline.html).
