Соотношение с алгоритмами в интуитивном смысле

Алгоритмы в интуитивном смысле — это не математиче­ские объекты. Судить о них можно лишь на основании практического опыта и интуиции. Никакие математические доказательства к ним неприменимы.

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

Каков бы ни был алгоритм в интуитивном смысле над формальным языком L, если его запись может быть призна­на конструкцией, то существует эквивалентный ему алго­ритм в широком формальном смысле, имеющий ту же запись.

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

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

В связи с широким формальным определением алгорит­ма приобретает интерес вопрос противоположного харак­тера. Является ли всякий алгоритм в широком смысле также алгоритмом в интуитивном смысле? Можно предпо­ложить, что не является, потому что алгоритмы в широком смысле могут быть настолько не «прозрачны», что у чело­века, не проследившего этапов их построения от начала до конца, интуиция будет молчать. § 9. Коллективы алгоритмов

До сих пор мы, применяя алгоритм, рассматривали его в совокупности с одним или несколькими операндами. При этом алгоритм, если рассуждать неформально, представал перед нами в роли правила для одного исполнителя, в со­ответствии с которым (правилом) осуществлялась перера­ботка одного или нескольких исходных данных. Можно го­ворить также, что один алгоритм перерабатывал один или несколько операндов. Но на практике нередко несколько человек выполняют общую работу. При этом возможны два случая: 1) имеется руководитель, координирующий дей­ствия исполнителей; 2) исполнители действуют согласованно и без общего руководителя. Первый случай можно свести ко второму, если руководителя посчитать некоторой раз­новидностью исполнителя. Описанное явление можно фор­мализовать, рассматривая несколько алгоритмов, которые перерабатывают общий для них операнд независимо друг от друга, но результативно. Связь между алгоритмами долж­на проявляться при выполнении тех шагов, в результате которых может нарушаться однозначность результата.

Если до сих пор, изучая алгоритмы, мы не фиксировали внимания на порождаемых ими процессах, то теперь без этого обойтись невозможно. Поэтому уточним понятие алго­ритмического процесса. При этом придется рассматривать операнд не в целом, а как состоящий из более мелких час­тей — элементов. Элементами операнда могут быть как отдельные буквы, так и более простые, чем операнд конст­рукции, заключенные в оболочки и не связанные непосред­ственно с частями операнда, внешними для этих оболочек. Если операнд перерабатывается первичным алгоритмом, то легко видеть, что процесс его переработки состоит из отдельных шагов, на каждом из которых выполняется неко­торое преобразование (чаще всего — локальное). Можно представить себе, что на каждом шаге изменяется один или несколько элементов операнда (обозначим их совокупность через y_i), причем «основанием» для такого изменения явля­ется имевшее место до начала данного шага состояние од­ного или нескольких элементов операнда (совокупность которых обозначим x_i), а сущность этого изменения заклю­чается в выполнении операции, указанной в соответствую­щем приказе первичного алгоритма (обозначим ее f_i). Опи­санием одного шага можно считать запись

h_i=(x_i, f_i, y_i).

Процессом, порождаемым первичным алгоритмом А при заданном операнде X, назовем последовательность шагов h₁, h₂, ..., h_n, где п — номер последнего шага, после кото-, рого операнд X окажется переработанным в соответствую­щий ему результат Y. При этом будем говорить, что на ни шаге происходят обращения кx_i y_i, причем x_i читается, a y_i пишется.

Заметим, что в ходе алгоритмического процесса возмож­но исчезновение или появление некоторых элементов опе­ранда.

Теперь предположим, что А не является первичным алгоритмом. Тогда рассмотрим его алгоритм выполнения W₀. Если W₀ не является первичным, то рассмотрим его ал­горитм выполнения W_-1 и т. д., пока не «опустимся» до алгоритма выполнения, являющегося первичным. Из ши­рокого формального определения алгоритма вытекает, что такой процесс закончится на некотором конечном номере k. Мы знаем, что применение А к X является не чем иным, как применением W₀, к конструкции , а это все равно, что применение W_-1 к и т. д., т. е. в ко­нечном счете это все равно, что применение W_-k к конструк­ции

. (*)

Процессом выполнения непервичного алгоритма А при­менительно к операнду X назовем процесс применения W_-k к операнду (*). Мы видим, что если А непервичный, то для выявления порождаемого им процесса необходимо не­сколько расширить операнд X, присоединяя к нему символь­ные конструкции W_o, W_-1, ..., W_-k+1 с помощью связей z₀, z₁, ..., z_k. Замечу, что вовсе необязательно «опускать­ся» до алгоритма выполнения, являющегося первичным. Достаточно «опуститься» до такого алгоритма выполнения, для которого тем или иным путем уже определено понятие алгоритмического процесса.

