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

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

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

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