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

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




Что такое колмогоровская сложность?
«На пальцах» это проще всего объяснить так. Существуют программы, которые сжимают файлы (для экономии места в архиве, без потери информации). Возможно, вы встречались с ними: наиболее распространённые называются zip, gzip, bzip2, compress, rar, arj (есть и другие).

Применив такую программу к некоторому файлу (с текстом, данными, программой), мы получаем его сжатую версию (которая, как правило, короче исходного файла). По пей можно восстановить исходный файл (с помощью парной программы-«декомпрессора»; часто сжатие и восстановление объединены в одну программу).

Так вот, в первом приближении колмогоровскую сложность файла можно описать как длину его сжатой версии. Файл, имеющий регулярную структуру и хорошо сжимаемый, имеет малую колмогоровскую сложность (в сравнении с его длиной). Напротив, плохо сжимаемый файл имеет сложность, близкую к длине.

Это описание весьма приблизительно и нуждается в уточнениях как технических, так и принципиальных. Начнём с технического: вместо файлов (последовательностей байтов) мы будем рассматривать двоичные слова (конечные последовательности битов, то есть пулей и единиц). Длиной такого слова называется число знаков (так что слово 1001, скажем, имеет длину 4, а пустое слово имеет длину 0).

ОГЛАВЛЕНИЕ.
Предисловие.
О чём эта книга?.
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. Регуляторы сходимости и функция BB(n).
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. Четыре алгоритмических лица случайности.
Используемые понятия и обозначения.
Литература.
Предметный указатель.
Указатель имён.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Колмогоровская сложность и алгоритмическая случайность, Верещагин Н.К., Успенский В.А., Шень А., 2013 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по математике :: математика :: Верещагин :: Успенский :: Шень :: колмогоровская сложность :: код Хаффмана