Алгоритмы программирования
Учебное пособие.
Гагарина Л.Г. Колдаев В.Д «Алгоритмы и структуры данных» Инфра-М, 2009 год, 304 стр. (25,4 мб. djvu)
В учебное пособие вошел материал содержащий базовые алгоритмы программирования с описанием их классификации (формы представления по методу и способу решения задачи), видов (линейный, разветвляющийся, циклический), свойств и их структурных данных. В учебнике предлагается множество рецептов оптимизации программ и, что самое главное, пособие дает возможность эти рецепты разрабатывать самостоятельно — основываясь на изложенном материале. Рассмотрена методика работы с линейными и нелинейными структурами данных. Дана оценка функциональности и сложности реализации различных алгоритмов используемых для работы с очередями, стеками, списками, деревьями, таблицами и графами.
Каждая глава заканчивается списком вопросов для самоконтроля и задачами для самостоятельного решения. Приложения содержат сведения по двоичной арифметике и единицам измерения объема информации. Ценность книги не в изучении техники программирования, а в возможности понимания принципов и правил решения поставленной перед программистом задачи. Для студентов изучающих алгоритмы программирования на специальностях: 080801 «Прикладная информатика в экономике», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»
ISBN 978-5-279-03351-5 (Финансы и статистика)
ISBN 978-5-16-003682-3 (ИНФРА-М)
Часть 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
Добавить комментарий