В этом учебном пособии представлены основные идеи и методы теории сложности вычислений. Рассматриваются вычислительные возможности и ограничения различных моделей вычислений, таких как машины Тьюринга. Особое внимание уделяется анализу сложности алгоритмов и классификации задач по сложности.
В книге подробно разбираются понятия вычислимости и разрешимости, сводимости задач, полиномиальной сводимости. Обсуждаются основные сложностные классы P, NP, co-NP, классы PSPACE и EXPTIME. Рассмотрены базовые алгоритмы для задач из этих классов.
Данное учебное пособие предназначено для студентов, обучающихся по направлениям "Прикладная математика и информатика" и "Фундаментальная информатика и информационные технологии". Оно будет полезно всем, кто интересуется теоретическими основами информатики и вычислительной сложностью алгоритмов.
В данном учебнике изложены философские и математические основы науки, применяющей теорию алгоритмов для оценки сложности вычислительных процессов, а именно - основных задач теории вычисления. Автор покрывает такие вопросы, как моделирование языков программирования с помощью машин Тьюринга и классификация алгоритмических задач по их сложности. Книга будет полезна как студентам старших курсов факультетов прикладной математики, так и тем, кто стремится углубить свои познания в алгоритмах и основе вычислительной теории.
Электронная Книга «Теория алгоритмов. Введение в сложность вычислений 2-е изд., испр. и доп. Учебное пособие для бакалавриата и магистратуры» написана автором Владимир Николаевич Крупский в 2017 году.
Минимальный возраст читателя: 0
Язык: Русский
Серии: Авторский учебник
ISBN: 9785534048179
Описание книги от Владимир Николаевич Крупский
В настоящем учебном пособии даны основные идеи и методы теории сложности вычислений. В нем представлены вычислительные возможности, схемы моделирования языков программирования машинами Тьюринга, а также сложностные классы задач.
