Главная Промышленная автоматика. Замечания по литературе Сведения по теории графов можно почерпнуть из книг Бержа [1958] и Харари [1969]. Алгоритм 5.1, строящий остовные деревья наименьшей стоимости, взят из работы Крускала [1956]. Прим [1957] указывает другой подход к этой задаче. Алгоритм, предложенный в упр. 5.3, указал нам Спира. Алгоритм, касающийся двусвязности и использующий поиск в глубину, принадлежит Хопкрофту. Алгоритм для сильно связных компонент взят у Тарьяна [1972]. В литературе отражены многочисленные применения поиска в глубину для построения оптимальных или наилучших из известных алгоритмов. Хопкрофг, Тарьян [1973а дают линейную проверку планарности. В другой работе Хопкрофт, Тарьян 19736] описывают линейный алгоритм нахождения 3-связных компонент. Тарьян [1973а] на основе той же идеи разработал наилучший из известных алгоритмов нахождения доминаторов. Кроме того, Тарьян [19736] предлагает тест для «редуцируемости потоковых графов». Алгоритм 5.5, т. е. общий алгоритм нахождения путей, по существу, принадлежит Клини [1956], который использовал его в связи с «регулярными выражениями» (разд. 9.1). Данная здесь форма этого алгоритма заимствована у Мак-Нотона, Ямады [1960]. Алгоритм сложности О(п), строящий транзитивное замыкание, взят из работы Уоршола [1962]. Аналогичный алгоритм, отыскивающий кратчайшие пути для всех пар узлов, заимствован у Флойда [1962] (см. также Ху [1968 • - - .. [1959 ). Алгоритм для случая одного источника изложен по работе Дейкстры . Сайра, Пан [1973] показывают, что алгоритм Дейкстры, по существу, оптимален, если в качестве модели брать деревья решений. Данциг, Блаттнер, Рао [1967] заметили, что наличие ребер с отрицательными стоимостями не влияет на решение задачи нахождения кратчайших путей между всеми парами точек, если нет цикла с отрицательной стоимостью. Джонсон [1973] обсуждает задачи с одним источником при наличии ребер с отрицательными стоимостями; он же приводит решения упр. 5.21 и 5.22. Спира [1973] дает алгоритм нахождения кратчайшего пути за среднее время 0(п logn). Связь между задачей нахождения путей и умножением матриц описана в работах Мунро [1971] и Фурмана [1970] (теорема 5.7) и Фишера, Мейера [1971] (теорема 5.6). Связь с транзитивной редукцией (упр. 5.13-5.15) заимствована у Ахо, Гэри, Ульмана [1972]. Ивен [1973] обсуждает ft-связность графов. УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ в этой главе мы исследуем асимптотическую вычислительную сложность умножения матриц, элементы которых берутся из произвольного кольца. Мы увидим, что "обычный" алгоритм умножения матриц, имеющий сложность О (п), можно асимптотически улучшить; чтобы умножить две (пХп)-матрицы, достаточно времени 0(п«1). Более того, мы увидим, что и другие операции, такие, как НВП-разложение, обращение матрицы и вычисление определителя, сводятся к умножению матриц, и потому их можно выполнить столь же быстро, как и умножение матриц. Затем покажем, что умножение матриц сводится к обращению матрицы, и потому любое улучшение асимптотического времени решения одной из этих задач привело бы к аналогичному улучшению для другой. Закончим главу двумя алгоритмами умножения булевых матриц, асимптотическая временная сложность которых меньше О(п). По существу к алгоритмам этой главы не следует относиться как к практическим, если исходить из технических возможностей современных вычислительных машин. Одна из причин состоит в том, что из-за скрытых постоянных множителей они работают быстрее обычных алгоритмов сложности О (п) только для достаточно больших значений п. Кроме того, для этого семейства алгоритмов недостаточно хорошо понято поведение ошибок округления. Тем не менее идеи данной главы, на наш взгляд, заслуживают рассмотрения, поскольку они свидетельствуют, что очевидные алгоритмы не всегда наилучшие, а также потому, что могут служить основой разработки еще более эффективных и действительно практических алгоритмов для этого важного класса задач. 6.1. ОСНОВНЫЕ ПОНЯТИЯ в настоящем разделе приводятся основные алгебраические понятия, полезные при изучении задач умножения матриц. Читатель, знакомый с кольцами и линейной алгеброй, может сразу перейти к разд. 6.2. Определение. Кольцом называется алгебраическая структура (S, +, •, О, 1), где S - множество элементов, а + и--бинарные операции на нем. Для каждых а, й и с из S выполняются следующие соотношения: 1) {а+Ь)+с-а+(Ь+с) и {a-b)C~a-{b-c) (операции + и - ассоциативны); 2) a+b=b+a (операция + коммутативна); 3) (а+Ь) • с=аС+Ьсиа-{Ь+с)=а-Ь+ас (операция - дистрибутивна относительно +); 4) а+0=0+а=а (О служит единичным элементом для +); 5) а - 1 = 1 -0=0 (1 служит единичным элементом для •); 6) для каждого aS существует обратный элемент -а, т. е. а+ (-а)=(-а)+а=0. Заметим, что последнее свойство - существование обратного элемента относительно сложения - в замкнутом полукольце может не выполняться (разд. 5.6). А свойство 4 замкнутого полукольца - существование и единственность бесконечных сумм - не обязательно выполняется в кольце. Кольцо, в котором операция-коммутативна, называется коммутативным. Если в коммутативном кольце для каждого элемента а, отличного от О, существует элемент а-, обратный относительно умножения, т. е. а-а-1=а-1-а=1, то кольцо называется полем. Пример 6.1. Вещественные числа образуют кольцо, если взять в качестве + и • обычные сложение и умножение. Вещественные числа, однако, не образуют замкнутого полукольца. Система ({О, 1}, +, -, О, 1), где + - сложение по модулю 2 и • - обычное умножение, образует кольцо, но не замкнутое полукольцо, поскольку значение 1-f Ц-. . .не определено. Но если переопределить + так, что а+&=0, если а=Ь=0, и а+Ь=1 в прочих случаях, то получится замкнутое полукольцо из упр. 5.1. Sa не является кольцом, поскольку 1 не имеет обратного. □ Введем важный класс колец матриц. Определение. Пусть R={S, +, -,0, 1) - кольцо и Л1„-множество (п X п)-матриц, элементы которых принадлежат R. Пусть On обозначает (пХп)-матрицу, все элементы которой равны О, и In-единичную (п X п)-матрицу, у которой на главной диагонали стоят 1, а на остальных местах 0. Для Л и fi из Л1„ обозначим через А+п В такую (пХп)-матрицу С, что С И, j]=A И, j]+B И, }]»), а через /4-„В - такую (пХп)-матрицу D, что D И, j]= А [i, k]-•В Ik, /]. *) M[i, j] - элемент, стоящий в матрице М на пересечении f-й строки и /-го столбца. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 [81] 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 0.0022 |