Главная Промышленная автоматика. Рис. 1.13. Моделирование SUB *i на РАСП. Например, команда SUB *г для РАМ имеет вес М = 1(с (0)) + / И) +1 (с (i)) + 1(с{с т. Последовательность S, моделирующая эту команду РАМ, показана на рис. 1.14. Здесь с(0), c{i) и c(c(i)) относятся к содержимому регистров РАМ. Так как занимает в РАСП регистры от 2 до г, то /<г-11. Кроме того, I (х+у)1 {х)+1 (у), так что вес S, разуме-
Рис. 1.14. Веса команд РАСП. ется, не превосходит 2/(1) + 4Af + 1И(г)< (6 + 11/(г))М. Поэтому можно заключить, что постоянная /г=6+П 1{г) такова, что если Р имеет временную сложность Т{п), то временная сложность для Pg не превосходит кТ(п). □ Теорема 1.2, Как при равномерном, так и при логарифмическом весе команд для любой РАСП-программы с временной сложностью Т (п) существует такая постоянная к, что найдется эквивалентная РАМ-программа, временная сложность которой не превосходит kT{n). Доказательство. РАМ-программа, которую мы построим для моделирования данной РАСП, будет использовать косвенную адресацию для декодирования и моделирования РАСП-команд, хранящихся в памяти РАМ. Некоторые регистры РАМ будут иметь специальное назначение: регистр 1 - для косвенной адресации, регистр 2 - для счетчика команд РАСП, регистр 3 - для хранения содержимого сумматора РАСП. РАСП-регистр с номером i будет храниться в РАМ-регистре с номером 1+3 при t>l. Искомая РАМ начинает работу с РАСП-программы конечной длины, расположенной в ее памяти с регистра 4 и далее. Регистр 2 (счетчик команд) содержит число 4; регистры 1 и 3 - число 0. РАМ-программа состоит из цикла моделирования, начинающегося со считывания РАСП-команды (с помощью РАМ-команды LOAD »2), декодирования ее и разветвления на один из 18 наборов команд, каждый из которых предназначен для обработки одного типа РАСП-команды. На неправильном коде операции РАМ, как и РАСП, остановится. Операции декодирования и разветвления строятся естественным образом; моделью может служить пример 1.2 (хотя символ, декодируемый там, был считан со входа, а здесь он считывается из памяти). В качестве примера приведем те команды РАМ, которые моделируют РАСП-команду с кодом 6, т. е. SUB i. Эта программа, изображенная на рис. 1.15, вызывается, когда с (с (2))=6, т. е. когда счетчик команд указывает на регистр, содержащий число 6 - код команды SUB. Дальнейшие детали построения нужной РАМ-программы мы опускаем. В качестве упражнения предлагаем доказать, что при равномерном и логарифмическом весовых критериях временная сложность РАМ-программы самое большее в постоянное число раз превосходит временную сложность исходной РАСП-программы. □ Увеличение счетчика команд на 1, так что он начинает указывать на регистр, содержащий операнд i команды SUB i. Вызов / в сумматор, прибавление числа 3 и запоминание результата в регистре 1. Извлечение содержимого сумматора РАСП из регистра 3. Вычитание содержимого регистра t + 3 и помещение результата обратно в регистр 3. Увеличение счетчика команд снова на 1, так что теперь он указывает на следующую команду РАСП Возвращение к началу цикла моделирования (обозначенному здесь через "а"). Рис. 1.15. Моделирование SUB i на РАМ.
Из теорем LI и L2 следует, что в отношении временной сложности (а также и емкостной - это остается в качестве упражнения) модели РАМ и РАСП эквивалентны с точностью до постоянного множителя, т. е. порядки величин их сложностей одинаковы для одного и того же алгоритма. Обычно мы будем выбирать из этих двух моделей модель РАМ, поскольку она проще ). ) Значительную часть недостатков РАМ и PAQl, указываемых авторами, можно устранить, если рассмотреть следующую модель, также основанную на принципе адресной организации памяти. Адресная машина состоит из бесконечного числа регистров, занумерованных двоичными числами. Первые три регистра служат для специальных целей: вход, выход и сумматор. (Мы рассматриваем лишь модель с хранимой программой.) В регистры можно записывать слова в алфавите {О, 1}. Для определенности выберем систему команд LOAD = (, LOAD i, LOAD *(, STORE i, STORE *(, ADD (, SUB i, SHIFT i (сдвиг содержимого сумматора на число разрядов, равное содержимому регистра i, знак этого содержимого определяет направление сдвига), AND ( (поразрядное булево умножение), OR i, EXCLUSIVE OR i, HALT. Машиной M будем называть пару (P, I), где P=Pi, ...,Pk - программа (т. е. список конкретных команд р,), а I - функция, ограничивающая длину содержимого регистров: при работе над входом длины п в регистры можно записывать слова длины ровно 1(п). Работа машины М над словом w определяется, как обычно: программа Р записывается в память машины, начиная с четвертого регистра; при k-u срабатывании команды LOAD вход в сумматор записывается й-я компонента входа; результатом работы (если машина остановилась) считается слово, получаемое последовательным приписыванием всех слов, засылавшихся в выходной регистр; если при выполнении какой-то 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 |