1.4. МОДЕЛЬ С ХРАНИМОЙ ПРОГРАММОЙ

Поскольку РАМ-программа не хранится в памяти РАМ, она не может изменять себя. Сейчас мы рассмотрим другую модель вычислительной машины, называемую машиной с произвольным доступом к памяти и хранимой программой (или, иначе, равнодоступной адресной машиной с хранимой программой — сокращенно РАСП), которая отличается от РАМ лишь тем, что ее программа находится в памяти и может изменять себя.

Набор команд для РАСП совпадает с соответствующим набором для РАМ во всем, кроме косвенной адресации, которая исключена, ибо она не нужна. Мы увидим, что РАСП может моделировать косвенную адресацию путем изменения команд в процессе выполнения программы.

Общая структура РАСП также подобна структуре РАМ, но только предполагается, что РАСП-программа находится в регистрах памяти. Каждая РАСП-команда занимает два последовательных регистра памяти. Первый регистр содержит код операции, второй — адрес. Если адрес имеет вид то первый регистр будет содержать (в закодированном виде) указание на то, что операнд является литералом, а второй регистр будет содержать Для кодирования команд берутся целые числа. На рис. 1.12 представлено одно возможное кодирование. Например, команда должна храниться в виде числа 2 в одном регистре и 32 в следующем регистре.

Так же как для РАМ, состояние РАСП можно представить с помощью

1) отображения памяти с, где содержимое регистра,

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

Вначале счетчик команд устанавливается на некоторый выделенный регистр. Обычно исходное содержимое регистров памяти не состоит из одних нулей, так как в память уже введена программа. Однако мы требуем, чтобы вначале все регистры, кроме конечного числа, содержали 0, и чтобы сумматор также содержал 0. После выполнения каждой команды счетчик команд всегда увеличивается на 2, кроме случаев (при положительном сумматоре) и (при нулевом сумматоре), когда он устанавливается на Действие каждой команды в точности то же, что и у соответствующей команды РАМ.

Временную сложность РАСП-программы можно определить, по существу, тем же способом, что и для РАМ-программы. Можно использовать либо равномерный весовой критерий, либо логарифмический. В последнем случае, однако, надо приписать вес не только

Рис. 1.12. Коды для команд РАСП.

вычислению операнда, но и выбору самой команды. Вес выбора команды равен где означает содержимое счетчика команд. Например, вес выполнения команды хранимой в регистрах равен Вес команды хранимой в регистрах равен

Интересно узнать, какова разница в сложности между РАМ-программой и соответствующей РАСП-программой. Ответ не будет неожиданным. Независимо от того, взят ли равномерный вес или логарифмический, любое отображение типа вход — выход, выполнимое за время одной моделью, может выполнить за время другая модель, где некоторая постоянная. Аналогично объемы памяти, используемые этими моделями, при любой из двух рассматриваемых весовых мер отличаются друг от друга только на постоянный множитель.

Сформулируем эти соотношения в виде двух теорем. Обе теоремы доказываются построением алгоритмов, моделирующих одну машину другой.

Теорема 1.1. Как при равномерном, так и при логарифмическом весе команд для любой -программы с временной сложностью существует такая постоянная что найдется эквивалентная РАСП-программа, временная сложность которой не превосходит

Доказательство. Покажем, как моделировать РАМ-программу некоторой РАСП-программой. Регистр 1 в РАСП будет служить для временного запоминания содержимого сумматора РАМ. Отправляясь от мы будем строить РАСП-программу которая будет занимать следующие регистров РАСП. Постоянная определяется РАМ-программой Содержимое регистра РАМ с номером будет храниться в регистре РАСП с номером так что все адреса в РАСП-программе будут на больше соответствующих адресов в РАМ-программе.

Каждая РАМ-команда в не содержащая косвенной адресации, прямо кодируется в такую же РАСП-команду (с надлежащим увеличением адресов). Каждая РАМ-команда в содержащая косвенную адресацию, переводится в последовательность из шести РАСП-команд, которые моделируют косвенную адресацию путем изменения команд.

Проиллюстрируем моделирование косвенной адресации на примере. Для моделирования РАМ-команды где положительное целое, построим последовательность РАСП-команд, которые

