Формальное определение алгоритма

Первичные алгоритмы. Предположим, что задан некоторый формальный язык L1, предложения которого являются исходными данными, для преобразований, определяемых ниже. L2 будем называть входным языком операндов. Предположим, что нам задан конечный набор операций, из которых некоторые могут быть применены к некоторым предложениям (символьным конструкциям) языка L1. Операции будем делить на действия и условия. Выполнение действия заключается в том, что конструкция-операнд заменяется конструкцией, получаемой из этого операнда путем выполнения операции; то, что получится, в дальнейшем считается операндом. Если операция к исходному операнду не применима, то никакого результата не получается и никакая информация о его отсутствии не вырабатывается. Выполнение условия заключается в проверке, справедливо ли оно для операнда, или нет. В первом случае результатом проверки является логическое значение истина, во втором — ложь. Операнд остается неизменным. Условия являются предикатами.

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

::= i

::=

::=

::= i

Для того чтобы L2 был полностью определен, необходимо задать с помощью метаформул значения метасимволов:

Мы этого не будем делать, определяя тем самым не один язык, а класс языков. В качестве L2 может быть принят любой из конкретных языков этого класса. Заметим только, что разделители должны быть выбраны так, чтобы они однозначно разделяли приказы на соответствующие части, а разделитель III должен быть отличим от разделителя VI, а также от любой отсылки и метки.

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

П р а в и л о выполнения первичного алгоритма.

1) Просматривая запись первичного алгоритма с начала, найти первый приказ; перейти к п.2.

2) Если рассматриваемый приказ является безусловным, перейти к п.3, иначе к п.5.

3) Применить операцию, соответствующую знаку действия данного приказа, к операнду; найти отсылку в данном приказе; перейти к п.4.

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

5) Если операнд удовлетворяет условию, соответствующему знаку условия данного приказа, то перейти к п.6, иначе — к п.7.

6) Найти первую отсылку данного приказа; перейти к п.4.

7) Найти вторую отсылку данного приказа; перейти к п.4.

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

Запись первичного алгоритма, рассматриваемая вместе с правилом его выполнения, называется первичным алгоритмом.

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

В первом случае говорят, что первичный алгоритм применим к данному операнду, а во втором и третьем случаях — что неприменим.

Следует обратить внимание на то, что алгоритмический процесс представляет собой процесс совместного преобразования совокупности записей алгоритма и операнда. Частной особенностью этого преобразования является неизменность символьной конструкции, являющейся записью алгоритма.

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

Пусть язык операндов L2 имеет в качестве предложений только слова в алфавите А. Будем считать, что заданием этого алфавита определен грамматический класс . Будем считать, что, кроме того, для задания L2 требуется единственная формула Бекуса ::= i

Алгоритмический язык L1 конкретизируем следующим образом:

::= i

::= 0i1i2i3i4i5i6i7i8i9

::= —

::= :

::= :

::= ;

::= :

::= :

::= /

::= h iDi*i®iii¯i!

::= Niнiк=

Смысл знаков действий и знаков условий разъясняет табл.3.2.

Приказы алгоритмического языка могут иметь вид

::;

или ::/;

Таблица 3.2.

Знаки натуральных операций

Название операции Знак Название операции Знак
a — генерация ha замена буквы на ? !?
аннигиляция ? отключение x
нахождение начала слова * линеаризация l
продвижение вперед делинеаризация d
продвижение назад условие непустоты N
удлинение вперед ^ условие начала н
отбрасывание конца v условие конца к

Для построения грамматик языков L1 и L2 достаточно знания операции конкатенации. Таким образом, построенный нами класс первичных (натуральных) алгоритмов, использующих только натуральные операции, линеаризацию и делинеаризацию, определен математически вполне строго.

Широкое формальное определение алгоритма. Мы знаем уже, что класс первичных алгоритмов задан, если заданы два языка: L1 и L2, причем предложения первого из них объявлены записями алгоритмов, а предложения второго — записями операндов и, если задано правило выполнения первичных алгоритмов, применимое к парам: запись алгоритма, запись операнда.

Первый пункт общего определения алгоритма гласит:

1) Первичные алгоритмы — это алгоритмы.

Но общее понятие алгоритма существенно шире. Его второй пункт гласит:

2) Если заданы два языка L1 и L2, причем предложения первого объявлены записями алгоритмов, а предложения второго — записями операндов, и если задан некоторый алгоритм W, операндами которого являются конструкции, получаемые связыванием каждого предложения из L1 с n предложениями языка L2 при помощи вполне определенной связи ранга n+1, то задано семейство n-местных алгоритмов.

Наконец, третий пункт общего определения гласит:

3) n-местные алгоритмы — тоже алгоритмы.

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

Одноместным называется n-местный алгоритм, для которого n=1. Первичные алгоритмы тоже будем называть одноместными.

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

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

Т е о р е м а. Для всякого семейства первичных алгоритмов (определяемого двумя языками L1 и L2 и правилом выполнения) существует алгоритм в широком формальном смысле, который эквивалентен правилу их выполнения и имеет запись, графически тождественную с записью этого правила.

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

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

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

Пусть L2={ } — алгоритмический язык, L1={ } — язык операндов, z — связь (n+1)-ого ранга и W — алгоритм выполнения. Обозначим через конструкцию, получаемую путем связывания языка L2 и n предложений языка L1. Тогда равенство означает, что t является алгоритмом и что . При этом — запись искомого результата.

Для каждого семейства алгоритмов, определяемого некоторым алгоритмом выполнения W, множество L3={r} записей всех возможных искомых результатов является формальным языком. Таким образом, каждому семейству алгоритмов отвечает еще один формальный язык: язык искомых результатов. В частном случае он может быть подмножеством языка операндов.

Рассмотрим два семейства алгоритмов, у которых эквивалентны алгоритмы выполнения. Ясно, что эти семейства имеют одни и те же языки операндов, искомых результатов и алгоритмический. Возьмем два алгоритма, принадлежащих разным семействам, но имеющих одну и ту же запись. Такие алгоритмы эквивалентны, но при выполнении порождают неодинаковые процессы.

О п р е д е л е н и е. Два алгоритма, которые имеют одинаковые записи и эквивалентны, являются одним и тем же алгоритмом (или экземплярами одного и того же алгоритма).

Теперь нетрудно уточнить приведенное выше общее определение алгоритма (вернее, дополнить его).

Алгоритм — это совокупность записи алгоритма и отображения, индуцируемого его алгоритмом выполнения.

Формальное исполнение алгоритма


Похожие статьи.

Понравилась статья? Поделиться с друзьями: