Колмогоровская сложность и алгоритмическая случайность, Верещагин Н.К., Успенский В.А., 2013

Колмогоровская сложность и алгоритмическая случайность, Верещагин Н.К., Успенский В.А., 2013.
 
   Классическая (шенноновская) теория информации измеряет количество информации, заключённой в случайных величинах. В середине 1960-х годов А. Н. Колмогоров (и другие авторы) предложили измерять количество информации в конечных объектах с помощью теории алгоритмов, определив сложность объекта как минимальную длину программы, порождающей этот объект. Это определение послужило основой для алгоритмической теории информации, а также для алгоритмической теории вероятностей: объект считается случайным, если его сложность близка к максимальной.
Предлагаемая книга содержит подробное изложение основных понятий алгоритмической теории информации и теории вероятностей, а также наиболее важных работ, выполненных в рамках «колмогоровского семинара но сложности определений и сложности вычислений», основанного А. Н. Колмогоровым в начале 1980-х годов.
Книга рассчитана на студентов и аспирантов математических факультетов и факультетов теоретической информатики.




Алгоритмические свойства.
Как мы видели, функция KS является перечислимой сверху, но не является вычислимой и даже не имеет вычислимых неограниченных нижних оценок (теорема 6. с. 17).
Заметим, что из этого вытекает, что никакой оптимальный способ описания не является всюду определенным (имеются слова, нс являющиеся описаниями). В самом деле, если бы оптимальный способ описания D был всюду определён, то мы могли бы вычислить KSd(x), просто перепробовав все описания в порядке возрастания длин (до нахождения кратчайшего).

При этом возникает следующий любопытный парадокс. С точки зрения оптимальности наличие слов, не являющихся описаниями, явно невыгодно. В самом деле, если D(y) не определено, можно рассмотреть другой способ описания D'. для которого D'(y’) равно некоторому слову z, а в остальном D' совпадает с D. При замене D на D' сложность слова z может уменьшиться, а сложность остальных слов не изменится. Тем нс менее для оптимального способа описания всегда есть слова, на которых он не определён!

