Лекции А. Шеня по алгоритмической теории информации

57 подписчиков

С 13-го по 27-е сентябра в рамках Computer Science клуба при ПОМИ РАН Александр Шень (Институт проблем передачи информации им. А.А. Харкевича РАН/LIF Marseille) прочтёт курс лекций по алгоритмической теории информации. Алгоритмическая теория информации пытается измерить количество информации в данном сообщении как число битов в наиболее сжатом его описании (колмогоровская сложность). Будут изучены * определение и свойства сложности; * условная сложность и сложность пары; * связь с комбинаторикой и шенноновской теорией информации; * сложность и случайность, эффективные теоремы теории вероятностей и случайные последовательности; * вероятностные доказательства и их сложностное изложение; * сложность и априорная вероятность (префиксная, монотонная сложности).