Марченков С.С. Избранные главы дискретной математики

М.: МАКС Пресс, 2015. — 134 с. — ISBN 978-5-89407-553-2. Пособие написано на основе потокового курса "Дополнительные главы дискретной математике", который автор на протяжении ряда лет читает на факультете вычислительной математики и кибернетики МГУ. Пособие состоит их четырех глав. В главе 1 "Функции многозначной логики" даются первоначальные сведения по функциям многозначной логики. Часть из них используется в главах 2 и 3. Глава 2 "Конечные автоматы-распознаватели" посвящена описанию конечно-автоматных множеств в терминах конечных автоматов, с использованием правоинвариантного отношения эквивалентности и на основе регулярных выражений. В главе 3 "Конечные автоматы-преобразователи" рассматривается класс конечно-автоматных функций, определенных на бесконечных последовательностях. Доказывается конечная порождаемость этого класса относительно операций суперпозиции и обратной связи и невозможность построить конечную полную систему только с операцией суперпозиции. В главе 4 "Машины Тьюринга и вычислимые функции" определяются машины Тьюринга и функции, вычислимые на машинах Тьюринга. Доказывается совпадение данного класса функций с классом частично рекурсивных функций. Вводятся понятия P-сводимости и NP-полноты. Устанавливается существование NP-полных проблем. Каждый параграф снабжен задачами и упражнениями.