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

и добавляет (Сь, Се) к НОВ. Кроме того, на шаге 3 вызываем КОР-РЕКТИР(Св, С,), и этот вызов полагает TEPM[C8]=Cs и добавляет (Cg, Cj) к НОВ. Поэтому после шага 3 НОВ содержит пары

(С„ CJ, (С, С), (С„ С,), (Сю, Cjo), (Cii, С,,), (С„ Се), (С„ С,).

На шаге 4 удаляем (С4, С4) из НОВ и вызываем КОРРЕКТИР(Сз,С5), поскольку (Сз, Сб) лежит ниже (С4, С4). Поскольку в этот момент ТЕРМ[С5]=Св, КОРРЕКТИР полагает ТЕРМ[Сз]=Се и добавляет (Сз, С,) к НОВ. Затем на шаге 4 удаляем (Се, Се) из НОВ и, поскольку (предположим, что это так) ниже (Се, Се) не лежит никакая пара, не вызываем КОРРЕКТИР »). Аналогично не вызываем КОРРЕКТИР для пар (С„ С,), (Сю, Сю), (Сц, С„) и (С,, Се). Когда (Cg, С,) удаляется из НОВ, вызываем КОРРЕКТИР(С,, Сю), и этот вызов полагает ТЕРМ[С,]=Сю и добавляет (С,, Сю) к НОВ. В этот момент НОВ содержит (Сз, С,) и (С,, Сю).

Удалив (Сз, С,) из НОВ, вызываем К0РРЕКТИР(с2, С,), что приводит к ТЕРМ[с2]=Сю и ТЕРМ[с11=Сю, поскольку ПРЕЩСг] содержит Ci. Добавляем (Cj. Сю) и (Ci, Сю) к НОВ.

Предлагаем читателю завершить это моделирование. □

Теорема 9.10. Алгоритм 9.4 правильно отвечает на вопрос "Принадлежит ли слово w языку ЦР)?" за время 0{\w\).

Доказательство. Можно показать, что каждая конфигурация попадает в список ВРЕМ не более одного раза. Поэтому каждый вызов процедуры КОРРЕКТИР закончится. Также можно показать, что никакая пара конфигураций не попадает в список НОВ более одного раза, следовательно, и сам алгоритм закончит работу. Подробное доказательство этих двух утверждений оставляем в качестве упражнения.

Покажем, что по окончании работы алгоритма 9.4 TEPMlCol будет заключительной конфигурацией тогда и только тогда, когда w£L(P). Легко показать индукцией по числу шагов работы алгоритма 9.4, что

1) если TEPMIC] полагается равным D, то D - терминатор для С,

2) если С добавляется к ПРЕД[], то С = D,

3) если (С, D) помещается в НОВ, то TEPM[C]=D.

Таким образом, если алгоритм 9.4 обнаруживает, что TEPMlCol- заключительная конфигурация, то в силу леммы 9.1 утверждение "ше(Р)" верно.

Кроме того, надо показать, что если D - терминатор для С, то TEPMIC] в конце концов становится равным D. Доказательство

) Для простоты мы считаем, что Р не делает шагов, которые не следуют из рис. 9.17.



проводится индукцией по числу шагов в последовательности С 1-* D. Базис, т. е. случай нулевого числа шагов, тривиален, поскольку C=D и TEPMIC] делается равным D на шаге 2 алгоритма 9.4.

Для шага индукции предположим, что С \- Е \-* D, и рассмотрим отдельно два случая.

