Алгоритмы. Руководство по разработке Алгоритмы. Руководство по разработке Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации. Приведены многочисленные примеры задач. Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей. BHV 978-5-9775-0560-4
767 руб.
Russian
Каталог товаров

Алгоритмы. Руководство по разработке

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

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

Оставить заявку на описание
?
Содержание
Предисловие................................................................................................................... 13
Читателю....................................................................................................................................... 13
Преподавателю............................................................................................................................. 15
Благодарности ............................................................................................................................... 16
Ограничение ответственности ..................................................................................................... 17
ЧАСТЬ I. ПРАКТИЧЕСКАЯ РАЗРАБОТКА АЛГОРИТМОВ ........................... 19
Глава 1. Введение в разработку алгоритмов........................................................... 21
1.1. Оптимизация маршрута робота ............................................................................................ 22
1.2. Задача календарного планирования ..................................................................................... 26
1.3. Обоснование правильности алгоритмов .............................................................................. 29
1.3.1. Представление алгоритмов......................................................................................... 30
1.3.2. Задачи и свойства ........................................................................................................ 31
1.3.3. Демонстрация неправильности алгоритма................................................................ 32
1.3.4. Индукция и рекурсия................................................................................................... 33
1.3.5. Суммирование ............................................................................................................. 35
1.4. Моделирование задачи.......................................................................................................... 37
1.4.1. Комбинаторные объекты ............................................................................................ 37
1.4.2. Рекурсивные объекты ................................................................................................. 39
1.5. Истории из жизни .................................................................................................................. 40
1.6. История из жизни. Моделирование проблемы ясновидения ............................................. 41
1.7. Упражнения........................................................................................................................... 45
Глава 2. Анализ алгоритмов....................................................................................... 49
2.1. Модель вычислений RAM..................................................................................................... 49
2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая ............................ 50
2.2. Асимптотические обозначения............................................................................................. 52
2.3. Скорость роста и отношения доминирования..................................................................... 55
2.3.1. Отношения доминирования........................................................................................ 56
2.4. Работа с асимптотическими обозначениями ....................................................................... 58
2.4.1. Сложение функций...................................................................................................... 58
2.4.2. Умножение функций................................................................................................... 58
2.5. Оценка эффективности.......................................................................................................... 59
2.5.1. Сортировка методом выбора...................................................................................... 59
2.5.2. Сортировка вставками ................................................................................................ 60
2.5.3. Сравнение строк .......................................................................................................... 61
2.5.4. Умножение матриц...................................................................................................... 63
6 Оглавление
2.6. Логарифмы и их применение................................................................................................ 64
2.6.1. Логарифмы и двоичный поиск................................................................................... 64
2.6.2. Логарифмы и деревья.................................................................................................. 64
2.6.3. Логарифмы и биты...................................................................................................... 65
2.6.4. Логарифмы и умножение............................................................................................ 65
2.6.5. Быстрое возведение в степень.................................................................................... 66
2.6.6. Логарифмы и сложение .............................................................................................. 66
2.6.7. Логарифмы и система уголовного судопроизводства.............................................. 67
2.7. Свойства логарифмов ............................................................................................................ 68
2.8. История из жизни. Загадка пирамид .................................................................................... 69
2.9. Анализ высшего уровня (*) ................................................................................................... 72
2.9.1. Малораспространенные функции .............................................................................. 73
2.9.2. Пределы и отношения доминирования ..................................................................... 74
2.10. Упражнения......................................................................................................................... 75
Глава 3. Структуры данных ....................................................................................... 84
3.1. Смежные и связные структуры данных ............................................................................... 84
3.1.1. Массивы ....................................................................................................................... 85
3.1.2. Указатели и связные структуры данных.................................................................... 86
3.1.3. Сравнение..................................................................................................................... 89
3.2. Стеки и очереди ..................................................................................................................... 90
3.3. Словари.................................................................................................................................. 91
3.4. Двоичные деревья поиска ..................................................................................................... 95
3.4.1. Реализация двоичных деревьев .................................................................................. 96
3.4.2. Эффективность двоичных деревьев поиска ............................................................ 100
3.4.3. Сбалансированные деревья поиска.......................................................................... 101
3.5. Очереди с приоритетами..................................................................................................... 102
3.6. История из жизни. Триангуляция....................................................................................... 104
3.7. Хэширование и строки ........................................................................................................ 107
3.7.1. Коллизии .................................................................................................................... 108
3.7.2. Эффективный метод поиска строк посредством хэширования............................. 110
3.7.3. Выявление дубликатов с помощью хэширования .................................................. 112
3.8. Специализированные структуры данных........................................................................... 113
3.9. История из жизни. Геном человека .................................................................................... 114
3.10. Упражнения....................................................................................................................... 118
Глава 4. Сортировка и поиск.................................................................................... 123
4.1. Применение сортировки...................................................................................................... 123
4.2. Практические аспекты сортировки .................................................................................... 126
4.3. Пирамидальная сортировка................................................................................................. 128
4.3.1. Пирамиды................................................................................................................... 129
4.3.2. Создание пирамиды .................................................................................................. 132
4.3.3. Наименьший элемент пирамиды.............................................................................. 133
4.3.4. Быстрый способ создания пирамиды (*) ................................................................. 135
4.3.5. Сортировка вставками .............................................................................................. 137
4.4. История из жизни. Билет на самолет.................................................................................. 138
4.5. Сортировка слиянием. Метод "разделяй и властвуй"....................................................... 141
4.6. Быстрая сортировка. Рандомизированная версия ............................................................. 143
4.6.1. Ожидаемое время исполнения алгоритма быстрой сортировки ........................... 146
Оглавление 7
4.6.2. Рандомизированные алгоритмы............................................................................... 147
4.6.3. Действительно ли алгоритм быстрой сортировки работает быстро? ................... 150
4.7. Сортировка распределением. Метод блочной сортировки .............................................. 150
4.7.1. Нижние пределы для сортировки............................................................................. 151
4.8. История из жизни. Адвокат Скиена ................................................................................... 152
4.9. Двоичный поиск и связанные с ним алгоритмы ............................................................... 154
4.9.1. Частота вхождения элемента.................................................................................... 155
4.9.2. Односторонний двоичный поиск ............................................................................. 155
4.9.3. Корни числа ............................................................................................................... 156
4.10. Метод "разделяй и властвуй"............................................................................................ 156
4.10.1. Рекуррентные соотношения ................................................................................... 157
4.10.2. Рекуррентные соотношения метода "разделяй и властвуй" ................................ 158
4.10.3. Решение рекуррентных соотношений типа "разделяй и властвуй" (*)............... 159
4.11. Упражнения....................................................................................................................... 161
Глава 5. Обход графов................................................................................................ 168
5.1. Разновидности графов ......................................................................................................... 169
5.1.1. Граф дружеских отношений..................................................................................... 172
5.2. Структуры данных для графов............................................................................................ 174
5.3. История из жизни. Жертва закона Мура............................................................................ 178
5.4. История из жизни. Создание графа .................................................................................... 181
5.5. Обход графа.......................................................................................................................... 184
5.6. Обход в ширину ................................................................................................................... 185
5.6.1. Применение обхода................................................................................................... 187
5.6.2. Поиск путей ............................................................................................................... 188
5.7. Применение обхода в ширину ............................................................................................ 189
5.7.1. Компоненты связности ............................................................................................. 189
5.7.2. Раскраска графов двумя цветами............................................................................. 191
5.8. Обход в глубину................................................................................................................... 192
5.9. Применение обхода в глубину............................................................................................ 195
5.9.1. Поиск циклов ............................................................................................................. 196
5.9.2. Шарниры графа ......................................................................................................... 196
5.10. Обход в глубину ориентированных графов..................................................................... 200
5.10.1. Топологическая сортировка ................................................................................... 202
5.10.2. Сильно связные компоненты.................................................................................. 203
5.11. Упражнения....................................................................................................................... 207
Глава 6. Алгоритмы для работы со взвешенными графами ............................. 213
6.1. Минимальные остовные деревья........................................................................................ 214
6.1.1. Алгоритм Прима........................................................................................................ 215
6.1.2. Алгоритм Крускала ................................................................................................... 218
6.1.3. Поиск-объединение ................................................................................................... 220
6.1.4. Разновидности остовных деревьев .......................................................................... 223
6.2. История из жизни. И все на свете только сети.................................................................. 224
6.3. Поиск кратчайшего пути..................................................................................................... 227
6.3.1. Алгоритм Дейкстры .................................................................................................. 228
6.3.2. Кратчайшие пути между всеми парами вершин..................................................... 231
6.3.3. Транзитивное замыкание .......................................................................................... 233
8 Оглавление
6.4. История из жизни. Печатаем с помощью номеронабирателя .......................................... 234
6.5. Потоки в сетях и паросочетание в двудольных графах .................................................... 239
6.5.1. Паросочетание в двудольном графе ........................................................................ 239
6.5.2. Вычисление потоков в сети...................................................................................... 240
6.6. Разрабатывайте не алгоритмы, а графы............................................................................. 244
6.7. Упражнения......................................................................................................................... 246
Глава 7. Комбинаторный поиск и эвристические методы................................. 251
7.1. Перебор с возвратом............................................................................................................ 251
7.1.1. Генерирование всех подмножеств ........................................................................... 254
7.1.2. Генерирование всех перестановок........................................................................... 255
7.1.3. Генерирование всех путей в графе........................................................................... 256
7.2. Отсечение вариантов поиска............................................................................................... 258
7.3. Судоку.................................................................................................................................. 259
7.4. История из жизни. Покрытие шахматной доски............................................................... 264
7.5. Эвристические методы перебора........................................................................................ 267
7.5.1. Произвольная выборка.............................................................................................. 268
7.5.2. Локальный поиск....................................................................................................... 271
7.5.3. Имитация отжига....................................................................................................... 274
7.5.4. Применение метода имитации отжига .................................................................... 278
7.6. История из жизни. Только это не радио ............................................................................ 280
7.7. История из жизни. Отжиг массивов ................................................................................... 283
7.8. Другие эвристические методы поиска ............................................................................... 286
7.9. Параллельные алгоритмы ................................................................................................... 287
7.10. История из жизни. "Торопиться в никуда" ...................................................................... 289
7.11. Упражнения....................................................................................................................... 290
Глава 8. Динамическое программирование .......................................................... 293
8.1. Кэширование и вычисления................................................................................................ 294
8.1.1. Генерирование чисел Фибоначчи методом рекурсии ............................................ 294
8.1.2. Генерирование чисел Фибоначчи посредством кэширования .............................. 295
8.1.3. Генерирование чисел Фибоначчи посредством динамического
программирования .............................................................................................................. 297
8.1.4. Биномиальные коэффициенты ................................................................................. 298
8.2. Поиск приблизительно совпадающих строк...................................................................... 300
8.2.1. Применение рекурсии для вычисления расстояния редактирования.................... 301
8.2.2. Применение динамического программирования для вычисления
расстояния редактирования................................................................................................ 302
8.2.3. Восстановление пути................................................................................................. 304
8.2.4. Разновидности расстояния редактирования............................................................ 306
8.3. Самая длинная возрастающая последовательность .......................................................... 310
8.4. История из жизни. Эволюция омара .................................................................................. 312
8.5. Задача разбиения.................................................................................................................. 315
8.6. Синтаксический разбор ....................................................................................................... 318
8.6.1. Триангуляция с минимальным весом...................................................................... 320
8.7. Ограничения динамического программирования. Задача коммивояжера...................... 322
8.7.1. Вопрос правильности алгоритмов динамического программирования ............... 323
8.7.2. Эффективность алгоритмов динамического программирования.......................... 324
8.8. История из жизни. Динамическое программирование и язык Prolog ............................. 325
Оглавление 9
8.9. История из жизни. Сжатие текста для штрих-кодов......................................................... 328
8.10. Упражнения....................................................................................................................... 332
Глава 9. Труднорешаемые задачи и аппроксимирующие алгоритмы............. 338
9.1. Сведение задач ..................................................................................................................... 338
9.1.1. Ключевая идея ........................................................................................................... 339
9.1.2. Задачи разрешимости................................................................................................ 340
9.2. Сведение для создания новых алгоритмов ........................................................................ 341
9.2.1. Поиск ближайшей пары............................................................................................ 341
9.2.2. Максимальная возрастающая подпоследовательность.......................................... 342
9.2.3. Наименьшее общее кратное ..................................................................................... 343
9.2.4. Выпуклая оболочка (*).............................................................................................. 344
9.3. Простые примеры сведения сложных задач...................................................................... 345
9.3.1. Гамильтонов цикл ..................................................................................................... 345
9.3.2. Независимое множество и вершинное покрытие ................................................... 347
9.3.3. Задача о клике............................................................................................................ 350
9.4. Задача выполнимости булевых формул............................................................................. 351
9.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме ............................ 352
9.5. Нестандартные сведения ..................................................................................................... 353
9.5.1. Целочисленное программирование ......................................................................... 354
9.5.2. Вершинное покрытие................................................................................................ 356
9.6. Искусство доказательства сложности ................................................................................ 358
9.7. История из жизни. Наперегонки со временем................................................................... 360
9.8. История из жизни. Полный провал .................................................................................... 362
9.9. Сравнение классов сложности P и NP................................................................................ 364
9.9.1. Верификация решения и поиск решения................................................................. 365
9.9.2. Классы сложности P и NP......................................................................................... 365
9.9.3. Почему задача выполнимости является самой сложной из всех сложных
задач?................................................................................................................................... 366
9.9.4. NP-сложность по сравнению с NP-полнотой.......................................................... 367
9.10. Решение NP-полных задач ................................................................................................ 367
9.10.1. Аппроксимация вершинного покрытия................................................................. 368
9.10.2. Задача коммивояжера в евклидовом пространстве .............................................. 370
9.10.3. Максимальный бесконтурный подграф................................................................. 371
9.10.4. Задача о покрытии множества................................................................................ 372
9.11. Упражнения....................................................................................................................... 375
Глава 10. Как разрабатывать алгоритмы.............................................................. 380
ЧАСТЬ II. КАТАЛОГ АЛГОРИТМИЧЕСКИХ ЗАДАЧ..................................... 385
Глава 11. Описание каталога ................................................................................... 387
Глава 12. Структуры данных ................................................................................... 389
12.1. Словарь ............................................................................................................................... 389
12.2. Очереди с приоритетами................................................................................................... 395
12.3. Суффиксные деревья и массивы....................................................................................... 398
12.4. Графы................................................................................................................................. 402
12.5. Множества .......................................................................................................................... 406
12.6. Kd-деревья .......................................................................................................................... 410
10 Оглавление
Глава 13. Численные задачи..................................................................................... 415
13.1. Решение системы линейных уравнений........................................................................... 416
13.2. Уменьшение ширины ленты матрицы ............................................................................. 419
13.3. Умножение матриц ............................................................................................................ 422
13.4. Определители и перманенты............................................................................................. 425
13.5. Условная и безусловная оптимизация.............................................................................. 427
13.6. Линейное программирование ........................................................................................... 431
13.7. Генерирование случайных чисел...................................................................................... 435
13.8. Разложение на множители и проверка чисел на простоту ............................................. 440
13.9. Арифметика произвольной точности............................................................................... 443
13.10. Задача о рюкзаке .............................................................................................................. 448
13.11. Дискретное преобразование Фурье ................................................................................ 451
Глава 14. Комбинаторные задачи............................................................................ 455
14.1. Сортировка ......................................................................................................................... 456
14.2. Поиск.................................................................................................................................. 461
14.3. Поиск медианы и выбор элементов.................................................................................. 465
14.4. Генерирование перестановок............................................................................................ 468
14.5. Генерирование подмножеств ............................................................................................ 472
14.6. Генерирование разбиений ................................................................................................. 475
14.7. Генерирование графов....................................................................................................... 479
14.8. Календарные вычисления.................................................................................................. 484
14.9. Календарное планирование............................................................................................... 486
14.10. Выполнимость.................................................................................................................. 489
Глава 15. Задачи на графах c полиномиальным временем исполнения ......... 493
15.1. Компоненты связности...................................................................................................... 494
15.2. Топологическая сортировка.............................................................................................. 497
15.3. Минимальные остовные деревья...................................................................................... 500
15.4. Поиск кратчайшего пути................................................................................................... 505
15.5. Транзитивное замыкание и транзитивная редукция ....................................................... 511
15.6. Паросочетание................................................................................................................... 514
15.7. Задача поиска эйлерова цикла и задача китайского почтальона ................................... 517
15.8. Реберная и вершинная связность...................................................................................... 521
15.9. Потоки в сети ..................................................................................................................... 524
15.10. Рисование графов............................................................................................................. 528
15.11. Рисование деревьев.......................................................................................................... 531
15.12. Планарность ..................................................................................................................... 534
Глава 16. Сложные задачи на графах ..................................................................... 538
16.1. Задача о клике .................................................................................................................... 539
16.2. Независимое множество.................................................................................................... 542
16.3. Вершинное покрытие ........................................................................................................ 544
16.4. Задача коммивояжера........................................................................................................ 547
16.5. Гамильтонов цикл.............................................................................................................. 551
16.6. Разбиение графов............................................................................................................... 554
16.7. Вершинная раскраска ........................................................................................................ 557
16.8. Реберная раскраска ............................................................................................................ 561
16.9. Изоморфизм графов........................................................................................................... 563
Оглавление 11
16.10. Дерево Штейнера............................................................................................................. 568
16.11. Разрывающее множество ребер или вершин................................................................. 572
Глава 17. Вычислительная геометрия ................................................................... 576
17.1. Элементарные задачи вычислительной геометрии......................................................... 577
17.2. Выпуклая оболочка............................................................................................................ 581
17.3. Триангуляция ..................................................................................................................... 585
17.4. Диаграммы Вороного ........................................................................................................ 589
17.5. Поиск ближайшей точки ................................................................................................... 592
17.6. Поиск в области ................................................................................................................. 596
17.7. Местоположение точки ..................................................................................................... 599
17.8. Выявление пересечений .................................................................................................... 603
17.9. Разложение по контейнерам ............................................................................................. 607
17.10. Преобразование к срединной оси................................................................................... 610
17.11. Разбиение многоугольника на части .............................................................................. 613
17.12. Упрощение многоугольников ......................................................................................... 615
17.13. Выявление сходства фигур ............................................................................................. 619
17.14. Планирование перемещений........................................................................................... 621
17.15. Конфигурации прямых .................................................................................................... 625
17.16. Сумма Минковского ........................................................................................................ 628
Глава 18. Множества и строки................................................................................. 631
18.1. Поиск покрытия множества .............................................................................................. 631
18.2. Задача укладки множества ................................................................................................ 635
18.3. Сравнение строк................................................................................................................. 638
18.4. Нечеткое сравнение строк................................................................................................. 641
18.5. Сжатие текста..................................................................................................................... 647
18.6. Криптография.................................................................................................................... 651
18.7. Минимизация конечного автомата................................................................................... 656
18.8. Максимальная общая подстрока....................................................................................... 659
18.9. Поиск минимальной общей надстроки ............................................................................ 663
Глава 19. Ресурсы ....................................................................................................... 666
19.1. Программные системы...................................................................................................... 666
19.1.1. Библиотека LEDA.................................................................................................. 666
19.1.2. Библиотека CGAL.................................................................................................. 667
19.1.3. Библиотека Boost ................................................................................................... 668
19.1.4. Библиотека GOBLIN ............................................................................................. 668
19.1.5. Библиотека Netlib .................................................................................................. 668
19.1.6. Коллекция алгоритмов ассоциации ACM............................................................ 669
19.1.7. Сайты SourceForge и CPAN .................................................................................. 669
19.1.8. Система Stanford GraphBase ................................................................................. 669
19.1.9. Пакет Combinatorica .............................................................................................. 670
19.1.10. Программы из книг.............................................................................................. 670
19.2. Источники данных ............................................................................................................. 672
19.3. Библиографические ресурсы............................................................................................. 673
19.4. Профессиональные консалтинговые услуги.................................................................... 673
Список литературы.................................................................................................... 675
Предметный указатель .............................................................................................. 713
Штрихкод:   9785977505604
Аудитория:   Общая аудитория
Бумага:   Офсет
Масса:   750 г
Размеры:   240x 170x 35 мм
Оформление:   Лакировка
Тираж:   1 500
Литературная форма:   Практическое руководство
Сведения об издании:   2-е издание
Тип иллюстраций:   Черно-белые
Метки:  Близкие метки
Отзывы
Найти пункт
 Выбрать станцию:
жирным выделены станции, где есть пункты самовывоза
Выбрать пункт:
Поиск по названию улиц:
Подписка 
Введите Reader's код или e-mail
Периодичность
При каждом поступлении товара
Не чаще 1 раза в неделю
Не чаще 1 раза в месяц
Мы перезвоним

Возникли сложности с дозвоном? Оформите заявку, и в течение часа мы перезвоним Вам сами!

Captcha
Обновить
Сообщение об ошибке

Обрамите звездочками (*) место ошибки или опишите саму ошибку.

Скриншот ошибки:

Введите код:*

Captcha
Обновить