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

1.8. ЯЗЫК ВЫСОКОГО УРОВНЯ - УПРОЩЕННЫЙ АЛГОЛ

3. Если на ленте 1 не нашлось места, соответствующего регистру 30, то, дойдя до самого левого пустого символа, машина печатает 11110#, затем содержимое сумматора и, наконец, ##.

Подумав немного, нетрудно понять, что можно указать МТ, которая правильно смоделирует РАМ. Мы должны показать, что вычисление на РАМ с логарифмическим весом k потребует не более О(й) шагов на машине Тьюринга. Сначала заметим, что регистр может появиться на ленте 1, только если его текущее значение когда-то раньше было помещено в этот регистр. Вес записи c в регистр ij равен / (б;)+/(г;), что с точностью до постоянной равно длине нашего представления ijCj. Отсюда мы заключаем, что длина непустой части ленты 1 есть О [к).

Моделирование любой команды, отличной от STORE, имеет порядок длины ленты 1, т. е. О (/г), ибо основное время уходит на поиск на ленте. Аналогично время моделирования STORE не больше суммы времен поиска на ленте 1 и копирования ее - все вместе б {к). Следовательно, одну команду РАМ (кроме умножения и деления) можно промоделировать не более чем за О (/г) шагов МТ. Так как одна команда РАМ занимает при логарифмическом весе по крайней мере одну единицу времени, общее время, затрачиваемое соответствующей МТ, есть 0(), что и требовалось доказать. □

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

Теорема 1.4. РАМ и РАСП с логарифмическим весом и многоленточные машины Тьюринга полиномиально связаны.

Доказательство. Примените теоремы 1.1 - 1.3 и проанализируйте подпрограммы для умножения и деления. □

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

1.8. ЯЗЫК ВЫСОКОГО УРОВНЯ -УПРОЩЕННЫЙ АЛГОЛ

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

Программу на Упрощенном Алголе можно перевести непосредственно в программу для РАМ или РАСП. Фактически это была бы



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

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

В Упрощенном Алголе применяются традиционные конструкции математики и языков программирования, такие, как выражения, условия, операторы и процедуры. Ниже приведены неформальные описания некоторых из этих конструкций. Никаких попыток дать точное определение не делается, ибо это выходит далеко за рамки тематики данной книги. Заметим, что легко написать программы, смысл которых зависит от деталей, не рассмотренных здесь, но лучше избегать этого, что мы и проделали (мы надеемся) в нашей книге.

Программа на Упрощенном Алголе - это оператор одного из следующих типов:

1) переменная выражение

2) if условие tlien оператор else оператор ) За) while условие do оператор

36) repeat оператор until условие

4) for переменная исходное значение step размер шага *) until заключительное значение do оператор

5) метка: оператор

6) goto метка

7) begin

оператор; оператор;

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

2) Часть «else оператор» не обязательна. Но такой вариант приводит к обычной двусмысленности типа «непривязанное else». Мы выбираем традиционный путь и предполагаем, что else спаривается с ближайшим еще не спаренным then.

3) Часть «$tep размер шага» не обязательна, если размер шага равен 1.



1.8, ЯЗЫК высокого уровня - УПРОЩЕННЫЙ АЛГОЛ

оператор; оператор

8а) procedure имя (список параметров): оператор

86) return выражение

8в) имя процедуры (аргументы)

9а) read переменная

96) write выражение

10) comment комментарий

11) любой другой произвольный оператор

Дадим обзор каждого из этих операторов.

1. Оператор присваивания

переменная >- выражение

означает, что надо вычислить выражение справа от стрелки и его значение присвоить переменной, стоящей слева от стрелки. Временная сложность оператора присваивания определяется временем, затрачиваемым на вычисление значения выражения и присваивание этого значения переменной. Если значение выражения не принадлежит к данным основного типа, таким как целые числа, то в некоторых случаях можно уменьшить время с помощью указателей. Например, присваивание А*-В, где А и В - матрицы размера пхп, обычно потребовало бы 0{п) шагов. Но если В больше нигде не встречается, то путем простого переименования массива можно сделать это время фиксированным, не зависящим от п.

2. В if-операторе

if условие tlien оператор else оператор

условием, следующим за if, может быть любое выражение, принимающее значение true или false. Если это условие имеет значение true, то надо выполнять оператор, стоящий за then. В противном случае надо выполнять оператор, стоящий за else (если else есть). Вес if-оператора равен сумме весов, требуемых для вычисления значения и проверки его, и веса оператора, стоящего сразу за then, или оператора, стоящего за else, в зависимости от того, какой из них выполнялся на самом деле.

3. Назначение while-оператора

while условие do оператор

и repeat-оператора

repeat оператор until условие





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