В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 5
Текст из файла (страница 5)
) получаем рекуррентное нера венство Ь(п) ( 7Ц вЂ” ) + 0(оз). 2 По теореме 2.4 о рекуррентном неравенстве отсюда получаем Ь(и) = 0(о "Я~ г). Теорема доказана. Замечание. Ожидается, что для умножения матриц порядка п существует алгоритм с числом арифметических операпий 0(ц~+') для любого фиксированного с ) 0 (сравните с алгоритмом Тоома), однако пока (середина 2002 года) наилучшей оценкой является 0(из зэ) 12]. гз 3.
Метод расширения модели Очень важным методом в математике является метод "расширения модели". Переход в более широкую модель обычно не упрощает задачу, но расширяя возможности, упрощает поиск решения задачи. Важным примером расшврения модели является развитие понятия числа: натуральные — дробные — пелые — рациональные — действительные — комплексные. Выход в более широкую модель позволяет более компактно описывать алгоритмы и за счет этого находить более быстрые алгоритмы для исходной модели. Примером может служить алгоритм Таама, где от умножения чисел мы переходим к умножению многочленов и используем возможность интерполяции многочленов.
В разжлах 3.1-3.2 и ЗА-3.5 мы рассмотрим другие примеры применения идеи расширения модели. 3.1. Алгоритмы умножения О-1-матриц Пусть матрицы А н В состоят только нз 0 и 1 н требуется вычислить С = А. В, где все элементы с„должны быть представлены в двоичной системе. В качестве операций разрешим только любые битовые операции нал двумя переменными. Теорема 3.1. Ллэ вычисления (обычного) произведение двух О-1-матриц порядка и суивествует алгоритм с числом битовых онераиий 0(и' ввг1обзп). Лемма 3.1. Если в исходных матрииох А и В порядка п все элементы имеют двоичную двину не более й (включая знак), то в алгоритме Штрассена для вычисления АВ все воэникаю~цие числа имеют двоичнУю длинУ не более 21 + 4(1обз и) . Доказательство леммы.
При формировании подзадач вычисления Рз — Рг в алгоритме Штрассена происходит сложение (или вычитание) не более чем двух матриц. Поэтому модули всех чисел не более чем удваиваются, то есть добавляется не более одного разряда. При переходе от размерности и к размерности 1 подзадачи формируются (1обзи) раз. Следовательно, в подзадачах размерности 1 все числа имеют длинУ не более й+ (1обз и). Йлк подзадач РазмеРности 1 алгоритм Штрассена производит обычное умножение. При этом длина полУчающнхсл чисел не пРевосходит 2й+2(1обз и).
ПРи вычислении С„ цо результатам подзадач Р~ -Рг складываются (вычвтаются) не более чем по 4 матрицы. При этом максимальные модули чисел возрастают не более чем в"4 раза, то есть добавляется не более чем ло 2 разряда. Поскольку обратных шагов также До6з п~, то все получаемые числа имеют длинУ не более 2/с + 2 ~1обз п1 + 2 ~1обз п1 = 2)с + 4 Г1обз п~). Лемма доказана. Докаэашельстпво тпеоремы. Применим для вычисления АВ алто- ритм Штрассена.
По условию в исходных матрицах А и В все элементы имеют длину 2 (включая знак). Тогда по лемме все возникающие в алгоритме числа будут иметь длину не более 4+ 4 бойз п1 = 0(1об и). Так как в алгоритме Штрассена используются только сложение, вычитание и умножение, то любая арифметическая операция в алгоритме Штрассена требует 0(1обз п) битовых операций. Поскольку алгоритм Штрассена использует 0(пьч* ) арифметических операций, то все они потребуют 0(п з'т 1оя~ и) битовых операций.
Теорема доказана. Замечание 1. Опенку можно улучшить, если использовать быстрые алгоритмы для умножения чисел. Замечание 2. В этой теореме можно получить оцеюсу 0(паза), если использовать известный более быстрый алгоритм умножения матриц. Рассмотрим теперь операцию булевского умножения 9-1-матриц. Определение. Пусть А = ))а; )) и В = ))Ьтл)) — две О-1-матприцтя порядка и. Булевским произведением А о В называется матрица Р = ))д„)) тпакая, чтпо для всех т и в. Пля булевского умножения матриц нельзя непосредственно применить идею Штрассена, так как в алгоритме Штрассена есть вычитание, а у дизъюнкции нет обратной операции.
Несмотря на это, справедлива следующая теорема. Теорема 3.2. Булевское произведение Р = А о В двух О-1-матприц А и В порядка п можно вычислитпь с числом битповых операций 0(пмзт 1ой~ и), Яокаэатпельстпво. Мы опишем соответствующий алгоритм, хоторый основан на идее "расширения модели". Вместо вычисления Р = А о В мы вычислим сначала обычное произведение С = АВ. При этом отметим следующую связь между Р и С: д,=1с=ьс,>0. По предыдущей теореме для вычисления С = ))с„,)) существует алгоритм с числом битовых операпий 0(п1ьв т 1обз п). После этого в каж- лом с„, дОстаточно взять дизъюнкшпо всех ргзрядов (исключая знак), чтобы вычислить 4, Поскольку О < с„< и, то длина каждого с„ не превосходит 0(1обп) и на вычисление всех 4., из с„потребуется 0(изйщп) битовых операций.
Общее число битовых операций будет О(п"вт т 1об~ п) + 0(пз 1ок и) = 0(пме т 1обз и). Теорема доказана. Замечание. См. замечания к предьцтущей теореме. 3.2. Транзитивное замьпсание графов ° Явно» ориентированный граф С в виде матрицы А = ()а; (), где а;т = 1, если в С есть дуга нз о; в от, и а,; = О, если такой дуги нет (оа =.О для всех т). Требуетпсзт построить матрипу В = )(ЬтД, такую, что Ьтт — — 1, если есть ориентированный путь из о, в о, и Ь„= О, если такого пути жт (в'частности, Ьи = 1 для всех т).
Определение. Ориентированный граф с матрицей смежности В называется тпранзитпивным замыканием графа С. Теорема З.З. Транзитпивное замыкание ориентпированного граута с п еер»зинами можно построить, используя 0(пмв т Ьтбз и) битповыз операт»ит1. Локазатпельстпео. Пусть А — матрица смежности орграфа С и матрица А = ))а; )( получается из А заменой всех диагональных элементов на 1. Тогда а;, = 1 в том и только в том случае, если из ю; в ит существует ориентированный путь длины (т.е, с числом дуг) не более 1.
Пусть А'» = А о А о... А, где число сомножителей равно Ь и умножение матриц булевское. Лемма 3.2. Если А'» = 'Оаз О, тпо а»" = 1 в тпом и ошлько в тпом случае, если в С сутцестпвуетп ориентпированныа путпь из оз в и длин»в не более й. Яоказаптельстпво (индукцией по й). При й = 1 утверждение верно. Пусть оно верно при й = р, то есть аб = 1 тогда и только тогда, когда существует путь из ез в и; длины не боже р. По определению лолучеем А'а+О '= А'з о А и агь~ = ~/ а" в акь Отсюда аз ~ = 1 тогда и только тогда, когда существует вершина ит такая, что из ит в ит существует цуть длины не более р, и из ит в и существует путь длины не более 1. Но это условие равносильно тому, что из о; в иу существует путь длины не более р+ 1.
Таким образом, утверждение леммы верно и при й = р+ 1. Лемма доказана. Если в орграфе С из и; в и существует хотя бы один ориентировелный пучь, то существует такой путь без повторения вершин и, сле- довательно, длины ве более и — 1, где и — число вершин в С. Поэтому из леммы следует, что А'» = В при любом й ) и — 1. Будем вычислять последовательно А,А'2,А'4,А'з,...А'~, где т = (1о82(п — 1)1. Так как 2 ) и — 1, то А'2 = В. По теореме 3.2 существует алгоритм для вычисления всех этих матриц, и в частности В, с числом битовых операций т ° О(п"в 2 1ой~п) = О(п'з 2 1ойз и). Теорема локазанв. Замечание.
См. замечания к теореме 3.1. 3.3. Распознавание принадлежности булевых функций предполным классам Поста Рассмотрим задачу распознавания свойств булевых фующий, причем сейчас будем считать, что булевы функции поступают на вход алгоритма в векторпом представлении. А именно, пусть все наборы длины и из О и 1 упорядочены естественным образом (хак соотвеэ ствуюшие им двоичные числа). Тогда булевскую функпию ((хь..., х„) от и переменных можно задать вектором (ав, ам..., аз 2) ее значений на всех 2" наборах.
В качестве алгоритмов мы рассмотрим алгоритмы с битовыми операциями. Любой такой алгоритм можно рассматривать как схему из функциональных элементов (СФЭ), элементами в которой могут быть любые функции от 2 переменных (или от 1 переменной). Если ответ в задаче для данного входа "да", то на выходе должна быть 1, иначе О. Под сложностью юпоритма будем понимать число битовых операций (число элементов в СФЭ). Теорема Поста о полноте системы булевых функций сводит вопрос о полноте к вопросу о првнадлежности функций б предполным классам Тв, Тп Я, Х, М (см. [18]). Мы рассмотрим вопрос о сложности распознавания этих свойств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
