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

1.5. МОДИФИКАЦИЯ РАМ

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

/. Неветвящиеся программы

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

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

команды получается слово, не помещающееся в регистр, то переполняющая часть этого слова бесследно исчезает. Пусть tM{w) hsm(w) - соответственно число шагов и память при работе М над w, а и м(.") - время и память в худшем

случае, т. е.

(м{п)= max Гм(ш), s„{n)= шах Sm{w).

\w\< п IшI< л

Очевидно, что log s;n («)<(") (здесь и ниже через log л обозначается длина двоичного представления числа п). Разумно ввести ограничение на функцию /:

;(пХшах{шах \Pi\, logtin)}. l<i<k

Первый член, а именно тахр,, стоит для того, чтобы программа могла помещаться в память машины естественным образом - одна команда в один регистр. Поскольку обязательно Hn)logsj(n), то для адресной машины всегда syn(n)< </д1(я). Если наложить на 1{п) еще и некоторые требования конструируемости (см. гл. 10), например считать, что 1(п) можно вычислить на машине с Цп) ячейками без переполнений за время, не большее 2*", то почти весь материал настоящей книги можно будет основать на понятии адресной машины. К числу важных преимуществ адресной машины по сравнению с РАМ, РАСП и машиной Тьюринга относится возможность в ее терминах точно и достаточно адекватно ставить вопрос о нижних оценках сложности и для задач с заведомо небольшой, например квадратичной, верхней оценкой.- Прим. перев.



ный алгоритм умножения матриц содержит циклы, которые следует выполнить точно п раз, при этом от команд разветвления требуется только сравнение параметра цикла с п. □

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

Кроме того, поскольку каждая неветвящаяся программа может обращаться только к конечному числу регистров памяти, удобно присвоить этим регистрам имена. Потому при ссылке на регистры мы будем употреблять символические адреса (символы или цепочки букв), а не целые числа.

Устранив потребность в командах READ, JUMP, JGTZ и JZERO, мы остаемся с командами LOAD, STORE, WRITE, HALT и арифметическими операциями из системы команд РАМ. Нам не нужна команда HALT, ибо на остановку указывает конец программы. Можно обойтись и без WRITE, назначив в качестве выходных переменных определенные символические адреса; выходом программы будет значение, принимаемое этими переменными к окончанию работы программы.

Наконец, можно "встроить" LOAD и STORE в арифметические операции, заменяя последовательности вида

LOAD а ADD Ь STORE с

на с*-а+Ь. Весь набор команд неветвящейся программы выглядит так:

x*-y + z х-<-г/-2 zf-г/* г

где x, у vl Z - символические адреса (или переменные), а i - постоянная. Легко видеть, что любую последовательность команд

2 А. Ахо, Дж. Хопкрофт, Дж. Ульман 33



LOAD, STORE и арифметических операций в сумматоре можно заменить последовательностью, составленной из пяти выписанных выше команд.

С неветвящейся программой связаны два выделенных набора переменных - входы и выходы. Функцией, вычисляемой данной неветвящейся программой, называется множество значений выходных переменных (в определенном порядке), выраженных через значения ее входных переменных.

Пример 1.4. Рассмотрим вычисление полинома

p(x)=a„x« + a„-l"+ • • +aiX+ao.

Входными переменными служат коэффициенты а„, Aj, . . ., а„ и неопределенная переменная х Выходной переменной будет р. По правилу Горнера р {х) вычисляется так:

1) aiX+a„ для п=1,

2) (flaX+ai) х+а„ для п=2,

3) ((азХ+аа) лг+ах) х+а„ для п==3.

На рис. 1.16 приведены неветвящиеся программы, соответствующие этим выражениям. Правило Горнера для произвольного п теперь должно быть понятно. Для каждого п у нас есть неветвящаяся программа из 2п шагов, вычисляющая полином п-й степени. В гл. 12 мы покажем, что для вычисления произвольного полинома п-й степени по его коэффициентам требуется п умножений и п сложений. Таким образом, если в качестве модели брать неветвящиеся программы, правило Горнера оптимально. □

Если брать в качестве модели вычислений неветвящуюся программу, то временная сложность последовательности программ равна числу шагов п-й программы как функции от п. Например, правило Горнера порождает последовательность с временной слож-

п= 1

п = 2

rt = 3

t >-а.;*х

t->- flg * л:

p*-t Н-а„

t*-t + ax

tt+a.

t"-t*x

t >- t *x

p - t+a.

t*-t+a.

t-- t*x

p*-t+a.

Рис. 1.16. Неветвящиеся программы, соответствующие правилу Горнера.





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