Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 289
Текст из файла (страница 289)
1279 Вектор, 1061, 1270 аннулирующий, ! 276 елиничный, ! 270 линейная зависимость, 1275 норма, !274 ортонормальность, 882 скалярное произведение, 1274 тензорное произведение, 1274 Векторное произведение, 1062 Вероатностный анализ, 51, 142-!69 алюритма Рабина — Карпа, 1040 быстрой сортировки, 209-213, 215, 217, 336 вероатностного подсчета, 170 высоты случайно построенного бинарного дерева попою, 332-336 задачи о найме, 166-1 69 идеального хеширование, 311-315 карманной сортировки 231-234 коллизий, 293, 315 многопоточных алгоритмов, 850 наибольшего числа исследований при хешировании, 315 нюкней границы сортировки, 234 парадокса дней рождешш, 157-160 последовательности выпадения орлов, 161-166 разбиения, 207, 213, 215, 217 рандомизированного выбора, 247-249, 256 теста Миллера-Рабина, 1015-!020 универсального хеширомнил, 297-300 хеширования с открытой адресацией, 307-310 хеширование с цепочками, 290-292 шары и корзины, 160, 161 эвристики Полларда, 1022-1025 Вероятностный подсчет, 170 Вероятность, 1241-1248 аксиомы, 1242 распределение, 1242 биномиальное, 1255-1267 геометричесюе, 1254, 1255 дискретное, 1242 непрерывное равномерное.
1243 равномерное, 1243 условнал, 1244 Верхний квадратный юрень, 582 Верхшш медиана, 243 Вершина многоугольника, 1066 переполненная, 776 промежуточная, 731 точка сочленения, 658 Вершинное покрытие, 1139 взвешенное, 1177-1179 Вес пути, 680 ребра, 628 Весовая функция, 628 Весовая эвристикв, 602 Взаимно однозначное соответствие, 1220 Взаимно простые числа, 973 попарно, 974 Взвешенная медиана, 255 Взвешенно-сбалансированное дерево, 371 Предметный указатель !305 Взвешенный матроид, 474-478 Виртуальнаа память, 46 Вложенные боксы, 717 Вложенный параллелизм, 815, 844 Время завершения и сильно связные юмпоненты, 655 Время работы алгоритма, 47 в наилучшем случае, 73 в среднем случае, 142 многопоточного вычисления, 819, 820 ожидаемое, 143 Вставка в В-дерево, 530-535 в бинарное дерево поиска, 327, 328 в битовый вектор с наложенным деревом постоянной высоты, 572 в дерево ван Эмде Боков, 538-590 в дерево отрезков, 383 в дерево порядювой статистики, 376, 377 в динамическую таблицу, 501-504 в красно-черное дерево, 348-356 в очередь, 265 в последовательность, 378 в протоструьтуру ван Эмде Бовен, 580, 581 в связанный список, 269, 270 в стек, 264 в таблицу Юнга, 195 в фибоначчиеву пирамццу, 547, 548 в хеш-таблицу с открытой адресацией, 302 303 элементарная, 501 Вторичная память лерево поиска, 521-541 размещение стека, 539 Вторичная хеш-таблица, 311 Второе минимальное остовное дерево, 674 Входные данные, 26 распределение, 142, 148 Выбор, 250, 251 в дереве порядковой статистики, 373, 374 процессов, 449-457 Выделение объекта, 275, 276 Выметание, 1068-! 075, 1092 по кругу, 1076-1035 Выполнимость, 1175-1! 77 схемы, 1119 †11 формулы, 1128-1131 Выпуклая комбинация, 1061 Выпуклая оболочка, 29, 1075-1086 Выпуклые слои, 1092 Выпуклый многоупшьник, 1066 Выракденность, 916 Высота В-дерева, 526, 527 дерева решений, 222 красно-черного дерева, 342 пирамиды, 181, 188 Вытеснение, 483 Выходные данные, 26 Вычисление многопоточное, 816 полнномов, 64 Вычислимость за полиномиальное время, 1105 Вычислительная геометрия, 1060-1095 Вычислительная задача, 26, 27 Г Гамильтонов путь, 1115, 1152 Гамильтонов цика, 1110, 1141-1146 Гармонический рха, 1200, 1206, 1207 Генератор подгруппы, 988 псевдослучайных чисел, 143 случайных чисел, 143 Геометрическая прогрессия, 1200 Геометрическое распределение, 160 Геометрия вычислительная, 1060-1095 Гиперграф, 1225 Глобальная переменная, 43 Глубина стека, 217 Гонка, 827-829 Горнера схема, 942 Граничные условия, 92 Граф, 1221-1226 е-плотный, 744 алгоритмы, 624-806 атрибут, 625, 629 ациклический, 1223 вершина, 1221 степень, 1222 вершинное покрытие, 1159 взвешенный, 627 гамильтонов, 1111 двудольный, 1225 динамический, 520 изоморфность, 1223 компонентов, 654 кратчайший пугь, 634 матрица инцидентности, 483, 630 матрица смежности, 628 множество вершин, 1221 множество ребер, 1221 независимое множество, 1152 неориентированный, 1221 решетка, 800 ограничений, 705-707 1306 Предметный уназатеьь односвязность, 649 односвязный, 64Я ориентированный, 1221 остовное дерево, 474, 661 отрезков, 456 паросочетание, 77! петля, 1221 плотный, 626 подграф, 1224 подзадач, 400, 401 лопнуть, 1223 поиск в глубвму, 639-649, 660 поиск в ширину, 630-639, 660 полный, 1225 порожденный подграф, 1224 прелставление, 626 простой, 1223 путь, 1222 простой, 1223 разреженный, 626 кратчайшие пути между всеми парами вершин, 738-744 разрез, 663 Раскраска, 1153, 1233 Ребро, 1221 инцидентное, ! 222 связный, 1223 сжатие, ! 225 сильно связный, 1223 смткные вершины, 1222 список смежности, 627 цикл, 1223 Грндонл, 486 Группа, 982-989 абелева, 983 адлнтивная по модулю л, 983 калечная, 983 мультнпликатнвнал по модулю и, 984 циклическая, 998 Групповой анализ, 488-$92 динамической таблицы, 502 для бинарного счетчике, 490, 491 стековых операций, 488-490 Д Данные с плавающей точкой, 46 Двойное хеширование, 305-307, 310 Двойственность, Я2!-Я27, 937 слабая, 922 Дек, 267 Реалнюция стеками, 268 Декартова сумма, 948 Декартово произведение, 1214 Делитель, 970 наибольший общий, 972 общий, 971 тривиаеьный, 970 Дерамида, 367, 371 Дерево, 1226-1233 2-3, 371 2-3-4-дерево, 526, 540 АА, 371 АМ., 366, 370 В*-дерево, 526 В+-дерево, 525 В-лерево, 521-541 амортизнрованное сбалансированное по весу, 510 бинарное, 278, 1230 биномиальное, 564 ван Эмде Бааса, 568-596 вставка, 588-590 кластер, 582 максимум, 586 минимум, 586 предшественник, 588 преемник, 586-588 со сниженным количеством памяти, 593 удаление, 590-592 членство, 586 взвешенно-сбалансированное, 371 внутренний узел, 1229 высота, 1230 дерамида, 367, 371 диаметр, 639 динамичесюе, 519 ворнеаое, 277-281, 1229 косое, 371 красно-черное [см.
Красно-черное дерево], 341 кратчайших путей, 684-715 лист, 1229 остовное графа, 474 остовное, 661 отрезюв, 381-387 пирамида, 179-197 позиционное, 1231 поиска бинарное оптимальное, 431-438, 446 поиска в глубину, 640 поиска в ширину, 631, 637 поиска зкспоненцивльное, 242, 520 полностью бинарное, 1230 порядковой статистики, запросы, 372-378, 380 пустое, 1230 расшнрающееся, 519 ребро, 637, 640 Предмешлый укаэамегь !307 рекурсии, 61, 113-1!Я и мсшд подсгановок, 116-! 18 решений, 221, 222 с й соселями, 371 свободное, 1226-1228 слияний, 242, 520 степень, !230 узел, 1229 упорядоченное, ! 230 центрированный обход, 375 Детерминант, 1276, ! 277 и умножение матриц, 871 Детерминированный алгоритм, 149 Диаметр дерева, 639 Днзьюнвтивная нормальная форма, 1133 Динамическая многопоточность, 812 Динамическая порадювая статистика, 372 — 378 Динамическая таблица, 500-509 анализ метолом бухгалтерского учета, 502 анализ методом потенциалов, 503, 506-508 групповой анализ, 502 юэффициент заполнения, 500 расширение, 500-504 Динамический граф, 520 кратчайшие пути между всеми парами вершин, 746 траизитивное замыкшше, 744, 746 Динамичесюе дерево, 519 Динамическое программирование, 392-447 алгоритм Витерби, 443 шпоритм Флойда-уоршевла, 731-735 битоническая евклидова задача о юммиаояжере, 439 в сравнении с жаднымн алгоритмамн, 457-461 восходящее, 398 вывод с форматированием, 440 задача разрезания сгерлшя, 393-403 запоминание, 421-423 и кратчайшие пути между всеми парами вершин, 724-735 и траизитивное замыкание, 735-737 наидлиннейшая палиндромная подпоследовательность, 439 наидлиинейший простой путь во взвешенном ориентированном ацикличесюм графе, 43Я нисходящее с запоминанием, 398 оптимальная подструктура, 412-417 оптимальные бинарные деревья поиска, 431-438 перекрытие подзадач„417-420 перемножение цепочки матриц, 403-4! 2 поиск нандлнннейшей общей подпоследовательности, 424-43! построение оптимального решения, 420 разбиение строки, 444 расстояние редактирования, 440 связь с методом "разделяй и властвуй", 392 элементы, 412-424 Дисковый накопитель, 522-524 Дискретнаа случайная величина, 1248-1254 Дискретное преобразование Фурье, 30, 946, 952 Дискретный логарифм, 999 Дисперсия, 1252 Джена кратчайшего пути, 634 Длиннейшая общая подпоследовательность, 29 ДНК, 27, 29, 424, 425, 440 Дополнение множества, 1213 Шура, 859 языка, 1107 Допустимое ребро, 788 Допустимое решение, 703, 886 ДПФ, 952 Е Единственность разложения целых чисел, 974 Ж Жадный алгоритм, 448-486 алгоритм Дейкстры, 696-702 алгоритм Крусюяа, 668-670 алгоритм Прима, 670-673 в континуальной задаче о рюкзаке, 460 выбор процессов, 449-457 для кодов Хаффмана, 463-471 для оффлайн-кешированиа, 484 лля размена, 482 лля расписания заданий, 483 для составления расписания, 484 и матроиды, 471-478 на взвешенном матронде, 474-478 оптимальная подструктура, 459 поиска минимального осговного лерева, 667-674 свойство жадного выбора, 458, 459 сравнение с динамическим программированием, 414-461 элементы, 457-462 7308 Предметный указатель 3 Задача абстрактная, 1103 выбора процессов, 449-457 выбора, 243 Иосифа, 388 класс сложности Р, 1104 конкретная, 1!04 линейного программирования, 703, 883, 886 прямая, 921 о вершинном покрытии, 1139 приближенный алгоритм, 1159-1163 о выполнимости схемы, 1121 о выполнимости формулы, 1128 о выходе, 800 о гамильтоновом пути, 1152 о гамильтоновом цикле, 1111, 1141 о гардеробщике, 148 о клике, 1136 о юммивояжере битоническая евклидова, 439 о юммиволжере, 1146 в общем случае, 1167, 1168 приближенный алгоритм, 1163-1169 с неравенством треупшьника, 1164-1166 о кратчайшем пути между всеми вершинами, 681 о кратчайшем пути между заданной парой вершин, 681 о кратчайшем пути, 680 о кратчайших путях в одну вершину, 681 о кратчайших путях из одной вершины, 681 о максимальном потоке, 749, 901 о минимальном покрытии путями, 801 о найме, 140-150, 172 в оперативном режиме, 166-169 о независимом множестве, 1152 о покрытии множества, 1169-1175 о разбиении мншкества, 1152 о раскраске графа, 1154 о рюкзаке дискретная, 460, 462 о рююаке контннуапьная, 460, 462 о самом длинном простом цикле, 1152 о сумме подмножества, 1147 приближенный алгоритм, 1180-1186 об изоморфизме ползрафу, 1151 оптимизации, 392, 1099, 1!03 астапова, 1096 перемножения последовательности матриц, 404 планировании единичных заданий, 479 планирования заданий, 484 поиска максимального подмассива, 93-100, 136 поиска минимального остовного дерева, 661 поиска подстроки, 1031 поиска потока минимальной стоимости, 902 поиска сильно связных юмпонентов графа, 654 поиска циркуляции минимальной стоимости, 938 принятия решения, 1099 проверки остовного дерева, 678 разрешимости системы линейных неравенств, 936 сборщика купонов, 161 сортировки, 26, 38 существования решения, 703 целочисленного линейного программирования, 937, 1151 экземпляр, 26 Закон Кирхгофа, 747 Законы де Моргана, 1133 Замкнутое полукольцо, 746 Заммканне клини, 1107 транзитивное 1см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
