1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 10
Текст из файла (страница 10)
Второй способ применения процедуры состоит в вызове ее с помощью оператора вызова процедуры (8в), Этот оператор есть, по существу, имя процедуры, за которым идет список фактических параметров. Оператор вызова процедуры может изменить и (обыч- гл. ь модвли зычислвнии но изменяет) данные (значения переменных, массивов и т. д.) вызываемой программы.
В определении вызываемой таким способом процедуры ге1цгп-оператор не нужен, Завершение выполнения последнего оператора процедуры завершает и выполнение оператора ее вызова. Например, следующий оператор определяет процедуру ВЗАИМОЗАМЕНА; ргосег)пге ВЗАИМОЗАМЕНА (х, у): Ьей(п 1 х; х у; у-1 епо Для обращения к этой процедуре можно было оы написать оператор вызова процедуры, такой, как ВЗАИМОЗАМЕНА (.А 11), Л 11!) Обмен информацией между процедурами можно осуществлять двумя способами. Во-первых, с помощью глобальных переменных. Мы предполагаем, что глобальные переменные неявно описаны в некоторой универсальной области. В этой области есть подобласть, в которой определены процедуры. Во-вторых, связь между процедурами можно осуществлять с помощью параметров. В Алголе 60 используется вызов по значению и вызов по наименованию.
Прн вызове по значеииюформальные параметры процедуры трактуются как локальные переменные, которым в качестве начальных значений придаются значения фактических параметров. При вызове по наименованию формальные параметры служат указателями места в программе, куда подставляются фактические параметры вместо каждого вхождения соответствующих формальных параметров.
Для простоты мы отходим от Алгола 60 и используем вызов по ссылке. При вызвав по ссьике параметры обрабатываются с помощью указателей на фактические параметры. Если фактический параметр является выражением (возможно, постоянной), то соответствующий формальный параметр трактуется как локальная переменная, которой в качестве начального значения присвоено значение этого выражения. Поэтому вес реализации вычисления функции или выполнения вызова процедуры на РАМ и РАСП равен сумме весов выполнения опера~оров в определении соответствующей процедуры.
Вес выполнения процедуры, вызывающей другие процедуры (возможно, себя), обсуждается в гл. 2. 9. Смысл геад-оператора н ътНе-оператора очевиден. Вес геадоператора равен 1. Вес ит! 1е-оператора на 1 больше веса вычисления значения выражения, стоящего за выделенным словом итИе. 52 ЬВ. ЯЗЫК ВЫСОКОГО УРОВНЯ УПРОЩЕННЫЙ АЛГОЛ !О. сопнпеп1-оператор позволяет вставлять замечания, облегчающие понимание программы, и имеет вес О.
! ! В дополнение к операторам общепринятых языков программирования мы включили под именем "произвольные" любые операторы, благодаря которым алгоритм можно понять легче, чем эквивалентную последовательность стандартных операторов языка программирования. Такие операторы используются в ситуациях, когда детали реализации либо несущественны, либо очевидны или когда желательно дать описание на языке еще более высокого уровня. Приведем примеры обычно используемых "произвольных*' операторов: а) пусть а будет наименьшим элементом множества 5 б) пометить элемент а как "старый" ') в) тт!1!ГОН!!Онзо1 депега!Ну (ти!й) считаем, что... О1)тетэм!Зе ...
!п оператор Например, ту!д считаем а (Ь о1!тепч!Зе переставить с и д !п оператор означает, что если а(Ь, то стоящий дальше оператор следует выполнять так, как он записан, а если а)Ь, то выполнять этот оператор, предварительно поменяв в нем с и с! местами. Реализация таких операторов в терминах общепринятых языков программирования или команд РАМ не вызывает затруднений, но она очень утомительна.
Приписывание весов операторам такого типа зависит от контекста, в котором оказывается данный опера яр. Дальнейшие примеры операторов такого рода не раз встретятся нам в этой книге в программах на Упрощенном Алголе. Поскольку переменные обычно не будут описываться, условимся об областях их действия. В одной программе или процедуре мы не будем употреблять одинаковые имена для двух разных переменных. Поэтому в качестве области действия переменной обычно можно брать всю процедуру или программу, в которую она входит '). Одно важное исключение возникает в случае, когда несколько процедур действуют на общей базе данных. В этом случае предполагается, что переменные общей базы данных глобальны, а переменные, используемые процедурой для временного запоминания в ходе работы с базой данных, локальны для этой процедуры.
Всякий раз, когда может возникнуть недоразумение по поводу области действия переменной, будет даваться явное описание. ') Под втнм мы подрввумеваем, что имеется массив СОСТОЯНИЕ, такой, что СОСТОЯНИЕ!а! есть й если а — «стврый«элемент, и О, если а — «новый». ') Это утверждение имеет нескольно несуюественных исключений.
Например, в процедуру могут входить двв невложенпых !ог-опервторв, обв с индексом а Строго говоря, область действия индексе 1ог-опервторв — это свм !от-опервтор, н потому вти индексы « являютсн разными переменными. ГЛ. ! МОДЕЛИ ВЫЧИСЛЕНИЙ УПРАЖНЕНИЯ 1.1. Докажите, что д(п) есть 0(((п)), если (а) )(п))е для некоторого В)О и для почти всех (т. е. для всех, кроме конечного числа) и и (б) существуют такие постоянные с,>0 и с,>0, чтой(п)<с,~(и)+ +с„для почти всех п)О.
1.2. Будем писать ~(п)<д(п), если существует такая положительная постоянная с, что ((и) =сд(п) для всех п. Покажите, что 1,<й, и (,<д, влечет (,+~.,~й,+д,. Какие еще свойства сохраняет отношение <? 1.3. Напишите программы для РАМ, РАСП и на Упрощенном Алголе для следующих задач: (а) Вычислить и! по входу и.
(б) Прочитать п положительных чисел, за которыми следует концевой маркер О, а затем напечатать их в порядке неубывания. (в) Допустить все входы вида 1"2"'О. 1.4. Проанализируйте временную и емкостную сложности ваших программ из упр. 1,3 при (а) равномерном и (б) логарифмическом весе. Введите меру "размера" входа.
*1.5. Напишите РАМ-программу для вычисления п" с временной сложностью О(!оя п) при равномерном весе, Докажите, что ваша программа правильна. *1.6. Покажите, что для любой РАМ-программы с временной сложностью Т(п) при логарифмическом весе существует эквивалентная РАМ-программа с временной сложностью 0(Т'(и)), в которой нет команд М1Л Т и 1)!У. Указании: Смоделируйте М1Л Т и О!У подпрограммами, в которых регистры с четными номерами используются для промежуточной памяти. В случае МЫЬТ покажите, что если 1 надо умножить на 1, то можно сосчитать каждое из ! (() частичных произведений и сложить их за О(!(()) шагов, а каждый шаг занимает время О(!(!)). *1.7, Что случится с вычислительной силой РАМ или РАСП, если из системы команд убрать МЫЬТ вместе с (?1У? Как это огра.
зится на весе вычисления? **1.8. Покажите, что любой язык, допускаемый РАМ, может допустить РАМ без косвенной адресации. Указание: Покажите, что всю ленту машины Тьюринга можно целиком закодировать одним целым числом. Таким образом, машину Тьюринга можно смоделировать в конечном числе регистров РАМ. 1.9. Покажите, что при (а) равномерном и(б) логарифмическом весах РАМ и РАСП эквивалентны в смысле равенства емкостных сложностей с точностью до постоянного множителя. УПРАЖНЕНИЯ 1.10.
Найдите неветвящуюся программу, которая вычисляет определитель (ЗхЗ)-матрицы по ее 9 элементам в качестве входов. 1.11. Напишите последовательность битовых операций для вычисления произведения двух двуразрядных двоичных целых чисел. 1.12. Покажите, что множество функций, вычислимых любой и-строчной неветвящейся программой с двоичными входами и булевыми операциями, можно реализовать в виде комбинационной логической сети из и булевых элементов. 1.13. Покажите, что любую булеву функцию можно вычислить неветвящейся программой. *1.14. Пусть граф с л узлами представлен множеством двоичных вектоРов Уо где !ЕЯ компонента вектоРа У, Равна 1 тогДа и только тогда, когда узлы ! и ! соединены ребром.
Найдите алгоритм сложности Одв(п), строящий вектор р„у которого на 1-м месте стоит 1 тогда и только тогда, когда есть путь из узла 1 в узел !. Можно применить поразрядные битовые логические операции на двоичных векторах, арифметические операции (на переменных типа "целые"), команды, которые преобразуют отдельные компоненты данных векторов в 0 или 1, и команду, которая присваивает значение 1 целочисленной переменной а, если самая левая единица в векторе у находится в разряде!, и полагает а=О, если у состоит из одних нулей.
"1.15. Постройте машину Тьюринга, которая по двум данным двоичным целым числам на лентах 1 и 2 печатает их сумму на ленте 3. Можете считать, что левые концы лент отмечены специальным символом 4~. 1.16. Приведите последовательность конфигураций (мгновенных описаний) МТ с рис. 1.21, если входом является (а) 0010, (б) О!!10. *1.17. Постройте МТ, которая (а) печатает 0" на ленте 2, начиная работу с 0" на ленте 1, (б) допускает входы вида 0" 10", 1.18.
Укажите множество состояний и функцию переходов МТ, моделирующей РАМ-команду 1.0АП 3, как в доказательстве теоремы 1.3. 1.19. Постройте РАМ-программу, вычисляющую 2' по данному а за 0(п) шагов. Чему равны (а) равномерный и (б) логарифмический веса вашей программы? *1.20. Определим д(т, и) равенствами д(0, п)=п и д(т, л)= =2з' -' "' при лг»О. Напишите РАМ-программу, вычисляющую й(л, п) по и. Как соотносятся равномерный и логарифмический веса вашей программы? ГЛ. Ь МОДЕЛИ ВЫЧИСЛЕНИЙ 1.2[. Выполните процедуру ВЗАИМОЗАМВНА из равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
