 |
Алгоритмы. Справочник с примерами на C, C++, Java и Python
Джордж Хайнеман, Гэри Поллис, Стэнли Селков
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
ISBN: 978-5-9908910-7-4
Переплёт: твердый
432 страниц
Цена: 580.00 грн.
|
Если вы считаете, что скорость решения той или иной задачи зависит, в первую очередь, от мощности компьютера, на котором она решается, то эта книга станет для вас откровением с самой первой страницы. Вы узнаете, что наибольший вклад в производительность программы вносят правильно выбранный алгоритм и его реализация в виде компьютерной программы. Выбор подходящего алгоритма среди массы других, способных решить вашу задачу, - дело не из самых простых, и этому вы тоже научитесь в данной книге.
В новом издании книги "Алгоритмы. Справочник с примерами на 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
|