Алгоритмы - построение и анализ (1021735), страница 169
Текст из файла (страница 169)
27.14а, то полученная в результате сеть будет перестановочной. Другими словами, для любой перестановки 1г существует способ установить переключатели в сети таким образом, чтобы соединить вход а с выходом я (4). На рис. 27.14б показана рекурсивная схема перестановочной сети Ра на 8 входов и 8 выходов, юторая содержит две юлии сети Р4 и 8 переключателей. Переключатели установлены таким образом, побы реализовать перестановку я = (я(1),тг(2),...,я(8)) = (4,7,3,5,1,6,8,2). При этом требуется (по рекурсии), чтобы в верхней сети Р4 реализовалась перестановка (4, 2, 3, 1), а в нижней — перестановка (2, 3, 1, 4).
б) Покаяапе, как в сети Рв реализовать перестановку (5,3,4,6, 1,8, 2, 7) путем изменения положений переключателей и перестановок, Выполняющихся В двух сетях Р4. Пусть га равно степени двойки. Дайте рекурсивное определение сети Р„ в терминах двух сетей Р„~з, аналогичное определению сети Ра. в) Опишите алгоритм, который в течение времени 0(п) (на обыч- ной машине с произвольным доступом к памяти) позволяет уста- 822 Часть ЧП. Избранные темы повить и переключателей, соединенных с входами и выходами сети Р„, и определить перестановки, которые необходимо реализовать в каждой из сетей Р„7з, чтобы выполнить любую перестановку п элементов.
Докажите корректность вашего алгоритма. г) Чему равны глубина и размер сети Р„7 Сколько времени потребуется, чтобы определить на обычном компьютере с произвольным доступом к памяти положения всех переключателей, включая те, которые содержатся в сетях Р„ру д) Докажите, что при п > 2 любая перестановочная сеть, а не только Р„, должна реализовать некоторую перестановку путем установки двух различных сочетаний положений переключателей. Заключительные замечания В книге Кнута (КлиГ)з) 1185) обсуждаются сортирующие сети и приводится их краткая история. Однозначно можно сказать, что впервые онн исследовались в 1954 году Армстронгом (Р Х. Аппзггопй), Нельсоном (К.7. Не!зоп) и О'Коннором (13.7. О'Соппог). В начале 1960-х Батчер (К.Е.
ВассЬег) разработал первую сеть, способную объединять две последовательности из п чисел в течение времени 0(18п). Он воспользовался нечетно-четным объединением (см. задачу 27-2), а также показал„как с помощью этого метода выполнить сортировку п чисел за время 0 (18~ и). Вскоре после этого он разработал битонический сортнровщнк глубиной 0 (18п), аналогичный тому, который представлен на рис. 27.3. Авторство нуль-единичного принципа Кнут приписывает Бурайсиусу (%.0. Воппс)ва) (1954 г.), доказавшему его в контексте деревьев решений.
В течение долгого времени открытым оставался вопрос о существовании сортирующих сетей глубиной О (18 и). В 1983 году на него удалось ответить утвердительно, но оказалось, что этот ответ нельзя считать удовлетворительным. Сортирующая сеть АКБ (названная так в честь своих разработчиков А1Га) (Айтаи), Комлеса (Кош!оз) и Семередн (Бгетегегй) [11]) имеет глубину О (1кп) и сортирует п чисел с помощью О (и 18 и) сравнений. К сожалению, константы, скрытые в О-обозначении, получаются слишком большими (порядка нескольких тысяч), поэтому считается, что такая сеть не имеет практической пользы.
ГЛАВА 28 Работа с матрицами Работа с матрицами — сердце научных расчетов, поэтому эффективные алгоритмы для работы с матрицами представляют значительный практический интерес. Эта глава представляет собой краткое введение в теорию матриц и операции над матрицами, делая особый упор на задачу умножения матриц и решение систем линейных уравнений. После раздела 28.1, который знакомит нас с основными концепциями теории матриц и используемыми обозначениями, в разделе 28.2 представлен алгоритм Штрассена, позволяющий выполнить умножение двух матриц размером п х п за время 9 (п'Я ) = О (п~ а1). В разделе 28.3 показано, как решать системы линейных уравнений с использованием 1.()Р-разложения.
Затем в разделе 28.4 показывается тесная связь задач умножения и обращения матриц. И наконец, в разделе 28.5 рассматривается важный класс симметричных положительно определенных матриц и их применение для поиска решения переопределенных систем линейных уравнений методом наименьших квадратов. Один из важнейших вопросов, возникающих на практике, — численная устойчивость (пшпепса! з1аЬ!1!Гу). Из-за ограниченной точности представления действительных чисел в реальном компьютере в процессе вычислений могут резко нарастать ошибки округления, что приводит к неверным результатам.
Такие вычисления являются численно неустойчивыми. Несмотря на важность данного вопроса, мы лишь поверхностно коснемся его в данной главе, так что мы рекомендуем читателям обратиться к отличной книге Голуба (Оо1иЬ) и Ван Лоана (Чап Ьоап) [1251, в которой детально рассматриваются вопросы численной устойчивости. 824 Часть Ч11. Избранные темы 28.1 Свойства матриц В этом разделе мы рассмотрим некоторые базовые концепции теории матриц и их фундаментальные свойства, обращая особое внимание на те из них, которые понадобятся нам в следующих разделах.
Матрицы и векторы Матрииа (щаП1х) представляет собой прямоугольный массив чисел. Например, аы а1г а1з 1 2 3 (28.1) является матрицей размера 2 х 3 А = (а;.), где ( = 1, 2 и г = 1, 2, 3. Элемент на пересечении (-й строки и ~'-го столбца матрицы — а,у. Мы используем заглавные буквы для обозначения матриц, а их элементы обозначаются соответствующими строчными буквами с нижними индексами.
Множество всех матриц размером т х и, элементами которых являются действительные числа, обозначается как К "". В общем случае множество матриц размером т х и, элементы которых принадлежат множеству Я, обозначается как 5"'"". траисионироваииая (1гапзрозе) матрица Ат получается из матрицы А путем обмена местами ее строк и столбцов. Так, для матрицы А из (28.1) 1 4 Ат= 2 б 3 6 Вектор (чесюг) представляет собой одномерный массив чисел. Например, (28.2) х= 3 является вектором размером 3.
Для обозначения векторов мы используем строчные буквы и обозначаем г'-й элемент вектора а как х;. Стандартной формой вектора будем считать вектор-столбеи (со!ппш чесюг), эквивалентный матрице п х 1. Соответствующий вектор-строка (гочч чесюг) получается путем транспонирования вектора-столбца: ж=(235) Единичным векторам (нш! чесюг) е; называется вектор, 1-й элемент которого равен 1, а все остальные элементы равны О. Обычно размер единичного вектора ясен из контекста.
Глава 28. Работа с матрицами 825 ап О ... О О а 22 ... О Гйаб(о11, Й22, . ° °, спи) = О О ... а„„ 2. Единичная матрица (Ыеп111у ша1пх) 1„размером и х и представляет собой диагональную матрицу, все диагональные элементы которой равны 1: 1 О ... О О 1 ... О 1„= Йаб(1,1,...,1) = О О ... 1 Если используется обозначение 1 без индекса, размер единичной матрицы определяется из контекста. Заметим, что тчм столбцом единичной матрицы является единичный вектор е;. 3.
Элементы трехдиагональной матрицы (Гпйайопа) та1пх) Т обладают тем свойством, что если ~1 — Я > 1, то 11 = О. Ненулевые элементы такой матрицы располагаются на главной диагонали, непосредственно над ней Щ+1 для 1 = 1, 2,..., т4 — 1) и непосредственно под ней (11+11 для 1 = = 1,2,...,и — 1): гп 212 О О $21 422 223 О О 232 Фзз 834 О О О О О О О О О О О О О О О О О Зп-2,п — 2 ги-1,п-2 ти-2,ь-1 Гь-1,п — 1 Гп,п-1 ~п-1,п О Нулевая магирица (хего шатпх) — это матрица, все элементы которой равны О.
Такая матрица часто записывается просто как О, поскольку неоднозначность между числом О и нулевой матрицей легко разрешается при помоши контекста. Если размер нулевой матрицы не указан, то он также выводится из контекста. Часто приходится иметь дело с квадратными (зйпаге) матрицами размером и х и. Некоторые из квадратных матриц представляют особый интерес. 1. Диагональная матрица (йайопа! ша1пх) обладает тем свойством, что а;; = = О при 1 ф 21 Поскольку все недиагональные элементы такой матрицы равны О, диагональную матрицу можно определить путем перечисления ее элементов вдоль диагонали: 826 Часть Ч11. Избранные темы 4. Верхне-треугольной матрицей (иррег-птапйи!аг шаптх) У называется матрица, у которой все элементы ниже диагонали равны О (и,з = О при 1 ) 7): игг игг ...
иг„ О игг .. игп О О ... и„„ Верхне-треугольная матрица является единичной верхне-треугольной матрицей (шп! иррег-!палйп!аг), если все ее диагональные элементы равны 1. 5. Нижне-треугольной матрицей (1о~чег-!палйп!аг шаизх) Ь называется матрица, у которой все элементы выше диагонали равны О (1; = О при г ( 1): 1и О ... О 1гг 1гг . О Ь= (чг 1чг Нижне-треугольная матрица является единичной нижне-треугольной матрицей (оп!1!очгег-1г!апйп1аг), если все ее диагональные элементы равны 1.
6. Матрица нерестановки (реппигайоп шаптх) Р имеет в каждой строке и столбце ровно по одной единице, а на всех прочих местах располагаются нули. Примером матрицы перестановки может служить матрица О 1 О О О О О О 1 О 1 О О О О Р= О О О О 1 О О 1 О О Такая матрица называется матрицей перестановки, потому что умножение вектора х на матрицу перестановки приводит к перестановке элементов вектора. 7. Симметричная матрица (зупппептс шаптх) А удовлетворяет условию А = = Ат. Например, матрица 1 2 3 2 б 4 3 4 б является симметричной.
Глава 28. Работа с матрицами 827 Операции над матрицами А+О=А=О+А. Если Л вЂ” число, а А = (аи) — матрица, то соотношение ЛА = (Ла; ) определяет скалярное произведение (зса1аг пш!бр1е) матрицы на число, которое также выполняется поэлементно. Частным случаем скалярного произведения является умножение на — 1, которое дает противоположную (пейабче) матр1щу — 1 А = = -А, обладающую тем свойством, что А + ( — А) = О = ( — А) + А.
Соответственно, можно определить вычитание матриц (шап1х зпЬ~гаспоп) как сложение с противоположной матрицей: А — В = А + ( — В). Матричное умножение (шаптх пш1пр!1сапоп) определяется следующим образом. Матрицы А и В могут быть перемножены, если они совместимы (сошрапЫе) в том смысле, что число столбцов А равно числу строк В (в общем случае выражение, содержащее матричное произведение АВ, всегда подразумевает совместимость матриц А и В). Если А = (а; ) — матрица размером т х п, а В = (6; ) — матрица размером и х р, то их произведение С = АВ представляет собой матрицу С = (с; ) размером т х р, элементы которой определяются уравнением с;ь = ~~> а;.6 ь 1=1 (28.3) для ( = 1,2,...,гп и к = 1,2,...,р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
