Язык алгоритмизации процессов

Мы видим, что идея алгоритмизации процессов для чело­вечества не нова. Она уже ставилась в отдельных областях человеческой деятельности и решалась. Но при этом она не была осознана как проблема алгоритмизации. Этот важный шаг был совершен человечеством лишь после появления ЭВМ и довольно значительного развития идей программи­рования. Естественно, что и идея универсального языка, удобного для алгоритмизации пр< це.сов, возникла в тесной связи с развитием языков программирования.

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

Операторами называются описания функционально од­нородных этапов изучаемого процесса. Операторы делятся на действующие, логические и варьирующие. Действую­щие операторы определяют изменения, происходящие в объектах. Именно они передают существо описываемого процесса. Логические операторы представляют собой опи­сание условий, от которых зависит направление процесса. Наконец, варьирующие операторы — это операторы, пре­дусматривающие изменения вспомогательных величин, на­зываемых параметрами. Обычно параметры являются либо номерами изменяемых объектов, имеющих одинаковые имена, либо номерами операторов, почему-либо объеди­ненных в одну группу; так что изменение параметров означает либо переход от одних объектов к другим, либо выбор некоторого оператора из группы операторов. Кроме указанных трех типов операторов, существуют еще опера­торы перехода, указывающие порядок выполнения опера­торов первых трех типов; их называют знаками перехода. Действующие операторы обозначаются символами D₁ D₁₀, D₂₀ и т. д. Если действующий оператор зависит от па­раметров, например i, j, то он обозначается знаками , и т. п.

Варьирующие операторы обычно сами не зависят от параметров, но изменяют значения параметров; их обозна­чают символами V₅(i), V₁₀ (i, j), указывая в скобках наиме­нования параметров, которые они изменяют (варьируют).

Логические операторы обозначают буквой Р, снабжен­ной снизу номером, а сверху индексами, обозначающими параметры (если эти операторы зависят от параметров), так что для обозначения логических операторов применяют знаки Р₅, , и т. п.

Знаки перехода обозначают в виде полускобок, снаб­женных числовым индексом:

Кроме перечисленных, применяют знак, указывающий начало процесса (И₀), конец процесса (Я, Я₇, Я₁₀ и т. д.) и так называемый знак приема управления, имеющий вид правой нижней полускобки, снабженной числовым индек­сом. Он может соответствовать как верхнему, так и ниж­нему знаку перехода. Соответствие определяется равенст­вом числовых индексов. Выглядит знак приема управления так:

После логического оператора должны стоять два знака перехода — один верхний (случай «да»), другой — ниж­ний (случай «нет»), после нелогического — один знак пере­хода: нижний.

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

Если между двумя операторами стоит знак приема уп­равления, то его присутствие не отделяет операторы друг от друга. Строка

может служить описанием некоторого процесса. Оно может

быть таким:

1. Оператор V₁ (_i) задает начальное значение парамет­ра, например i=l.

2. Выполняется оператор D₁.

3. Выполняется оператор .

4. Оператор V₂(i) изменяет значение параметра. На­пример, делает его равным i=3.

5. Оператор P₁ проверяет некоторое условие. Допустим, ответ получился отрицательный. Тогда управление пере­дается знаком перехода оператору, стоящему после знака приема управления

6. Выполняется оператор .

7. Оператор V₂ (i) снова меняет значение параметра. Например, делает его i = 10.

8. Оператор P₁ проверяет соответствующее условие. Допустим, что теперь получен ответ «да». Должен выпол­няться верхний знак перехода. Его нет. Значит, он вообра­жаемый.

9. Выполняется оператор D₃.

10. Процесс окончен, так как далее следует опера­тор Я₁

Итак, в соответствии с нашим истолкованием строки операторов, был выполнен процесс

Само собой разумеется, что смысл операторов должен быть задан.

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

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

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

