Учебник по курсу \"Теория алгоритмов\" для педагогических вузов по специальности \"Информатика\", полностью соответствующий стандарту. Изложение имеет четкую логическую структуру и охватывает следующие темы: понятие алгоритма, машина Тьюринга, примитивно-рекурсивные функции, нормальные алгоритмы, вычислимость и разрешимость, сложность вычислений, NP-полные задачи. Каждая тема сопровождается тестовыми заданиями и упражнениями. Для студентов и преподавателей педагогических вузов, учителей общеобразовательных школ.

Рекомендовано УМО по специальностям педагогического образования.

Предисловие
Глава I. Предварительные обсуждения
1.1. Неформальное понятие алгоритма
1.1.1. Основные требования к алгоритмам
1.1.2. Блок-схемы алгоритмов
1.1.3. Подходы к уточнению понятия алгоритма
1.2. Предварительные определения
1.2.1. Множества и функции
1.2.2. Функции от натуральных чисел
1.2.3. Отношения и предикаты. Логические
обозначения
1.3. Алгоритм как программа для компьютера
Тестовые задания
Глава П. Машина Тьюринга
2.1. Основные определения
2.2. Операции над машинами Тьюринга
2.3. Универсальная машина Тьюринга
2.4. Тезис Тьюринга
2.5. Проблема остановки
Упражнения
Тестовые задания
Глава III. Рекурсивные функции
3.1. Примитивно-рекурсивные функции
3.2. Примитивно-рекурсивные операторы
3.3. Функции Аккермана
3.4. Частично-рекурсивные функции. Тезис Чёрча
Упражнения
Тестовые задания
Глава IV. Нормальные алгоритмы Маркова
4.1. Нормальные алгоритмы
4.2. Операции над алгоритмами Маркова. Принцип
нормализации
Упражнения
Тестовые задания
Глава V. Машина с неограниченными регистрами
5.1. Основные определения
5.2. МНР-вычислимые функции
5.3. Порождение вычислимых функций
5.3.1. Соединение программ
5.3.2. Подстановка
5.3.3. Рекурсия
5.3.4. Минимизация
5.3.5. Развилка и повторение
5.4. Тезис Чёрча
Упражнения
Тестовые задания
Глава VI. Вычислимость и разрешимость
6.1. Эквивалентность различных теорий
алгоритмов
6.2. Нумерация алгоритмов
6.2.1. Нумерация программ
6.2.2. Нумерация вычислимых функций
6.3. Теоремы параметризации
6.4. Универсальный алгоритм
6.5. Неразрешимые проблемы в теории
вычислимости
6.6. Разрешимые и перечислимые множества
6.7. Теорема Раиса
Тестовые задания
Глава VII. Эффективные операции на множестве
частичных функций
7.1. Рекурсивные операторы
7.2. Эффективные операции на вычислимых
функциях
7.3. Первая теорема о рекурсии
7.4. Приложение к семантике языков
программирования
7.5. Вторая теорема о рекурсии
Тестовые задания
Глава VIII. Сложность вычисления
8.1. Меры сложности
8.2. Теорема об ускорении
8.3. Элементарные функции
Тестовые задания
Глава IX. Введение в теорию NP-полных задач
9.1. Задачи распознавания, языки и кодирование
9.2. Детерминированные машины Тьюринга и класс
Р
9.3. Недетерминированные вычисления и класс NP
9.4. Полиномиальная сводимость и NP-полные
задачи
9.5. Примеры NP-полных задач
Тестовые задания
Литература
Предметный указатель
Обозначения