Рейнгольд Э., Нивергельт Ю., Део Н. — Комбинаторные алгоритмы: теория и практика :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Красота

Рейнгольд Э., Нивергельт Ю., Део Н. — Комбинаторные алгоритмы: теория и практика

Рейнгольд Э., Нивергельт Ю., Део Н. — Комбинаторные алгоритмы: теория и практика

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Комбинаторные алгоритмы: теория и практика

Авторы: Рейнгольд Э., Нивергельт Ю., Део Н.

Аннотация:

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

Язык:

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1980

Количество страниц: 476

Добавлена в каталог: 09.12.2004

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

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

= Хеммингово расстояние между двоичными последовательностями и , т.е. число разрядов, в которых они различаются      19
— n-е гармоническое число = $\sum_{k=1}^n 1/k=\ln n+O(1)-n$       93
$\alpha$ - $\beta$ -отсечение      145—150 172 179
$\alpha$ -отсечение      147
$\beta$ -отсечение      147
$\Lambda$ (пустой указатель)      53
$\mathrm{WB}(\alpha)$       270
$\mathscr{H}(p_1,\ldots,p_n)$ — энтропия = $-\sum_{i=1}^n p_i\lg p_i$ (для $n\geq2$ )      35
$\mathscr{H}(\alpha)$ — частный случай энтропии = $-\alpha\lg\alpha-(1-\alpha)\lg(1-\alpha)$       272
$\mathscr{N}\mathscr{P}$       441
$\mathscr{N}\mathscr{P}$ -3-выполнимость      448 459
$\mathscr{N}\mathscr{P}$ -вершинное множество обратных связей      464
$\mathscr{N}\mathscr{P}$ -вершинное покрытие      452
$\mathscr{N}\mathscr{P}$ -выполнимость      446 459
$\mathscr{N}\mathscr{P}$ -гамильтонов цикл      453—454
$\mathscr{N}\mathscr{P}$ -изоморфизм подграфов      459
$\mathscr{N}\mathscr{P}$ -матричные задачи      462
$\mathscr{N}\mathscr{P}$ -многопродуктовый поток      461
$\mathscr{N}\mathscr{P}$ -полный подграф      450—451
$\mathscr{N}\mathscr{P}$ -раскрашиваемость      461—462
$\mathscr{N}\mathscr{P}$ -реберное множество обратных связей      464
$\mathscr{N}\mathscr{P}$ -составление расписания      461
$\mathscr{N}\mathscr{P}$ -трудные задачи: задача коммивояжера      456—458 464—465
$\mathscr{N}\mathscr{P}$ -трудные задачи: максимум клик      451
$\mathscr{N}\mathscr{P}$ -трудные задачи: минимальное покрытие вершин      452
$\mathscr{N}\mathscr{P}$ -трудные задачи: разреженные полиномы      463
$\mathscr{N}\mathscr{P}$ -трудные задачи: целочисленное программирование      464
$\mathscr{N}\mathscr{P}$ -трудный      445
$\mathscr{N}\mathscr{P}$ -упаковка множеств      464
$\mathscr{P}$       441
$\varepsilon$ -субоптимальность      457—458
3-выполнимость      448
B-деревья      см. «Сильно ветвящиеся деревья»
DFS-дерево      363-364
DP-t-код      49 (см. также «Коды сохраняющие
get-cell      54
ILLIAC      1 42
k-выполнимость      448
K-подмножества (сочетания)      202—212 220
K-подмножества, лексикографический порядок      202—204 220
K-подмножества, порядок минимального изменения      204—212
K-подмножества, случайные K-множества      212 220
lg* (повторный логарифм по основанию 2)      77
lowlink(v)      373
lowpt(v)      367—368
Maniac II      343
nexlopt(v)      404
num(v)      363
Overflow      56
Padj(v)      406
Pr(x) (вероятность события x)      148
rand(k,l)      194
U (последовательность Улама)      160
Underflow      57
Y-пентамино      177
Алгоритм ближайшего соседа      163—165 358—360 425
Алгоритм включения ближайшего города      165—170
Алгоритм Евклида      105
Алгоритм на графах, вершинная база      433
Алгоритм на графах, вершинное множество обратных связей      440
Алгоритм на графах, гамильтонов цикл      452—456
Алгоритм на графах, двусвязные компоненты      366—369 426
Алгоритм на графах, доминатор      439
Алгоритм на графах, жадный алгоритм      74 358 425
Алгоритм на графах, задача коммивояжера      140—145
Алгоритм на графах, изоморфизм      396—402 431—432 459—460
Алгоритм на графах, клика (максимальная)      433 437 451
Алгоритм на графах, клики (все)      389—396 430 433 437
Алгоритм на графах, кратчайшие пути      377—382 452 428—429 333 451
Алгоритм на графах, максимальное независимое множество вершин      438
Алгоритм на графах, мосты      435
Алгоритм на графах, остовное дерево (минимальное)      357—360 425 433—434
Алгоритм на графах, остовные деревья (все)      357—360 425 433—434
Алгоритм на графах, планарность      402—424 433 438
Алгоритм на графах, поиск в глубину      361—366 426
Алгоритм на графах, поиск в ширину      377—436
Алгоритм на графах, покрытие вершин      452—453
Алгоритм на графах, поток в сети      439—440 461
Алгоритм на графах, раскраска      440 461—462
Алгоритм на графах, реберное множество обратных связей      440
Алгоритм на графах, связные компоненты      364
Алгоритм на графах, сильно связные компоненты      369—373 426 436
Алгоритм на графах, топологическая сортировка      365—366 427 432
Алгоритм на графах, транзитивное замыкание      374—376 427—428 436
Алгоритм на графах, транзитивное сокращение      436
Алгоритм на графах, циклы (все)      384—389 429 433 437
Алгоритм на графах, циклы (фундаментальное множество)      382—384 429 437
Алгоритм на графах, эйлеров путь      439
Алгоритм отыскания      74 (см. также «Алгоритм объединения отыскания»)
Алгоритм самого дешевого включения      181
Алгоритм слияния множеств      72—80 358
Алгоритм суммирования числа единиц в двоичном наборе      12—17 24—25 42
Алгоритмы на графах      352—440
Анализ алгоритмов      36—41
Анализ сетей      351 360
Асимптотики      38—94
Асимптотические ряды      90—91
Асимптотический рост      88 90—91
Бернсайда лемма      114 116—117
Беспорядки      224
Боры      255—256 297 462
Брат (в дереве)      59
Венок перестановок      224
Вершина (графа)      351
Вершина смежная      355
Вершина, последователь      354
Вершина, предшественник      355
Вершина, соседи      355
Вершинная база      439
Вершинное покрытие      452
Ветви и границы      140—150 171 360
Взвешенная длина пути      242 249—252
Включение в бинарные деревья поиска      258
Включение в боры      258
Включение в очереди      56—58
Включение в последовательно размещенные списки      49—51
Включение в сбалансированные по весам бинарные деревья поиска      269—271
Включение в сбалансированные по высоте бинарные деревья поиска      261—266
Включение в связные списки      51
Включение в стеки      51
Включение в таблицу хеширования      287 291—293
Включение в упорядоченные хеш-таблицы      305
Вложенные циклы (в перестановке)      189—191
Внешние узлы (дерева)      58
Внутренние узлы (дерева)      58
Возвращение      87 124—153 166—170 171 183 185 196 361 386 391
Возвращение, ветви и границы      140—150 171 360
Возвращение, динамическое программирование      150—153 172 243 437 442
Возвращение, использование макрорасширений      133—134 139 171
Возвращение, недетерминированный алгоритм      453 454 458
Возвращение, общий алгоритм      125—128
Возвращение, оценка сложности выполнения      131—133 171
Возвращение, применение к DP 1 кодам      135—140 171
Возвращение, усовершенствования      128—131
Вращение      264—265 274—276
Вращение двойное      264—265 276—277 303
Выполнимость      446—450
Высота (дерева)      66
Гамильтонов цикл      452—456
Гармонические числа      93
Грамматический разбор      124
Граф      351
Граф ациклический      356
Граф взвешенный      354
Граф гомеоморфный      438
Граф двудольный      439
Граф двусвязный      366—369
Граф изолированный      366
Граф изоморфный      396—398
Граф Муна — Мозера      390—391 430

Граф неориентированный      351
Граф неразделимый      см. «Граф двусвязный»
Граф несвязный      356
Граф ориентированный      351
Граф планарный      402
Граф плотный      354
Граф полный      359 480
Граф простой      351 354
Граф разделимый      366
Граф разреженный      354
Граф связный      356
Граф, доминатор      439
Граф, подграф      356
Граф, представления      352—355
Граф, связные компоненты      356
Граф, сильно связные компоненты      359 369—374 426 435
Графа дополнение      438
Группа (перестановок)      112—118
Дважды связанный список      55
Двойное хеширование      292 293—295
Деревья      26—28 58—72 357
Деревья бинарного поиска      162 240—254
Деревья бинарные      54 107—109
Деревья корневые      58 357
Деревья монотонные      249—253 297
Деревья остовные      357—361 425—426 433
Деревья полностью сбалансированные бинарные      70 239
Деревья прошитые      84—85
Деревья пустые бинарные      59
Деревья расширенные t-арные      86
Деревья расширенные бинарные      68
Деревья решений      26—28 311
Деревья сбалансированные      248—283 261—277 297—298
Деревья случайные бинарные      249—253 258—261 297 302
Деревья тернарные      27—28
Деревья, 3-2-деревья      298
Деревья, длина внешних путей      66—72 298 311 239
Деревья, длина внутренних путей      66—72 121—122 240
Деревья, длина максимальная      69—70
Деревья, длина минимальная      70—72
Деревья, естественное соответствие между бинарными деревьями и лесами      62 64
Деревья, игры      126—149
Деревья, пирамида      250 322—324
Деревья, представления      60—62
Деревья, прохождения      62—66 126
Деревья, раскраска узлов      110—116
Деревья, сбалансированные по весам      269—277 298 303
Деревья, сбалансированные по высоте      261—269 298 303
Деревья, сильно ветвящиеся      278—282 298 303
Детерминированный алгоритм      453
Дизъюнкт (в булевом выражении)      447
Динамическое программирование      150—153 437 442
Естественное соответствие (между бинарными деревьями и лесами)      62 64
Естественный порядок (таблицы)      226 294
Задача о кёнигсбергских мостах      424
Задачи коммивояжера      140—145 150—153 162—170 354 425 445 450 456—458 459
Задачи о назначениях      179
Задачи о потоке      439—440 461
Задачи о почтовых марках      175
Задачи о расписании занятий      461
Задачи о фальшивой монете      26—36 43—44 58 71—72
Задачи о ферзях      127—131 135 136 161—162 176
Задачи об упаковках      179
Задачи покрытия (паркеты)      175
Задачи составления расписаний      124 175 179 351
Закон Зипфа      233 234 304
Золотое сечение      95 156 263—264
Имена      226
Инверсии (в перестановке)      187
Инверсии, выбор инверсий      187—188 219 223 315
Индуцированный подграф      356
Информационный поиск      390 430
Исключение из бинарных деревьев      259
Исключение из боров      258
Исключение из очередей      56—58
Исключение из последовательно размещенных списков      49—51
Исключение из сбалансированных по весам бинарных деревьев поиска      269—271
Исключение из сбалансированных по высоте бинарных деревьев поиска      281 282
Исключение из сбалансированных сильно ветвящихся деревьев      277—282
Исключение из связанных списков      49—51
Исключение из таблицы хеширования      258
Исключение из характеристического вектора      51
Исследование операций      351 425 458
Исходные отрезки      329—330 343
Каскадное слияние      343 349
Квадратичные вычеты      157
Квадратичные невычеты      157
Китайское кольцо      220
Классы алгоритмов      25—36 309—310
Клики (в графах)      389
Клики, максимальная клика      433—435
Клики, порождение всех клик      389—396 430 433 437
Ключ      228
Кодирование хеширования      285; см. «Методы вычисления адреса»
Коды Грея      43 196—202 220—221 224—225
Коды Грея двоично-отраженные      197—198 221
Коды Грея, порождения      191—202 205—212
Коды Грея, последовательность прохождения      197—198
Коды оптимальные      20—21 23 135—140 171
Коды цепные      42
Коды, сложение порогов      22—23
Коды, сохраняющие разности      17—25 37—41 44 196
Коды, увеличение ранга      23 37—38
Коллизия      285—286
Комбинаторная математика      7 41
Комбинаторные вычисления      22
Композиции (целых чисел)      213—214 221—222 225
Конъюнктивная нормальная форма      447
Корень (дерева)      58—59
Коэффициент загрузки      293—295
Кратчайшие пути (в графе)      377—382 425 428—429 433 459
Кратчайшие пути из одной вершины в другую      377—378
Кратчайшие пути из одной вершины до всех остальных вершин      380
Кратчайшие пути между всеми парами вершин      381—382
Кратчайшие пути, отрицательные веса      380—381
Крестики-нолики      145—147 179
Куб Минусинского      177
Кубики сома      176
Куратовского теорема      438
Латинские квадраты      178
Лексикографически меньше чем      161 184
Лексикографический порядок в бинарном дереве      61 (см. также «Симметричный порядок прохождения дерева»)
Лексикографический порядок перестановок      181 184—187 219 222—223
Лексикографический порядок разбиений      214—218 225
Лексикографический порядок сочетаний      202—204 221
Лес (= множество деревьев)      59 62—66
Линейные рекуррентные соотношения      94—98
Линейные уравнения      462
Листья (дерева)      58 (см. также «Внешние узлы»)
Литерал (в булевском выражении)      447
Магические квадраты      177
Макроконструкции в возвращении      133—135 139 171
Макроконструкции в порождении перестановок      194 220 223
Максимальное независимое множество вершин      438
Максимальный и максимум      356
Максимум клик      433 448 451
Маркова цепи      351
Маршрут коня      153
Массива размещение      49—50 83
Математическая логика      458
Матрица      см. также «Массива размещение»
Матрица весов      354
Матрица инциденций      438
Матрица разреженная      84 462
Матрица связности      374
Матрица соединений (= матрица смежностей)      353
Матрица, NP-полные задачи      462
Матрица, логическое произведение      435
Матрица, перемножение      179 428 436
Метод U (последовательность Улама)      160 174 180

1 2 3

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте