Введение в теорию информации

Сколько информации содержится в генетическом коде человека? Какова взаимная информация между текстами романов “Война и мир” и “Анна Каренина”?

Чтобы попытаться ответить на эти вопросы (или хотя бы понять, есть в них какой-то смысл), нужно уточнить понятие “количество информации”. Математики и инженеры в разных контекстах используют разные определения информации: комбинаторное определение информации по Хартли, вероятностное определение энтропии Шеннона, алгоритмическое определение сложности по Колмогорову.

В курсе мы изучим эти определения и обсудим их области применения:

— сжатие данных, передача информации в каналах без шума;
— передача информации в дискретных и непрерывных каналах с шумом;
— шифрование с точки зрения теории информации; задача разделения секрета;
— информационные неравенства; приложения теории информации в комбинаторике;
— оптимальный поиск: энтропийные нижние оценки и энтропийные эвристики;
— колмогоровская сложность и метод несжимаемых объектов;
— колмогоровская сложность в нижних оценках сложности вычислений;
— коммуникационная сложность, детерминированные и вероятностные протоколы; информационная сложность.

Страница курса на сайте Computer Science Center