Зюзьков В.М. Теория алгоритмов

Учебное пособие. — Томск: Томский государственный университет, 2005. — 71 с.В пособии содержится материал спецкурса, читаемого автором в последние годы на механико-математическом факультете ТГУ для студентов специализации «Компьютерная математика». Основные разделы: алгоритмы и вычислимые функции, ламбда-исчисление, вычислимое и невычислимое, формальные аксиоматические теории, элементарная арифметика и неполнота, сложность вычислений, NP-полнота.
Предназначено для преподавателей математики и компьютерных наук, а также для студентов высших учебных заведений.Предисловие.
Алгоритмы и вычислимые функции.
Понятие алгоритма и неформальная вычислимость.
Частично-рекурсивные функции.
Определения.
Примеры рекурсивности.
Машины Тьюринга.
Вычислимое и невычислимое.
Тезис Чёрча.
Теорема о рекурсии.
Куины.
Некоторые алгоритмически неразрешимые проблемы.
Формальные аксиоматические теории.
Основные определения.
Что такое формальная теория?
Выводимость.
Интерпретация.
Общезначимость и непротиворечивость.
Полнота, независимость и разрешимость.
Примеры формальных теорий.
Формальная система MIU.
Формальная система PR.
Формальная система UR.
Формальная система PR1.
Исчисление высказываний.
Классическое определение исчисления высказываний.
Полнота, разрешимость и непротиворечивость исчисления высказываний.
Теории первого порядка.
Языки первого порядка.
Синтаксические свойства истинности теорий с языком первого порядка.
Определение теории первого порядка.
Некоторые свойства теорий первого порядка.
Непротиворечивость, полнота и неразрешимость исчисления предикатов.
Элементарная арифметика и неполнота.
Элементарная арифметика.
Теория элементарной арифметики.
Арифметические функции и отношения.
Неполнота элементарной арифметики.
Геделева нумерация.
Лемма о рефлексии.
Теорема Гёделя о неполноте.
Нестандартное расширение EA.
Об аксиоматизации.
Теорема Гудстейна.
Сложность вычислений.
Асимптотические обозначения.
Θ–обозначение.
O– и Ω-обозначения.
Сравнение роста функций.
Алгоритмы и их сложность.
Сложность задач.
NP-полнота.
Задачи разрешения и задачи оптимизации.
Формальные языки.
Проверка принадлежности языку и класс NP.
NP-полнота и сводимость.
Литература.