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

Алгоритмическая теория информации


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

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

Прочтения курсов

Семестр
осень 2008