Дурнев В.Г., Зеткина О.В. Дополнительные вопросы теории алгоритмов

Учебно-методическое пособие. — Ярославль: Ярославский государственный университет им. П.Г. Демидова (ЯрГУ), 2020. — 120 с.В пособии излагаются дополнительные вопросы теории алгоритмов, прежде всего связанные с доказательством фундаментальной теоремы о совпадении классов диофантовых и рекурсивно перечислимых множеств. Приводятся необходимые для этого факты из теории уравнения Пелля, метод цепных дробей для получения минимального решения этого уравнения.
Пособие предназначено для студентов, обучающихся по специальности “Компьютерная безопасность” и по направлению “Информационная безопасность”. Оно может быть использовано при изучении дисциплин “Математическая логика и теория алгоритмов”, “Теория алгоритмов”, “Сложность вычислений”, “Криптографические методы защиты информации”, “Модели безопасности компьютерных систем” и “Криптографические протоколы”, а также специальных дисциплин.Проблемы Д. Гильберта. 10-я проблема Д. Гильберта
Примитивно рекурсивные и частично рекурсивные функции
Нумерационные функции
Рекурсивно перечислимые множества
Рекурсивно перечислимые предикаты
Диофантовы предикаты, отношения и функции
Уравнение Пелля
Разрешимость уравнения Пелля в натуральных числах
Непрерывные дроби
Алгоритмически неразрешимые проблемы в “непрерывных” разделах математики
Неразрешимые алгоритмические проблемы для обыкновенных дифференциальных уравнений
Несобственные интегралы
Арифметическая иерархия