Описание:Курс состоит из трех частей. В первой части "Конечные автоматы-распознаватели" вводятся понятия конечного автомата без выхода и конечно-автоматного множества. Конечно-автоматные множества характеризуются в терминах правоинвариантного отношения эквивалентности. Доказывается замкнутость класса конечно-автоматных множеств относительно теоретико-множественных операций и операций произведения и итерации. Вводится понятие регулярного множества и устанавливается совпадение класса конечно-автоматных множеств с классом регулярных множеств.
Во второй части "Машины Тьюринга и вычислимые функции" определяются машины Тьюринга и функции, вычислимые на машинах Тьюринга. Рассматриваются операции суперпозиции, примитивной рекурсии, минимизации и доказывается замкнутость класса вычислимых функций относительно этих операций. Определяются классы примитивно-рекурсивных и частично-рекурсивных функций, приводятся примеры функций из этих классов. С использованием формулы Клини доказывается частичная рекурсивность вычислимых функций. Устанавливается существование универсальной машины Тьюринга, выводится ряд следствий из этого факта. Определяются классы P и NP, приводятся примеры задач из этих классов. Вводится понятие NP-полноты и доказывается теорема Кука о NP-полноте проблемы выполнимости КНФ.
В третьей части "Конечные автоматы-распознаватели" конечно-автоматные функции определяются с помощью бесконечных деревьев, канонических уравнений, диаграмм Мура и схем из автоматных элементов. Доказывается замкнутость класса конечно-автоматных функций относительно операций суперпозиции и обратной связи. Устанавливается конечная порождаемость класса конечно-автоматных функций относительно этих операций. Доказывается несводимость операции суперпозиции к операции обратной связи.