Название: Элементы теории алгоритмов: учебное пособие
Автор: Дурнев В.Г.
Издательство: Ярославль: ЯрГУ
Год: 2008
Страниц: 248
Формат: djvu
Размер: 12,2 Мб
Язык: Русский

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