1) временно запоминают содержимое сумматора в регистре 1,

2) вызывают содержимое регистра в сумматор (РАСП-регистр с номером соответствует РАМ-регистру с номером

3) прибавляют к сумматору,

4) запоминают число, вычисленное на шаге 3 в адресном поле команды

5) восстанавливают сумматор из временного регистра 1,

6) используют команду созданную на шаге 4, для выполнения вычитания.

Например, применяя кодирование команд РАСП, приведенное на рис. 1.12, и предполагая, что последовательность РАСП-команд начинается в регистре 100, можно смоделировать последовательностью, показанной на рис. 1.13. Сдвиг можно будет определить, когда станет известно количество РАСП-команд в программе

Мы видим, что для моделирования каждой РАМ-команды требуется самое большее шесть РАСП-команд, так что при равномерном весовом критерии временная сложность получаемой РАСП-программы не превосходит (Заметим, что эта мера не зависит от того, каким способом определен размер входа.)

При логарифмическом весовом критерии каждая команда из РАМ-программы моделируется последовательностью состоящей в либо из одной, либо из шести РАСП-команд. Можно показать, что существует постоянная зависящая от такая, что суммарный вес команд не более чем в раз превосходит вес команды

Рис. 1.13. Моделирование на РАСП.

Например, команда для РАМ имеет вес

Последовательность моделирующая эту команду РАМ, показана на рис. 1.14. Здесь относятся к содержимому регистров РАМ. Так как занимает в РАСП регистры от 2 до то Кроме того, так что вес

Рис. 1.14. Веса команд РАСП.

разумеется, не превосходит

Поэтому можно заключить, что постоянная такова, что если имеет временную сложность то временная сложность для не превосходит

Теорема 1.2. Как при равномерном, так и при логарифмическом весе команд для любой РАСП-программы с временной сложностью существует такая постоянная что найдется эквивалентная РАМ-программа, временная сложность которой не превосходит

Доказательство. РАМ-программа, которую мы построим для моделирования данной РАСП, будет использовать косвенную адресацию для декодирования и моделирования РАСП-команд, хранящихся в памяти РАМ. Некоторые регистры РАМ будут иметь специальное назначение:

регистр 1 — для косвенной адресации,

регистр 2 — для счетчика команд РАСП,

регистр 3 — для хранения содержимого сумматора РАСП.

РАСП-регистр с номером будет храниться в РАМ-регистре с номером при

Искомая РАМ начинает работу с РАСП-программы конечной длины, расположенной в ее памяти с регистра 4 и далее. Регистр 2 (счетчик команд) содержит число 4; регистры 1 и 3 — число 0. РАМ-программа состоит из цикла моделирования, начинающегося со считывания РАСП-команды (с помощью РАМ-команды декодирования ее и разветвления на один из 18 наборов команд, каждый из которых предназначен для обработки одного типа РАСП-команды. На неправильном коде операции РАМ, как и РАСП, остановится.

Операции декодирования и разветвления строятся естественным образом; моделью может служить пример 1.2 (хотя символ, декодируемый там, был считан со входа, а здесь он считывается из памяти).

В качестве примера приведем те команды РАМ, которые моделируют РАСП-команду с кодом 6, т. е. Эта программа, изображенная на рис. 1.15, вызывается, когда с т. е. когда счетчик команд указывает на регистр, содержащий число 6 — код команды

Дальнейшие детали построения нужной РАМ-программы мы опускаем. В качестве упражнения предлагаем доказать, что при равномерном и логарифмическом весовых критериях временная сложность РАМ-программы самое большее в постоянное число раз превосходит временную сложность исходной РАСП-программы.

Рис. 1.15. (см. скан) Моделирование на РАМ.

Из теорем 1.1 и 1.2 следует, что в отношении временной сложности (а также и емкостной — это остается в качестве упражнения) модели РАМ и эквивалентны с точностью до постоянного множителя, т. е. порядки величин их сложностей одинаковы для одного и того же алгоритма. Обычно мы будем выбирать из этих двух моделей модель РАМ, поскольку она проще.