City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Algorithmic Information Theory
Saint Petersburg / autumn 2008, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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