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