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

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

Авторизация

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

Красота

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

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

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

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

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

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

Аннотация:

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

Язык:

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

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

ed2k: ed2k stats

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

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

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

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

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

Метод исключения Гаусса      462
Метод квадратов Фибоначчи      156—158 175
Метод Монте-Карло (в возвращении)      131—133 139 171 183
Метод нерекурсивного модульного решета      154—158
Метод обобщенного модульного решета      155 173
Метод отбраковки изоморфных объектов      161—162 174
Метод простых чисел      154—155 158 180
Метод рекурсивного решета      158—160
Метод решета      153—162 173—174
Метод цепочек      292—293
Метод Эратосфена решета      154—155 158 159
Методы вычисления адреса      282—299
Минимальный и минимум      356
Минимум остовных деревьев      357—361 433
Минимум покрытий вершин      452
Многопродуктовый поток      461
Многошаговый процесс решения      150
Множество      72
Множество вершинное      440 464
Множество обратных связей      440 464
Множество реберное      470
Мост (в графе)      436
Мультимножество      72
Мультипликативные функции хеширования      290
Начальная ячейка последовательности      52
Невыполнимость      450
Недетерминированные алгоритмы      445—453 458
Недетерминированные алгоритмы для выполнимости      448
Недетерминированные алгоритмы для задачи коммивояжера      445
Недетерминированные алгоритмы для поиска с возвращением      458
Неоднородные рекуррентные соотношения      97—98
Несравнимые прямоугольники      175
Неудача (функция)      444
Неустойчивость      98
Нижние границы алгоритмов выбора      342
Нижние границы алгоритмов слияния      338—340
Нижние границы алгоритмов сортировки      309—313
Новое хеширование      287
Нумерация Штралера      69
Обратное ребро      363
Ограничение      129
Однородные рекуррентные соотношения      94—97
Оптимальность алгоритмов      16—17
Оптимальные боры      462
Оптимальные коды, сохраняющие разности      20—23 135—140 171
Орграф (= ориентированный граф)      351
Ортогональные латинские квадраты      178
Основание системы счисления      46—49
Основание системы счисления r      46
Основание системы счисления двоичной      46 193
Основание системы счисления десятичной      46
Основание системы счисления с убывающими факториалами      48 191
Основание системы счисления с факториалами      48 184 188
Основание системы счисления смешанное      47—48
Основание системы счисления уравновешенной тернарной      82
Отец (в дереве)      59—60
Открытая адресация      291
Отрезки исходные      329—330
Отсечение ветвей      129
Отыскание середины квадрата      290
Очередь      55—58
Очередь с двумя концами (= дек)      84
Очередь с приоритетом      84
Очередь, последовательная реализация      56
Очередь, связанное распределение      57—58
Ошибка абсолютная      96
Ошибка относительная      97
Пандиагональные магические квадраты      178
Паросочетание (в графах)      439
Пентамино      176
Перестановки      110—118 182 184—195 218—219
Перестановки случайные      194—195 220 223 224
Перестановки, беспорядки      224
Перестановки, векторы инверсии      187—188
Перестановки, венки      224
Перестановки, группы      112
Перестановки, лексикографический порядок      181—187 222—223
Перестановки, порядок минимального изменения      191—194 220 223
Перестановки, представление вложенными циклами      189—194 219
Перестановки, представление цикла      112
Петля (в графе)      351
Пирамида      250 322—324
Подграфы      356
Подграфы индуцированные      356
Подграфы максимальные полные (= клики)      389
Подграфы полные      450
Подграфы, изоморфизм      959
Поиск      125—170 226—295
Поиск быстрый      226—296
Поиск в глубину      134 761 366 426
Поиск в ширину      377 466
Поиск исчерпывающий      170—174
Поиск общий бинарный      296 301 236—240
Поиск последовательный      230—235
Поиск приближения      162—170
Поиск цифровой (боры)      253—257
Поиск, вычисление адреса (хеширование)      240—253 258—277 296—298
Поиск, самоорганизующиеся файлы      254 295 301
Поле      228
Поле INFO      52
Поле LINK      52
Поле NAME      241
Полиномиально сводимый      460
Полиномиальный алгоритм      460
Полустепень захода вершины      397
Полустепень исхода вершины      397
Понятие «O-большое»      88—99
Понятие «o-малое»      88—89
Поперечное ребро      370
Порог (кода, сохраняющего разности)      19
Порождение всех подмножеств      196—202
Порождение подмножеств      195—212
Порождение сочетаний      202—212
Порядок (в дереве)      59
Порядок минимального изменения      183
Порядок минимального изменения для перестановок      191—193 220 223
Порядок минимального изменения для сочетаний      204—205 221
Последователь (вершины)      354
Последовательная реализация      56—57
Последовательная реализация очереди      56
Последовательная реализация последовательности      56—57
Последовательная реализация стеков      55
Последовательная реализация таблиц      234
Последовательности      48—58 (см. также «Связанное распределение»)
Последовательности переходов      196
Последовательности сумм      180
Поток в сети      425 439—440 461
Потомок (в дереве)      59
Правило Де Моргана      447
Представление графов      352—356
Представление деревьев      60—62
Представление комбинаторных объектов      44—86
Представление лесов      60—62
Представление множеств      72—80
Представление целых      45—48
Представление чисел      46—49
Представление чисел в двоичной системе      46
Представление чисел в десятичной системе      46
Представление чисел в системе по основанию r      46—47
Представление чисел в системе Фибоначчи      83
Представление чисел в смешанной системе счисления      47
Представление чисел в уравновешенной тернарной системе      82
Представление чисел вычетами      83
Предшественник (вершины)      355
Преобразование числа в его представлении в системе счисления      47—48
Преобразуемая (задача)      446 459
Приближение Стирлинга      93 120 311
Приведенные латинские квадраты      178
Прикладные задачи      349 351
Принцип оптимальности      150

