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

Алгоритмическая теория информации, заложенная Колмогоровым и другими учеными в 1960е, занимает особое место: с одной стороны это математическая теория с теоремами и доказательствами, а с другой стороны её мотивировка в значительной степени связана с основаниями теории вероятностей и статистики. В докладе представлен обзор работ, затрагивающий следующие направления: колмогоровская сложность; случайность конечных и бесконечных объектов; связь с частотным подходом (Мизес); связь с мартингалами (Вилль, Шнорр); игровой подход (Вовк, Шейфер); практические генераторы и тесты случайности; псевдослучайность в теории сложности вычислений и криптографии; законы теории информации универсальны (Шеннон, Колмогоров, комбинаторика); алгоритмическая статистика (Витаньи, Верещагин).