1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 70
Текст из файла (страница 70)
8.16. Используйте ваш алгоритм из упр. 8.15, чтобы найти НОД (377, 233). "8.17. Пусть р(х) — разреженный полипом с л мономами. Найдите как функцию от и сложность наилучшего метода вычисления р'(х) при условии, что умножения выполняются по алгоритму 8.8. **8.18. Предлагается следующий метод вычисления ~(х),'д(х) по полнномам г и д в предположении, что д делит 7. пусть | н и нме. ют степень и — 1 или меньше. (1) Вычислить дискретные преобразования Фурье Р и сз полиномов ! и д соответственно. (2) Разделить члены полинома Р на соответствующие члены по. лннома 6; получится последовательность Н.
(3) Взять обратное преобразование от Н. Считаем, что резуль. татом будет )78. Будет ли работать этот алгоритм? *"8.19. Пусть М(п) — время умножения двух л-разрядных двоичных чисел и (~(п) — время нахождения ( )~Т ( для и-разрядного двоичного целого числа !. Предположим, что М(ал))аМ(п) при а-.1 и аналогичное неравенство верно для (~(л). Покажите, что М(п) и Я(л) равны с точностью до постоянного множителя. *8.20. Обобщите упр. 8.19 на (а) полиномы, (б) корни г-й степени при фиксированном г.
*"8.21. Напишите алгоритм сложности ОА(п 1ой и), который вычислял бы полинам степени и — ! и все его производные в данной точке. **8.22. Плотный полипом от г переменных ') можно представить в виде «-~ «-~ «-1 ~ ... ~~.', аць х х,*х,'...х,«. Ь=О Ь=О С =0 ') По мере роста г предположение о плотности поаинома стаиоантсп Осе менее полезным. зи гл. а лги«метичяскив опегкции Покажите, что можно умножать такие полиномы за время Оь(н'1ой и), если аля вычисления значений и интерполяции использовать точки х,=в~', х,=а~', ..., х„=ьр, 0()„с.2а, где гв— примитивный корень степени 2н из единицы. ««8.23.
Покажите, что при разумных допущениях о гладкости функций М(п) и О(л) время умножения и время деления плотных полиномов от г переменных, т. е. М(н) и 0(н), равны с точностью постоянного множителя. **8.24. Найдите алгоритм сложности Ов(п 1ой'и 1оя!ой и), который переводил бы (а) и-разрядные двоичные числа в десятичные; (б) и-разрядные десятичные числа в двоичные.
«"8.25. Наименьшим общим кратным (НОК) целых чисел (полиномов) х и у — называется целое число (некоторый полипом), которое делится на х и у и делит всякое другое целое число (всякий другой полииом), делящееся (делящийся) на х и у. Покажите, что время нахождения НОК двух л-разрядных двоичных чисел не меньше времени их умножения.
8.26. Порождает ли метод умножения целых чисел из разд. 2.6 алгоритм умножения полиномов за время Оа(п'")9 *"8.27. Покажите, что за Ол(л 1ой п) шагов можно вычислить полипом степени л — 1 в точках а', а',..., а" '. Уклпание: Покажи- «-1 л-ь те, что с! — — ~~~Р Ь!аа можно записать какое — — ~'~(!)8(у — 1) для некоток-о ~-« рых функций ~ и д.
**8.28. Покажите, что за Оа(л 1од и) шагов можно вычислить полином степени и — 1 в п точках бае~+са/+е(, 0<1(н. 8.29. Укажите рекурсивные варианты алгоритмов 8.4 и 8,5. Проблемы для исследования 8.30. В этой главе мы показали, что много задач о полиномах и целых числах (1) имекп, по существу, ту же сложность, что и умножение, или (2) сложнее умножения не более чем в логарифмический множитель. Некоторые из этих задач приводятся в упражнениях к данной главе. Упр. 9,9 дает еще одну задачу из группы (2) — задачу о (и/или)-умножении.
Разумно попытаться пополнить множество задач группы (!) или (2). другая область исследования — показать, что некоторые задачи группы (2) должны иметь одинаковые сложности. Например, ЗИ ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ можно предположить, что это верно для задач нахождения НОД и НОК. 8.31. Еще одна проблема, которая кажется обманчиво простой: выяснить, яеляется ли алгоритм 8.8 наилучшим алгоритмом умножения упорядоченных разреженных полиномое и упорядочения результата. Некоторые аспекты этой проблемы рассмотрел Джонсон [1974). 8.32. Значение и, при котором многие из описанных алгоритмов становятся практичными, огромно. Однако их можно было бы тщательно скомбинировать для небольших и с 0(лг ьь)-методами, упомянутыми е равд.
2.6 н упр. 8.26, н для самых малых и с очевидными методами сложности 0(п'). Получите таким путем верхние оценки на те значения и, для которых задачи этой глазы обладают алгоритмами, лучшими очевидных. Некоторая работа на этом пути уже проделана Кунгом [19731. Замечания по лмтературе Теорема 8.2, утверждающая, что обращение ие сложнее умножения, взята у Кука [!966), Любопытно, что существование полиноынального аналога алто. ритма 8.1 не осознавали в течение нескольких лет.
Моенк, Бородин [1972) описали алгоритм сложности Ов (и !ойз и 1оя 1ой и) для деления, а вскоре затем алгоритм деления сложности Ое(л 1ой и 1ой 1оВ и) независимо изложили несколько авторов, в том числе Зивекинг [1972). Построение алгоритмов длк модульной арифметики а также для вычисления значений и интерполяции полнномов следует работе Йоенка, Бородина [1972]. Хейндел, Хоровиц [1971) нашли алгоритм сложности Оз (и 1ойз и 1ой !ой и), восстанавливающий числа по китайской теореме об остатках и использующий предварительнттю обработку данных.
Бородин„Мунро [19?Ц описали алгоритм сложности О(я Лт) для вычисления значений полинома в нескольких точках, а Хоровиц [1972) обобщил его на интерпопяцию. Кунг [1973] построил алгоритм сложности ОА(п 1ойзп) для вычисления значений полинома без применения быстрого (сложности и 1оя и) алгоритма деления. Единство восстановления по вычетам, интерполяции, вычисления значений полииомов и вычисления вычетов целых чисел установил Липсон [1971].
Алгоритм сложности Ок(и 1оаз л 1ой 1ой л) для нахождения НОД целых чисел принадлежит Шенхаге [1971]. На полиномы и общие евклндовы области его перенес Моенк [19?3). Обзор классической техники для нахождения НОД дан Кнутом [1969). Некоторую подборку материала о сложности арифметических операций иад раз. Д еженными полиномами можно найти у Брауна [197!], Джентльмена [1972), ентльмена, Джонсона [1973), Дополнительные результаты о реализации ариф. метических операций над полииомами на вычислительных машинах приведены Холлом [1971), Брауном [1973] и Коллинзом [1973].
Алгоритм 8.8 со структурой данных в виде сортирующего дерева реализовал С. Джонсон на языке А1.ТКАН (см. [Браун, 1973)). Упр. 8.19 и 8.20 принадлежат Карпу и Ульману. Упр. 8.21 о вычислении значений полииома и его производных можно найти в работах Вари [1974! и Ахо, Стейглица, Ульмака 1!974]. Из последней работы взято также упр. 8.28. Упр. 8.27 приведено Блюстейном [1970] и Рабннером, Шафером, Рейдером [1969]. Подробно арифметические операции над полииомами н целыми числами обсуждаются в книге Бородина, Мунра [1976). !2 А. Ахо, дж.
Хопкрофт, дж. ульмья АЛГОРИТМЫ ИДЕНТИФИКАЦИИ Идентификация цепочек символов входит как составная часть во многие задачи, связанные с редактированием текстов, поиском данных и символьной обработкой. В типичной задаче идентификации цепочек задаются цепочка-текст х и множество цепочек-образов (уо Р„...). Требуется найти либо одно, либо все вхождения цепочек-образов в х.
Множество образов часто является регулярным множеством, заданным регулярным выражением. В настоящей главе мы обсудим несколько приемов решения такого рода задач идентификации цепочек. Начнем с краткого обзора регулярных выражений и конечных автоматов. Затем изложим алгоритм, выявляющий в данной цепочке вхождение какой-нибудь цепочки из множества, заданного регулярным выражением. Время работы алгоритма равно по порядку произведению длин цепочки х и данного регулярного выражения. Потом приведем алгоритм линейной сложности, который распознает, является ли данная цепочка у подцепочкой данной цепочки х.
Далее докажем сильный теоретический результат, состоящий в том, что любую проблему распознавания вхождения цепочек, разрешимую на двустороннем детерминированном магазинном автомате, можно решить на РАМ за линейное время. Вто замечательный результат, поскольку магазинный автомат может потребовать для решения задачи квадратичное или даже зкспоненцнальное время.
Наконец, введем понятие дерева позиций (позиционного дерева) и применим его к другим задачам идентификации цепочек, таким, как поиск в данной цепочке самого длинного повторения. 9»т. НОнечные АВтОмАты и РеГуляРные ВыРАжения Многие задачи идентификации (распознавания образов) и их решения можно выразить в терминах регулярных выражений и конечных автоматов.
Позтому начнем с обзора соответствующего материала. РЛ. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ Определение. Алфавитом называется конечное множество символов. Цепочка в алфавите ! — это конечная последовательность символов из !. Пустая цепочка е — это цепочка, че содержащая символов. Конкатенацией цепочек х и у называется цепочка ху. Если цепочка имеет вид хуг, то х — ее префикс (начало), у — надцепочка, а г — суффикс (конец).
Длиной (х! цепочки х называется число различных вхождений символов в х. Например, длина цепочки ааЬ равна 3; е имеет длину О. Языком над алфавитом ! называют произвольное множество цепочек в !. Пусть Е, и Е, †д языка. Язык Е,Е„ называемый конкатенацией Е, и Е„есть множество (ху(хЕЕ, и уЕЕР). Пусть Š— язык. Тогда положим !.'=(Е) н Е'=ЕЕГ-' при Г 1. Замыканием Клина (итерацией) Е' языка Е называют язык !.'= = (! Е', а позитивной итерацией Е+ — язык Е+= (! ЕЕ ! ВМ Регулярные выражения и языки, которые они представляют !регулярные множества), полезны во многих областях науки о вычислениях.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
