Все статьи

ГРАММАТИКА <<---  --->> СОЕДИНЕНИЯ АЛГОРИТМОВ

АЛГОРИТМЫ

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

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

Наряду с понятием нормального алгоритма А.А. Марков вводит понятие универсального алгоритма. Для универсального алгоритма исходными данными служат исходное слово и нормальный алгоритм. Универсальный алгоритм на основе этих данных формирует результирующее слово. Таким образом, универсальный алгоритм выступает в качестве алгоритма выполнения нормального алгоритма. В своей монографии А.А. Марков провозглашает принцип нормализации, согласно которому любой алгоритм может быть представлен в нормальной форме. В связи с введением понятия универсального алгоритма или, точнее, алгоритма выполнения  конкретных алгоритмов, возникает законный вопрос: а кто выполняет сам алгоритм выполнения? Другой алгоритм выполнения? А этот, последний, кто выполняет? Еще один алгоритм выполнения?  Так может возникнуть “дурная бесконечность” алгоритмов выполнения. Разумный ответ на эти вопросы может быть только один: всякий алгоритм выполняется, в конечном счете, либо человеком, либо автоматическим устройством, созданным человеком (например, ЭВМ).

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