Основные алгоритмические модели: учебное пособие

Description

В пособии представлено описание таких алгоритмических моделей, как класс рекурсивных функций, машина Тьюринга, машина Поста, машины произвольного доступа, нормальные алгоритмы Маркова. Особое внимание уделено разработке вычислительных алгоритмов в указанных алгоритмических моделях. Пособие предназначено студентам педагогических вузов, изучающих теорию алгоритмов. Об издании Основной титульный экран Дополнительный титульный экран непериодического издания – 1 Дополнительный титульный экран непериодического издания – 2 Содержание Предисловие Глава 1. «Алгоритм» как центральное понятие теории алгоритмов 1.1. Развитие понятия алгоритма 1.2. Возникновение и основные этапы развития теории алгоритмов как науки 1.3. Алгоритмы: интуитивное представление об алгоритмах, исполнитель алгоритма, свойства и способы записи алгоритмов 1.3.1. Интуитивное представление об алгоритмах 1.3.2. Исполнитель алгоритма 1.3.3. Свойства алгоритмов 1.3.4. Способы записи алгоритмов 1.4. Базовые алгоритмические структуры Вопросы к главе 1 Задания к главе 1 Глава 2. Класс рекурсивных функций 2.1. Введение в теорию рекурсивных функций 2.2. Примитивно рекурсивные функции 2.3. Частично рекурсивные функции 2.4. Взаимосвязь между различными классами рекурсивных функций 2.5. Тезис Черча Вопросы к главе 2 Задания к главе 2 Глава 3. Машина Тьюринга 3.1. Назначение и предпосылки создания машины Тьюринга 3.2. Устройство машины Тьюринга 3.3. Команды и порядок работы машины Тьюринга 3.4. Вычислимые по Тьюрингу функции 3.5. Основные операции над машинами Тьюринга 3.6. Тезис Тьюринга 3.7. Машины Тьюринга и современные электронно-вычислительные машины Вопросы к главе 3 Задания к главе 3 Глава 4. Машина Поста 4.1. Назначение и устройство машины Поста 4.2. Команды и порядок работы машины Поста 4.3. Примеры типичных программ машины Поста 4.4. Тезис Поста Вопросы к главе 4 Задания к главе 4 Глава 5. Машины произвольного доступа 5.1. Устройство и порядок работы машины произвольного доступа 5.2. Вычисление функций на машине произвольного доступа 5.3. Композиция программ машин произвольного доступа Вопросы к главе 5 Задания к главе 5 Глава 6. Нормальные алгоритмы Маркова 6.1. Марковские подстановки 6.2. Нормальные алгоритмы и их применение к словам 6.3. Нормально вычислимые функции 6.4. Способы сочетания нормальных алгоритмов 6.5. Принцип нормализации Маркова Вопросы к главе 6 Задания к главе 6 Заключение Ответы, указания и решения Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Библиографический список