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

В новом издании книги "Алгоритмы. Справочник с примерами на C, C++, Java и Python" описано множество алгоритмов для решения задач из самых разных областей, и вы сможете выбрать и реализовать наиболее подходящий для ваших задач алгоритм. Здесь даже совершенно незнакомый с математикой читатель найдет все, что нужно для понимания и анализа производительности алгоритма.

Написанная профессионалами в своей области, книга достойна занять место на книжной полке любого практикующего программиста.

Для создания надежного программного обеспечения необходимы эффективные алгоритмы, но программисты редко представляют себе весь спектр алгоритмов для решения своих задач.

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

Будучи акцентированной на приложениях, а не на теории, эта книга основана на строгих принципах, включая документированные решения реальных задач на разных языках программирования. В это издание добавлены десяток новых алгоритмов, реализованных на языке Python, в том числе реализация диаграмм Вороного, а также новая глава о пространственных древовидных структурах, таких как R-деревья и Quadtrees.

В книге "Алгоритмы. Справочник с примерами на C, C++, Java и Python" вы научитесь:
- Решать новые задачи и повышать эффективность имеющихся решений
- Быстро находить алгоритмы для решения своих задач и выбирать наиболее подходящие
- Находить решения на языках программирования C, C++, Java, Python с помощью рекомендаций из книги
- Оценивать производительность алгоритмов и создавать условия для достижения максимальной эффективности
- Использовать наиболее подходящие структуры данных для повышения эффективности алгоритмов

Об авторах:
Джордж Хайнеман - адъюнкт-профессор информатики в WPI. В 2005 году был Председателем Международного симпозиума по компонентно-ориентированному программному обеспечению.
Гэри Поллис - профессор Вустерского политехнического института; соавтор книги Head First Object-Oriented Analysis and Design.
Стэнли Селков в течение почти четырех десятилетий преподавал в университетах Ноксвилла, Вустера, Монреаля, Чунцина, Лозанны и Парижа

Отзывы экспертов:

Эта книга потрясающая по трем причинам: в ней легко найти нужные алгоритмы и структуры данных; стиль изложения материала - скорее разговорный, чем академический; внимание читателя постоянно акцентируется на сравнительном анализе производительности алгоритмов. Если вы живете в реальном мире, эта книга навсегда изменит ваш способ использования структур данных.
Ричард Резник, директор GQ Life Science



Содержание книги Джордж Хайнеман, Гэри Поллис, Стэнли Селков "Алгоритмы. Справочник с примерами на C, C++, Java и Python"




