В этом учебном пособии представлены основные идеи и методы теории сложности вычислений. Рассматриваются вычислительные возможности и ограничения различных моделей вычислений, таких как машины Тьюринга. Особое внимание уделяется анализу сложности алгоритмов и классификации задач по сложности.
В книге подробно разбираются понятия вычислимости и разрешимости, сводимости задач, полиномиальной сводимости. Обсуждаются основные сложностные классы P, NP, co-NP, классы PSPACE и EXPTIME. Рассмотрены базовые алгоритмы для задач из этих классов.
Данное учебное пособие предназначено для студентов, обучающихся по направлениям "Прикладная математика и информатика" и "Фундаментальная информатика и информационные технологии". Оно будет полезно всем, кто интересуется теоретическими основами информатики и вычислительной сложностью алгоритмов.
В данном учебнике изложены философские и математические основы науки, применяющей теорию алгоритмов для оценки сложности вычислительных процессов, а именно - основных задач теории вычисления. Автор покрывает такие вопросы, как моделирование языков программирования с помощью машин Тьюринга и классификация алгоритмических задач по их сложности. Книга будет полезна как студентам старших курсов факультетов прикладной математики, так и тем, кто стремится углубить свои познания в алгоритмах и основе вычислительной теории.
#учебники и пособия для вузов
#математика
