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

Санкт-Петербург, весна 2015

Описание

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

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

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

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

Преподаватели