Register · 
Username: Password:
 ·  Forgot password?

Steven S. Skiena / Стивен С. Скиена - The Algorithm Design Manual (2th Edition) / Алгоритмы. Руководство по разработке (2-е издание) [2011, PDF, RUS]

Reply to topic
DL-List and Torrent activity [Update пиров]
Size:  26 MB   |    Registered:  5 months 25 days   |    Completed:  1 time

Seeder not seen: 2 hours 41 minute

 
   
 
 
 
Author Message

rychkalov ®

Gender:

Longevity: 6 years 4 months

Posts: 18690

Post 22-Aug-2019 18:31

[Quote]

The Algorithm Design Manual (2th Edition) / Алгоритмы. Руководство по разработке (2-е издание)
Год издания: 2011
Автор: Steven S. Skiena / Стивен С. Скиена
Жанр или тематика: Анализ и построение алгоритмов
Издательство: БХВ-Петербург
ISBN: 978-5-9775-0560-4
Язык: Русский
Формат: PDF
Качество: Распознанный текст с ошибками (OCR)
Интерактивное оглавление: Да
Количество страниц: 722
Описание: Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 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. Умножение матриц ......................................................................................................636 Оглавление
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. Транзитивное замыкание ........................................................................................... 2338 Оглавление
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-деревья ........................................................................................................................... 41010 Оглавление
Глава 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
Доп. информация: На данный момент наилучшее качество этого издания.
[ru-zerkalo.org]_t_5765348
Torrent: Registered ·  [ 2019-08-22 18:31 ] ·  33292bf33eca9917278539debbc2d1c45df2c53a

17 KB

Status: checked
Completed: 1 times
Size: 26 MB
Rating: 
(Votes: 0)
Say thanks: 0  Thanks
 
Похожие темы
[Profile] [PM]
Display posts from previous:    
Reply to topic

The time now is: Today 15:04

All times are GMT + 7 Hours



You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum