Структуры и алгоритмы обработки данных: Учебник для СПО

Description

Рассмотрены математические основы анализа вычислительной сложности алгоритмов, типовые структуры данных для представления множеств: массивы и динамические списковые структуры, стеки, очереди и деревья. Приведены методы решения комбинаторных задач и основные способы сокращения перебора, задачи поиска, сортировки и алгоритмы на графах. Соответствует современным требованиям Федерального государственного образовательного стандарта среднего профессионального образования и профессиональным квалификационным требованиям. Для обучающихся среднего профессионального образования по специальностям «Программирование в компьютерных системах», «Инфор-мационные системы и программирование», а также других специально-стей, связанных с разработкой программного обеспечения. ПРЕДИСЛОВИЕ Глава 1. АЛГОРИТМЫ И ИХ СЛОЖНОСТИ 1.1. Псевдокод для записи алгоритмов 1.2. Асимптотические обозначения 1.3. Определение времени работы алгоритмов 1.4. Рекуррентные соотношения Упражнения Глава 2. СТРУКТУРЫ ДАННЫХ 2.1. Последовательное распределение 2.2. Связное распределение 2.2.1. Связный список 2.2.2. Реализация связных списков 2.2.3. Разновидности связных списков 2.3. Стеки 2.4. Очереди 2.5. Деревья 2.5.1. Основные определения 2.5.2. Представления деревьев 2.5.3. Прохождения деревьев 2.5.4. Прошитые бинарные деревья 2.5.5. Расширенные бинарные деревья Упражнения Глава 3. ИСЧЕРПЫВАЮЩИЙ ПОИСК 3.1. Поиск с возвратом 3.1.1. Общий алгоритм поиска с возвратом 3.1.2. Применение общего алгоритма 3.1.3. Повышение эффективности поиска с возвратом 3.1.4. Оценка сложности выполнения поиска с возвратом 3.1.5. Способы программирования поиска с возвратом 3.2. Метод ветвей и границ 3.3. Альфа-бета-отсечение 3.4. Методы решета 3.5. Эвристические алгоритмы Упражнения Глава 4. МЕТОДЫ ПОИСКА 4.1. Последовательный поиск 4.2. Логарифмический поиск в статических таблицах 4.2.1. Бинарный поиск 4.2.2. Однородный бинарный поиск 4.2.3. Поиск Фибоначчи 4.2.4. Интерполяционный поиск 4.3. Логарифмический поиск в динамических таблицах 4.3.1. Деревья бинарного поиска 4.3.2. АВЛ-деревья 4.3.3. Красно-черные деревья 4.3.4. Цифровой поиск 4.4. Хеширование 4.4.1. Варианты хеширования 4.4.2. Хеш-функции 4.4.3. Разрешение коллизий 4.5. Внешний поиск Упражнения Глава 5. СОРТИРОВКА 5.1. Оценки эффективности алгоритмов сортировки 5.2. Сортировка вставками 5.2.1. Простая сортировка вставками 5.2.2. Сортировка Шелла 5.3. Обменная сортировка 5.3.1. Пузырьковая сортировка 5.3.2. Быстрая сортировка 5.4. Сортировка выбором 5.4.1. Простая сортировка выбором 5.4.2. Пирамидальная сортировка 5.5. Распределяющая сортировка 5.6. Сортировка подсчетом 5.7. Сортировка слиянием 5.8. Гибридный алгоритм сортировки Timsort 5.9. Внешняя сортировка 5.9.1. Порождение исходных отрезков 5.9.2. Распределение и слияние отрезков 5.10. Порядковые статистики Упражнения Глава 6. АЛГОРИТМЫ НА ГРАФАХ 6.1. Представления графов 6.2. Поиск в глубину 6.3. Поиск в ширину 6.4. Остовные деревья 6.4.1. DFS-дерево 6.4.2. BFS-дерево 6.4.3. Минимальное остовное дерево 6.4.4. Остовные деревья ориентированных графов 6.5. Связность графов 6.5.1. Связные компоненты неориентированного графа 6.5.2. Двусвязные компоненты 6.5.3. Сильно связные компоненты 6.6. Топологическая сортировка 6.7. Транзитивное замыкание 6.8. Фундаментальное множество циклов 6.9. Кратчайшие пути 6.9.1. Кратчайшие пути от фиксированной вершины 6.9.2. Кратчайшие пути между всеми парами вершин 6.10. Эйлеровы пути Упражнения ЗАКЛЮЧЕНИЕ СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