03. Концепция алгоритма

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

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

(1)

И будем говорить: Алгоритм типа .

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

Всюду в дальнейшем мы будем рассматривать частный случай конструктивного объекта, а именно, Слово в конечном алфавите [9]. Здесь базовые элементы – буквы алфавита, а единственное правило сборки – известная операция соединения слов. Это частный случай, но важнейший. Можно выдвинуть гипотезу, согласно которой любой конструктивный объект может быть представлен (более или менее сложно) в виде слова в конечном алфавите.

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

Не всякий преобразователь слов, однако, будет алгоритмом. Алгоритм характеризуется следующими тремя признаками:

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

- Признак массовости: алгоритм есть такое предписание, которое единообразно применяется в широком классе входных данных независимо от их индивидуальных особенностей (например, алгоритм вычисления корней квадратного уравнения един для всех уравнений и никак – сам по себе – не зависит от коэффициентов конкретного уравнения);

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

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

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

Имеется входной алфавит , и множество входных данных есть некоторое множество слов в этом алфавите, то есть язык , где есть множество Всех слов в указанном алфавите. Задан выходной алфавит , и множество результатов есть некоторый язык в выходном алфавите, то есть . Тогда алгоритм типа , представленный формулой (1), может быть описан в виде

(2)

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

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

(3)

(без точки под стрелкой).

Теперь введем понятие вербальной (словарной) функции и вычислимой (в интуитивном смысле слова) вербальной функции.

Вербальная (словарная) функция типа Есть любое, в общем случае частичное, отображение вида:

(4)

(точка под стрелкой указывает на частичность).

Здесь разумно привести некоторые примеры.

Примеры. 1) Функция удвоения: для любого слова значение функции . Эта функция определена для всех слов во входном алфавите, который совпадает с выходным.

2) Характеристическая функция определенного множества слов в заданном входном алфавите :

.

Здесь мы полагаем, что выходной алфавит .

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

Для вербальной функции обозначим область ее определения.

Следующее понятие является в этом разделе основным.

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

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

Перейдем теперь к рассмотрению точной модели алгоритма в виде нормального алгорифма Маркова. Заметим сразу, что школе А. А. Маркова принят именно термин «алгорифм», и сочетание «нормальный алгоритм» считается недопустимым.

< Предыдущая		Следующая >