Главная Промышленная автоматика. РАМ-программа Соответствующие операторы на Упрощенном Алголе полож: пока: продолж: конецесли:
read r\ if rlO then write 0 г2г1 while r3 > 0 do г2+-г2 * rl гЗгЗ-1 write г2 Рис. 1.7. РАМ-программа для n". допускается некоторой РАМ тогда и только тогда, когда он рекурсивно перечислим. Язык допускается РАМ, останавливающейся на всех входах, тогда и только тогда, когда он рекурсивен (о рекурсивных и рекурсивно перечислимых языках см. Хопкрофт, Ульман [19691). РассмЬтрим две программы для РАМ. Первая определяет функцию, вторая допускает язык. Пример 1.1. Пусть [ п" для всех целых nl, /(«) = \ О для п = 0.
Рис. 1.9. РАМ-программа, соответствующая алгоритму на рис. 1.8. begin read х; while хфО do begin if хф\ then d -d-1 else d-d+l; read X end; if d = 0 then write 1 end Рис. 1.8. Распознавание цепочек с одинаковыми числами вхождений 1 и 2. Программа на Упрощенном Алголе, вычисляющая f(n) путем (п-1)-кратного умножения на п, приведена на рис. 1.6 ). Соответствующая программа для РАМ дана на рис, 1.7. Переменные г1, г2 и гЗ хранятся в регистрах 1, 2 и 3 соответственно. Мы специально не сделали очевидных улучшений программы, чтобы яснее было видно соответствие между рис. 1.6 и 1.7. □ Пример 1.2. Рассмотрим РАМ-программу, которая допускает язык во входном алфавите {1, 2}, состоящий из всех цепочек с одинаковым числом вхождений 1 и 2. Эта программа считывает каждый входной символ в регистр 1, а в регистре 2 оставляет разность d между количеством символов 1 и 2, поступивших до текущего момента. Встретив концевой маркер О, программа сравнивает d с нулем и в случае совпадения печатает 1 постанавливается. Мы считаем О, 1 и 2 единственно возможными входными символами. Основные детали алгоритма приведены в программе на рис. 1.8, Эквивалентная программа для РАМ дана на рис. 1.9; х хранится в регистре 1, ad - в регистре 2. □ 1.3. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ РАМ-ПРОГРАММ Двумя важными мерами сложности алгоритма являются временная и емкостная сложности, рассматриваемые как функции размера входа. Если при данном размере в качестве меры сложности берется наибольшая из сложностей (по всем входам этого размера), то она называется сложностью в худшем случае. Если в качестве меры сложности берется "средняя" сложность по всем входам данного размера, то она называется средней (или усредненной) сложностью. Обычно среднюю сложность найти труднее, чем сложность в худшем случае. Нужно еще принять некоторое предположение о распределении входов, а реалистичные допущения часто бывает трудно сформулировать математически. Мы будем уделять основное внимание худшему случаю, поскольку его легче исследовать и он имеет универсальную приложимость. Однако следует помнить, что алгоритм с наименьшей сложностью в худшем случае не обязательно имеет лучшую сложность в среднем. Временная сложность в худшем случае (или просто временная сложность) РАМ-программы - это функция f{n), равная наибольшей (по всем входам размера п) из сумм времен, затраченных на каждую сработавшую команду. Временная сложность в среднем - это средцее, взятое по всем входам размера п, тех же самых сумм. Такие же понятия определяются для емкости памяти, только вместо "времен, затраченных на каждую сработавшую команду" надо подставить "емкостей всех регистров, к которым было обращение". 1) Описание Упрощенного Алгола см. в разд. 1.8. 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.0021 |