Russia, Saint-Peterburg, SPIIRAS,

e-mail: marley@mail.iias.spb.su

Abstract: This paper is devoted to the problem of links the algoritmics nets and reccurent equatations.

Россия, Санкт-Петербург, СПИИРАН e-mail: marley@mail.iias.spb.su

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

Статья основана на анализе опыта практической работы с различными категориями пользователей по разработке и эксплуатации математических моделей в различных предметных областях. Пользователей, в своей основной массе, не имеющих хорошей математической подготовки и/или недостаточно компьютерно грамотных. Были выявлены некоторые общие для большинства пользователей закономерности в мышлении и восприятии проблем, а именно:

1. Дискретность описания и восприятия анализируемого процесса, стремление рассматривать процесс, с шагом равным привычному дискрету наблюдения и/или съема информации.
2. Стремление представить анализируемый процесс как некоторый связный сценарий, с описанием пред и пост условий выполнения каждого этапа.
3. Стремление свести описание к некоторой регулярной циклически повторяющейся процедуре.
4. Стремлением рассматривать этапы сценария в основном во временной последовательности.
5. Стихийный параллелизм описания сценария, заключающийся в частом использовании связок типа "...а в это время...".
6. Стремлением уменьшить число используемых единиц измерения и число анализируемых показателей и нежелание использовать непривычные единицы измерения и показатели.
7. В большинстве случаев довольно четкое представление о допустимых и оптимальных границах значений анализируемых показателей.
8. Недоверие к результатам, полученным методами, которые они не могут наложить на свой сценарий процесса.
9. Частое стихийное сведение анализируемого процесса к описанию взаимодействия некоторых "хранилищ", "емкостей" (например, какого-либо ресурса, результирующего продукта и т.п.).

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

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

Известно два основных подхода в моделировании: функциональный и алгоритмический [1-4]. При функциональном подходе главное, чтобы реакция модели на подобное воздействие была подобна реакции объекта с заданной степенью точности. Соответствие структуры модели и объекта не обязательно. При алгоритмическом подходе, модель — это некоторое формальное представление сценария моделируемого процесса, которое имеется у предметного специалиста и ее структура подобна структуре причинно-следственных связей между явлениями, описанными в сценарии. Основным средством достижения адекватности при функциональном подходе является подбор модели и ее идентификация путем нахождения требуемых параметров. Основным средством достижения адекватности для алгоритмической модели является коррекция ее структуры на основе уточнения исходного сценария.

Конечно, в чистом виде подходы не существуют, можно говорить только о преобладании одного из них.

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

Алгоритмический подход и алгоритмическое моделирование интенсивно развивались, особенно на начальном этапе его становления, в Санкт-Петербургском институте информатики и автоматизации РАН [4-6]. В рамках данного направления был разработан язык представления структуры алгоритмических моделей на основе "алгоритмических сетей" [5-6].

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

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

Структура АС удовлетворяет следующим ограничениям:

• не существует контура, в котором хотя бы одна вершина не содержала оператор задержки;
• переменная может быть вычислена только в одной вершине;
• в одной АС все операторы задержки определяют рекуррентные соотношения относительно одной и той же величины и с одинаковым шагом ее изменения, и срабатывают одновременно после вычисления всех остальных вершин. Доказано, что АС можно построить расчетную программу тогда и только тогда, когда заданы значения всех переменных соответствующим входным дугам АС.

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

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

В одной модели могут использоваться выражения от переменных различного типа, которые обладают различными свойствами (например, числовые и символьные) и желательно определить некоторые их общие свойства, не зависящие от типов используемых переменных. Так как АС это графически представляете некоторую вычислительную схемы, то преобразования АС это будет графическое представление преобразований над математическими выражениями. Подграф АС в этом случае становится схемой вычисляющей некоторое подмножество внутренних (расчетных) переменных АС и, чтобы он сохранял это качество, необходимо чтобы вершины подграфа АС сохраняли все связанные с ними переменные. Это отличается от принятого в теории графов определения подграфа, и привело к разработке собственной системы преобразований АС [6] как графических конструкций.

Данные преобразования не зависят от типа используемых переменных и позволили рассмотреть распределенные АС и АС со ссылками в вершинах на другие модели [6]. Можно говорить об эквивалентности класса таких АС классу структурных (по Дийкстре) алгоритмов (с учетом возможности выделения подалгоритмов).

ЛИТЕРАТУРА.

1. Бирюков Б.В. Кибернетика и методология науки. М.: Наука, 1974, 412с.
2. Поспелов Г.С., Ириков В.А., Курилов А.Е. Процедуры и алгоритмы формирования комплексных программ. М.: Наука, 1985, 423с.
3. Управление, информация, интеллект. (Под ред. Берга А.И.) М.: Мысль, 1976, 383с.
4. Пономарев В.М. Алгоритмические модели в задачах исследования систем. // "Алгоритмы и системы автоматизации исследований и проектирования." М.: Наука, 1980, С.4-8.
5. Иванищев В.В. Алгоритмический базис для описания механизмов экономики. // Алгоритмические модели в автоматизации исследований и проектирования. М.: Наука, 1980. С.37-42.
6. Иванищев В.В., Марлей В.Е. Основы теории алгоритмических сетей. СПб: СП6ГТУ, 2000,180 с.