Учебное пособие. - Барнаул: Изд-во АлтГТУ, 2010. – 277 с.
Содержание:
Введение.
Формальные теории.
Формальные модели.
Исчисление высказываний.
Исчисление предикатов.
Другие логические теории.
Частично-рекурсивные функции.
Свойства алгоритмов.
Примитивно–рекурсивные функции.
Оператор минимизации.
Ограниченный оператор минимизации.
Быстро растущие функции.
Частично–рекурсивные функции и тезис Черча.
Рекурсивные и рекурсивно перечислимые множества.
Контрольные вопросы к разделу.
Машины Тьюринга.
Неформальное определение машины Тьюринга.
Формальное определение машины Тьюринга.
Способы представления машины Тьюринга.
Функции, вычислимые по Тьюрингу.
Машина Тьюринга с полулентой.
Разветвление и повторение.
Тезис Тьюринга.
Общая теория алгоритмов.
Геделевский номер машины Тьюринга.
Проблема остановки машины Тьюринга.
Метод сводимости и доказательство неразрешимости.
Алгоритмы Маркова.
Эквивалентность алгоритмических моделей.
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций.
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова.
Теория сложности алгоритмов.
Понятие временной и емкостной сложности алгоритмов.
Практическая оценка временной сложности.
NP–полные задачи.
NP-полнота задачи о дизъюнкциях.
Несколько NP–полных задач.
Методы решения NP-полных задач.
Построение и анализ эффективных алгоритмов.
Типы рекурсивных алгоритмов.
Устранение рекурсии.
Методы отсечения.
Динамическое программирование.
Виртуальные графы.
Эффективные алгоритмы на графах.
Производящие функции.
Формальные грамматики и языки.
Понятие порождающей грамматики и языка.
Классификация грамматик.
Основные свойства КС–языков и КС–грамматик.
Грамматический разбор.
Преобразования КС–грамматик.
Теорема о языке a^n b^n c^n.
Языки и автоматы.
Понятие автомата и типы автоматов.
Формальное определение автомата.
Конечные автоматы.
Регулярные множества.
Минимизация конечных автоматов.
Операции над регулярными языками.
Автоматные грамматики и конечные автоматы.
Автоматы с магазинной памятью и КС–языки.
Разбор с возвратом.
Автоматы-преобразователи.
Поведение автоматов с выходом.
Автоматы Мили.
Автоматы Мура.
Равносильность автоматов Мили и Мура.
Синтез конечных преобразователей.
Эксперименты по распознаванию состояний.
Алгоритмически разрешимые и неразрешимые проблемы теории формальных грамматик и.
языков.
Заключение.
Содержание:
Введение.
Формальные теории.
Формальные модели.
Исчисление высказываний.
Исчисление предикатов.
Другие логические теории.
Частично-рекурсивные функции.
Свойства алгоритмов.
Примитивно–рекурсивные функции.
Оператор минимизации.
Ограниченный оператор минимизации.
Быстро растущие функции.
Частично–рекурсивные функции и тезис Черча.
Рекурсивные и рекурсивно перечислимые множества.
Контрольные вопросы к разделу.
Машины Тьюринга.
Неформальное определение машины Тьюринга.
Формальное определение машины Тьюринга.
Способы представления машины Тьюринга.
Функции, вычислимые по Тьюрингу.
Машина Тьюринга с полулентой.
Разветвление и повторение.
Тезис Тьюринга.
Общая теория алгоритмов.
Геделевский номер машины Тьюринга.
Проблема остановки машины Тьюринга.
Метод сводимости и доказательство неразрешимости.
Алгоритмы Маркова.
Эквивалентность алгоритмических моделей.
Теорема об эквивалентности Машин Тьюринга и частично–рекурсивных функций.
Теорема об эквивалентности машин Тьюринга и алгоритмов Маркова.
Теория сложности алгоритмов.
Понятие временной и емкостной сложности алгоритмов.
Практическая оценка временной сложности.
NP–полные задачи.
NP-полнота задачи о дизъюнкциях.
Несколько NP–полных задач.
Методы решения NP-полных задач.
Построение и анализ эффективных алгоритмов.
Типы рекурсивных алгоритмов.
Устранение рекурсии.
Методы отсечения.
Динамическое программирование.
Виртуальные графы.
Эффективные алгоритмы на графах.
Производящие функции.
Формальные грамматики и языки.
Понятие порождающей грамматики и языка.
Классификация грамматик.
Основные свойства КС–языков и КС–грамматик.
Грамматический разбор.
Преобразования КС–грамматик.
Теорема о языке a^n b^n c^n.
Языки и автоматы.
Понятие автомата и типы автоматов.
Формальное определение автомата.
Конечные автоматы.
Регулярные множества.
Минимизация конечных автоматов.
Операции над регулярными языками.
Автоматные грамматики и конечные автоматы.
Автоматы с магазинной памятью и КС–языки.
Разбор с возвратом.
Автоматы-преобразователи.
Поведение автоматов с выходом.
Автоматы Мили.
Автоматы Мура.
Равносильность автоматов Мили и Мура.
Синтез конечных преобразователей.
Эксперименты по распознаванию состояний.
Алгоритмически разрешимые и неразрешимые проблемы теории формальных грамматик и.
языков.
Заключение.