Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 290

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 290)

Транзитивное замыкание), 735 язмка, 1107 Запись, 174 Запоминание, 398, 421-423 применение хеширояашш, 421 Запрос, 261 Золотое сечение, 84, 133 И Идеальное паросочетание, 775 Идеальное хеширование, 310-315, 318 Илеальный параллельный юмпьютер, 818 Идентификатор, 544 Иерархия запоминающих устройств, 46 Избыточный поток, 776 Инвариант цикла, 40, 41, 66 автомата поиска подстрок, 1046 автомата поиска подстроки, 1044 алгоритма "поднять-в-начало", 795 алгоритма Дейкстры, 697 алгоритма Прима, 672 алгоритма Рабина-Карпа, 1039 вставки в красно-черное лерево„351 для модульного возведения в степень, 1001 завершение, 4! инициализация, 41 обобщенного алгоритма проталкивания предпотока, 782 обобщенного метода получения минимального остовного дерева, 662 Предметный указатель !309 определения ранга элемента в дереве порядковой статистики, 375 пирамидальной сортировки, 189 поиска в дереве отрезков, 385 поиска в ширину, 632 построения пнрамнаы, 185 правила Горнера, 64 разбиеннл, 199 симплекс-алгоритма, 913 сканирования по Грэхему, 1081 слияния, 54, 55 алучвйной перестановки, 153 сортировки вставкой, 40 сохранение, 41 увеличения ключа в пирамиде, 194 уплотнения списка корней фибоначчиевой пирамиды, 553 Инверсия в последовательности, 65, 148 Индикаторная случайны величина, 144-147 математнчесюе вкидание, 145 Интервал, 381 Интерполяция, 943 кубическим сплайном, 880 полиномом, 948 Инъекция, 1220 Иосифа задача, 388 Испытание Бернулли, 1254 Исток, 751, 752 Итерированная логарифмическая функция, 83 Итерированные функции, 88 Й Йенсена неравенство, 1251 К Кармвйкла числа, 1012, 1020 Карман, 230 Карманная сортировка, 230-234 Каскадное вырезание, 557 Каталана числа, 339, 405 Квадрат ориентированного графа, 630 Квадратичная функции, 50 Квадратичное исследование, 305, 316 Квадратичный вычет, 1027 Квантиль, 253 Кеш, 46, 484 Класс слолвосги, 1108 1ь1Р, 1113 Класс эквивалентности, 971, 1216 Классификация ребер при поиске в ширину, 658 Кластер в битовом векторе с налвкенным деревом постоянной высоты, 572 в дереве ван Эмде Бааса, 582 в протострукгуре ван Эмде Бааса, 575 длл параллельных вычислений, 811 Клика, 1136-1139 Клини замыкание, 1107 Ключ, 38, 174, 260 фиктивный, 432 Ключевое слово многопоточного псевдокода, 815-825 псевдокода, 42, 43 Код, 463 переменной длины, 463 префиксный, 464 фиксированной длины, 463 Хвффмана, 463-471, 486 Кодирование эюемпляров зацачи, 1103-1106 Коллизия, 289 разрешение с помощью открытой адресации, 302-310 разрешение с помощью цепочек, 289-292 Каллинеарносгь, 1062 Комбинаторика, 1235-1241 правило произведенив, 1236 правило суммы, 1235 Комментарии псевдоюда, 43 Компактный список, 282 Комплексный юрень из единицы, 949 Компонент двусввзный, 658 Компьютер идеальный параллельный, 818 Конечный автомат, 1042 для поиска подстроки, 1043-1048 состояние, 1042 функция юнечного состояния, 1042 Конечный фрагмент, 818 Конкатенация, 1032 взыков, 1107 Константа Эйлера, 987 Конфигурация, 1123 Конъюнкгивная нормальная форма, 1131 Корневое дерево представление, 277-281 Кортем, 1214 Косое дерево, 371 Коэффициент заполнения динамической таблицы, 500 палинома, 79 Краона-черное дерево, 341 †3 вставка, 348-356 высота, 342 и пересекающиеся отрезки, 1070 максимальный элемент, 344 минимальный элемент, 344 ослабленное, 344 перестройка, 511 1310 Предметный указатель поворот, 345 — 347 поиск, 344 расширение, 379, 380 свойства, 341-345 соединение, 365 удаление, 356-364 черная высота узла, 342 Кратное, 970 Кратчайшие пути, 680, 722 — 746 алгорипе Беллмана-Форда, 688-692 алгоритм Дейкстры, 696-702 алгоритм масштабироваюш Габона, 718 алгоритм Флойда-уоршелла, 731-735 в ориентированном ацикпичесаом графе, 693-695 во взвешенном графе, 680 дерево, 634-685 и циклы с отрицательным весом, 682, 690-692, 738 из одной вершины, 680-721 алгоритм Беллмена-Форда, 688-692 алгоритм Дейкстры, 696-702 как задача линейного программирования, 900, 901 между всеми вершинами, 681 между всеми парами вершин, 722 — 746 алгоритм Джонсона, 738-744 возведение в квадрат, 723, 729 между парой вершин, 68! неравенство треугольника, 709, 710 оптимальная подструктура, 725-732 ослабление, 685-687 оценка, 685 поиск в ширину, 681 при наличии ребер с отрицательным весом 682, 683 разностные ограничеюш, 702-709 с одной целевой вершиной, 681 свойство верхней границы, 710 свойство ослабления пути, 711, 712 свойспю отсутствия пути, 711 свойство лодграфа предшествовання, 714, 715 свойство сходимости, 711 умнвкение матриц, 724-731, 745 Кратчайший путь, 23 в невзвешенном графе, 634 длина, 634 поиск в ширину, 634-637 Крафта неравенство, 1233 Криптосистема с открытым ключом, 1002-1009, 1029 сертификат, 1008 Критическое ребро, 768 Круг, 1075 Л Лагранжа теорема, 987 Леграюка формула, 944 Левый поворот, 345 Лежандра символ, 1028 Лекснкографическая сортировка, 337 Лемма о делении пополам, 950 о дополнении Шура, 873 о перекрывающихся суффиксах, 1033 о сокрюцении, 949 о суммировании, 951 об итерации префиксной фуюшни, 1053 Фаркаша, 937 Лес, 1225 непересекающихся множеств, 604-603 поиска в глубину, 640 Линейнал функция, 49, 835 Линейное исследование, 304, 305 Линейное неравенство, 886 и линейное равенство, 894 Линейное ограничение, 886 Линейное программирование, 28, 883-886, 939 алгоритм Кармаркара, 939 алгоритмы, 890 базисные переменные, 896 вспомогательная задача, 928 вспомогательная переменная, 895 двойственность, 92 1-927, 937 допустимое решение.

