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

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

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