Косовская Т.М. Алгоритмы и анализ их сложности

М.: Ай Пи Эр Медиа, 2023. — 111 с. — ISBN 978-5-4497-1855-6.В учебном пособии излагаются некоторые аспекты вычислительной сложности при работе с целыми числами и графами, а также описаны основные понятия теории алгоритмов и некоторые классы сложности алгоритмов. Приводятся алгоритмы работы с «длинными» целыми числами, которые не помещаются в одну ячейку компьютера, доказываются оценки числа шагов работы этих алгоритмов. Анализируется число шагов решения некоторых задач на графах при разных способах их задания. Отдельная глава посвящена описанию трёх математических понятий алгоритма: рекурсивных функций, машин Тьюринга и их модификаций, нормальных алгоритмов Маркова. Доказываются теоремы о невозможности построения некоторых алгоритмов и об алгоритмической неразрешимости некоторых массовых проблем. Изложены основные понятия вычислительной сложности алгоритмов, даны сведения о современном делении алгоритмов на классы сложности. Учебное пособие предназначено для студентов, обучающихся по направлениям подготовки, связанным с технологиями программирования и искусственным интеллектом, и изучающих дисциплины «Теория алгоритмов», «Теория вычислительной сложности алгоритмов», «Анализ алгоритмов».
Учебное пособие написано по результатам чтения лекций на математико-механическом факультете Санкт-Петербургского университета. В него вошли материалы, излагавшиеся в курсах «Алгоритмы и анализ сложности», «Анализ алгоритмов», «Математическая логика» (раздел «Теория алгоритмов») для студентов бакалавриата и «Дополнительные главы математической логики и теории алгоритмов» для студентов магистратуры.PDF scan (HQ)