URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика
Id: 34115
 

Комбинаторные алгоритмы. Теория и практика

1980. 480 с. Твердый переплет. Букинист. Состояние: 4. .
Обращаем Ваше внимание, что книги с пометкой "Предварительный заказ!" невозможно купить сразу. Если такие книги содержатся в Вашем заказе, их цена и стоимость доставки не учитываются в общей стоимости заказа. В течение 1-3 дней по электронной почте или СМС мы уточним наличие этих книг или отсутствие возможности их приобретения и сообщим окончательную стоимость заказа.

 Аннотация

Первые два автора известны советскому читателю по переводу их книги «Машинный подход к решению математических задач» (М.: Мир, 1977), написанной совместно с Дж. Фарраром. В данной книге предпринята попытка систематизации комбинаторных алгоритмов, выявления их общих черт и закономерностей. Подробно рассматриваются конкретные задачи использования комбинаторных алгоритмов, в частности очень важная для программирования задача сортировки данных. Каждая глава сопровождается достаточно подробной исторической справкой и большим числом упражнений.

Книга будет полезна математикам-прикладникам, аспирантам и студентам, имеющим дело с задачами дискретной математики.


 ОГЛАВЛЕНИЕ

От редактора перевода.......................

Предисловие.............................

Глава 1. Что такое комбинаторные вычисления?..........

1.1. Пример. Подсчет числа единиц в двоичном наборе.....

1.2. Проблема представления: коды, сохраняющие разности..

1.3. Способы композиции...................

1.4. Способы декомпозиции..................

1.5. Классы алгоритмов....................

1.6. Анализ алгоритмов....................

1.7. Комментарии и ссылки.................

1.8. Упражнения.......................

Глава 2. Представление комбинаторных объектов..........

2.1. Целые..........................

2.2. Последовательности....................

2.2.1. Последовательное распределение..........

2.2.2. Связанное распределение..............

2.2.3. Стеки и очереди..................

2.3. Деревья.........................

2.3.1. Представления...................

2.3.2. Прохождения....................

2.3.3. Длина путей...................

2.4. Множества и мультимножества.............

2.5. Комментарии и ссылки.................

2.6. Упражнения.......................

Глава 3. Подсчет и оценивание..................

3.1. Асимптотики.......................

3.2. Рекуррентные соотношения................

3.2.1. Линейные рекуррентные соотношения с постоянными коэффициентами..................

3.2.2. Общие рекуррентные соотношения.........

3.3. Производящие функции..................

3.4. Подсчет классов эквивалентности: теорема Пойа......

3.4.1. Пример: раскраска бинарного дерева.......

3.4.2. Теорема Пойа и лемма Бернсайда.........

3.5. Комментарии и ссылки.................

3.6. Упражнения.......................

Глава 4. Исчерпывающий поиск..................

4.1. Поиск с возвращением...................

4.1.1. Общий алгоритм.................

4.1.2. Усовершенствования................

4.1.3. Оценка сложности выполнения...........

4.1.4. Два способа программирования........ 133

4.1.5. Пример. Оптимальные коды, сохраняющие разности.. 135

4.1.6. Метод ветвей и границ.............. 140

4.1.7. Динамическое программирование.......... 150

4.2. Методы решета..................... 153

4.2.1. Нерекурсивное модульное решето.......... 154

4.2.2. Рекурсивное решето................. 158

4.2.3. Решето, отбраковывающее изоморфные объекты... 161

4.3. Приближения исчерпывающего поиска.......... 162

4.4. Комментарии и ссылки................. 170

4.5. Упражнения....................... 175

Глава 5 Порождение элементарных комбинаторных объектов..... 182

5.1. Перестановки различных элементов........... 184

5.1.1. Лексикографический порядок............ 184

5.1.2. Векторы инверсий................. 187

5.1.3. Вложенные циклы................. 189

5.1.4. Транспозиция смежных элементов......... 191

5.1.5. Случайные перестановки............. 194

5.2. Подмножества множеств.................. 195

5.2.1. Коды Грея.................... 196

5.2.2. ^-подмножества (сочетания)............. 202

5.3. Композиции и разбиения целых чисел.......... 213

5.3.1. Композиции.................... 213

5.3.2. Разбиения..................... 214

5.4. Комментарии и ссылки................. 218

5.5. Упражнения...................... 222

Глава 6. Быстрый поиск..................... 226

6.1. Поиск и другие операции над таблицами......... 226

6.2. Последовательный поиск................. 230

6.3. Логарифмический поиск в статических таблицах..... 235

6.3.1. Бинарный поиск................. 236

6.3.2. Оптимальные деревья бинарного поиска...... 240

6.3.3. Почти оптимальные деревья бинарного поиска... 248

6.3.4. Цифровой поиск.................. 253

6.4. Логарифмический поиск в динамических таблицах..... 257

6.4.1. Случайные деревья бинарного поиска........ 258

6.4.2. Бинарные деревья, сбалансированные по высоте.. 261

6.4.3. Бинарные деревья, сбалансированные по весу... 269

6.4.4. Сбалансированные сильно ветвящиеся деревья.... 277

6.5. Методы вычисления адреса................ 282

6.5.1. Хеширование и его варианты........... 283

6.5.2. Хеш-функции................... 288

6.5.3. Разрешение коллизий............... 291

6.5.4. Влияние коэффициента загрузки.......... 293

6.6. Комментарии и ссылки.................. 295

6.7. Упражнения....................... 300

Глава 7. Сортировка........................ 307

7.1. Внутренняя сортировка.................. 308

7.1.1. Вставка..................... 312

7.1.2. Обменная сортировка............... 314

7.1.3. Выбор....................... 321

7.1.4. Распределяющая сортировка............ 326

7.2. Внешняя сортировка................... 329

7.3. Частичная сортировка.................. 334

7.3.1. Выбор...................... 335

7.3.2. Слияние...................... 338

7.4. Комментарии и ссылки................. 341

7.5. Упражнения...................... 344

Глава 8. Алгоритмы на графах................... 351

8.1. Представления...................... 352

8.2. Связность и расстояние................. 356

8.2.1. Остовные деревья................. 357

8.2.2. Поиск в глубину................. 361

8.2.3. Двусвязность.................... 366

8.2.4. Сильная связность................. 369

8.2.5. Транзитивное замыкание.............. 374

8.2.6. Кратчайшие пути................. 377

8.3. Циклы.......................... 382

8.3.1. Фундаментальные множества циклов........ 382

8.3.2. Порождение всех циклов............. 384

8.4. Клики.......................... 389

8.5. Изоморфизм....................... 396

8.6. Планарность....................... 402

8.7. Комментарии и ссылки................. 424

8.8. Упражнения....................... 433

Глава 9. Эквивалентность некоторых комбинаторных задач..... 441

9.1. Классы и oJf^.................... 441

9.2. ^^-трудные и JV^-полные задачи........... 445

9.2.1. Выполнимость................... 446

9.2.2. Некоторые ^^-полные задачи........... 450

9.2.3. Еще раз о задаче коммивояжера......... 456

9.3. Комментарии и ссылки.................. 458

9.4. Упражнения...................... 463

Предметный указатель....................... 466

 
© URSS 2016.

Информация о Продавце