Город: Санкт-Петербург Казань Язык: Русский English

Алгоритмическая теория информации
Санкт-Петербург / осень 2008, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Алгоритмическая теория информации пытается измерить количество информации в данном сообщении как число битов в наиболее сжатом его описании (колмогоровская сложность). Будут изучены

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

В.А. Успенский, Н.К. Верещагин, А. Шень, Колмогоровская сложность (черновик книги)

Видео лекций: https://www.lektorium.tv/course/22751