Глава 5. Коллективы алгоритмов

5.1. Несколько алгоритмов и один операнд

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

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

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

1. Один алгоритм и несколько операндов. Этот случай рассмотрен в § 4.5. Как мы помним, несколько операндов (от одного до n) объединены вспомогательной связью в совокупный операнд. Затем алгоритм и этот совокупный операнд (точнее, их записи) объединены с помощью новой вспомогательной связи в одну конструкцию. И эта конструкция подвергается переработке алгоритмом выполнения. Алгоритм выполнения порождает алгоритмический процесс, который представляет собой последовательность шагов. На каждом шаге либо происходит некоторое элементарное преобразование, либо выполняется логическая операция. Что при этом преобразуется или проверяется легко понять, если алгоритм принадлежит классу первичных. Преобразуется, по существу, операнд, а запись первичного алгоритма только просматривается (хотя и это является преобразованием, так как "просматривание" представляет собой связывание отдельных частей записи алгоритма различными выделяющими связями).

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

2. Несколько алгоритмов и несколько операндов при одном алгоритме выполнения. Этот случай ненамного сложнее предыдущего. Рассмотрим его вкратце. Предположим, что, как и в § 4.5, заданы два языка: L₁ - исходных данных (операндов) и алгоритмический язык L₂. С помощью связи m-го жанра и ранга, играющей вспомогательную роль, свяжем m предложений языка L₂ (т. е. записей алгоритмов) в совокупную запись. Как и в первом случае, построим совокупный операнд из n предложений языка L₁. Далее, с помощью вспомогательной связи 2-го ранга и жанра совокупную запись алгоритмов свяжем с совокупной записью операндов. Именно эту символьную конструкцию должен перерабатывать алгоритм выполнения W. Алгоритм выполнения определит процесс совместного выполнения сразу m алгоритмов над n операндами. Как и в первом случае, этот процесс будет последовательностью актов и будет полностью детерминированным^*.

^* (Примечание для программистов: операционная система мультипрограммного режима, обеспечивающая "одновременное" выполнение с помощью однопроцессорной ЭВМ сразу нескольких программ, является алгоритмом выполнения n алгоритмов, имеющих n операндов.)

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

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

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

Выполнение локальной операции можно расчленить на части:

• обращение к операнду для определения исходных данных операции;
• внесение в преобразуемую символьную конструкцию результата операции.

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

Теперь мы можем указать еще один случай безконфликтности алгоритмов, имеющих общий операнд. В этом случае операнд состоит из n+1 подконструкций, где n - число алгоритмов. Пронумеруем мысленно алгоритмы числами 1, 2, ..., n и подконструкций - числами 0, 1, ..., n. Предположим, что из подконструкций № 0 любой алгоритм может только читать, а в подконструкций № i может как писать, так и читать только алгоритм № i (где i = 1, или 2, ... , или n). Очевидно, при таких условиях хаотичность алгоритмического совокупного процесса не приведет к неоднозначности результата.

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