1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 5
Текст из файла (страница 5)
Например, команда 1.ОА0=32 должна храниться в виде числа 2 в одном регистре и 32 в следующем регистре. Так же как для РАМ, состояние РАСП можно представить с помощью 1) отображения памяти с, где с(1), 1»0,— содержимое 1'-го регистра, 2) счетчика команд, указывающего первый из двух последовательных регистров памяти, из которых надлежит взять текущую команду. Вначале счетчик команд устанавливается на некоторый выделенный регистр. Обычно исходное содержимое регистров памяти не состоит из одних нулей, так как в память уже введена программа. Однако мы требуем, чтобы вначале все регистры, кроме конечного числа, содержали О, и чтобы сумматор также содержал О.
После выполнения каждой команды счетчик команд всегда увеличивается на 2, кроме случаев ЛЗМР 1, ЛОТЕ( (при положительном сумматоре) и ЗЕЕКО1(при нулевом сумматоре), когда он устанавливается на й Действие каждой команды в точности то же, что и у соответствующей команды РАМ. Временную сложность РАСП-программы можно определить, по существу, тем же способом, что и для РАМ-программы. Можно использовать либо равномерный весовой критерий, либо логарифмический.
В последнем случае, однако, надо приписать вес не только !Мя МОДЕЛЬ С ХРАНИМОЙ ПРОГРАММОЙ Команда Код Код Команда Рнс. 1.12. Коды дия команд РАСП. вычислению операнда, но и выбору самой команды. Вес выбора команды равен 1(СК), где СК означает содержимое счетчика команд. Например, вес выполнения команды АРР=(, хранимой в регистрах ! и !+1, равен 1(1)+1(с(0))+1(!) '). Вес команды АРР г, хранимой в регистрах 1 и !+1, равен !())+!(с(0))+!(!)+!(с(!)). Интересно узнать, какова разница в сложности между РАМ-программой и соответствующей РАСП-программой.
Ответ не будет неожиданным. Независимо от того, взят ли равномерный вес илилогарифмическнй, любое отображениетнпа вход — выход, выполнимое за время Т (и) одной моделью, может выполнить за время яТ (и) другая модель, где й — некоторая постоянная. Аналогично объемы памяти, используемые этими моделями, при любой из двух рассматриваемых весовых мер отличаются друг от друга только на постоянный множитель.
Сформулируем эти соотношения в виде двух теорем. Обе теоремы доказываются построением алгоритмов, моделирующих одну машину другой. Теорема 1.1. Как при равномерном, так и при логарифмичгском весе команд для любой РАМ-программы с временной сложностью Т (и) существует такая постоянная й, ипо найдется вквивалгнтная РАСП-программа, временная сложность которой не превосходит йТ (и). ») Можно было бы также добавить и вес считывания регистра !+1, но он не мон«ет сильно отличаться от! ((). Во всей этой главе нас не интересует величина мультипликативных постоянных, а только порядок роста функций.
Поэтому (0)+1(/+1) «приблизитеиьно» равняется 10), т. е. с точностью до множителя, не превышающего 3. "ау 1.ОАР 1 ОАР АВТОВЕ АРР АРР =1 Я)В Я)В =1 МИ.Т МШ.Т Р1Ч Р(Ч КЕАР У((И ТЕ %Е1ТЕ !()МР !ОТО !АЛЕКО НА1.Т 10 11 12 13 14 15 16 17 18 ГЛ. ) МОДЕЛИ ЗЫЧИСЛЕИИИ до к аз а тел ь с та о. Покажем, как моделировать РАМ- программу некоторой РАСП-программой. Регистр 1 в РАСП будет служить для временного запоминания содержимого сумматора РАМ.
Отправляясь от Р, мы будем строить РАСП-программу Р„ которая будет занимать следующие г — 1 регистров РАСП. Постоянная г определяется РАМ-программой Р. Содержимое регистра РАМ с номером 1, 1)1, будет храниться в регистре РАСП с номером г+1, так что все адреса в РАСП-программе будут на г больше соответствующих адресов в РАМ-программе. Каждая РАМ-команда в Р, не содержащая косвенной адресации, прямо кодируется в такую же РАСП-команду (с надлежащим увеличением адресов), Каждая РАМ-команда в Р, содержащая косвенную адресацию, переводится в последовательность из шести РАСП- команд, которые моделируют косвенную адресацию путем изменения команд.
Проиллюстрируем моделирование косвенной адресации на примере. Лля моделирования РАМ-команды Я)В е1, где 1 — положительное целое, построим последовательность РАСП-команд, которые !) временно запоминают содержимое сумматора в регистре 1, 2) вызывают содержимое регистра г+1 в сумматор (РАСП-регистр с номером г+(соответствует РАМ-регистру с номером 1), 3) прибавляют г к сумматору, 4) запоминают число, вычисленное на шаге 3 в адресном поле команды Я)В, 5) восстанавливают сумматор из временного регистра 1, 6) используют команду Я)В, созданную на шаге 4, для выполнения вычитания.
Например, применяя кодирование команд РАСП, приведенное на рис. 1.12, и предполагая, что последовательность РАСП-команд начинается в регистре 100, можно смоделировать Я)В ЕГ последовательностью, показанной на рис. 1.13. Сдвиг г можно будет определить, когда станет известно количество РАСП-команд в программе Р,. Мы видим, что для моделирования каждой РАМ-команды требуется самое большее шесть РАСП-команд, так что при равномерном весовом критерии временная сложность получаемой РАСП-программы не превосходит 67 (л), (Заметим, что зта мера не зависит от того, каким способом определен размер входа,) При' логарифмическом весовом критерии каждая команда 7 из РАМ-программы Р моделируется последовательностью 3, состоящей в Р, либо из одной, либо из шести РАСП-команд. Можно показать, что существует постоянная й, зависящая от Р, такая, что суммарный вес команд в 5 не более чем в е раз превосходит вес команды 1, Регистр Содержимое Значение ВТОРОЕ 1 !.ОАП .+! А1)1) 6ТОКЕ 111 10АО 1 Я)В Ь, где Ь вЂ” содержимое Ого регистра РАМ Рис, 1.!3.
Моделирование ЯЗВ М на РАСП. Нанример, команда 5БВ е! для РАМ имеет вес Л4 = 1 (с (О)) + 1(1) + 1 (с (1)) + 1(с (с (1))). Последовательность 5, моделирующая эту команду РАМ, показана на рис. 1.14. Здесь с(0), с(1) и с(с(1)) относятся к содержимому регистров РАМ. Так как Р, занимает в РАСП регистры от 2 до г, то ((г — 11, Кроме того, 1(х+у)(1(х)+1(у), так что вес Я, разуме- Регистр РАСП Команда Вес ЕТОЕ Е 1 1.0АО г+1 АР!) = г ВТОРОЕ 1+11 1.0АР 1 8!)В 1 1+2 1+4 1+6 1+8 /+ 10 Рис.
1.14. Веса команд РАСП. 100 101 102 103 104 106 106 !07 108 !09 1!О 111 8~ г+! 1 6 ~ з~ 1 ье модель с хрлнимои пногнлммои 1(1)+1(1)+1(с (О)) 1(1+2)+1(г+1)+1(с (1)) 1(1+ 4) +1(с(1)) +1(г) 1О+6)+1О+11)+1(с(1)+г) 1(1+ 8) +1(1) +1(с (О)) 1 (1 + 10) + ! (с (1) + г) + + 1 (с (О)) + 1 (с (с (1))) гл. ь модвли вычислении ется, не превосходит 21(1)+4й4+ 111(г) ((б+1П(г)) й(. Поэтому можно заключить, что постоянная А=6+11 1(г) такова, что если Р имеет временную сложность Т(п), то временная сложность для Р, не превосходит АТ(п). Д Теорема !.2. Как при равномерном, так и при логарифмическом весе команд для любой РАСП-программы с временной сложноапью Т (и) существует такая постоянная й, что найдется эквивалентная РАМ-программа, временная сложность которой не превосходит йТ (и).
Д о к а з а т е л ь с т в о. РАМ-программа, которую мы построим для моделирования данной РАСП, будет использовать косвенную адресацию для декодирования и моделирования РАСП- команд, хранящихся в памяти РАМ. Некоторые регистры РАМ будут иметь специальное назначение: регистр 1 — для косвенной адресации, регистр 2 — для счетчика команд РАСП, регистр 3 — для хранения содержимого сумматора РАСП. РАСП-регистр с номером 1 будет храниться в РАМ-регистре с номером 1+3 при 1)1. Искомая РАМ начинает работу с РАСП-программы конечной длины, расположенной в ее памяти с регистра 4 и далее.
Регистр 2 (счетчнк команд) содержит число 4; регистры 1 и 3 — число О. РАМ- программа состоит из цикла моделирования, начинающегося со считывания РАСП-команды (с помощью РАМ-команды 1.ОА(1 +2), декодирования ее и разветвления на один из 18 наборов команд, каждый из которых предназначен для обработки одного типа РАСП-команды. На неправильном коде операции РАМ, как и РАСП, остановится. Операции декодирования и разветвления строятся естественным образом; моделью может служить пример 1.2 (хотя символ, декодируемый там, был считан со входа, а здесь он считывается из памяти).
В качестве примера приведем те команды РАМ, которые моделируют РАСП-команду с кодом 6, т. е. Я)В 1. Эта программа, изображенная на рис. 1.15, вызывается, когда с(с(2))=б, т. е. когда счетчик команд указывает на регистр, содержащий число 6 — код команды Я)В. Дальнейшие детали построения нужной РАМ-программы мы опускаем. В качестве упражнения предлагаем доказать, что при равномерном и логарнфмическом весовых критериях временная сложность РАМ-программы самое большее в постоянное число раз превосходит временную сложность исходной РАСП-программы. Д ЗФ !.К МОДЕЛЬ С ХРАИИМОЙ ПРОГРАММОЙ ЕОА)) А()Р ВТОР Е ВОАТ А()1) 8ТОг(Е 2 Увеличение счетчика команд на 1, так что он = 1 начинает указывать на регистр, содержащий 2 операнд ! команды Я)В !.
«2 Вызов ! в сумматор, прибавление числа 3 и запоминание результата в регистре 1. Извлечение содержимого сумматора РАСП из регистра 3. Вычитание содержимого регистра 1+3 и помещение результата обратно в регистр 3. 2 Увеличение счетчика команд снова на 1, так что =1 теперь он указывает на следующую команду 2 РАСП а Возвращение к началу цикла моделирования (обозначенному здесь через "а"). (.ОА0 Я!В ВТОКЕ 1.ОА() А00 ЯТОМ Е Л()МР Рис. 1.15. Моделирование З()В 1 на РАМ. ') Значительную часть недостатков РАМ и РАОП, указываемых авторами, можно устранить, если рассмотреть следующую модель, также основанную на принципе адресной организации памяти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
