Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 164
Текст из файла (страница 164)
Здесь также показано, что перемножение и обращение матриц можно выполнять с одинаковой скоростью. В заключительной части главы показано, как получить приближенное решение системы линейных уравнений методом наименьших квадратов, если эта система не имеет точного решения. В главе 29 исследуется линейное программирование, цель которого — минимизировать или максимизировать целевую функцию при заданных ограниченных ресурсах и конкурирующих ограничениях. Линейное программирование применяется в самых различных прикладных областях.
В главе описывается постановка задач линейного программирования и их решение. В качестве метода решения изложен симплекс-алгоритм, который является одним из древнейших алгоритмов, используемых в линейном программировании. В отличие от многих других алгоритмов, о которых идет речь в этой книге, для симплекс-алгоритма время работы в наихудшем случае не выражается полиномиальной функцией, однако он достаточно эффективен и широко применяется на практике.
В главе 30 изучаются операции над полиномами. Здесь показано, что с помощью такого известного метода обработки сигналов, как быстрое преобразование Фурье (Раз1 Роипег Тгапз(опп, РРТ), два полинома и-й степени можно перемножить за время 0 (п 18п). В этой главе также исследуются методы эффективной реализации РРТ, включая параллельные вычисления. Часть Ч11. Избранные темы В главе 31 представлены теоретико-числовые алгоритмы.
После обзора элементарной теории чисел здесь описан алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя. Далее представлены алгоритмы для решения модульных линейных уравнений и для возведения числа в степень по модулю другого числа. Затем читатель сможет ознакомиться с важным приложением теоретико-числовых алгоритмов: криптографической системой с открытым ключом КБА. С ее помощью можно не только кодировать сообщения таким образом, чтобы их не могли прочитать посторонние, но и создавать цифровые подписи.
Далее в главе представлен рандомизированный тест для простых чисел Миллера- Рабина (М(Пег-йаЬ(п), позволяющий производить эффективный поиск больших целых чисел, необходимый для реализации схемы КЗА. В заключительной части главы описан эвристический р-метод Полларда (Ро11агд) для разбиения целых чисел на множители, а также обсуждаются успехи, достигнутые в этой области. В главе 32 исследуется задача поиска всех вхождений заданной строки-образца в имеющуюся строку текста; эта задача часто возникает при написании программ, предназначенных для редактирования текста. После ознакомления с "наивным" подходом в этой главе представлен элегантный метод решения данной задачи, разработанный Рабином (КаЬ|п) и Карпом (Катр).
Затем, после демонстрации эффективного решения, основанного на теории конечных автоматов, здесь вниманию читателя предложен алгоритм Кнута-Морриса-Пратта (Кпий-Мопзз-ргап), позволяющий достичь высокой эффективности за счет предварительной обработки образца. Тема главы 33 — вычислительная геометрия. После обсуждения основных принципов этого раздела вычислительной математики, в главе показано, как с помощью метода "обметания" можно эффективно определить, содержатся ли какие- нибудь пересечения в множестве прямолинейных отрезков.
Два остроумных алгоритма, предназначенных для поиска выпуклой оболочки заданного множества точек, — метод сканирования по Грэхему (СтгаЬатп'з зсап) и метод продвижения по Джарвису (йтч1з'з шатсЬ), — также иллюстрируют мощь метода обметания. В заключение в главе описан эффективный алгоритм, предназначенный для поиска пары самых близких точек в заданном множестве точек на плоскости. Глава 35 посвящена ХР-полным задачам. Многие интересные вычислительные задачи являются ХР-полными, однако неизвестен ни один алгоритм решения какой бы то ни было из этих задач, время работы которого выражалось бы полиномиальной функцией. В данной главе представлены методы определения того, является ли задача ХР-полной.
Доказана ХР-полнота для нескольких классических задач: определение того, содержит ли граф цикл Гамильтона, определение того, выполнима ли заданная булева формула, и определение того, содержит ли заданное множество чисел такое подмножество, сумма элементов в котором была бы равна заданному значению.
В этой главе также доказано, что знаменитая задача о коммивояжере также является ХР-полной. 798 Часть Ч11. Избранные темы В главе 35 показано, как эффективно находить приближенные решения ХР- полных задач с помощью приближенных алгоритмов. Для некоторых МР-полных задач достаточно легко выразить приближенные решения, достаточно близкие к оптимальным, в то время как для других задач даже самые лучшие из известных приближенных алгоритмов работают все хуже по мере увеличения размера задачи.
Есть также другой класс задач, для которых наблюдается возрастание времени вычисления с увеличением точности приближенных решений. Эгн возможности проиллюстрированы на задаче о вершинном покрытии (представлены невзвешенная и взвешенная версии), на задаче о коммивояжере и других. ГЛАВА 27 Сортирующие сети Во второй части этой книги были рассмотрены алгоритмы сортировки, предназначенные для последовательных компьютеров (вычислительных машин, оснащенных памятью с произвольным доступом), в которых в заданный момент времени может выполняться лишь одна операция.
В этой главе исследуются алгоритмы сортировки, основанные на модели сравнивающих сетей, в которых одновременно можно выполнять большое количество операций сравнения. Сравнивающие сети имеют два важных отличия от последовательных компьютеров. Во-первых, в них могут выполняться только сравнения.
Это означает, что в этой сети нельзя реализовать такой алгоритм, как сортировка подсчетом. Во-вторых, в отличие от последовательных компьютеров, в которых операции выполняются последовательно, т.е. одна за другой, операции в сравнивающей сети могут выполняться одновременно или "параллельно*'. Мы сможем убедиться, что эта характеристика позволяет строить сравнивающие сети, сортирующие п величин за время, меньшее линейного.
В начальном разделе главы, разделе 27.1, дается определение сравнивающих и сортирующих сетей. Здесь также представлено естественное определение "времени работы" сравнивающей сети в терминах глубины сети. В разделе 27.2 доказывается "нуль-единичный принцип", позволяющий значительно упростить задачу анализа корректности работы сортирующих сетей. Эффективная сортирующая сеть, которая будет разработана в этой главе, по сути, представляет собой параллельную версию алгоритма слиянием, изложенную в разделе 2.3.1. Процесс разработки состоит из трех этапов.
В разделе 27.3 представлена схема "битонического" сортировщика, который станет нашим основным строительным блоком. В разделе 27.4 битонический сортировщик будет слегка 800 Часть Ч11. Избранные темы модифицирован, с тем чтобы получить объединяющую сеть, позволяющую объединять две отсортированные последовательности в одну. Наконец, в разделе 27.5 из этих обьединяюших сетей будет собрана сортируюшая сеть, позволяющая выполнить сортировку п величин за время О (10~ п). 27.1 Сравнивающие сети Сортируюшие сети — это такие сравнивающие сети, в которых входные данные всегда сортируются, поэтому есть смысл вначале обсудить сравнивающие сети и их характеристики.
Сравнивающая сеть состоит только из сравнивающих устройств и соединяющих их проводов. Компаратор, или сраваиваюа(ееусагройство (сошрага(ог, рис. 27.1), — это устройство с двумя входами, х и у, и двумя выходами, х' и у', выполняющее такую операцию: х' = пцп (х, у), у' = шах(х,у). Поскольку представленное на рис. 27.1а схематическое изображение сравнивающего устройства слишком громоздкое, мы примем в качестве условного обозначения этого устройства вертикальную линию, показанную на рис. 27.16. Входные величины изображены слева, а выходные — справа, причем меньшая входная величина на выходе переходит вверх, а ббльшая — вниз.
Таким образом, можно сказать, что сравнивающее устройство сортирует две входных величины. В дальнейшем предполагается, что сравнивающее устройство выполняет требуемое действие за время 0(1). Другими словами, предполагается, что время, которое проходит с момента подачи входных величин х и у до момента выдачи выходных величин х' и у', равно константе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
