Теория алгоритмов

Учебное пособие подробно излагает фундаментальные основы теории алгоритмов. Рассматриваются три основные формализации понятия алгоритма: машины Тьюринга, рекурсивные функции и нормальные алгоритмы Маркова, с доказательством их эквивалентности.

В книге представлены основные теоремы общей теории алгоритмов, включая теорему о параметризации (s-m-n-теорему) и теорему о неподвижной точке. Изучаются теория разрешимых и перечислимых множеств, алгоритмически неразрешимые массовые проблемы, а также теория сложности вычислений и массовых проблем.

Особое внимание уделяется алгоритмическим проблемам математической логики и других разделов математики. Рассматриваются взаимосвязи теории алгоритмов с компьютерами и информатикой, что делает книгу актуальной в контексте современного развития вычислительной техники.

Пособие предназначено для студентов университетов, технических и педагогических вузов, обучающихся по специальностям «Математика», «Прикладная математика», «Математик-педагог», «Учитель математики» на уровнях бакалавриата, магистратуры и специалитета.