Алексеев В.В. Теория алгоритмов

Учебно-методическое пособие. — Саров: Саровский физико-технический институт — филиал Национального исследовательского ядерного университета «МИФИ», 2021. — 98 с.Данное пособие представляет собой самостоятельный модуль и предназначено для студентов, изучающих теорию алгоритмов по информационным направлениям подготовки.
Пособие составлено на основании лекций, читающихся студентам факультета информационных технологий и электроники в СарФТИ НИЯУ МИФИ.
В пособии изложены основные положения теории алгоритмов, приведены основные его формализации, алгоритмические проблемы, рассмотрены классы сложности алгоритмов.
Теоретические сведения для наглядности иллюстрируются рисунками, таблицами. Даны примеры построения типовых алгоритмов.
Учебно-методическое пособие может быть полезно студентам и аспирантам других специальностей, использующих теорию алгоритмов и современные методы дискретного анализа в направлении своей подготовки.Основы теории алгоритмов.
Определение алгоритма.
Формализация понятия алгоритма. Универсальные модели алгоритма.
Рекурсивные функции.
Примитивно-рекурсивные функции.
Оператор суперпозиции.
Оператор примитивной рекурсии.
Оператор минимизации.
Частично рекурсивные функции. Тезис Чёрча.
Машина Тьюринга.
Реализация математической модели Тьюринга.
Некоторые операции над машинами Тьюринга.
Универсальная машина Тьюринга.
Тезис Тьюринга.
Проблема остановки.
Другие модели абстрактных машин.
Многоленточные машины Тьюринга.
Недетерминированные машины Тьюринга.
Машины с произвольным доступом к памяти.
Имитация машины Тьюринга на компьютере и компьютера на машине Тьюринга.
Машина Э. Поста.
Математическая модель Э. Поста.
Тезис Поста.
Нормальные алгоритмы Маркова.
Базовые положения.
Особенности работы нормальных алгоритмов Маркова.
Принцип нормализации Маркова.
Эквивалентность теорий алгоритмов.
Оценка сложности алгоритма.
Классификация алгоритмов.
Основы анализа алгоритмов.
Сравнительные оценки алгоритмов.
Классификация алгоритмов по виду функции трудоемкости.
Временной анализ трудоемкости алгоритмов.
Асимптотический анализ трудоемкости алгоритмов.
Классы сложности алгоритмов.
Литература.