Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 3
Текст из файла (страница 3)
Задача о максимальном потоке 26.1 Транспортные сети Транспортные сети и потоки Пример потока Сети с несколькими источниками и стоками Как работать с потоками Упражнения 26.2 Метод Форда-Фалкерсона Остаточные сети Увеличивающие пути Разрезы транспортных сетей Базовый алгоритм Форда-Фалкерсона Анализ метода Форда-Фалкерсона Алгоритм Эдмонлса-Карпа Упражнения 26.3 Максимальное паросочетание Задача поиска максимального паросочетания в двудольном графе Поиск максимального паросочетания в двудольном графе Упражнения * 26.4 Алгоритмы проталкивания предпотока Интуитивные соображения Основные операции Операция проталкивания Операция подъема Универсальный алгоритм Корректность метода проталкивания предпопжа 720 720 722 724 726 726 728 728 730 731 732 734 735 735 737 739 740 741 742 743 745 746 749 750 752 755 756 757 758 761 761 762 764 764 766 766 768 Содержание 21 795 796 Анализ метода проталкивания предпотока Упражнения * 26.5 Алгоритм "поднять-в-начало" Допустимые ребра и сети Списки соседей Разгрузка переполненной вершины Алгоритм "поднять-в-начало'* Анализ Упражнения Задачи Заключительные замечания Часть У11.
Избранные темы Введение озава 27. Сортирующие сети 27.1 Сравнивающие сети Упражнения 27.2 Нуль-единичный принцип Упражнения 27.3 Битоническая сортирующая сеть Полуфильтр Битонический сортировщик Упражнения 27.4 Объединяющая сеть Упражнения 27.5 Сортирующая сеть Упражнения Задачи Заключительные замечания озава 28. Работа с матрицами 28.1 Свойства матриц Матрицы и векторы Операции над матрицами Обратные матрицы, ранги и детерминанты Положительно определенные матрицы Упражнения 28.2 Алгоритм умножения матриц Штрассена Обзор алгоритма Определение произведений подматриц Обсуждение метода 770 773 774 775 777 777 780 783 785 786 793 799 800 803 805 807 808 809 810 812 813 815 816 818 819 822 823 824 824 827 828 83! 831 833 833 834 838 Содержание Упражнения 28.3 Решение систем линейных уравнений Обзор 1ПР-разложения Прямая и обратная подстановки Вычисление Ш-разложения Вычисление ШР-разложения Упражнения 28.4 Обращение матриц Вычисление обратной матрицы из ШР-разложения Умножение матриц и обращение матрицы Упражнения 28.5 Симметричные положительно определенные матрицы и метод наименьших квадратов Метод наименьших квадратов Упражнения Задачи Заключительные замечания Глава 29.
Линейное программирование Политическая задача Общий вид задач линейного программирования Краткий обзор задач линейного программирования Приложения линейного программирования Алгоритмы решения задач линейного программирования 29.1 Стандартная и каноническая формы задач линейного программирования Стандартная форма Преобразование задач линейного программирования в стандартную форму Преобразование задач линейного программирования в каноническую форму Упражнения 29.2 Формулирование задач в виде задач линейного программирования Кратчайшие пути Максимальный поток Поиск потока с минимальными затратами Многопродукговый поток Упражнения 29.3 Симплекс-алгоритм Пример симплекс-алгоритма 839 839 841 842 845 848 852 853 853 854 857 858 861 865 865 867 869 869 872 872 876 877 877 878 879 882 885 886 887 887 888 889 891 892 893 Содержание 23 926 926 928 928 929 929 932 934 935 935 938 938 941 942 943 944 947 949 949 953 954 955 956 956 956 Замещение Формальный симплекс-алгоритм Завершение Упражнения 29.4 Двойственность Упражнения 29.5 Начальное базисное допустимое решение Поиск начального решения Основная теорема линейного программирования Упражнения Задачи Заключительные замечания Глава 30.
Полиномы и быстрое преобразование Фурье Полиномы Краткое содержание главы 30.1 Представление полиномов Представление, основанное на коэффициентах Представление, основанное на значениях в точках Быстрое умножение полиномов, заданных в коэффициентной форме Упражнения 30.2 ДПФ и БПФ Комплексные корни из единицы Дискретное преобразование Фурье Быстрое преобразование Фурье Интерполяция в точках, являющихся комплексными корнями из единицы Упражнения 30.3 Эффективные реализации БПФ Итеративная реализация БПФ Параллельная схема БПФ Упражнения Задачи Заключительные замечания Глава 31.
Теоретико-числовые алгоритмы Размер входных наборов данных и стоимость арифметических вычислений 31.1 Элементарные обозначения, принятые в теории чисел Делимость и делители Простые и составные числа 897 899 905 907 908 914 914 914 920 921 922 924 24 Содержание Теорема о делении, остатки и равенство по модулю Общие делители и наибольшие общие делители Взаимно простые целые числа Единственность разложения на множители Упражнения 31.2 Наибольший общий делитель Алгоритм Евклида Время работы алгоритма Евклида Развернутая форма алгоритма Евклида Упражнения 31.3 Модульная арифметика Конечные группы Группы, образованные сложением и умножением по модулю Подгруппы Подгруппы, сгенерированные элементом группы Упражнения 31.4 Решение модульных линейных уравнений Упражнения 31.5 Китайская теорема об остатках Упражнения 31.6 Степени элемента Возведение в степень путем последовательного возведения в квадрат Упражнения 31.7 Криптосистема с открытым ключом КБА Криптографические системы с открытым ключом Криптографическая система КБА Упражнения * 31.8 Проверка простоты Плотность распределения простых чисел Проверка псевдопростых чисел Ранломизированный тест простоты Миллера-Рабина Частота ошибок в тесте Миллера-Рабина Упражнения * 31.9 Целочисленное разложение Эвристический р-метод Полларда Упражнения Задачи Заключительные замечания 957 958 960 960 961 962 963 964 965 967 968 968 969 972 973 975 975 979 979 982 983 985 987 987 988 991 995 995 996 997 999 1002 1006 1006 1007 1012 1013 1015 Содержание 25 Глава 32.
Поиск подстрок Обозначения и терминология 32.1 Простейший алгоритм поиска подстрок Упражнения 32.2 Алгоритм Рабина-Карпа Упражнения 32.3 Поиск подстрок с помощью конечных автоматов Конечные автоматы Автоматы поиска подстрок Вычисление функции переходов Упражнения * 32.4 Алгоритм Кнута-Морриса-Пратта Префиксная функция для образца Анализ времени работы Корректность вычисления префиксной функции Корректность алгоритма Кнута-Морриса-Пратга Упражнения Задачи Заключительные замечания Глава 33.
Вычислительная геометрия 33.1 Свойства отрезков Векторное произведение Поворот последовательных отрезков Определение того, пересекаются ли два отрезка Другие применения векторного произведения Упражнения 33.2 Определение наличия пересекающихся отрезков Упорядочение отрезков Перемещение выметающей прямой Псевдокод, выявляющий пересечение отрезков Корректность Время работы Упражнения 33.3 Построение выпуклой оболочки Сканирование по Грэхему Обход по Джарвису Упражнения 33.4 Поиск пары ближайших точек Алгоритм декомпозиции Корректность 1017 1019 1020 1021 1022 1028 1028 1029 1030 1035 1036 1036 1037 1040 1041 1043 1044 1045 1046 1047 1048 1049 1050 1051 1053 1053 1055 1056 1057 !058 1060 1061 1062 1063 1065 1071 1073 1074 1075 1077 26 Содержание Реализация и время работы алгоритма Упражнения Задачи Заключительные замечания Глава 34.
ХР-полнота ХР-полнота и классы Р и ХР Как показать, что задача является ХР-полной Краткое содержание главы 34.1 Полиномиальное время Абстрактные задачи Кодирование Структура формальных языков Упражнения 34.2 Проверка за полиномиальное время Гамильтоновы циклы Алгоритмы верификации Класс сложности ХР Упражнения 34.3 ХР-полнота и приводимость Приводимость ХР-полнота Выполнимость схем Упражнения 34.4 Доказательство ХР-полноты Выполнимость формулы 3-СХР выполнимость Упражнения 34.5 ХР-полные задачи 34.5,! Задача о клике 34.5.2 Задача о вершинном покрытии 34.5.3 Задача о гамильтоновых циклах 34.5.4 Задача о коммивояжере 34.5.5 Задача о сумме подмножества Упражнения Задачи Заключительные замечания Глава 35.
Приближенные алгоритмы Оценка качества приближенных алгоритмов Краткое содержание главы 35.1 Задача о вершинном покрытии 1078 1079 1080 1083 1085 1087 1088 1091 1091 1092 1093 1096 1100 1100 1101 1102 1103 1105 1106 1106 1108 1110 1117 1118 1119 1122 1126 1127 1128 1131 1133 1138 1140 1144 1145 1149 1151 1151 1153 1154 Содержание 27 1157 1157 1158 1161 1163 1164 1166 1166 1169 1170 1170 1172 1175 1176 1176 1178 1182 1182 1186 1189 1190 Упражнения 35.2 Задача о коммивояжере 35.2.1 Задача о коммивояжере с неравенством треугольника 35.2.2 Общая задача о коммивояжере Упражнения 35.3 Задача о покрытии множества Жадный приближенный алгоритм Анализ Упражнения 35.4 Рандомизация и линейное программирование Рандомизированный приближенный алгоритм для задачи о МАХ-3-СИР выполнимости Аппроксимация взвешенного вершинного покрытия с помощью линейного программирования Упражнения 35.5 Задача о сумме подмножества Точный алгоритм с экспоненциальным временем работы Схема аппроксимации с полностью полиномиальным временем работы Упражнения Задачи Заключительные замечания Часть УП1.
Приложения: математические основы Введение Приложение А. Ряды А.1 Суммы и их свойства Линейность Арифметическая прогрессия Суммы квадратов и кубов Геометрическая прогрессия Гармонический ряд Интегрирование и дифференцирование рядов Суммы разностей Произведения Упражнения А.2 Оценки сумм Математическая индукция Почленное сравнение Разбиение рядов 1191 1192 1192 1193 1193 1193 1194 1194 1194 1195 1195 1195 1196 1196 1198 28 Содержание Приближение интегралами Упражнения Задачи Заключительные замечания Приложение Б.Множества и прочие художества Б.1 Множества Упражнения Б.2 Отношения Упражнения Б.З Функции Упражнения Б.4 Графы Упражнения Б.5 Деревья Б.5.1 Свободные деревья Б.5.2 Деревья с корнем и упорядоченные деревья Б.5.3 Бинарные и позиционные деревья Упражнения Задачи Заключительные замечания Приложение В.
Комбинаторика и теория вероятности В.1 Основы комбинаторики Правила суммы и произведения Строки Перестановки Сочетания Биномиальные коэффициенты Оценки биномиальных коэффициентов Упражнения В.2 Вероятность Аксиомы вероятности Дискретные распределения вероятностей Непрерывное равномерное распределение вероятности Условная вероятность и независимость Теорема Байеса Упражнения В.З Дискретные случайные величины Математическое ожидание случайной величины Дисперсия и стандартное отклонение Упражнения 1199 1201 1201 1201 1202 1202 1207 1207 1209 1210 1212 1213 1217 1218 1218 1220 1221 1223 1224 1225 1226 1226 1227 1227 1227 1228 1229 1229 1230 1232 1232 1233 1234 1234 1236 1237 1238 1239 1242 1243 Содержание 29 В.4 Геометрическое и биномиальное распределения Геометрическое распределение Биномиальное распределение Упражнения * В.5 Хвосты биномиального распределения Упражнения Задачи Заключительные замечания Библиография Предметный указатель 1243 1244 1245 1248 1249 1254 1255 1256 !257 1277 Введение Эта книга служит исчерпывающим вводным курсом по современным компьютерным алгоритмам.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
