Книга: Гагарина Л. Г., Колдаев В. Д. «Алгоритмы и структуры данных»

Приведены основные понятия алгоритмизации, свойства алгоритмов, общие принципы их построения, основные алгоритмические конструкции, представлена эволюция языков программирования. Рассмотрен широкий круг методов обработки линейных и нелинейных структур данных. Описана технология функционирования и оценки функции сложности различных алгоритмов для работы с очередями, стеками, списками, деревьями, таблицами и графами. В приложениях приведены системы счисления и методы измерения количества информации.
Для студентов, аспирантов, преподавателей, специалистов — от инженера до системного аналитика в области численных методов и компьютерного моделирования. Может быть использовано для самообразования.

Содержание:

Предисловие...... 7 Часть 1. Основы алгоритмизации...... 9 Глава 1. Структурная организация данных...... 9 1. 1. Основные понятия структур данных...... 9 1. 2. Классификация структур данных по признаку изменчивости...... 12 1. 3. Линейные и нелинейные структуры данных...... 13 Контрольные вопросы...... 19 Глава 2. Модели объектов и процессов...... 20 2. 1. Модели структурные и функциональные...... 22 2. 2. Модели натурные и информационные...... 23 2. 3. Классификация моделей...... 25 2. 4. Этапы моделирования...... 26 2. 5. Свойства алгоритма...... 27 2. 6. Виды алгоритмов и их реализация...... 28 2. 7. Базовые канонические структуры алгоритмов...... 34 2. 8. Полное построение алгоритма...... 38 2. 9. Главные принципы создания эффективных алгоритмов...... 42 Контрольные вопросы...... 44 Глава 3. Эволюция языков программирования...... 45 3. 1. Классификация языков программирования по функциональному назначению...... 45 3. 2. Классификация языков программирования по парадигме (концепции) и методологии программирования...... 46 3. 3. Классификация языков программирования по типам задач...... 48 Контрольные вопросы...... 49 Глава 4. Функция сложности алгоритма...... 49 4. 1. Виды функции сложности алгоритмов...... 52 4. 2. Временная функция сложности...... 53 4. 3. Анализ функции сложности по программе...... 53 4. 4. Оценка алгоритма бинарного поиска...... 55 4. 5. Теоретическая и практическая функции сложности...... 56 Контрольные вопросы...... 58 Часть 2. Алгоритмы обработки структур данных...... 59 Глава 5. Методы сортировки...... 59 5. 1. Сортировка выбором...... 60 5. 2. Сортировка вставкой и сортировка слиянием...... 61 5. 3. Сортировка обменом и шейкерная сортировка...... 63 5. 4. Сортировка Шелла...... 66 5. 5. Быстрая сортировка (сортировка Хоара)...... 68 5. 6. Турнирная сортировка...... 69 5. 7. Пирамидальная сортировка...... 71 Контрольные вопросы...... 73 Глава 6. Методы поиска...... 74 6. 1. Последовательный поиск...... 75 6. 2. Бинарный поиск...... 76 6. 3. Фибоначчиев поиск...... 78 6. 4. Интерполяционный поиск...... 79 6. 5. Поиск по бинарному дереву...... 81 6. 6. Поиск по бору...... 87 6. 7. Поиск хешированием...... 90 6. 8. Алгоритмы поиска словесной информации...... 92 Контрольные вопросы...... 96 Глава 7. Итеративные и рекурсивные алгоритмы...... 97 7. 1. Итеративный алгоритм...... 98 7. 2. Рекурсивный алгоритм...... 100 7. 3. Рекурсивные структуры данных...... 103 7. 4. Виды обхода бинарных деревьев...... 107 Контрольные вопросы...... 109 Глава 8. Основные определения теории графов...... 110 8. 1. Изоморфизм графов...... 113 8. 2. Степень вершины графа...... 115 8. 3. Понятие подграфа...... 119 8. 4. Циклы на графе...... 119 8. 5. Цикломатическое число графа...... 124 8. 6. Представление графов в ПЭВМ...... 127 Контрольные вопросы...... 130 Глава 9. Алгоритмы построения остовного (покрывающего) дерева сети...... 131 9. 1. Метод Крускала...... 134 9. 2. Метод Прима...... 141 Контрольные вопросы...... 144 Глава 10. Алгоритмы нахождения на графах кратчайших путей...... 145 10. 1. Построение дерева решений...... 145 10. 2. Метод динамического программирования...... 148 10. 3. Метод Дейкстры...... 154 10. 4. Алгоритм Флойда...... 157 10. 5. Алгоритм Йена...... 158 10. 6. Алгоритм Беллмана — Форда...... 160 Контрольные вопросы...... 161 Глава 11. Эвристические алгоритмы...... 162 11. 1. Волновой алгоритм...... 162 11. 2. Двухлучевой алгоритм...... 165 11. 3. Четырехлучевой алгоритм...... 167 11. 4. Маршрутный алгоритм...... 168 11. 5. Геометрическая модель задачи о лабиринте...... 170 11. 6. Алгоритмы составления расписания...... 173 11. 7. Задача упаковки...... 175 11. 8. Задача о джипе...... 178 11. 9. Задача о кодовом замке...... 181 Контрольные вопросы...... 183 Глава 12. Метод ветвей и границ. Задача коммивояжера...... 184 12. 1. Расшифровка криптограмм...... 186 12. 2. Задача о радиоактивном шаре...... 189 12. 3. Задача коммивояжера...... 190 12. 4. Примеры решения задачи коммивояжера...... 195 Контрольные вопросы...... 210 Глава 13. Моделирование с использованием генераторов случайных чисел...... 211 13. 1. Числовые характеристики случайных величин...... 211 13. 2. Метод середины квадрата...... 212 13. 3. Линейный конгруэнтный метод...... 213 13. 4. Полярный метод генерации случайных чисел...... 215 Контрольные вопросы...... 216 Глава 14. Машина Тьюринга...... 216 14. 1. Структура машины Тьюринга...... 218 14. 2. Функциональные таблицы и диаграммы...... 219 14. 3. Примеры записи алгоритмов...... 222 14. 4. Композиция машин Тьюринга...... 224 Контрольные вопросы...... 227 Глава 15. Элементы математической логики...... 227 15. 1. Алгебра высказываний...... 228 15. 2. Законы математической логики...... 235 15. 3. Решение логических задач...... 236 15. 4. Логические основы ПЭВМ...... 258 15. 5. Логический синтез вычислительных схем...... 261 15. 6. Представление логической функции в виде графа...... 263 15. 7. Проверка истинности заключений из серии посылок...... 264 Контрольные вопросы...... 266 Библиографический список...... 267 Приложение 1. Системы счисления...... 268 Приложение 2. Измерение количества информации...... 287 Словарь терминов...... 295

Издательство: "Финансы и статистика" (2009)

ISBN: 9785279033515