703, 886, 892 задачи максимизации и минимизации, 893 замещение, 910, 911 и кратчайшие пути из одной вершинм, 702-709 каноничесюы форма, 895-897 методы внутренней точки, 939 недопустимое решение, 892 область допусппаых реюеннй, 887 оптимальное решение, 892 основная теорема, 933 поиск начального решении, 927-933 прилвкеиия, 889, 890 применение дла поиска кратчайших путей, 900, 901 применение для поиска максимального потока, 901 применение для поиска многопродуатного потока, 903, 904 применение пля поиска потока минимальной сюимости, 901-903 прямая задача, 921 Предмемяый указатшь 1ЗП симплекс, 888 симплекс-алгоритм, 905 — 939 стандартная форма, 891-895 целевая функция, 887 целевое значение, 887, 892 целочисленное, 890, 937 эквивалентные задачи, 892 зллипсоидный алгоритм, 890, 939 Линейное равенство, 885 и линейное неравенство, 894 Линейное ускорение, 820 Линейный поиск, 45 Логарифм дискретный, 999 Логарифмическаа функция (1об), 81, 82 Логический параллелизм, 816 Логический элемент, 1119 Локальная переменнал, 43 Луч, 1067 М Максимальное паросочегание, 771-775, 1162 Максимальные слои, 1092 Максимальный поток, 747-806 алгоритм Эдмондов-Карпа, 766-769 алгоргпмы проталкивания предпотока, 775-800 и максимальное паросочетание, 771-775 как задача линейного программирование, 901 обновление, 802 Максимальный элемент красно-черного дерева, 344 Максимум, 243 в бинарном дереве поиска, 324 в дереве ваи Эмде бааса, 586 в дереве порядювой статистики, 380 поиск, 244, 245 Мацхззтенсюе расстояние, 255 Маркова неравенство, 1253 Массив, 43 Монжа, 135 передача в качестве параметра, 44 Масштабирование кратчайших путей из одной вершины, 718 Математическое ожидание, 50, 1249-! 251 индикаторной случайной величины, 145 линейность, 1250 Матрица, 1269-1281 133р-разложение, 854 алгебраическое дополнение элемента, 1276 аинулирующий вектор, 1276 Вандермоцяа, 944, 1279 верхнстреугольная, 1271 вырожденная„!275 вычитание, 1272 главная подматрица, 872 детерминант, 1276, 1277 диагональная, 1270 дополнение Шура, 859, 873 единичная, 1270 инцидентности, 483, 630 и разностные ограничения, 705 неориентированного графа, 483 ориентированного графа, 483 квадратная, 1270 минор, 1276 ншкнетреугольнал, 1271 нулеюя, 1270 обратная, 1275 обращение, 845, 866-871 определитель, 1276, 1277 перестановки, 127! положительно определенная, 1277 предшествования, 723 произведение, 1272, 1273 псевдообратнаа, 877 ранг, 1275 полный, 1276 симметричная положительно определенная, 872-874 симметричная, 1272 сингулярное разложение, 882 скалярное произведение, 1272 сложение, 1272 смежности, 628 совместимость, 404 сопряженно-транспонированная, 872 теплица, 963 транспонирование, 836, 1269 мнопшоточное, 831 трехднагональная, 879, 1271 умножение !сн.

