[Анфиса]

Алгоритмы и структуры данных


Год: 2009
Автор: Гагарина Л.Г., Колдаев В.Д.
Издательство: Финансы и статистика; ИНФРА-М
Язык: Русский
Формат: PDF
Качество: Отсканированные страницы
Количество страниц: 303

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

Предисловие
Часть 1. Основы алгоритмизации 9
Глава 1. Структурная организация данных 9
11. Основные понятия структур данных 9
12. Классификация структур данных по признаку изменчивости 12
13. Линейные и нелинейные структуры данных .... 13 Контрольные вопросы 19
Глава 2. Модели объектов и процессов 20
21. Модели структурные и функциональные 22
22. Модели натурные и информационные 23
23. Классификация моделей 25
24. Этапы моделирования 26
25. Свойства алгоритма 27
26. Виды алгоритмов и их реализация 28
27. Базовые канонические структуры алгоритмов ... 34
28. Полное построение алгоритма 38
29. Главные принципы создания эффективных алгоритмов 42
Контрольные вопросы 44
Глава 3. Эволюция языков программирования 45
31. Классификация языков программирования
по функциональному назначению 45
32. Классификация языков программирования по парадигме (концепции) и методологии программирования 46
33. Классификация языков программирования
по типам задач 48
Контрольные вопросы 49
Глава 4. Функция сложности алгоритма 49
41. Виды функции сложности алгоритмов 52
42. Временная функция сложности 53
43. Анализ функции сложности по программе 53
44. Оценка алгоритма бинарного поиска 55
45. Теоретическая и практическая функции сложности 56 Контрольные вопросы 58
Часть 2. Алгоритмы обработки структур данных . . . 59
Глава 5. Методы сортировки 59
5.1. Сортировка выбором 60
5.2. Сортировка вставкой и сортировка слиянием ... 61
5.3. Сортировка обменом и шейкерная сортировка ... 63 .4. Сортировка Шелла 66
55. Быстрая сортировка (сортировка Хоара) 68
56. Турнирная сортировка 69
57. Пирамидальная сортировка 71
Контрольные вопросы 73
Глава 6. Методы поиска 74
61. Последовательный поиск 75
62. Бинарный поиск 76
63. Фибоначчиев поиск 78
64. Интерполяционный поиск 79
65. Поиск по бинарному дереву 81
66. Поиск по бору 87
67. Поиск хешированием 90
68. Алгоритмы поиска словесной информации 92
Контрольные вопросы 96
Глава 7. Итеративные и рекурсивные алгоритмы .... 97
71. Итеративный алгоритм 98
72. Рекурсивный алгоритм 100
73. Рекурсивные структуры данных 103
74. Виды обхода бинарных деревьев 107
Контрольные вопросы 109
Глава 8. Основные определения теории графов 110
81. Изоморфизм графов 113
82. Степень вершины графа 115
83. Понятие подграфа 119
84. Циклы на графе 119
85. Цикломатическое число графа 124
86. Представление графов в ПЭВМ 127
Контрольные вопросы 130
Глава 9. Алгоритмы построения остовного
(покрывающего) дерева сети 131
91. Метод Крускала 134
92. Метод Прима 141
Контрольные вопросы 144
Глава 10. Алгоритмы нахождения на графах кратчайших
путей 145
101. Построение дерева решений 145
102. Метод динамического программирования 148
103. Метод Дейкстры 154
104. Алгоритм Флойда 157
105. Алгоритм Йена 158
106. Алгоритм Беллмана — Форда 160
Контрольные вопросы 161
Глава 11. Эвристические алгоритмы 162
111. Волновой алгоритм 162
112. Двухлучевой алгоритм 165
113. Четырехлучевой алгоритм 167
114. Маршрутный алгоритм 168
115. Геометрическая модель задачи о лабиринте .... 170
116. Алгоритмы составления расписания 173
117. Задача упаковки 175
118. Задача о джипе 178
119. Задача о кодовом замке 181
Контрольные вопросы 183