Теория алгоритмов: учебник для студентов высших учебных заведений, обучающихся по специальности 050202.65 (030100) - информатика

Оглавление ......Page 4 Предисловие ......Page 7 1.1. Неформальное понятие алгоритма ......Page 10 1.1.1. Основные требования к алгоритмам ......Page 13 1.1.2. Блок-схемы алгоритмов ......Page 18 1.1.3. Подходы к уточнению понятия алгоритма ......Page 20 1.2.1. Множества и функции ......Page 22 1.2.3. Отношения и предикаты. Логические обозначения ......Page 24 1.3. Алгоритм как программа для компьютера ......Page 25 Тестовые задания ......Page 28 Глава П. Машина Тьюринга ......Page 31 2.1. Основные определения ......Page 32 2.2. Операции над машинами Тьюринга ......Page 37 2.3. Универсальная машина Тьюринга ......Page 44 2.4. Тезис Тьюринга ......Page 46 2.5. Проблема остановки ......Page 47 2.6. Машина фон Неймана ......Page 49 Упражнения ......Page 50 Тестовые задания ......Page 53 3.1. Примитивно-рекурсивные функции ......Page 56 3.2. Примитивно-рекурсивные операторы ......Page 61 3.3. Функции Аккермана ......Page 64 3.4. Частично-рекурсивные функции. Тезис Чёрча ......Page 65 Упражнения ......Page 68 Тестовые задания ......Page 69 4.1. Нормальные алгоритмы ......Page 73 4.2. Операции над алгоритмами Маркова. Принцип нормализации ......Page 80 Упражнения ......Page 87 Тестовые задания ......Page 89 5.1. Основные определения ......Page 92 5.2. МНР-вычислимые функции ......Page 97 5.3. Порождение вычислимых функций ......Page 102 5.3.1. Соединение программ ......Page 103 5.3.2. Подстановка ......Page 106 5.3.3. Рекурсия ......Page 108 5.3.4. Минимизация ......Page 110 5.3.5. Развилка и повторение ......Page 112 5.4. Тезис Чёрча ......Page 114 Упражнения ......Page 116 Тестовые задания ......Page 118 Глава VI. Вычислимость и разрешимость ......Page 122 6.1. Эквивалентность различных теорий алгоритмов ......Page 123 6.2.1. Нумерация программ ......Page 126 6.2.2. Нумерация вычислимых функций ......Page 129 6.3. Теоремы параметризации ......Page 133 6.4. Универсальный алгоритм ......Page 135 6.5. Неразрешимые проблемы в теории вычислимости ......Page 136 6.6. Разрешимые и перечислимые множества ......Page 142 6.7. Теорема Раиса ......Page 146 Тестовые задания ......Page 148 7.1. Рекурсивные операторы ......Page 151 7.2. Эффективные операции на вычислимых функциях ......Page 153 7.3. Первая теорема о рекурсии ......Page 155 7.4. Приложение к семантике языков программирования ......Page 157 7.5. Вторая теорема о рекурсии ......Page 160 Тестовые задания ......Page 162 8.1. Меры сложности ......Page 164 8.2. Теорема об ускорении ......Page 168 8.3. Элементарные функции ......Page 171 Тестовые задания ......Page 174 9.1. Формальные языки и грамматики ......Page 176 9.1.1. Основные понятия ......Page 177 9.1.2. Грамматики с фразовой структурой ......Page 179 9.1.3. Иерархия Хомского ......Page 180 9.2. Задачи распознавания, языки и кодирование ......Page 182 9.3. Детерминированные машины Тьюринга и класс Р ......Page 185 9.4. Недетерминированные вычисления и класс NP ......Page 186 9.5. Полиномиальная сводимость и NP-полные задачи ......Page 189 9.6. Примеры NP-полных задач ......Page 192 Тестовые задания ......Page 195 Литература ......Page 197 Предметный указатель ......Page 199 Обозначения ......Page 202