Умнолшнне матриц), 403, 852, 1272 эрюпова, 872 Матр д, 471-478, 483, 678 взвешенный, 474 трефовый, 472, 473 матричный, 472 оптимальное подмншкество, 474 сужение, 477 Медиана, 243-257 верхняя, 243 взвешеннал, 255 ншкняя, 243 отсортированных списюв, 254 Метод внутренней точки, 890 1312 Предметный указатель деления, 295, 301 исключения Гаусса, 858 наименьших квадратов, 874-878 подстановок, 108-113 замена переменных, 112 и дерево рекурсии, 116 — 118 потенциалов, 495-499 динамическая таблица, 503 для динамической таблицы, 506-508 "разделяй и властвуй", 52-90 анализ, 57, 58 сортировка слиянием, 53-61 умншкения, 296, 297 Форда-Фалкерсона, 753-770 цепочек, 289-292, 3!6 Минимальное осговное дерево, 661-679 алгоритм Крускала, 668-670 алгоритм Прима, 670-673 второе, 674 динамического графа, 674 обобщенный метод построения, 662-667 связь с матронлами, 472, 474, 475 Минимальный разрез, 760, 770 Минимальный элемент в протострувтуре ван Эмде Боаса, 578, 579 красно-черного дерева, 344 Минимум, 243 в бинарном дереве поиска, 324 в дереве ван Эмле Боаса, 586 в дереве пораженой статистики, 380 поиск, 244, 245 Многопоточное вычисление, 816 Многопоточное планирование, 821-823 Многопоточность динамическая, 8! 2 Многопоточный алгоритм, 32, 811-851 Многоугольник, 1066 Многочлен, 940 Мншкественное присваивание, 43 Множество, 12! 0 — 12! 5 бесконечное, 12!3 дополнение, !2!3 конечное, !213 мощность, 1213 независимое, !! 52 непересекающиеся множества, 1213 несчетное, !213 объединение, 1211 пересечение, !211 перестановка, !220 пустое, 12!0 разбиение, 1213 разность, !211 симметрическая разность, 803 счетное, 1213 частично упорядоченное, 1217 Множитель, 970 Модифицирующая операцна, 261 Модульная арифметика, 79, 966, 982-989 Модульное возведение в степень, 1000 Модульное линейное уравнение, 990-994 Монте массив, 135 Монотонная последовательность, 197 Мост, 658 Мультиграф, 1225 преобразование в эквивалентный неориентированный граф, 629 Мультимножесгво, 1210 Мульткпликативное обратное, 993 Н Наибольший общий делитель, 972, 973, 976 алгоритм Евклида, 976-982 бинарный алгоритм поиска, 1026 нескольких аргументов, 982 Нвидлиннейшая общая подпоследояагельносгь, 424-431, 446 Наиллиннейшая палиндромная подпоследовательность, 439 Наименьшее общее кратное, 982 Наименьший общий предок, 620 Наихудший случай, 50 Направленный отрезок, 1062, 1063 Насыщающее проталкивание, 785 Насыщенное ребро, 779 Натуральный логарифм, 81 Начальный фрагмент, 818 Невзвешенные длиннейшие пути, 4! 5 Невзвешенные кратчайшие пути, 415 Невозрастаюшая пирамила в пирамидальной сортировке, 188-190 построение, !85-188 Невязка, 876 Недопустимое ребро, 789 Независимое мншкество, 1152 Независимое семейство подмншкеств, 472 Независимость подзадач в динамическом программировании, 416, 417 Независимые фрагменты, 829 Ненасыщающее проталкивание, 785 Неориентиромнный граф вычисление минимального остовного дерева, 661-679 мост, 658 точка сочленения, 658 Непересекающиеся множества анализ, 611-617 Предметный указатель !3!3 реализация лесом, 604-608 реализация связанными списками, 600-604 Неравенство Буля, 1247 Йенсена, 1251 Крафта, 1233 линейное, 886 Марковж 1253 треугольника, ! 163 для кратчайших путей, 709, 710 Неубывающая пирамида построение, 185-188 Нижний квадратный корень, 582 Ниющя медиана, 243 Нормальное уравнение, 877 Ньютона бином, 1238 О Обмен валют, 424, 7!7 Оболочка выпуклая, 1075-1086 Обратная подстановка, 856 Обратное ребро, 646 Обращение матрицы, 866-871 Обход дерева, 320, 326 в обратном порядке, 320 в прямом порядке, 320 центрированный, 320 Обход по Джарвису, 1083-1085 Общая подпоследовательность, 29, 425 наидлиннейшая, 424-431, 446 Общее подвыралгение, 958 Общий делитель, 97! наибольший [гм Наибольший общий делитель!, 972 Объединение по рангу, 605 связанных списюв, 601-604 фибоначчиевых пирамид, 549 языков, 1107 Объединяемые пирамиды, 518, 542 Обьект, 43 передача в качестве параметра, 44 реализация массивом, 273-277 Ограничение, 891 линейное, 886 нестрицательности, 89! Ограничитель, 270-272, 342 Однократно связанный список, 269 Односвязный граф, 649 Ожидаемое значение, 1249-1251 Оконечная рекурсии, 216, 455 Определитель, !276, !277 Оптимальная подструктура, 395 в динамичесюм прозраммировании, 412-4!7 в жадном алгоритме, 459 взвешенного матроида, 477 задачи о рюкзаке, 460 юдов Хаффмана, 469, 470 кратчайших путей, 725-732 Оптимальное бинарное дерево поиска, 431-438, 446 Оптимизация, 392 Опустошение очереди, 266 стека, 265 Ориентированный ациклический граф, наидлиннейший простой путь, 439 обратные ребра, 650 топологическаа сортировка, 649-652 граф всеобщий сток, 630 квадрат, 630 кратчайшие нуги из одной вершины, 680-721 кратчайшие пути между всеми парами вершин, 722-746 сдносвязный, 649 покрытие путями, 801 цолусвязный, 658 транспонирование, 629 эйлеров цикл, 659 Ортонормальность векторов, 882 Освобождение объекта, 275, 276 Ослабление ребра, 685-687 Ослабленная пирамида, 567 Ослабленное красно-черное дерево, 344 Основная теорема, 119 доказательство, 123-132 Основной метод, 119-123 Остаток ст деления, 79 Остаток, 971 Остаточнав пропускная способность, 754, 758 Остаточная сеть, 754 †7 Остаточное ребро, 755 Остовное дерево, 474, 661 узкое, 677 Открытая адресация, 302-310 двойное хеширование, 305-307, 310 квадратичное исследование, 305, 316 линейное исследование, 304, 305 Отношение, 12!5-1218 антиснмметрнчное, 12!7 бинарное, 1215 рефлексивное, 1215 симметричное, 1216 транзнтивное, !216 !3!4 Предметный указатель полного порядка, 1217 частичного порядка, 1217 эквивалентности, 1216 Отрезок, 381, 382, 1061 выяснение наличия пересечения, 1063-1066 перекрытие, 382 сравнимые отрезки, 1068 Отсортированный связанный список, 269 Отступы в псевдокоде, 42 Очередь, 264-267 вставка, 265 голова, 266 опустошение, 266 переполнение, 266 с двусторонним доступом, 267 с приоритетами, 190-194 в алгоритме Дейкстры, 699 в алгоритме Прима, 670„ 672 на бюе дерева ван Эмке Боаса, 568-596 невозрастающая, 190 неубывающая, 191 реализация пирамидой, ! 90-! 94 удаление, 265 хвост, 266 П Пваиндром, 439 Память вторичнал, 522 оперативная, 522 распределенная, 8!1 с произвольным доступом, 45-47 совместно используемая, 8! 1 Пара ближайших точек, 1086-1091 Парадокс дней рождения, 157-160, 169 Параллелизм вложенный, 815, 844 логический, 8!6 многопоточного вычисления, 820 рандомнзированного многопоточного алгоритма, 850 Параллельные вычисления, 32 Параллельный мэмпьютер, 811 Параллельный цикл, 824 — 827, 844 Параметр передача по значению, 44 стоимость передачи, 132 Паросочетанне, 771-775 в двудольном графе максимальное, 803 идеальное, 775 максимальной мощности, 1188 Паскаля треугольник, 1240 Первообразный корень Ж„', 998 Перекрестное ребро, 646 Перекрывшощиеся прямоугольники, 387 Перекрытие подзадач, 417-420 Переменная в псевдопэде, 43 Переполнение очереди, 266 стека, 265 Переполненная вершина, 776 разгрузка, 790 Пересечение хорд, 378 языаов, 1!07 Перестановка, 1220, 1236 1с-перестановка, 153 Иосифа, 388 случайная, ! 50-154 Перманентная структура данных, 364, 520 Ппрамила, 179-197 2-3-4-пирамида, 566 о-арнмг, 195, 744 биномиальная, 564 в алгоритме Дейкстры, 700 высота, 181 как очередь с приоритетами, 190-! 94 невозрастмошая, 181 неубыашошая, 181 обьединяемая, 281 обьединлемые пирамиды, 518 ослабленная, 567 построение, 185-188, 195 свойство неубмваюшей пирамиды, 184 свойство, 180 сравнение с фнбоначчиевой пирамидой, 543, 544 Фибоначчи, 542-567 в алгоритме Джонсона, 743 Пирамидальная сортировка, 179-197 Планировщик в многопоточных вычислениях, 816 многопоточных вычислений, 821-823 Поворачивающий множитель, 955 Поворот в красно-черном дереве, 345-347 Подграф, 1224 предшествоаания, 684, 723 поиска в глубину, 640 поиска в ширину, 637 Подгруппа, 987-989 истинная, 987 Подмножество, 121! истинное, 1211 Подпись, 1004 Подпоследовательность, 425 общаа, 425 Подстрока, ! 236 Предметный указатель !315 Поиск, 45 бинарный, 62, 838, 839 в В-дереве, 528, 529 в бинарном дереве поиска, 322, 323 в глубину, 639-649, 660 в поиске сильно связных юмпонентов, 652-658 в топологичесюй сортировке, 649-652 классификация ребер, 646-648 в дереве отрезков, 384-386 в компактном списке, 282 в красно-черном дереве, 344 в неотсортированном массиве, 170 в прстоструктуре ын Эмде Бааса, 577, 578 в связанном списке, 269 в хеш-таблице с открытой адресацией, 303 в ширину, 630-639, 660 и кратчайшие пуси, 634-637 кратчайшие пути, 681 максимальный поток, 766-769 линейный, 45 псдстрок, 1031-!059 алгоритм Кнута-Морриса-Пратга, 1048-1058 алсоритм Рабина-Карпа, 1036-!041 простейший алгоритм, 1034-1036 с помощью юнечного автомата, 1041-1048 Показательная функция, 80, 81 Покрытие вершинное взвешенное, 1! 77-1179 пу ям , 80! Пол, 78 в основной теореме, 128-131 Поле бр(2), 1279 Полинам, 79, 940 асимптотическое поведение, 85 вычисление, 64, 942 вычисление, 947, 965 граница степени, 940 шперпавщия в комплексных корнях единицы, 955, 956 интерполяция полииомом, 948 коэффициент, 79 юэффициенты, 940 представление, основанное на значениях в точках, 943 представление, основанное на коэффициентах, 942 произведение, 941, 946, 947, 963 производная, 964 сложение, 940 степень, 940 сумма, 940 схема Горнера, 942 Полнота языка, 1127 Полуинтервал, 38! Полусвязный граф, 658 Полярный угол, 1066 Попарно взаимно простые числа, 974 Поразрядная сортировка, 228, 229 Порядювая статистика, 243-257 динамическая, 372-378 Порядок в группе, 988 роста, 51 Последовательности выпадения орлов, 161-166 Последовательность бесконечная, 1219 битоническая, 720 вставка, 378 длина, 1219 инверсия, 65, 148 юнечная, 1219 Потенциал структуры данных, 495 Поток, 748-753, 812 нзбьпочный„776 сокращение, 756 сохранение, 749 увелчение, 756 целочисленный, 772 Потолок, 78 в основной теореме, 128-131 Правило Бленда, 919 Горнера, 64 Правый поворот, 345 Предок наименьший общий, 620 Предпсток, 775 Представитель множества, 597 Предшественник в дереве ван Эмке Бааса, 588 Преемник в дереве ван Эмде Бааса, 586-588 в протоструктуре ван Эмде Бааса, 579, 580 Преобразование Фурье быстрое, 952-955 дискретное, 946, 952 Префикс, 1032 последовательности 426 Приблшкениые алгоритмы, 31, 1157-1193 Приводимость, 1116-1118 Пробное деление, !010 Проверка за полиномнальное время, 1110-!115 простоты, 1009 †10, 1029 Миллера-Рабина, !О!2-1020, !029 13!В Предмтяяый указатель БЕРЕТ!Т!ОМ-МАТСНЕК, 1059 В!ОНТ, 180 БАМЕ-СОМРОМЕМТ, 599 БСАМ, 846 БЕОМЕМТ$-!МТЕК$ЕСТ, 1064 Б!мРьех,912 БЕОЮ-Азл.-РА!кз-БКОктезт-РАтнз, 728 Б О О А КЕ- МАТ К 1Х - М 1Л.Т1Р !.У- НЕС 0 К Я Ч Е, 102 БООАКЕ-МАТМХ-М!Л.Т1Р1.у, 100, 727 Бтхск-ЕмгтУ, 265 БУЕОМОЬЧ-СОМместеО-СОМРОМЕмтз, 654 БОМ-АККАУ5, 844 ТАВ1.Е-1мзект, 501 ТА!С-Кесцкз!Уе-!301ск50кт, 217 ТОРОСОО!ОАЕ-БОкт, 650 ТЕАНЯт!че-СЕ05цке, 736 ТКАМЕРЕАМТ,330 Ткее-Пе Сете, 331 ТКЕЕ-1М5ЕКТ, 327 ТКЕЕ-МАХ1МОМ, 324 ТКЕК-М1М1МОМ, 324 ТКЕЕ-БЕАКСН, 323 ТКЕЕ-БОССЕ550К, 325 ТК1м, 1183 ЧЕВ-ЕМРТУ-ТКЕЕ-1МЕЕКТ, 589 ЧЕВ-ТКЕЕ-ПЕСЕТЕ, 590 ЧЕВ-ТКЕЕ-!М5ЕКТ, 589 УЕВ-ТКЕЕ-МАХ1МОМ, 586 чЕВ-Ткее-Мемнек, 586 УЕВ-ТКЕЕ-М1М!МОМ, 586 УЕВ-ТК ЕЕ.РКЕОЕСЕ$$0К, 588 УЕВ-ТК ЕЕ-БОСС Е$$ОК, 587 зЧ1тме$5, 1013 двухпроходная, 607 Прямая адресация, 286, 287, 569-573 Прямая подстановка, 855, 856 Прямое ребро, 646 Прямоугольник, 387 Псевдоюд, 38, 42-44 Псевдопросгое число, 1011 Пузырьював сортировка, 63 Пустой стек, 264 Путь вес, 680 гамильтонов, ! 115 критический, 695 увеличивающий, 758, 759 Р Равенство линейное, 885 Разбиение, 199-202 метод Хоара, 214 по медиане трех элементов, 217 рандомизированное, 207 узла В-дерева, 530-532 Разгрузка переполненной вершины, 790 Разлвкение на множители, 1021-! 026 Размен монет, 482 Размер входных данных алгоритма, 47, 969-1106 Размещение, 153, 1236 Разностные ограничения, 702-709 Разрез минимальный, 760, 770 неориентированного графа, 663 пропускная способность, 760 транспортной сети, 759-763 чистый поток, 759 Разрезание стержня, 393-403 Ранг, 372 в дереве порядковой статистики, 374-378 узла леса непересекающихся множеств, 605, 610, 611, 617 числа в упорядоченном множестве, 333 Рандомизированный алгоритм, 51, ! 42-! 56 быстрой сортировки, 207, 208, 213 быстрой сортировки, 215, 2! 7 вероятностный анализ, 149, 150 выбора, 245-250 сортировки сравнением, 234 универсальное хеширование, 297-300 эвристняа Полларда, 1021-1025 Раскраска, 1233 графа, 1153 Расписание, 479, 1155 Распределение вероятностей, 1242 Расстояние манхэттенское, 255, 1091 редахтироваиия, 440 Расширение динамичесюй таблицы, 500-504 мнвкеспм, 473 структур данных, 372-388 Расширяющееся дерево, 519 Реберная связность, 770 Ребро антипараллельное, 750, 75! безопасное, 663 вес, 628 возврата, 818 вызова, 818 дерева, 637, 640, 646 допустимое, 788 запуска, 818 кяассификация в поиске в глубину, 646, 647 классификация прн поиске в ширину, 658 Предметный уяаэатеяь 1319 критическое, 768 мост, 658 насыщенное, 779 недопусгимое, 789 обратное, 646, 650 остаточное, 755 перекрестное, 646 продолжение, 8! 8 прямое, 646 с отрицательным весом, 682, 683 Реверс битов, 960 Рекуррентное соотношение, 90-139 решение меюдом Акра-Ваэзи, 138, 139 решение методом деревьев рекурсии, !13-!19 решение методом подстановок, 108-113 решение основным методом, 119-123 Рекуррентное уравнение, 57 Рекуррентность, 57 Рекурсия, 52 оюнечная, 216, 455 Рефлексивносгь асимптотических обозначений, 76 Решение вычислительной задали,27 допустимое, 703, 886, 892 Решений дерево, 221 Решетка, 800 Ряд, !33„ !198 абсолютно сюдящийся, 1199 гармонический, 1200, 1206, 1207 интегрирование и дифференцирование, 1200 цриближение интегралами, 1207 расходящийся, ! 199 сходящийся, ! 199 Тейлора, 339 телескопический, 120! С Самоорганизуюшийся список, 513 Сбалансированное дерево поиска 2-3-4-дерево, 540 2-3-лерево, 371 АА-дерево, 371 АЧЕ-дерево, 366, 370 В-дерево, 52! -541 взвешенно-сбалансированное дерево, 371 дерамида, 367, 37! дерево с 1с соседями, 371 юсое дерево, 371 красно-черное, 341-371 Сборка мусора, 179 Сборщик мусора, 275 Сверна, 943 Свойство верхней границы, 710 жадного выбора, 458„459 взвешенного матроида, 476 замены, 472 ослабленна пугн, 711, 712 отсутствия пугн, 711 подаержка, 182-!85 подграфа предшествования, 714, 715 сходимосги, 711 Связанный список, 268-273 вставка, 269, 270 головной элемент, 268 двюкды связанный, 268, 269 кольцевой, 269 компактный, 277, 282 обьединение, 272 однократно связанный, 269 отсортированный, 269 поиск, 269, 301 реализация непересекающихся множеств, 600-604 самоорганизующийся, 513 соседей, 790 удаление, 270 хвостовой элемент, 268 Связный компонент ияентификация поиском в глубину, 649 Сернализация многопоточного юпоритма, 813, 815 Сертификат алгоритма верификации, ! 112 Сеть допустимая, 783 — 790 остаточная, 754-758 с несколькими неллами и стоками, 751, 752 транспортная, 748-753 Сжатие динамичесюй таблицы, 504-503 пути, 605 Сильно связные компоненты декопрозицня, 652-658 Символ Лежандра, 1028 Символьный код, 463 Симплекс, 888 Симплекс-кагоритм, 888, 905 — 939 зацикливание, 917 Система линейных уравнений, 845, 852-866 недоопределеннаа, 853 переопределенная, 854 решение, 853 трехдиагональная, 879 Система разностных ограничений, 703 Скалярное произведение, 1274 !320 Предметлыйуказатеаь Сканирование по Грзхему, 1077-1083 Скобочная структура, 643 Скорость роста, 51 Слияние, 53 Словарь, 260 Сложение двоичных целых чисел, 45 Слои выпуклые, 1092 максимальные, 1092 Случайная величина, 1248-1254 индикаторная !г м Индикаторная случайная величина], 144 выборка, 156 перестановка, ! 50-154 равновероятная, 142 с использованием обменов, 152 с равномерным распределением, 151 Случайно построенное бинарное дерево поиска, 337 Соединение красно-черных деревьев, 365 Сокращение потока, 756 Сопутствующие данные, 260 Сортировка, 26, 38, 42-178 0-!-лемма, 238 бинарным деревом поиска, 332 быстрая, ! 98-219 вероятностная нижняя граница, 234 вставкой, 33, 38-63 в быстрой сортировке, 213 Дерево решений, 221 сравнение с сортировкой слнанием, 36 выбором, 52 эа линейное время, 223-235 карманнал, 230-234 лексикографическая, 337 на месте, 39.

Характеристики

Список файлов книги