Случай 1. Е - конфигурация, т. е. шаг С [- £ не является ни шагом push, ни шагом pop. Тогда на шаге 3 вызывается КОРРЕК-ТИР{С, Е). Если к этому моменту ТЕРМ[£1 было присвоено значение D, то конфигурация С будет помещена в список ВРЕМ в строке 2 и в конце концов значение ТЕРМ[С] сделается равным D в строке 5. Если значение ТЕРМ[£] еще не равно D, то добавляем С к ПРЕД[£1 в строке 1 процедуры КОРРЕКТИР(С, Е). По предположению индукции мы в конце концов получим, что TEPM[£]=D. Если это случится в строке 5 процедуры КОРРЕКТИР, то С добавится к ВРЕМ в строке 7, а значение ТЕРМ1С] сделается равным D во время этого вызова процедуры КОРРЕКТИР. Значение ТЕРМ[£] не может стать равным D на шаге 2 алгоритма 9.4, поскольку ЕфО. (Если бы оказалось, что £=D, то ТЕРМ[£] уже было бы присвоено значение D к тому моменту, когда мы стали рассматривать С\- Е на шаге 3.) Итак, в случае 1 значение TEPMIC1 оказывается равным D.

Случай 2. Е - это такое МО, что С \- Е является шагом push. Тогда можно найти такие конфигурации А, В н F, что (С, F) лежит ниже (А, В), А \-* В н F-* D, причем каждый из этих переходов совершается за меньшее число шагов, чем переход С \-* D. (Конфигурация А служит "поверхностью" МО Е.) По предположению индукции, значение ТЕРМ[Л полагается равным В, а значение TEPM[F] - равным D.

Допустим, что последнее происходит раньше первого. Тогда (Л, В) со временем помещается в НОВ, а на шаге 4 вызывается КОРРЕКТИР(С, F). Так как в этот момент TEPM[/=]=D, то в строке 5 полагаем TEPM[C]=D.

Допустим теперь, что ТЕРМ[Л] присвоено значение В до того, как TEPM[f ] присвоено значение D. Тогда при вызове КОРРЕК-THP(C,F) TEPM[F]=0 и С добавляется к ПPEД[F]. Но тогда D становится значением ТЕРМ[С] при вычислении TEPMlf ]. Это завершает индукцию и доказательство корректности алгоритма 9.4.

Проанализируем время работы алгоритма 9.4. Шаги 1 и 2 занимают 0{п) времени, поскольку всего конфигураций 0{п). Так как для каждой конфигурации 2ДМА делает не более одного шага, то пар конфигураций (С, D), в которых С\- D, всего 0{п). Поэтому процедура КОРРЕКТИР вызывается на шаге 3 не более 0{п) раз.

Пара (С, D) попадает в список НОВ, когда С D и уже найдено, что D - терминатор для С. Так как каждая конфигурация имеет лишь один терминатор (если она его вообще имеет), то никакая пара не помещается в список НОВ более одного раза. Следователь-



НО, общее число пар, помещаемых в список НОВ, не превосходит 0{п). Ниже каждой пары, попавшей в НОВ, лежит ограниченное число пар, ибо если (С, D) лежит ниже (С, D), то положения головок конфигураций С и С, а также D и D, различаются не более чем на 1. Поэтому КОРРЕКТИР вызывается 0{п) раз.

Теперь оценим общее время, затрачиваемое на подпрограмму КОРРЕКТИР. Можно показать, что в массиве ПРЕД каждая конфигурация появляется не более одного раза и в список ВРЕМ никакая конфигурация не попадает более одного раза. Общее время выполнения строк 4-6 процедуры КОРРЕКТИР пропорционально количеству конфигураций В, удаляемых из ВРЕМ, а время выполнения строки 7 - количеству конфигураций А, добавляемых к ВРЕМ. Так как КОРРЕКТИР вызывается не более 0{п) раз, то общее время, занимаемое процедурой КОРРЕКТИР, без учета времени на строки 4-6 и 7 составляет 0{п). Следовательно, алгоритм 9.4 работает линейное время. □

Результаты настоящего раздела применяются главным образом при доказательстве существования алгоритмов линейной сложности, решающих определенные задачи. Мы уже видели, что некоторые задачи идентификации образов можно сформулировать как задачи распознавания языков. Если мы сможем построить 2ДМА, распознающий язык, соответствующий задаче идентификации образов, то сможем утверждать, что существует алгоритм линейной сложности, решающий ту же задачу. Так как на входе длины п 2ДМА может делать п" или даже 2" шагов, то часто бывает проще найти алгоритм для распознавания языка на 2ДjV\A, чем алгоритм линейной сложности для решения задачи идентификации образов прямо на РАМ.

9.5. ПОЗИЦИОННЫЕ ДЕРЕВЬЯ И ИДЕНТИФИКАТОРЫ ПОЗИЦИЙ

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

1. По данным цепочке-тексту х и цепочке-образу у найти все вхождения у в X.





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