В учебном пособии рассматриваются основные понятия теории алгоритмов: машины Тьюринга, примитивно рекурсивные, рекурсивные и частично рекурсивные функции, рекурсивные и рекурсивно перечислимые множества, их нумерация, арифметизация теории машин Тьюринга, алгоритмически неразрешимые проблемы из теории алгоритмов, математической логики и алгебры, недетерминированные машины Тьюринга и классы NP и Р.
Пособие предназначено для студентов, обучающихся по направлениям 010100 Математика и 010500 Прикладная математика и информатика, специальности 090102 Компьютерная безопасность, очной формы обучения. Оно может быть использовано при изучении дисциплин “Математическая логика и теория алгоритмов”, “Теория алгоритмов”, “Математическая логика” и “Дискретная математика и математическая логика” (блок ОПД, ДС), а также специальных дисциплин.




