Алгоритмическая теория информации
Курс Хит![](https://www.lektorium.tv/sites/lektorium.tv/files/courses/1283292485_22751_1269635342_12798_c10_l3.flv_000416033.jpg)
Алгоритмическая теория информации пытается измерить количество информации в данном сообщении как число битов в наиболее сжатом его описании (колмогоровская сложность). Будут изучены:
- определение и свойства сложности;
- условная сложность и сложность пары;
- связь с комбинаторикой и шенноновской теорией информации;
- сложность и случайность, эффективные теоремы теории вероятностей и случайные последовательности;
- вероятностные доказательства и их сложностное изложение;
- сложность и априорная вероятность (префиксная, монотонная сложности).
Лекции курса
6