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