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

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

10. comment-оператор позволяет вставлять замечания, облегчающие понимание программы, и имеет вес 0.

11 В дополнение к операторам общепринятых языков программирования мы включили под именем "произвольные" любые операторы, благодаря которым алгоритм можно понять легче, чем эквивалентную последовательность стандартных операторов языка программирования. Такие операторы используются в ситуациях, когда детали реализации либо несущественны, либо очевидны или когда желательно дать описание на языке еще более высокого уровня. Приведем примеры обычно используемых "произвольных" операторов:

а) пусть а будет наименьшим элементом множества S

б) пометить элемент а как "старый" )

в) without lossof generality (wig) считаем, что... otherwise ... in

оператор Например,

wig считаем а <6 otherwise переставить с и d in оператор

означает, что если аЬ, то стоящий дальше оператор следует выполнять так, как он записан, а если а>Ь, то выполнять этот оператор, предварительно поменяв в нем с и d местами.

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

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

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

Под этим мы подразумеваем, что имеется массив СОСТОЯНИЕ, такой, что СОСТОЯНИЕ[а] есть I, если а - «старый» элемент, и О, если а -- «новый».

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



УПРАЖНЕНИЯ

1.1. Докажите, что g{n) есть 0{f(n)), если (а) для некоторого в>0 и для почти всех (т. е. для всех, кроме конечного числа) п и (б) существуют такие постоянные Ci>0 и С2>0, что g (n)c-f {п)+ +С2 для почти всех пО.

1.2. Будем писать f(n)<,g{n), если существует такая положительная постоянная с, что f{n)cg{n) для всех п. Покажите, что /i<gi и /2<g2 влечет fi+/2<gi+g2- Какие еще свойства сохраняет отношение <?

1.3. Напишите программы для РАМ, РАСП и на Упрощенном Алголе для следующих задач:

(а) Вычислить п\ по входу п.

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

(в) Допустить все входы вида 1"2"0.

1.4. Проанализируйте временную и емкостную сложности ваших программ из упр. 1.3 при (а) равномерном и (б) логарифмическом весе. Введите меру "размера" входа.

*1.5. Напишите РАМ-программу для вычисления п" с временной сложностью О (log п) при равномерном весе. Докажите, что ваша программа правильна.

*1.6. Покажите, что для любой РАМ-программы с временной сложностью Т (п) при логарифмическом весе существует эквивалентная РАМ-программа с временной сложностью 0(Т{п)), в которой нет команд MULT и DIV. Указание: Смоделируйте MULT и D1V подпрограммами, в которых регистры с четными номерами используются для промежуточной памяти. В случае MULT покажите, что если i надо умножить на /, то можно сосчитать каждое из / (/) частичных произведений и сложить их за О (/(/")) шагов, а каждый шаг занимает время 0(/(i)).

*1.7. Что случится с вычислительной силой РАМ или РАСП, если из системы команд убрать MULT вместе с D1V? Как это отразится на весе вычисления?

**1.8. Покажите, что любой язык, допускаемый РАМ, может допустить РАМ без косвенной адресации. Указание: Покажите, что всю ленту машины Тьюринга можно целиком закодировать одним целым числом. Таким образом, машину Тьюринга можно смоделировать в конечном числе регистров РАМ.

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



1.10. Найдите неветвящуюся программу, которая вычисляет определитель (ЗхЗ)-матрицы по ее 9 элементам в качестве входов.

1.11. Напишите последовательность битовых операций для вычисления произведения двух двуразрядных двоичных целых чисел.

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

1.13. Покажите, что любую булеву функцию можно вычислить неветвящейся программой.

*1.14. Пусть граф с п узлами представлен множеством двоичных векторов Vj, где /-я компонента вектора равна 1 тогда и только тогда, когда узлы i и / соединены ребром. Найдите алгоритм сложности Одв(«), строящий вектор Pi, у которого на /-м месте стоит 1 тогда и только тогда, когда есть путь из узла 1 в узел /. Можно применить гюразрядные битовые логические операции на двоичных векторах, арифметические операции (на переменных типа "целые"), команды, которые преобразуют отдельные компоненты данных векторов в О или 1, и команду, которая присваивает значение / целочисленной переменной а, если самая левая единица в векторе v находится в разряде/, и полагает а=0 , если v состоит из одних piy-лей.

*1.15. Постройте машину Тьюринга, которая по двум данным двоичным целым числам на лентах 1 и 2 печатает их сумму на ленте 3. Можете считать, что левые концы лент отмечены специальным символом #.

1.16. Приведите последовательность конфигураций (мгновенных описаний) МТ с рис. 1.21, если входом является (а) 0010, (б) 01110.

*1.17. Постройте МТ, которая

(а) печатает О"" на ленте 2, начиная работу с О" на ленте 1,

(б) допускает входы вида 010".

1.18. Укажите множество состояний и функцию переходов МТ, моделирующей РАМ-команду LOAD 3, как в доказательстве теоремы 1.3.

1.19. Постройте РАМ-программу, вычисляющую 2" по данному п за 0(п) шагов. Чему равны (а) равномерный и (б) логарифмический веса вашей программы?

*1.20. Определим g{m, п) равенствами g(0, п)=п и g(m, п) = =2s<"--" при m>0. Напишите РАМ-программу, вычисляющую g(n, п) по п. Как соотносятся равномерный и логарифмический веса вашей программы?





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