1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 97
Текст из файла (страница 97)
11.7, 11.6, заимствованы у Хеппи, Стирнза [1966). Что касается иерархий для ИМТ, то упр. 11.5 (память) взято у Ибврры [!972), а 11.6 (время) — у Кука [1973). Иерархия для РАМ в упр. 11.11 принадлежит Куку Рекхау [19731, упр. 11.14— Хопк офту, упр. 11.19 — Мейеру, Стокмейеру [19731. У становление зкспоненциальных нижних оценок для «естественных» задач началось с работ Мейера [1972] и Мейера, Стокмейера [1972].
Теорема 11.2 о полурасшнренных регулярных выражениях взята у Ханта [19736], теорема 11.3 о расширенных регулярных выражениях — у Мейера, Стокмейера [!973]. Другие результаты о трудно разрешимых задачах приводят Бук [1972], Хант [1973а, 1974], Стокмейер. Мейер [1973), Мейер [1972], Хааг, Розенкранц [!974], Раундз [1973] н Констейбл, Хант, Салин [1974]. НИЖНИЕ ОЦЕНКИ | у~ ЧИСЛА АРИФМЕТИЧЕСКИХ йй ОПЕРАЦИЙ При разработке алгоритма для решения данной задачи основной вопрос, ответ на который нам хотелось бы знать,— это "Какова ее подлинная вычислительная сложность?". Зная теоретическую нижнюю границу для эффективности алгоритма, можно лучше оценить имеющиеся алгоритмы и определить, сколь много усилий следует тратить на поиск лучшего решения. Например, если известно, что задача трудно разрешима, можно довольствоваться эвристическими способами нахождения приближенных решений.
К сожалению, выяснить подлинную вычислительную сложность данной задачи обычно очень трудно. Для большинства практических задач, чтобы судить о качестве алгоритма, приходится полагаться на опыт. Однако иногда можно довольно точно оценить снизу число арифметических операций, требуемых для выполнения вычислений. В этой главе мы изложим некоторые важные результаты этого рода.
Например, покажем, что умножение (пХр)-матрицы на р-вектор требует ар умножений, а вычисление значения полинома л-й степени требует и умножений. Много дополнительных результатов о нижних оценках содержится в упражнениях. Читателю, интересующемуся нижними оценками, советуем рассматривать эти упражнения как неотьемлемую часть данной главы. 12Л. ПОЛЯ Чтобы получить точные нижние границы, надо определить, какие операции считать основными. Для определенности будем предполагать, что все вычисления ведутся в некотором поле, таком, как поле вещественных чисел, где основные операции — сложение и умножение элементов поля. Определение. Полем называется такая алгебраическая система (А, +,, (), 1), что 1) она — кольцо с единицей 1 относительно умножения, 2) умножение коммутативно, Гл.
Рх нижние Оценки числА АРНФметических ОпеРАций 3) каждый элемент а из А — (О) обладает Обратным а-' относительно умножения, т. е. аа-"=а-'а=1'). Пример 12.1. Вещественные числа с обычными операциями сложения и умножения образуют поле. Целые числа образуют кольцо, но не поле, поскольку целые числа, отличные от ь-1, не имеют обратных, являющихся целыми числами.
Но для простого числа р целые числа по модулю р образуют (конечное) поле. (З Рассмотрим задачу вычисления произвольного полинома р(х)= ~а,х' в некоторой точкех. Мы хотим найти алгоритм, который по 7 о значениям а, и х в качестве входов строит соответствующее значение р(х) в качестве выхода. Этот алгоритм должен работать на всех возможных значениях своих входов, принадлежащих некоторому полю. Максимальное число сложений, вычитаний и умножений, выполняемых алгоритмом, где максимум берется по всем допустимым входам, называется арифметической сложностью этого алгоритма.
Заметим, что одни полиномы и-й степени вычислить оказывается проще, чем другие. Например, на вычисление х"+2 тратится порядка 1оя п операций, тогда как интуитивно мы чувствуем, что на вычисление "произвольного" полинома и-й степени должно расходоваться линейное число операций. Поэтому алгоритм для вычисления значений, пригодный только для конкретного полинома, может работать много быстрее, чем алгоритм, применимый ко всем поли номам. Чтобы сформулировать понятие алгоритма, пригодного для целого класса задач, введем для представления входных переменных формальные переменные. Определение. Формальной переменной над алгебраической системой называется символ, не принадлежащий множеству элементов этой системы.
Пусть Р=(А, +, -, О, 1) — поле и х„..., х„— формальные переменные иад Г. Расширением Яхн..., х„! поля Р этими переменными хн..., х„называется такое наименьшее коммутативное ') кольцо (В, +,, О, 1), что В содержит А (! (х„... ° ~ хя). Заметим, что эти формальные переменные не связаны никакими тождествами. Всякий полинам с коэффициентами из Р и "неизвестными" х„..., х„представляет некоторый элемент из Р(хь..., х„1. Два полинома обозначают один и тот же элемент из Р(х,,..., х„), если один из них можно превратить в другой с помощью аксиом коммутативного кольца. Единица в Р будет также единицей в Р(хн..., х„). >~ Как обычно, знак ° опускается, еслн ато не прнводнт к недоразумениям. ) Кольпо с номмутатнвным умножением. ° уз 12.2. ЕЩЕ РАЗ 0 НЕВЕТЕЯЩИХСЯ ПРОГРАММАА Пример 12.2.
Пусть Р— поле вещественных чисел. Тогда кольцо Р[х, у1 включает в себя х, у и все вещественные числа. Так как оио замкнуто относительно сложения, то х+у к х+4 принадлежат Р[х, у1. Так как оно замкнуто относительно умножения, то оно содержит элемент (х+у)(х+4), эквивалентный х'+ху+4х+4у в силу закона дистрибутивиости для кольца. П 42.2. ЕЩЕ РАЗ О НЕВЕТВЯЩИХСЯ ПРОГРАММАХ Зададим снова вопрос. "Сколько арифметических операций требуется для вычисления значений произвольного полинома?» На самом деле вопрос касается числа операций + и, необходимых для построения выражения Да,х' (или эквивалентного ему) от формальных переменных а„..., а„н х. Это мотивирует следующую модель вычислений, которая, по существу, есть модель неветвящейся программы, введенной в равд.
1.5. Определение. Пусть Р— поле. Вычисление относительно Р состоит из !) множества формальных переменных, называемых входами, 2) множества имен переменных, 3) последовательности ии2гов вида а «-Ьйс, где Π— один из знаков +, — или», а — переменная, не участвующая на предыдущих шагах, Ь и с — либо входы, либо элементы из Р, либо имена переменных, появившиеся слева от стрелки иа одном из предыдущих шагов. Краткости ради будем писать а «- Ь вместо а «- Ь+О и а «- — Ь вместо а -Π— Ь. Элемент поля Р, входящий в вычисление, называется постоянной.
Для определения результата вычисления нам нужно понятие значения переменной в вычислении, Говоря неформально, мы считаем, что вычисление производится шаг за шагом; на каждом шаге новой переменной присваивается элемент из Р[х„ ..., х„1, где х„ ..., х„ — входы, Значение о(а) переменной или входа а определяется следующим образом. Если а — вход нли элемент из Р, топ(а)=а. Если а — переменная и а «-Ьйс — шаг, в котором а стоит слева, то о(а)=о(Ь)йо(с). Данное вычисление вычисляеп2 множество Е выражений из Р[хь..., х„1 относительно поля Р, если для каждого выражения еЕЕ найдется вэтом вычислении такая переменная г, что оЯ=е. Заметим, что вычисление рассматривается относительно данного основного поля. Например, чтобы вычислить х'+у' относительно поля Р вещественных чисел, требуются два умножения, даже если Атт ГЛ.
1К НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ не считать умножений на постоянную. Но если г — поле комплекс- ных чисел, достаточно одного умножения (не считая умножений на постоянные), а именно (к+1у) (к — (у). В качестве основного поля обычно берется поле вещественных чисел, хотя можно было бы взять и поле комплексных или рациональных чисел или какое-нибудь ко- нечное поле. Какое поле взять, зависит от того, какие операции счи- тать основными. Если предполагается, что мы умеем представлять вещественные числа и выполнять сложение и умножение их как ос- новные операции, то в качестве г" берется поле вещественных чисел.
Пример 12.3. Вспомним, что вычисление произведения двух комплексных чисел а+(Ь и с+И относительно поля вещественных чисел можно рассматривать как вычисление выражений ас — Ы и ас(+Ьс. Очевидное вычисление выглядит так: аРС 1',-ь. ( 11-11 — 1, ааа — ЬРС 1в 1а+11 Значением 1, является ас. Аналогично п(11)=Ы и о(1,)=ас — Ы.
Таким образом, значение 1, равно первому выражению. Значение 1, равно ас(+Ьс, т. е. второму выражению. Следовательно, это вы- числение вычисляет произведение двух комплексных чисел. Другое вычисление для комплексного умножения использует только три вещественных умножения: 11 — а+ ь 11ас 1( — С 1,'-"1.
11 1.+1. — 1(+ С 1,'-ь»1, 1~ 1,— 1. Легко показать, что п(1,)=а1(+Ьс и п(1,)=ас — Ы. П Должно быть ясно, что данное вычисление вычисляет некоторое выражение тогда и только тогда, когда, подставляя вместо входов произвольные значения из поля Р, получаем вычисление того частного случая выражения, который получается, если подставить эти входные значения вместо формальных переменных рассматриваемого выражения.
В оставшейся части главы нас будут интересовать прежде всего нижние оценки числа умножений, необходимых для вычисления данного множества выражений, поскольку в некоторых ситуациях 4УВ РХЗ МАТРИЧНАЯ ФОРМУЛИРОВКА ЗАДАЧ умножения имеют гораздо большую сложность, чем сложения илн вычитания.
Например, в гл. 6 мы видели, что умножение двух (2 х 2)-матриц за 7 арифметических умножений дает алгоритм умножения произвольных матриц за время ОА(пьч'). Использование же 18 сложений в алгоритме Штрассена не влияет иа асимптотику. На первом уровне рекурсии для алгоритма Штрассена 7 умножений ((п/2)х(п/2))- матриц по мере роста п становятся гораздо сложнее, чем 18 (или любое другое число) сложений и вычитаний матриц того же размера. На самом деле если бы можно было умножать две (2 с 2)-матрицы с помощью только шести умножений в некоммутативном кольце, то у нас мог бы быть алгоритм умножения матриц со сложностью ОА(пьз')=ОА(пп'") независимо от того, сколько тратится на умножение (2х2)-матриц сложений и вычитаний.
(Можно, однако, показать, что для того, чтобы такой алгоритм работал для произвольного кольца, для умножения (2Х2)-матриц необходимы 7 умножений; см. Хопкрофт, Керр (197Н.) Вот другой пример. В равд. 2.6 мы видели, что можно умножить два п-разрядных двоичных целых числа за ОВ(ам™) шагав, потому что достаточно трех умножений, чтобы вычислить выражения ас, Ьп' и ап+Ьс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
