Коварцев А.Н., Даниленко А.Н. Алгоритмы и анализ сложности

Учебник. — Самара: Самарский университет, 2018. — 128 с. — ISBN: 978-5-7883-1263-7.Приведены основные направления исследований в теории алгоритмов, определены базовые понятия и требования, предъявляемые к написанию алгоритмов и определению порядка их сложности. Описаны методы и подходы для работы с массивами, списками, деревьями, графами и другими линейными и нелинейными структурами. Введены понятия детерминированной и недетерминированной машины Тьюринга. Представлена алгоритмическая модель языка GRAPH. В учебнике содержатся задачи и упражнения, а также вопросы для самопроверки.
Предназначен для студентов, обучающихся по направлениям подготовки «Фундаментальная информатика и информационные технологии», «Информатика и вычислительная техника».
Подготовлен на кафедре программных систем.Введение в теорию алгоритмов.
Историческая справка.
Понятие алгоритма.
Основные требования, предъявляемые к алгоритмам.
Машина Тьюринга.
Тезис Тьюринга.
Граф машина.
Модель данных.
Построение моделей алгоритмов в системе GRAPH.
Вопросы для самопроверки.
Задачи.
Оценка сложности алгоритмов.
Временная и пространственная сложность алгоритма.
Классы сложности.
Полиномиальность и эффективность. Иерархия классов сложности.
Алгоритмическая сводимость задач.
Вопросы для самопроверки.
Задачи.
Алгоритмы и их сложность.
Представление абстрактных объектов (последовательностей).
Смежное представление последовательностей.
Связанное представление последовательностей.
Характеристические векторы.
Списки. Деревья.
Задачи.
Сортировка и поиск.
Сортировка вставками.
Сортировка всплытия Флойда.
Задачи поиска.
Сортировка с вычисляемыми адресами.
Задачи.
Эффективность методов оптимизации.
Унимодальные, непрерывные одномерные функции.
Оптимизации многоэкстремальных функций.
Сложность выпуклых экстремальных задач.
Задачи.
Задачи на графах.
Представление графов.
Задача о «коммивояжере».
Алгоритм эффективного порождения перестановок.
Алгоритм полного перебора решения задачи о коммивояжере.
Эвристический алгоритм решения задачи о коммивояжере.
Жадные алгоритмы. Алгоритм Дейкстра.
Метод ветвей и границ ("поиск с возвратом" (backtracking)).
Алгоритм Литтла решения задачи о коммивояжере.
Задачи.
Вопросы для самопроверки.
Список литературы.
Алфавитный указатель.