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

выражение для ЦИКЛ((д;#)*) i). Длина выражения Ri должна быть не больше длины выражения R, умноженной на постоянную.

**П.14. Постройте недетерминированный алгоритм с емкостной сложностью О (л), выясняющий, пусто ли множество, представленное произвольным полурасширенным регулярным выражением. Почему ваш алгоритм не срабатывает, когда вы пытаетесь узнать, представляет ли данное регулярное выражение все цепочки? Почему он должен не срабатывать?

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

11.16. Напишите регулярное выражение для "нарушений структуры" в доказательстве леммы 11.4.

11.17. Элементарна ли функция, определяемая равенствами f (0)=1 и f (л)=2*"-1> для /г>1? (Эта функция введена в разделе 4.7.)

*11.18. Постройте алгоритм, выясняющий, представляет ли произвольное расширенное регулярное выражение пустое множество. Какова временная и емкостная сложности вашего алгоритма?

**11,19. Покажите, что задача пустоты для расширенных регулярных выражений, использующих только знаки операций -f, • и -i, неэлементарна.

Проблемы для исследования

11.20. Естественная область исследований, подсказываемая материалом этой главы,- поиск практически важных задач, про которые можно доказать, что они трудно разрешимые. Работу в этом направлении проделали Фишер, Рабин 1974], исследовавшие сложность задач с элементарными арифметическими операциями, Кук, Рекхау [1974], изучившие процедуры доказательства теорем 2), Хаит [1974], рассмотревший ряд задач из теории языков, и некоторые другие авторы, упомянутые в замечаниях по литературе.

11.21. Интересен также вопрос о том, насколько плотнее могут быть иерархия по времени для ДМТ и иерархии по времени и емкости для НМТ по сравнению с иерархиями, указанными в упр. 11.5, 11.6 и 11.8. Например, существуют ли конструируемые по времени функции Т{п), для которых нет языков, распознаваемых за время 7(rt)logr(n), но не Т{п)? Читателю советуем обратиться к работе Сайфераса, Фишера, Мейера [1973], где приводится самая плотная из известных иерархий для НМТ.

) Результатом применения операции ЦИКЛ к множеству цепочек служит объединение ее значений на каждой отдельной цепочке из этого множества.

2) Здесь уместно сослаться еще на статью Цейтина [1968].-Ярил, перев.



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

Первое обширное исследование иерархий по емкости и времени для машин Тьюринга выполнили Хартманис, Стирнз [1965] и Хартманис, Льюис, Стирнз [1965]. Статья Рабина [1963] была одной из первых работ о временной сложности, и она заслуживает изучения. Улучшения иерархии по времени, данные в упр. 11.7, 11.8, заимствованы у Хенни, Стирнза [1966]. Что касается иерархий для НМТ, то упр. 11.5 (память) взято у Ибарры [1972], а 11.6 (время) - у Кука [1973]. Иерархия для РАМ в упр. 11.11 принадлежит Куку, Рекхау [1973], упр. 11.14 - Хопкрофту, упр. 11.19 - Мейеру, Стокмейеру [1973].

Установление экспоненциальных нижних оценок для «естественных» задач началось с работ Мейера [1972] и Мейера, Стокмейера [1972]. Теорема 11.2 о полурасширенных регулярных выражениях взята у Ханта [19736], теорема 11.3 о расширенных регулярных выражениях - у Мейера, Стокмейера [1973]. Другие результаты о трудно разрешимых задачах приводят Бук [1972], Хаит [1973а, 1974], Стокмейер, Мейер [1973], Мейер [1972], Хаит, Розенкранц [1974], Раундз 11973] и Констейбл, Хант, Сахни [1974].



НИЖНИЕ ОЦЕНКИ

ЧИСЛА АРИФМЕТИЧЕСКИХ

ОПЕРАЦИЙ

При разработке алгоритма для решения данной задачи основной вопрос, ответ на который нам хотелось бы знать,- это "Какова ее подлинная вычислительная сложность?". Зная теоретическую нижнюю границу для эффективности алгоритма, люжно лучше оценить имеющиеся алгоритмы и определить, сколь много усилий следует тратить на поиск лучшего решения. Например, если известно, что задача трудно разрешима, можно довольствоваться эвристическими способами нахождения приближенных решений.

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

12.1. ПОЛЯ

Чтобы получить точные нижние границы, надо определить, какие операции считать основными. Для определенности будем предполагать, что все вычисления ведутся в некотором поле, таком, как поле вещественных чисел, где основные операции - сложение и умножение элементов поля.

Определение. Полем называется такая алгебраическая система (Л, -f, ., О, 1), что

1) она - кольцо с единицей 1 относительно ухшожения,

2) улшожение коммутативно,





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