Главная Промышленная автоматика.

ЗАМЕЧАНИЯ ПО ЛИТЕРАТУРЕ

можно предположить, что это верно для задач нахождения НОД и НОК.

8.31. Еще одна проблема, которая кажется обманчиво простой: выяснить, является ли алгоритм 8.8 наилучшим алгоритмом умножения упорядоченных разреженных полиномов и упорядочения результата. Некоторые аспекты этой проблемы рассмотрел Джонсон [1974].

8.32. Значение п, при котором многие из описанных алгоритмов становятся практичными, огромно. Однако их можно было бы тщательно скомбинировать для небольших п с 0(п*-")-методами, упомянутыми в разд. 2.6 и упр. 8.26, и для самых малых п с очевидными методами сложности 0(п*). Получите таким путем верхние оценки на те значения п, для которых задачи этой главы обладают алгоритмами, лучшими очевидных. Некоторая работа на этом пути уже проделана Кунгом [1973].

Замечания по литературе

Теорема 8.2, утверждающая, что обращение не сложнее умножения, взята у Кука [1966]. Любопытно, что существование полиномиального аналога алгоритма 8.1 не осознавали в течение нескольких лет. Моенк, Бородин [1972] описали алгоритм сложности Об(п log*n log log п) для деления, а вскоре затем алгоритм деления сложности Об(п log п log log n) независимо изложили несколько авторов, в том числе Зивекинг [1972].

Построение алгоритмов для модульной арифметики, а также для вычисления значений и интерполяции полиномов следует работе Моенка, Бородина [1972]. Хейндел, Хоровиц [1971] нашли алгоритм сложности Об (л log"n og log п), восстанавливающий числа по китайской теореме об остатках и использующий предварительную обработку данных. Бородин, Мунро [1971] описали алгоритм сложности 0{rifi) для вычисления значений полинома в нескольких точках, а Хоровиц [1972] обобщил его на интерполяцию. Кунг [1973] построил алгоритм сложности Оа(п log*n) для вычисления значений полинома без применения быстрого (сложности п log п) алгоритма деления. Единство восстановления по вычетам, интерполяции, вычисления значений полиномов и вычисления вычетов целых чисел установил Липсои [1971].

Алгоритм сложности Об (п log" п log log п) для нахождения НОД целых чисел принадлежит Шёнхаге [1971]. На полиномы и общие евклидовы области его перенес Моенк [1973].

Обзор классической техники для нахождения НОД дан Кнутом [1969]. Некоторую подборку материала о сложности арифметических операций над разреженными полиномами можно найти у Брауна [1971], Джентльмена [1972], Джентльмена, Джонсона [1973]. Дополнительные результаты о реализации арифметических операций над полиномами на вычислительных машинах приведены Холлом [1971], Брауном [1973] и Коллинзом [1973]. Алгоритм 8.8 со структурой данных в виде сортирующего дерева реализовал С. Джонсон на языке ALTRAN (см. [Браун, 1973]).

Упр. 8.19 и 8.20 принадлежат Карпу и Ульману. Упр. 8.21 о вычислении значений полинома и его производных можно найти в работах Вари [1974] и Ахо, Стейглица, Ульмана [1974]. Из последней работы взято также упр. 8.28. Упр. 8.27 приведено Блюстейном [1970] и Рабинером, Шэфером, Рейдером [1969]. Подробно арифметические операции над полиномами и целыми числами обсуждаются в книге Бородина, Мунро [1975].



АЛГОРИТМЫ ИДЕНТИФИКАЦИИ

Идентификация цепочек символов входит как составная часть во многие задачи, связанные с редактированием текстов, поиском данных и символьной обработкой. В типичной задаче идентификации цепочек задаются цепочка-текст х и множество цепочек-образов {1. У2, . . .}. Требуется найти либо одно, либо все вхождения цепочек-образов в X. Множество образов часто является регулярным множеством, заданным регулярным выражением. В настоящей главе мы обсудим несколько приемов решения такого рода задач идентификации цепочек.

Начнем с краткого обзора регулярных выражений и конечных автоматов. Затем изложим алгоритм, выявляющий в данной цепочке вхождение какой-нибудь цепочки из множества, заданного регулярным выражением. Время работы алгоритма равно по порядку произведению длин цепочки х и данного регулярного выражения. Потом приведем алгоритм линейной сложности, который распознает, является ли данная цепочка у подцепочкой данной цепочки х. Далее докажем сильный теоретический результат, состоящий в том, что любую проблему распознавания вхождения цепочек, разрешимую на двустороннем детерминированном магазинном автомате, можно решить на РАМ за линейное время. Это замечательный результат, поскольку магазинный автомат может потребовать для решения задачи квадратичное или даже экспоненциальное время. Наконец, введем понятие дерева позиций (позиционного дерева) и применим его к другим задачам идентификации цепочек, таким, как поиск в данной цепочке самого длинного повторения.

9.1. КОНЕЧНЫЕ АВТОМАТЫ И РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯ

Многие задачи идентификации (распознавания образов) и их решения можно выразить в терминах регулярных выражений и конечных автоматов. Поэтому начнем с обзора соответствующего материала.



Определение. Алфавитом называется конечное множество символов. Цепочка в алфавите / - это конечная последовательность символов из /. Пустая цепочка е - это цепочка, че содержащая символов. Конкатенацией цепочек хну называется цепочка ху. Если цепочка имеет вид лгуг, тох - ее префикс (начало), у - подцепочка, а 2 - суффикс (конец). Длиной \х\ цепочки х называется число различных вхождений символов в х. Например, длина цепочки aab равна 3; е имеет длину 0.

Языком над алфавитом / называют произвольное множество цепочек в /. Пусть Li и La-два языка. Язык LiLa, называемый конкатенацией L, и La. есть множество {xy\xLi и yLt).

Пусть L - язык. Тогда положим L={e} и U=LU- при Замыканием Клини (итерацией) L* языка L называют язык L* =

00 00

= и а позитивной итерацией L+ - язык L+= и

1.=.\

Регулярные выражения и языки, которые они представляют (регулярные множества), полезны во многих областях науки о вычислениях. В этой главе мы увидим, что они полезны для описания идентифицируемых образов.

Определение. Пусть / - алфавит. Регулярные выражения над I и языки, представляемые ими, рекурсивно определяются следующим образом.

1. 0 является регулярным выражением и представляет пустое множество.

2. е является регулярным выражением и представляет множество {е}.

3. Для каждого а / символ а является регулярным выражением и представляет множество {а}.

4. Если р и q - регулярные выражения, представляющие множества Р и Q соответственно, то {p-\-q), {pq) и (р*) являются регулярными выражениями и представляют множества Я U Q, PQ и Р* соответственно.

При записи регулярного выражения можно опустить многие скобки, если предположить, что операция * имеет более высокий приоритет, чем конкатенация и -f, а конкатенация - более высокий приоритет, чем +. Например, ((0(1*))-Ь0) можно записать как 01*+0. Кроме того, вместо рр* будем для краткости писать р+.

Пример 9.1.

1. 01 - регулярное выражение, представляющее множество {01}.

2. (О-Ы)* представляет {О, 1}*.

3. 1(0-М)*Ц-1 представляет множество всех цепочек, начинающихся и кончающихся символом 1. □

12* )55





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.0038