Основы математической логики и теории алгоритмов

Description

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