Предисловие ко второму изданию 15
Изменения во втором издании 15
Целевая аудитория 16
Соглашения, используемые в данной книге 17
Использование примеров кода 18
Благодарности 18
Об авторах 19
Об изображении на обложке 19
Ждем ваших отзывов! 20
Глава 1. Мысли алгоритмически 21
Понимание проблемы 21
Прямое решение 23
Интеллектуальные подходы 23
Жадный подход 24
Разделяй и властвуй 25
Параллельное вычисление 25
Приближение 25
Обобщение 26
Резюме 28
Глава 2. Математика алгоритмов 29
Размер экземпляра задачи 29
Скорость роста функций 30
Анализ наилучшего, среднего и наихудшего случаев 34
Наихудший случай 37
Средний случай 37
Наилучший случай 38
Нижняя и верхняя границы 39
Семейства производительности 40
Константное поведение 40
Логарифмическое поведение 41
Сублинейное поведение 43
Линейная производительность 44
Линейно-логарифмическая производительность 47
Квадратичная производительность 47
Менее очевидные производительности 49
Экспоненциальная производительность 52
Резюме по асимптотическому росту 53
Эталонные операции 53
Глава 3. Строительные блоки алгоритмов 57
Формат представления алгоритма 58
Название и краткое описание 58
Входные и выходные данные алгоритма 58
Контекст применения алгоритма 58
Реализация алгоритма 58
Анализ алгоритма 58
Вариации алгоритма 59
Формат шаблона псевдокода 59
Формат эмпирических оценок 60
Вычисления с плавающей точкой 60
Производительность 61
Ошибка округления 61
Сравнение значений с плавающей точкой 62
Специальные значения 64
Пример алгоритма 64
Название и краткое описание 65
Входные и выходные данные алгоритма 65
Контекст применения алгоритма 65
Реализация алгоритма 66
Анализ алгоритма 69
Распространенные подходы 69
Жадная стратегия 69
Разделяй и властвуй 70
Динамическое программирование 71
Глава 4. Алгоритмы сортировки 77
Терминология 77
Представление 78
Сравниваемость элементов 79
Устойчивая сортировка 80
Критерии выбора алгоритма сортировки 81
Сортировки перестановкой 81
Сортировка вставками 81
Контекст применения алгоритма 83
Реализация алгоритма 83
Анализ алгоритма 84
Сортировка выбором 86
Пирамидальная сортировка 87
Контекст применения алгоритма 91
Реализация алгоритма 91
Анализ алгоритма 93
Вариации алгоритма 93
Сортировка, основанная на разбиении 93
Контекст применения алгоритма 97
Реализация алгоритма 98
Анализ алгоритма 99
Вариации алгоритма 99
Сортировка без сравнений 101
Блочная сортировка 101
Реализация алгоритма 103
Анализ алгоритма 106
Вариации алгоритма 107
Сортировка с использованием дополнительной памяти 109
Сортировка слиянием 109
Входные и выходные данные алгоритма 110
Реализация алгоритма 110
Анализ алгоритма 111
Вариации алгоритма 112
Результаты хронометража для строк 114
Анализ методов 116
Глава 5. Поиск 119
Последовательный поиск 120
Входные и выходные данные алгоритма 121
Контекст применения алгоритма 121
Реализация алгоритма 122
Анализ алгоритма 123
Бинарный поиск 124
Входные и выходные данные алгоритма 124
Контекст применения алгоритма 124
Реализация алгоритма 125
Анализ алгоритма 127
Вариации алгоритма 128
Поиск на основе хеша 129
Входные и выходные данные алгоритма 131
Контекст применения алгоритма 131
Реализация алгоритма 135
Анализ алгоритма 137
Вариации алгоритма 140
Фильтр Блума 146
Входные и выходные данные алгоритма 147
Контекст применения алгоритма 148
Реализация алгоритма 148
Анализ алгоритма 149
Бинарное дерево поиска 150
Входные и выходные данные алгоритма 151
Контекст применения алгоритма 152
Реализация алгоритма 153
Анализ алгоритма 163
Вариации алгоритма 163
Глава 6. Алгоритмы на графах 165
Графы 166
Проектирование структуры данных 169
Поиск в глубину 169
Входные и выходные данные алгоритма 173
Контекст применения алгоритма 174
Реализация алгоритма 174
Анализ алгоритма 175
Вариации алгоритма 175
Поиск в ширину 175
Входные и выходные данные алгоритма 177
Контекст применения алгоритма 178
Реализация алгоритма 178
Анализ алгоритма 179
Кратчайший путь из одной вершины 180
Входные и выходные данные алгоритма 183
Реализация алгоритма 183
Анализ алгоритма 184
Алгоритм Дейкстры для плотных графов 185
Вариации алгоритма 188
Сравнение вариантов поиска кратчайших путей из одной вершины 191
Данные хронометража 191
Плотные графы 192
Разреженные графы 192
Кратчайшие пути между всеми парами вершин 193
Входные и выходные данные алгоритма 193
Реализация алгоритма 195
Анализ алгоритма 198
Алгоритмы построения минимального остовного дерева 198
Входные и выходные данные алгоритма 200
Реализация алгоритма 200
Анализ алгоритма 202
Вариации алгоритма 202
Заключительные мысли о графах 202
Вопросы хранения 203
Анализ графа 203
Глава 7. Поиск путей в ИИ 205
Дерево игры 206
Функции статических оценок 209
Концепции поиска путей 210
Представление состояния 210
Вычисление доступных ходов 211
Максимальная глубина расширения 211
Minimax 211
Входные и выходные данные алгоритма 213
Контекст применения алгоритма 214
Реализация алгоритма 214
Анализ алгоритма 217
NegMax 217
Реализация алгоритма 219
Анализ алгоритма 221
AlphaBeta 221
Реализация алгоритма 225
Анализ алгоритма 227
Деревья поиска 229
Эвристические функции длины пути 232
Поиск в глубину 232
Входные и выходные данные алгоритма 233
Контекст применения алгоритма 234
Реализация алгоритма 234
Анализ алгоритма 236
Поиск в ширину 238
Входные и выходные данные алгоритма 239
Контекст применения алгоритма 240
Реализация алгоритма 240
Анализ алгоритма 242
A*Search 242
Входные и выходные данные алгоритма 244
Контекст применения алгоритма 244
Реализация алгоритма 247
Анализ алгоритма 251
Вариации алгоритма 252
Сравнение алгоритмов поиска в дереве 254
Глава 8. Алгоритмы транспортных сетей 257
Транспортная сеть 258
Максимальный поток 260
Входные и выходные данные алгоритма 261
Реализация алгоритма 261
Анализ алгоритма 270
Оптимизация 270
Связанные алгоритмы 273
Паросочетания в двудольном графе 274
Входные и выходные данные алгоритма 274
Реализация алгоритма 275
Анализ алгоритма 278
Размышления об увеличивающих путях 278
Поток минимальной стоимости 283
Перегрузка 284
Реализация алгоритма 285
Перевозка 285
Реализация алгоритма 287
Назначение 287
Реализация алгоритма 287
Линейное программирование 287
Глава 9. Вычислительная геометрия 289
Классификация задач 290
Входные данные 290
Вычисления 292
Природа задачи 293
Предположения 293
Выпуклая оболочка 294
Сканирование выпуклой оболочки 295
Входные и выходные данные алгоритма 296
Контекст применения алгоритма 297
Реализация алгоритма 298
Анализ алгоритма 300
Вариации алгоритма 301
Вычисление пересечения отрезков 304
LineSweep 305
Входные и выходные данные алгоритма 306
Контекст применения алгоритма 306
Реализация алгоритма 308
Анализ алгоритма 313
Вариации алгоритма 316
Диаграмма Вороного 316
Входные и выходные данные алгоритма 322
Реализация алгоритма 322
Анализ алгоритма 329
Глава 10. Пространственные древовидные структуры 331
Запросы ближайшего соседа 332
Запросы диапазонов 333
Запросы пересечения 333
Структуры пространственных деревьев 334
k-d-деревья 334
Дерево квадрантов 335
R-дерево 336
Задача о ближайшем соседе 337
Входные и выходные данные алгоритма 339
Контекст применения алгоритма 339
Реализация алгоритма 340
Анализ алгоритма 343
Вариации алгоритма 348
Запрос диапазона 348
Входные и выходные данные алгоритма 349
Контекст применения алгоритма 349
Реализация алгоритма 350
Анализ алгоритма 352
Деревья квадрантов 355
Входные и выходные данные алгоритма 357
Реализация алгоритма 357
Анализ алгоритма 361
Вариации алгоритма 361
R-деревья 362
Входные и выходные данные алгоритма 366
Контекст применения алгоритма 366
Реализация алгоритма 366
Анализ алгоритма 372
Глава 11. Дополнительные категории алгоритмов 375
Вариации на тему алгоритмов 375
Приближенные алгоритмы 376
Контекст применения алгоритма 378
Реализация алгоритма 378
Анализ алгоритма 380
Параллельные алгоритмы 382
Вероятностные алгоритмы 387
Оценка размера множества 388
Оценка размера дерева поиска 390
Глава 12. Эпилог: алгоритмические принципы 397
Используемые данные 397
Разложение задачи на задачи меньшего размера 398
Выбор правильной структуры данных 400
Пространственно-временной компромисс 401
Построение поиска 402
Приведение задачи к другой задаче 403
Тестировать алгоритмы труднее, чем писать 404
Допустимость приближенных решений 406
Повышение производительности с помощью параллелизма 406
Приложение. Хронометраж 409
Статистические основы 409
Пример 411
Решение для Java 411
Решение для Linux 412
Хронометраж с использованием Python 416
Вывод результатов 417
Точность 419
Литература 421
Предметный указатель 425