Содержание.
Предисловие О чём эта книга?
1. Простая колмогоровская сложность
1.1. Определение и основные свойства.
1.2. Алгоритмические свойства.
1.2.1. Простые слова и простые множества.
1.2.2. Сложность больших чисел.
2. Сложность пары и условная сложность
2.1. Сложность нары.
2.2. Условная сложность.
2.3. Количество информации.
3. Случайность по Мартин-Лёфу
3.1. Пространство и меры.
3.2. Усиленный закон больших чисел.
3.3. Эффективно нулевые множества.
3.4. Свойства случайных последовательностей.
3.5. Дефект случайности.
4. Априорная вероятность и префиксная сложность
4.1. Вероятностные машины и полумеры на N.
4.2. Наибольшая полумера.
4.3. Префиксные машины.
4.4. Отступление: машины с самоограниченным входом.
4.4.1. Беспрефиксные функции.
4.4.2. Префиксно корректные функции.
4.4.3. Непрерывные вычислимые отображения.
4.5. Основная теорема о префиксной сложности.
4.6. Свойства префиксной сложности.
4.7. Условная префиксная сложность и сложность нары.
4.7.1. Условная префиксная сложность.
4.7.2. Свойства условной префиксной сложности.
4.7.3. Префиксная сложность пары.
4.7.4. Обычная и префиксная сложности.
5. Монотонная и априорная сложности и случайность
5.1. Вероятностные машины и полумеры на дереве.
5.2. Наибольшая перечислимая полумера на дереве.
5.3. Свойства априорной сложности.
5.4. Вычислимые отображения Е-Е.
5.4.1. Непрерывные отображения Е-Е.
5.4.2. Монотонные машины с неблокирующим чтением.
5.4.3. Перечислимость множества вычислимых отображений.   
5.5. Монотонная сложность.
5.5.1. Доказательство теоремы Гача-Дея.
5.6. Теорема Левина - Шнорра.
5.7. Случайное число.
5.7.1. Сводимость и полнота по Соловею.
5.7.2. Полные по Соловею числа случайны.
5.7.3. Критерий случайности в терминах предсказаний.
5.7.4. Случайные перечислимые снизу числа полны.
5.7.5. Медленная сходимость и функции Соловея.
5.7.6. Свойство Соловея для ряда определяется его суммой.   
5.7.7. Регуляторы сходимости и функция ВВ(п).
5.8. Эффективная размерность Хаусдорфа.
5.9. Случайность но различным мерам.
5.9.1. Переход от одной меры к другой.
5.9.2. Последовательности, не случайные по вычислимым мерам.
5.9.3. Случайность по образу меры.
5.9.4. Теорема Ламбальгена.
5.9.5. Теорема Кучеры-Гача.
6. Общая классификация сложностей
6.1. Сложность разрешения.
6.2. Сравнение сложностей.
6.3. Условные сложности.
6.4. Сложности и оракулы.
6.4.1. Сложность с оракулом.
6.4.2. Сложность при условии больших чисел.
6.4.3. Пределы частот и априорная вероятность относительно 0'.
7. Шенноновская энтропия и колмогоровская сложность
7.1. Шенноновская энтропия.
7.1.1. Коды.
7.1.2. Определение шенноновской энтропии.
7.1.3. Код Хаффмана.
7.1.4. Неравенство Крафта-Макмиллана.
7.2. Энтропия пары и условная энтропия.
7.2.1. Энтропия пары случайных величин.
7.2.2. Условная энтропия.
7.2.3. Независимость и энтропия.
7.2.4. «Релятивизация» и базисные неравенства.
7.3. Сложность и энтропия.
7.3.1. Колмогоровская сложность и энтропия частот.
7.3.2. Математическое ожидание сложности.
7.3.3. Сложность начальных отрезков случайных последовательностей.
7.3.4. Вероятность отклонения сложности от энтропии.
7.3.5. Теорема Шеннона о кодировании.
8. Некоторые приложения
8.1. Бесконечность множества простых чисел.
8.2. Перенос информации но ленте.
8.3. Конечные автоматы с несколькими головками.
8.4. Усиленный закон больших чисел.
8.5. Последовательности без запрещённых подслов.
8.5.1. Запрещённые и простые слова.
8.5.2. Лемма Ловаса.
8.5.3. Лемма Ловаса и запрещённые слова.
8.5.4. Запрещённые подпоследовательности.
8.5.5. Сложные подпоследовательности.
8.5.6. «Эффективное» доказательство леммы Ловаса.
8.6. Доказательство одного неравенства.
8.7. Нетранзитивность липшицевых преобразований.
9. Частотный и игровой подходы к определению случайности
9.1. Исходный замысел фон Мизеса.
9.2. Правила выбора как множества слов.
9.3. Случайность но Мизесу- Чёрчу.
9.4. Пример Вилля.
9.5. Мартингалы.
9.6. Отступление: мартингалы в теории вероятностей.
9.7. Перечислимые мартингалы.
9.8. Вычислимые мартингалы.
9.9. Мартингалы и случайность по Шнорру.
9.10. Мартингалы и эффективная размерность.
9.11. Частичные правила выбора.
9.12. Немонотонные правила выбора.
9.13. Случайность по изменённой мере.
9.13.1. Случайность но двум мерам.
9.13.2. Закон больших чисел для переменных вероятностей.  
9.13.3. Закон больших чисел для подпоследовательностей.   
9.13.4. Примеры.
10. Неравенства для энтропии, сложности и размера
10.1. Постановка задачи и результаты.
10.2. Однородные множества.
10.3. Построение однородного множества.
10.4. Однородные множества и орбиты.
10.5. Почти однородные множества.
10.6. Метод типизации.
10.7. Комбинаторная интерпретация: примеры.
10.8. Комбинаторная интерпретация: общий случай.
10.9. Комбинаторная интерпретация: другой вариант.
10.10. Неравенства для двух и трёх слов.
10.11. Размерности и неравенство Инглетона.
10.12. Условно независимые случайные величины.
10.13. Неравенства, не сводящиеся к базисным.
11. Общая информация
11.1. Представление слов в несжимаемом виде.
11.2. Выделение общей информации.
11.3. Комбинаторный смысл общей информации.
11.4. Условная независимость и общая информация.
12. Алгоритмическая теория информации для нескольких источников
12.1. Постановка задачи о передаче информации.
12.2. Условное кодирование.
12.3. Условное кодирование: теорема Мучника.
12.4. Комбинаторный смысл теоремы Мучника.
12.5. Отступление: on-line паросочетания.
12.6. Относительное кодирование пары слов.
12.7. Кодирование при двух условиях.
12.8. Поток информации через разрез.
12.9. Сети с одним источником.
12.10. Выделение общей информации.
12.11. Упрощение программы.
12.12. Минимальная достаточная статистика.
13. Информация и логика
13.1. Задачи, логические операции, сложность.
13.2. Сложность задач и интуиционистская логика.
13.3. Примеры.
13.4. Примеры и доказательство теоремы о полноте.
13.5. Теорема о полноте и модели Крипке.
13.6. Задача, нс сводящаяся к условным сложностям.
14. Алгоритмическая статистика
14.1. Постановка задачи. Дефект случайности.
14.2. Стохастические объекты.
14.3. Двухчастные описания.
14.4. Ограниченные классы гипотез.
14.5. Дефект оптимальности и дефект случайности.
14.6. Минимальные гипотезы.
14.7. Немного философии.
Приложение 1. Колмогоровская сложность и основания теории вероятностей.
Приложение 2. Четыре алгоритмических лица случайности.
Используемые понятия и обозначения.
Литература Предметный указатель Указатель имён.

Купить .





Теги: учебник по математике :: математика :: Верещагин :: Успенский