Введение в теорию информации
Санкт-Петербург / весна 2015, посмотреть все семестры

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

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

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

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

Дата и время Название Место Материалы
04 апреля
17:20–18:55
Комбинаторный подход к определению понятия информации, информация по Хартли, лекция ПОМИ РАН видео
04 апреля
19:15–20:50
Вероятностный подход к определению понятия информации, информация по Шеннону, лекция ПОМИ РАН видео
05 апреля
11:15–12:50
Вокруг теоремы Шеннона об оптимальном кодировании, лекция ПОМИ РАН видео
05 апреля
13:00–14:35
Блоковое кодирование, информационные неравенства, лекция ПОМИ РАН видео
05 апреля
15:35–17:00
Энтропийные профили наборов случайных величин и информационные неравенства, лекция ПОМИ РАН видео
11 апреля
17:20–18:55
Энтропия в классической криптографии, лекция ПОМИ РАН видео
11 апреля
19:15–20:50
Колмогоровская сложность, лекция ПОМИ РАН видео
12 апреля
11:15–12:50
Приложения колмогоровской сложности, лекция ПОМИ РАН видео
12 апреля
13:00–14:35
Случайность по Мартин-Лёфу, лекция ПОМИ РАН видео
12 апреля
15:35–17:10
Коммуникационная сложность, лекция ПОМИ РАН видео