Язык логических схем фактически является целым се­мейством языков, так как применяемые в нем символы объектов и операций не имеют раз и навсегда заданного смысла. Придавая им конкретный смысл, мы получим од­ну из конкретных реализаций языка логических схем.

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

В начале процесса ряд объектов находится в некоторой начальном состоянии. Каждый действующий оператор пред ставляет собой последовательность формул вида

y:= f(x, y, z,...).

Такая формула означает, что результат выполнения опе­рации f над значениями (состояниями) объектов х, у, z,... нужно считать новым значением (состоянием) объекта у, указанного в левой части формулы.

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

Аналогично записываются варьирующие операторы, с той разницей, что в них фигурируют математические опера­ции, поскольку значениями параметров являются целые неотрицательные числа.

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

После того как операторы указанным способом описа­ны, делают одно из двух. Либо в логической схеме каждый оператор заменяют его описанием, либо в конце логической схемы в квадратных скобках выписывают так называемые расшифровки всех операторов. Каждая расшифровка со­стоит из знака, обозначающего оператор, и написанных вслед за этим знаком формул, представляющих его смысл[28].

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

В данном случае объектами, состояниями которых оп­ределяется процесс, являются внутреннее время (время, отсчет которого начинается с момента начала процесса) и человек, совершающий физическую зарядку. Состояни­ями человека будем считать различные его позы, а под опе­рациями будем понимать движения, приводящие к изме­нениям поз. Пусть f₁ означает движение обеими руками впереди корпуса снизу вверх, при котором угол, образу­емый руками и корпусом, изменяется на 90°; операция f ₂ означает движение обеими руками вниз и в разные стороны так, что обе руки и корпус остаются в одной плоскости, а угол между каждой рукой и корпусом изменяется на 90°. Каждая операция считается применимой лишь к такой позе, находясь в которой человек способен совершить соответст­вующее движение (например, если человек стоит, разведя руки в стороны на уровне плеч, то операция f₁ непримени­ма). Символом f ₃ обозначим операцию, заключающуюся в сжатии (из естественного положения) кистей обеих рук в кулаки, а символом f ₄ — обратную ей операцию, в ре­зультате которой кисти принимают естественное положение с полусогнутыми пальцами.

Обозначим время буквой t, человека в произвольной позе — буквой х, а того же человека, стоящего в стойке «смирно»,— буквой х₀. Нетрудно прочесть следующую за­пись и представить себе изображенный ею процесс:

Описываемый процесс состоит в том, что человек х в момент t = 0 принимает позу х₀ (стойку «смирно»), в момент t = 1 он сжимает руки в кулаки. После этого в момент t = 2 он поднимает их перед собой до уровня плеч, готом в момент t=3 еще раз поднимаем их перед собой (теперь обе руки протянуты вверх); далее, в момент t = 4 руки разводятся в обе стороны до уровня плеч; далее, в момент t — 5 они опускаются вниз. Затем, если t<30, процесс повторяется, начиная с подъема рук снизу вверх впереди себя на 90°. Если в момент выполнения логического опе­ратора окажется, что время больше или равно 30, то кисти рук расслабляются, и процесс считается оконченным. Если нужна большая точность, то операции могут быть заданы с помощью рисунков или серий рисунков.

Читатель, конечно, понял, что подобным образом мож­но описать и более сложные процессы. Например, можно описать известный танец маленьких лебедей из балета «Лебединое озеро». Это значит, что, построив достаточно совершенные роботы, мы могли бы их заставить исполнять даже балетные номера. Качество исполнения будет зави­сеть от точности задания операций и, конечно, от качества и внешнего вида роботов.

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

В описанном процессе физзарядки человек находится всегда в одном из пяти состояний, для получения которых задано 4 операции (не считая тождественной операции, использованной в операторе х:= лг₀). Следовательно, че­ловека, выполняющего описанное гимнастическое упраж­нение, можно было бы представить в виде переменной, ко­торая в начальный момент имеет состояние, изображаемое числом 0, а затем в течение некоторого времени пробегает значения 1,2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 1.