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

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

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