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

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

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