Теперь рассмотрим применение нескольких алгоритмов A₁, A₂, ..., A_n к общему для них операнду X. Те элементы операнда, к которым производятся обращения только од­ним из алгоритмов (или несколькими, но только по чтению), называются собственными для этого алгоритма (или каждо­го из этих алгоритмов), а шаги,на которых происходят такие обращения, называются регулярными. При этом подчеркнем, что обращения разных алгоритмов к одному и тому же эле­менту считаются происходящими всегда последовательно, хотя это следование в некоторых случаях может склады­ваться непредсказуемым образом, а «длительность» каждого обращения считается равной нулю (это является результа­том абстрагирования от времени). Если же один из алго­ритмов производит запись некоторого элемента, а другие к нему обращаются (неважно, по чтению или по записи), то указанный элемент называется несобственным, а шаги, на которых к нему происходят обращения, называются кри­тическими.

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

Будем считать, что в каждом частном процессе шаги за­нумерованы в порядке их следования (который и выражен этой нумерацией и называется естественным). Зафиксиро­вать порядок критических обращений можно следующим образом. Каждому критическому шагу, связанному с дан­ным несобственным элементом, будем ставить в соответствие два числа: i и n_i, первое из которых является специальным номером, а второе показывает количество критических ша­гов, получивших одинаковые специальные номера. Для четных i будем всегда считать, что n_i=1. Если первое об­ращение к несобственному элементу является записью, то критическому шагу, на котором оно производится, припи­сывают (специальный) номер 0. Если первым обращением является чтение без записи, то считают, что существует фиктивный нулевой шаг. Очередной нечетный номер припи­сывают каждому из шагов, на котором должно быть произ­ведено чтение критического элемента (без записи) до новой записи. Очередной четный номер приписывают критическо­му шагу, который производит сперва чтение, а потом запись в тот же несобственный элемент. Если после группы чтений данного несобственного элемента такого «комбинирован­ного» обращения нет, то процесс нумерации считают закон­ченным. Совокупность всех критических шагов, соответст­вующих некоторому несобственному элементу а, для кото­рых установлена описанным способом нумерация, называет­ся (критическим) а-фрагментом, а порядок, заданный спе­циальной нумерацией — специальным.

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

Совокупный процесс переработки алгоритмами А₁, А₂, …, А_п операнда X называется согласованным, если каждый шаг каждого из частных процессов выполняется тогда и только тогда, когда: 1) он не является запрещенным, 2) все шаги, непосредственно ему предшествующие, в силу естественного порядка в частном процессе или в силу спе­циальных порядков уже выполнены.

Совокупность алгоритмов А₁, А₂, …, А_п, при совмест­ном применении которых к каждому операнду X, являюще­муся предложением формального языка L₁, возникает сог­ласованный совокупный процесс, называется коллективом алгоритмов.

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

Разъясним понятие коллектива алгоритмов на примерах.

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

Совокупный процесс выполнения этого коллектива алго­ритмов не содержит критических шагов. Исходное слово «511112 коп» приведенный коллектив алгоритмов преобразовал бы в «535 руб».

2. Более интересен коллектив следующих алгоритмов:

Этот коллектив перерабатывает исходное данное, являю­щееся словом, первая буква которого К, а остальные — рус­ские строчные, в слово, образованное из русских строчных букв. Например «λ мама» он перерабатывает в «тата».

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

Два нижеприведенных алгоритма образуют коллектив алгоритмов.

Алгоритм 1. 1) Увеличить х на 1. Перейти к п. 2.

2) Величину х+у принять за новое значение у. Перейти к п. 3.

3) Сделать а равным 0. Перейти к п. 4.

4) Если а—\, то перейти к п. 5, иначе вернуться к п. 4.

5) Величину у—х сделать значением у. Конец.

А л г о р и т м 2. 1) Если а=0, то перейти к п. 2, иначе к п. 1.

2) Величину 2-у сделать значением г. Перейти к п. 3.

3) Сделать а равным 1. Конец.

Собственным элементом для первого алгоритма являет­ся столбец х, для второго алгоритма — столбец г, а несобст­венным элементом является столбец у. Вспомогательный столбец а фактически является тоже несобственным. При­казы 4-й первого алгоритма и 1-й второго алгоритма были бы недопустимы в одиночных алгоритмах, но очень полезны в алгоритмах коллектива. Описанный коллектив алгоритмов преобразует табл. 9 в табл. 10.

4. Если бы в последнем коллективе алгоритмов второй алгоритм заменить нижеприведенным, то полученная пара уже не являлась бы коллективом алгоритмов.

Алгоритм 3. 1) Если а=0, то перейти к п. 3, ина­че к п. 2.

2) Увеличить г на 1. Перейти к п. 1.

3) Величину z-y сделать значением г. Перейти к п. 4.

4) Сделать а равным 1. Конец.

Для новой пары алгоритмов не существовало бы фикси­рованного порядка шагов для второго частного процесса. Это привело бы к тому, что если бы 1-й алгоритм совершил 3 шага за время выполнения 2-м алгоритмам 2-х шагов (при условии, что выполнение началось одновременно), то был бы один результат (табл. 11), а если бы скорость работы 1-го алгоритма была в два раза меньше (3 шага на 4 шага 2-го алгоритма), то результат был бы другой (табл. 12).

Величина а, включенная в последних двух примерах в состав операнда называется сигнальным элементом, придан­ным несобственному элементу у. Условия а=0 и а=1на­зываются регулирующими предикатами.