В учебном пособии изложены основы качественной и количественной теории алгоритмов; рассмотрены основные модели вычислений (машины Тьюринга, машины с неограниченными регистрами, рекурсивные функции) и связанные с ними подходы к формализации понятия алгоритма; даны начала алгоритмической теории множеств; представлены наиболее известные результаты об алгоритмической неразрешимости, а также элементы теории сложности вычислений. Для студентов высших учебных заведений. Может быть полезно широкому кругу читателей, интересующихся основами теории вычислимости.
ОГЛАВЛЕНИЕ
Предисловие............................... 3 Глава 1. Начальные понятия теории алгоритмов...... 9 1.1. Неформальное понятие алгоритма................ 9 1.2. Конструктивные объекты.....................11 1.3. Алгоритмический процесс.....................19 1.4. Вычислимые функции.......................21 1.5. Сигнализирующее множество...................24 Глава 2. Алгоритмическая теория множеств ........26 2.1. Разрешимые множества......................26 2.2. Полу разрешимые множества...................31 2.3. Перечислимые множества.....................35 2.4. Равнообъемность понятий полу разрешимостии перечислимости...... 40 2.5. Теорема о графике.........................44 2.6. Основные факты о разрешимых и перечислимых множествах......46 Глава 3. Машины Тьюринга................... 48 3.1. Определение одноленточной машины Тьюринга........ 48 3.2. Вычисление функций на машинах Тьюринга.......... 53 3.3. Синтез машин Тьюринга...................... 56 3.4. Тезис Тьюринга........................... 57 3.5. Универсальная машина Тьюринга................ 58 3.6. Теорема о компиляции....................... 62 3.7. Многоленточные машины Тьюринга............... 65 Глава 4. Рекурсивные функции.................73 4.1. Введение...............................73 4.2. Примитивно рекурсивные функции ...............74 4.3. Частично-рекурсивные функции.................89 4.4. Нормальная форма Клини.....................98 Глава 5. Машины с неограниченными регистрами .... 102 5.1. Определение и примеры программ...............102 5.2. МНР-вычислимость частично-рекурсивных функций .... 107 Глава 6. Нумерации вычислимых функций........113 6.1. Нумерации вычислимых функций натурального аргумента ......113 6.2. Нумерации, порожденные машинами Тьюринга ....... 117 6.3. Нумерации, порожденные МНР................. 120 Глава 7. Неразрешимые алгоритмические проблемы . . 125 7.1. Примеры невычислимых функций............... 125 7.2. Проблема остановки....................... 128 7.3. Теорема Раиса .......................... 129 Глава 8. Алгоритмические проблемы в математикеи логике... 133 8.1. Диофантово представление множеств и десятая проблема Гильберта.. 133 8.2. Проблема равенства слов в полугруппах............ 135 8.3. Арифметические множества и функции............ 141 Глава 9. Элементы теории сложности вычислений . . . 152 9.1. Некоторые предварительные сведения............. 152 9.2. Меры сложности вычислений.................. 155 9.3. Оценка эффективности вычислительных алгоритмов .... 160 Глава 10. Легко- и трудноразрешимые задачи ...... 170 10.1. Класс Р ............................. 170 10.2. Булевы схемы полиномиального размера........... 179 10.3. Класс NP ............................ 186 10.4. Примеры заведомо трудных задач............... 194 Список литературы.......................... 203 Предметный указатель........................ 204
Подробно изложены три формализации понятия алгоритма — машины Тьюринга, рекурсивные функции и нормальные алгоритмы Маркова, доказана их эквивалентность. Рассмотрены основные теоремы общей теории алгоритмов, теория разрешимых и перечислимых множеств, алгоритмически неразрешимые массовые проблемы, теория сложности вычислений и массовых проблем, алгор ...
В пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков 1-го порядка, исчисление предикатов и теорема о его полноте, дается введение в теорию алгор ...
В книге излагаются основные исчисления математической логики: исчисления высказываний и исчисления предикатов; основы теории моделей и теории алгоритмов, а также элементы неклассических логик.
Учебник по курсу «Теория алгоритмов» для педагогических вузов по специальности «Информатика», полностью соответствующий стандарту. Изложение имеет четкую логическую структуру и охватывает следующие темы: понятие алгоритма, машина Тьюринга, примитивно-рекурсивные функции, нормальные алгоритмы, вычислимость и разрешимость, сложность вычислений, NP-по ...
Данный материал НЕ НАРУШАЕТ авторские права никаких физических или юридических лиц. Если это не так - свяжитесь с администрацией сайта. Материал будет немедленно удален. Электронная версия этой публикации предоставляется только в ознакомительных целях. Для дальнейшего её использования Вам необходимо будет приобрести бумажный (электронный, аудио) вариант у правообладателей.
Название: 
Распечатать