Программирование линейное      459
Программирование целочисленное      464
Производящие функции      86 103—109 118 211
Производящие функции, изменение масштаба      106—107
Производящие функции, линейные операции      104
Производящие функции, свертка      107—109
Производящие функции, сдвиг начала      104—105
Производящие функции, таблица      105
Производящие функции, частичные суммы      106
Пропускная способность      354 439
Простой путь (в графе)      356
Пространство имен      225
Прохождение дерева в глубину      62—66 84 126
Прохождение дерева снизу вверх      62 63 84
Прохождение дерева, симметричный порядок      63 66
Псевдоквадраты      180
Путь (в орграфе)      356
Путь простой      356
Путь, цикл      356
Разбиения (множеств)      220 225
Разбиения (целых чисел)      213-218 221 225
Разбиения случайные      216—218 222
Разбиения, лексикографический порядок      214 225
Разбиения, словарный порядок      215—216
Разделяющая вершина (= точка сочленения)      366
Размещение памяти для массивов      50 84
Размещение памяти для последовательностей      36—52 254
Размещение памяти связанное      53—58
Размещение памяти, последовательное распределение      49—51 56—58 234
Разностные уравнения (= рекуррентные соотношения)      118
Разреженная матрица      84 462
Разреженные полиномы      463
Разрез      439
Разрешение коллизий      285 291—293
Ранг (кодов сохраняющих разности)      19 37—38 44
Раскраска      110—114 440 461—462
Раскрашиваемость      461—462
Расстояние Хемминга      19
Ребро (графа)      351
Ребро, направленное вперед      370
Рекуррентные соотношения      86 94—103 107—108 118
Рекуррентные соотношения неоднородные      97—98
Рекуррентные соотношения однородные      94—95
Ряд Тейлора      103
Сбалансирование      74—77 249—253 261—277 297—298
Сбор мусора      54
Свертка последовательностей      107—109
Сводимая задача      460
Связанное распределение      52—55 (см. также «Связанный список»)
Связанное распределение очереди      55—58
Связанное распределение последовательности      52—55
Связанное распределение стека      55—58
Связанный список      52—55 84 234
Сжатие путей (в алгоритме объединения/отыскания)      76
Симметрическая разность      383
Симметричный порядок прохождения дерева      64
Система переписывания      458
Слияние      129 151 308 338—340
Слияние бинарное      338—340 344 350
Слияние прямое      338—339 349
Слияние прямое, нижняя граница      339
Сложение порогов (в кодах сохраняющих разности)      22—23
Случайные деревья      250—251 258—261 297
Случайные конфигурации, беспорядки      224
Случайные конфигурации, венок перестановок      224
Случайные перестановки      194—195 220 222—224
Случайные разбиения (целых чисел)      216—218
Случайные сочетания      209 220
Смежные вершины      356
Собственный адрес      285
Совершенное распределение (в многофазном слиянии)      332
Сортировка быстрая      316—321 344—350
Сортировка внешняя      329—334
Сортировка внутренняя      308—329
Сортировка вставками      312—314 344
Сортировка выбором      321—326
Сортировка выбором с замещением      330
Сортировка каскадным слиянием      343
Сортировка линейным алгоритмом выбора      335
Сортировка многофазным слиянием      332
Сортировка наименьшей занумерованной вершиной      404
Сортировка нижней оценкой      309—312
Сортировка обменная      314—321
Сортировка перечислением      344
Сортировка пирамидальная      324—326 342
Сортировка пузырьковая      314—316
Сортировка распределяющая      308 326—329
Сортировка с уменьшающимся шагом (сортировка Шелла)      344
Сортировка слиянием      330—334 338—340
Сортировка топологическая      365—366 427
Сортировка устойчивая      347
Сортировка цифровая обменная      346
Сортировка цифровая распределяющая      327 347
Сортировка, шейкер-сортировка      345
Сосед (вершины)      355
Составное число      363
Список ребер      354
Способ декомпозиции с возвращением      130—131
Способы декомпозиции      23—25 150
Способы композиции      21—23
Стек      55—58
Сток      433
Структура смежности      354—355
Счастливые числа      158 173 180
Сын (в дереве)      59
Таблица динамическая      229 257
Таблица статическая      229 235—236
Табличный порядок      227
Теорема о максимальном потоке и минимальном разрезе      440
Теория вероятностей      351
Теория вычислимости      459
Теория графов      424—425
Теория информации      35
Теория кодирования      296
Теория перечисления Пойа      117
Точка решетки      225
Точка сочленения      366
Транзитивное замыкание      374—377 427 436
Транзитивное сокращение      436
Транзитивный орграф      436
Транспортные сети      439
Трехсвязность      427
Указатель      228
Указатель FATHER      60
Указатель LEFT      61
Указатель RIGHT      61
Упаковка множества      464
Упорядочение дерева (= техника перестройки дерева)      130 141
Упорядоченные прохождения дерева      63 (см. также «Симметричный порядок прохождения дерева»)
Упорядоченные таблицы хеширования      299 305
Успех      444
Файл      228
Фибоначчи (= Леонардо из Пизы)      94
Фибоначчи деревья (= наиболее асимметричные деревья, сбалансированные по высоте)      262—263
Фибоначчи квадраты      156 157 173
Фибоначчи поиск      300—301
Фибоначчи числа      94—96 156 157 173
Фибоначчи числовая система      83
Фундаментальное множество циклов (в графе)      382—386
Функции хеширования      288—291 299
Функции хеширования, метод середины квадрата      290
Функции хеширования, методы деления      291
Функции хеширования, мультипликативные методы      290
Характеристический вектор (последовательности)      51—52
Хеширование      73 282—288
Хеширование середины квадрата      290
Хроматическое число      440
Циклы в графе      358
Циклы в подстановках      112—113
Циклы вложенные в перестановках      189—191

1 2 3

Реклама

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

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

Valid HTML 4.01!

|

Valid CSS!

О проекте