Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 179
Текст из файла (страница 179)
В главе 27 представлена алгоритмическая модель для параллельных вычислений на основе динамической многопоточности. В этой главе сначала вводятся основы указанной модели и демонстрируется, как количественно описать параллелизм, а затем изучается несколько интересных многопоточных алгоритмов, включая алгоритмы умножения матриц и сортировки слиянием. В главе 28 изучаются эффективные алгоритмы, предназначенные для работы с матрицами. В ней представлены два общих метода — Ш-разложение и ШР- разложение. Онн предназначены для решения системы линейных уравнений по методу исключения Гаусса за время 0(п~). Здесь также показано, что перемножение и обращение матриц можно выполнять с одинаковой скоростью. В заключительной части главы показано, как получить приближенное решение системы линейных уравнений методом наименьших квадратов, если эта система не имеет точного решения.
В главе 29 исследуется линейное программирование, цель которого — минимизировать или максимизировать целевую функцию при заданных ограниченных ресурсах и конкурирующих ограничениях. Линейное программирование применяется в самых различных прикладных областях.
В этой главе описывается постановка задач линейного программирования н их решение. В качестве метода решения предложен симплекс-апгоритм, который является одним из древнейших алгоритмов, используемых в линейном программировании. В отличие от многих Чпояь Г!1 Избраннне темы 809 других алгоритмов, о которых идет речь в этой книге, для симплекс-алгоритма время работы в наихудшем случае не выражается полиномиальной функцией, однако он достаточно эффективен и широко применяется на практике.
В главе 30 изучаются операции над полиномами. Здесь показано, как с помощью такого известного метода обработки сигналов, как быстрое преобразование Фурье (Еазг Роппег ТгапзГопп — РЕТ), можно перемножить два полинома и-й степени за время 0(п1яп). В этой главе также исследуются методы эффективной реализации РРТ, включая параллельные вычисления. В главе 31 представлены теоретико-числовые алгоритмы. После обзора элементарной теории чисел здесь описан алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя. Далее представлены алгоритмы для решения модульных линейных уравнений и для возведения числа в степень по модулю другого числа.
Затем читатель сможет ознакомиться с важным приложением теоретико-числовых алгоритмов: криптографической системой с открытым ключом КЯА. С ее помощью можно не только кодировать сообщения таким образом, чтобы их не могли прочитать посторонние, но и создавать цифровые подписи. Далее в главе представлен рандомизированный тест простоты чисел Миллера — Рабина (М(Пег-йаЬ(п), позволяющий выполнять эффективный поиск больших простых чисел, необходимый для реализации схемы йЗА. В заключительной части главы описан эвристический р-метод Полларда (Ройап1) для разбиения целых чисел на множители, а также обсуждаются успехи, достигнутые в области целочисленной факторизации.
В главе 32 исследуется задача поиска всех вхождений заданной строки-образца в имеющуюся строку текста; эта задача часто возникает при написании программ, предназначенных для редактирования текста. После ознакомления с "наивным*' подходом в этой главе представлен элегантный метод решения данной задачи, разработанный Рабином (йаЬ1п) и Карпом (Катр).
Затем, после демонстрации эффективного решения, основанного на теории конечных автоматов, вниманию читателя предложен алгоритм Кнута-Морриса — Пратта (КппгЬ-Могпз-Ргап), позволяющий достичь высокой эффективности за счет предварительной обработки образца. Тема главы 33 — некоторые задачи вычислительной геометрии. После обсуждения основных примитивов этого раздела вычислительной математики в главе показано, как с помощью метода "обметания" можно эффективно определить, имеются ли пересечения в множестве прямолинейных отрезков. Два остроумньгх алгоритма, предназначенных для поиска выпуклой оболочки заданного множества точек — метод сканирования по Грэхему (бгаЬаш'з зсал) и метод продвижения по Джарвису ()аг918'з шагсЬ), — также иллюстрируют мощь метода обметания. В заключение в главе описан эффективный алгоритм, предназначенный для поиска пары самых близких точек в заданном множестве точек на плоскости.
Глава 34 посвящена ХР-полным задачам. Многие интересные вычислительные задачи являются ХР-полнымн, однако неизвестен ни один алгоритм решения какой бы то ни было из этих задач, время работы которого выражалось бы полиномиальной функцией. В данной главе представлены методы определения того, является ли задача ХР-полной. Доказана ХР-полнота для нескольких классичес- вго Часть е71. Избранныетемы ких задач: определение того, содержит ли граф цикл Гамильтона, выполнима лн заданная булева формула и содержит ли заданное множество чисел такое подмножество, сумма элементов в котором была бы равна заданному значению.
В этой главе, кроме того, доказано, что знаменитая задача о коммивояжере также является МР-полной. В главе 35 показано, как эффективно находить приближенные решения МР- полных задач с помощью приближенных алгоритмов. Для одних ХР-полных задач не так уж сложно выразить приближенные решения, достаточно близкие к оптимальным, в то время как для других задач даже самые лучшие из известных приближенных алгоритмов работают все хуже по мере увеличения размера задачи.
Есть также другой класс задач, для которых наблюдается возрастание времени вычисления с увеличением точности приближенных решений. Эти возможности проиллюстрированы на примере решения задачи о вершинном покрытии (представлены невзвешенная и взвешенная версии), о коммивояжере и др. Глава 27. Многопоточные алгоритмы Подавляющее большинство алгоритмов в этой книге — посаедоаательные (зепа1), пригодные для выполнения на однопроцессорном компьютере, который в каждый момент времени выполняет только одну инструкцию. В этой главе мы расширим нашу алгоритмическую модель иариалельными алгоритмами (рагайе1 а!бог(бппз), которые могут выполняться на многопроцессорных компьютерах, допускающих одновременное выполнение нескольких команд.
В частности, мы рассмотрим элегантную модель динамических многопоточных алгоритмов, которые подчиняются общим принципам проектирования и анализа алгоритмов и при этом могут быть эффективно реализованы на практике. Параллельные компьютеры, т.е. компьютеры с несколькими устройствами обработки данных, становятся все более распространенными и охватывают широкий диапазон цен и производительности. Относительно недорогие настольные и переносные компьютеры оснащены одним многоядерньгм процессором, в который входят несколько "ядер", которые сами по себе являются полноценными процессорами с доступом к общей памяти.
В среднем диапазоне как по цене, так и по производительности находятся кластеры, составленные из отдельных компьютеров, зачастую относящихся к классу персональных, со связывающей их некоммутируемой сетью. К дорогостоящим относятся суперкомпьютеры, которые зачастую используют комбинацию специализированных архитектуры и сетей для достижения высочайшей производительности, выражаемой в количестве выполняемых за секунду команд. В той или иной форме многопроцессорные компьютеры существуют уже десятилетия.
Но несмотря на то, что модель машины с произвольным доступом для последовательных вычислений появилась н была принята еще на ранней стадии развития компьютерных наук, до сих пор ни одна модель для параллельных вычислений не получила широкого признания. Основная причина этого в том, что производители не договорились о единой архитектурной модели для параллельных компьютеров. Например, одни параллельные компьютеры оснащены совместно используемой памятью (зЬагеб шешогу), где каждый процессор может непосредственно обращаться к любой ячейке памяти.
Другие параллельные компьютеры используют распределенную памяшь (гйз1пЬи1ед шепюгу), где каждый процессор имеет собственную память, и для доступа одного процессора к памяти другого между процессорами должны передаваться явные сообщения. Однако с появлением многоядерных технологий каждый новый настольный или перенос- Часть И1. Избранные темы ной компьютер в настоящее время представляет собой параллельный компьютер с совместно используемой памятью. Время покажет, правы ли мы в своем выборе, но в данной главе принята именно эта модель — многопроцессорности с совместно используемой памятью.
Распространенным методом программирования многоядерных и иных параллельных компьютеров с совместно используемой памятью является применение еиеаизической миогоиоизочиоеизи (кайс г)неве(1пй), предоставляющей программную абстракцию "виртуальных процессоров", или потоков (1пгеа<Ь)„совместно использующих общую память. Каждый поток поддерживает связанный с ним счетчик команд и может выполнять код независимо от других потоков. Операционная система загружает поток в процессор для выполнения и переключает потоки, когда выполнения требует другой поток. Хотя операционная система и позволяет программистам создавать и уничтожать потоки, эти операции относительно медленные.
Таким образом, для большинства приложений потоки сохраняются на протяжении всего времени вычислений, почему они и получили название "статические". К сожалению, непосредственное программирование параллельного компьютера с совместно используемой памятью с применением статических потоков — дело сложное и чреватое ошибками. Одна из причин этого заключается в сложности равномерного динамического распределения работы между потоками. Для любого (кроме самых простейших) приложения программист для сбалансированной загрузки потоков должен использовать сложные протоколы обмена информацией.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
