Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 169
Текст из файла (страница 169)
г) Чему равна глубина нечетно-четной обьединяющей сети на 2и входов? Чему равен ее размер? 27-3. Перестановочные сети Перестаноеочная сеть (реппигаг1оп пепчог1с) на п входов и и выходов содержит переключатели, позволяющие соединять входы сети с ее выходами в соответствии с любой из п) возможных перестановок. На рис. 27.14а показана перестановочная сеть Рз на 2 входа и 2 выхода, Глава 27.
Сортирующие сети 821 К б) а) Рис. 27.14. Перестановочная сеть состоящая из одного переключателя, с помощью которого входы можно соединить с выходами напрямую или крест-накрест. а) Докажите, что если каждое сравнивающее устройство в сортирующей сети заменить переключателем, показанным на рис.
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 Нулевая магирица (хего шатпх) — это матрица, все элементы которой равны О. Такая матрица часто записывается просто как О, поскольку неоднозначность между числом О и нулевой матрицей легко разрешается при помоши контекста.
Если размер нулевой матрицы не указан, то он также выводится из контекста. Часто приходится иметь дело с квадратными (зйпаге) матрицами размером и х и. Некоторые из квадратных матриц представляют особый интерес. 1. Диагональная матрица (йайопа! ша1пх) обладает тем свойством, что а;; = = О при 1 ф 21 Поскольку все недиагональные элементы такой матрицы равны О, диагональную матрицу можно определить путем перечисления ее элементов вдоль диагонали: ап О ... О О а 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,п О 826 Часть Ч11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
