Алгоритмические модели и их представление

В двадцатых годах нашего века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение этой проблемы развивалось по двум направлениям.

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

Второе направление [i41] развивало точное описание процессов, которые может совершать достаточно просто устроенная «машина». В 1934 г. Курт Гёдель (1906—1978) описал класс числовых функций, вычислимых в некоторой формальной системе (исчислении). В 1936 г. Алонзо Чёрч (р.[i42] 1903) предложил другую формальную систему, названную им λ-исчислением. В 1936 г. Клини ввел строгое понятие класса рекурсивных (от лат. recurcio —возвращение) функций, которые вычислимы при помощи алгоритмов. Им было доказано совпадение классов вычислимых функций, построенных Геделем и Черчем с классом рекурсивных функций.

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

В 1936 г. английский математик Алан Матисон Тьюринг (1912—1954) предложил точное описание алгоритма в виде некоторой машины — «машины Тьюринга», которая использует конечное множество символов, имеет процессор, выполняющий предписания определенного вида, устройство для хранения входных, промежуточных и выходных результатов. В 1937 г. Тьюринг доказал, что его машина может вычислять совокупность функций, эквивалентную λ-исчислению Черча.

В 1936 г. американский математик Эмиль Леон Пост (1897—1954) независимо от Тьюринга предложил свою конструкцию машины для уточнения понятия алгоритма. Машины Поста и Тьюринга оказались эквивалентными по своим вычислительным возможностям рекурсивным функциям.

В 1951 г. советский математик Андрей Андреевич Марков-сын (1903—1979) предложил принцип нормализации алгоритмов для приведения их к стандартной форме, которая получила название нормального алгорифма Маркова (НАМ).

[i44]

Алгоритмические модели и их представление

[i45] Модель (фр. modèle, от лат. modulus — «мера, аналог, образец») [i46] — это упрощенное представление реального устройства и/или протекающих в нем процессов, явлений.

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

Моделировани[i47] е является обязательной частью исследований и разработок, неотъемлемой частью нашей жизни, поскольку сложность любого материального объекта и окружающего его мира бесконечна вследствие неисчерпаемости материи и форм её взаимодействия внутри себя и с внешней средой.

Алгоритмическая модель или модель алгоритмов - это упрощенное представление алгоритма или алгоритмического процесса на основе чего-либо (математической конструкции или гипотетического/реального механизма[i48])

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

Следующим признаком, по которому можно различать ЭММ, является связь с фактором времени:

· динамические — модели, в которых входные факторы, а следовательно, и результаты моделирования явно зависят от времени;

· статические — модели, в которых зависимость от времени отсутствует совсем либо проявляется слабо или неявно.

[i49] Понятие "алгоритм" было принято для обозначения совокупности правил вычислительных процессов, в которых искомые результаты практических задач находят последовательно из исходных данных по определенным правилам и инструкциям.

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

Основными объектами алгоритма стали данные[i50]. Для уточнения этого понятия фиксируют конечный алфавит символов (цифр, букв и т.п.) и правил построения алгоритмических объектов. Такими объектами вычислительных алгоритмов являются списки и стеки, множества и отображения. Процесс преобразования алгоритмических объектов от исходных данных до искомого результата выполняется дискретно или, как говорят, "по шагам". Преобразование за один шаг носит локальный характер, т.е. этому преобразованию подвергается не весь объект, а лишь его часть: элемент стека или компонента кортежа, столбец или строка матрицы и т.п. Последовательность шагов детерминирована, т.е. после каждого шага указывается точно, что и как следует выполнять на следующем шаге. Процесс преобразования алгоритмического объекта, включающий в себя заданную последовательность шагов, называют алгоритмическим процессом[i51]. Механизм реализации алгоритмического процесса удобнее проследить на алгоритмических моделях, использующих конечные наборы простейших объектов и конечные наборы элементарных действий. Выделяют три основных класса или типа алгоритмических моделей:

1. Вычислительные алгоритмы[i52]. Предполагается, что любые данные можно закодировать числами, а всякое их преобразование становится в этом случае арифметическим вычислением. Алгоритмом в таких моделях является вычисление значения некоторой числовой функции, а его элементарными шагами – арифметические операции. Последовательность шагов определяется способами суперпозиции и рекурсии.

2. Символьные алгоритмы[i53]. Задается алфавит, конечное множество допустимых подстановок и некоторое правило, определяющее порядок применения подстановок (например, нормальный алгоритм Маркова, формальные грамматики).

3. Алгоритмы для исполнителей. [i54] Алгоритм задается последовательностью правил (инструкций), которые может выполнить машина, удовлетворяющая требованиям простоты и универсальности (абстрактные машины Тьюринга и Поста, конечные или магазинные автоматы).

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

1.4 Вычислительные алгоритмы[i55]

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

Напомним, что общее определение рекурсии как процесс повторения элеменубратьто общее определение рекурсии как виде блок-схемы.

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

Рекурсия[i56] здесь есть способ вычисления значения числовой функции по известным значениям независимых переменных аргумента и известному значению функции в некоторой исходной точке. Поэтому любую вычислимую функцию, заданную на множестве натуральных чисел и принимающую значения на том же множестве принято называть рекурсивной функцией. [i57]

Если значения функции найдены не для всех значений области определения, то её называют частично рекурсивной функцией [i58] и, наоборот, если они найдены для всех значений области определения, то её называют общерекурсивной функцией. [i59]

Для формального построения функций вычислимых алгоритмом необходимо иметь:

1) набор элементарных функций, которые изначально считаются вычислимыми;

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

Для формирования механизма вычисления рекурсивных функций даны наборы простейших базовых функций[i60]: константы, тождества и следования и наборы элементарных операций[i61]: суперпозиции, рекурсии, минимизации и итерации.

Рекурсивная функция — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений f(n-1),f(n-2),…, подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n=0,1). Этот вид функций определен на множестве натуральных чисел — N (точнее N и 0).

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

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

Функция константа. Если f={(x₁, x₂,..., x_n, у)| x_i N, y N}=C_n или y = f(x₁, x₂,…x_n)=C_n, то любым значениям независимых переменных аргумента функции ставится в соответствие значение функции, равное постоянной величине (константе) - С_n, где n –число независимых переменных аргумента. Чаще всего C_n=0. Поэтому её называют также нуль-функцией. Например, если f={(x₁, x₂, x₃, у)}=C₃, то для x1 = 5, x₂ = 4, x₃ = 7 и C₃ = 0 имеем у=f(5, 4, 7)=0 или, если С_n=1 при тех же значениях независимых переменных, то y=f(5, 4, 7)=1.

Функция следования. Если f={(x, у)| x_i N, y N}=λ(x), то любому значению независимой переменной аргумента ставится в соответствие значение функции, равное числу, непосредственно следующему за числом, являющимся значением независимой переменной. Например, если для f={(x, у)}=λ(x) дано x = 5, то у = (5+1) = 6, если для f={(x, у)}=λ(x) дано x = 7, то у = (7+1) = 8.

Функция тождества. Если f={(x₁, x₂,..., x_n, у)| x_i N, y N}= , то любым значениям независимых переменных аргумента функции ставится в соответствие ее значение, равное значению m-го независимого переменного аргумента, где 1≤m≤n – место независимого переменного аргумента в их упорядоченном списке. Поэтому её называют также функцией выбора аргумента. Например, если f={(x₁, x₂, x₃, у)}=I₃², то для x1 = 5, x2 = 4, x3 = 7 [i62] имеем у = 4, если f={(x₁, x₂, x₃, у)}=I₃³, то для x₁ = 5, x₂ = 4, x₃ = 7 имеем у = 7.

Операции, с помощью которых из простейших базовых функций могут быть получены различные рекурсивные функции, называют элементарными. [i63]

В данном случае это операторы[i63] подстановки и примитивной рекурсии. Они определяются следующим образом:

Оператор суперпозиции (иногда — оператор подстановки). Пусть — функция от m[i64] переменных, а — упорядоченный набор функций от переменных каждая. Тогда результатом суперпозиции функций в функцию называется функция от переменных, сопоставляющая любому упорядоченному набору натуральных чисел число

.

Оператор примитивной рекурсии. Пусть — функция от n переменных, а — функция от переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций и называется функция от переменной вида

; .

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

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

Таким образом, из элементарных функций С_n, I_n^m и λ(x +1) с помощью операторов суперпозиции и примитивной рекурсии были получены основные функции арифметики, алгебры и анализа. Тем самым было показано, что эти функции имеют примитивно рекурсивное описание, которое однозначно определяет процедуру их вычисления.

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

Частично рекурсивная функция - определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента.

Оператор минимизации аргумента или поиск наименьшего корня. Пусть — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции называется функция от переменной, задаваемая следующим определением:

, при условии ,

то есть функция возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.

Операция минимизации решает элементарную поисковую задачу[i66]: 1) есть функция последовательного порождения значений для y; 2) есть предикат P, истинность которого проверяется. На каждый акт порождения производится проверка предиката. Процесс заканчивается, когда P истина.

При помощи частично-рекурсивных функций можно описать все арифметические операции и организовать вычисление.

Тезис А. Чёрча: Любая интуитивно вычислимая функция является частично-рекурсивной.

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

Эти два тезиса являются эквивалентными.

Функции, которые могут быть получены из простейших , λ(x +1), применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.[i67]

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

является[i68] рекурсивной. Действительно, , а ранее было установлено, что функция примитивно рекурсивна.

Операция итерации. Многократное повторение данного процесса, пока не будет выполнено некоторое условие, называют итерацией[i69]. При этом на каждом шаге итерации данный процесс выполняется полностью. Условием итерации, как правило, является число повторений рекурсивной функции.

Итак, функция называется примитивно рекурсивной[i70], если она получена из базовых функций с помощью конечного числа операторов суперпозиции и/или примитивной рекурсии. Она же называется рекурсивной[i71], если получена с помощью примитивно рекурсивных функций и конечного числа операторов суперпозиции, примитивной рекурсии и/или минимизации. Иначе говорят так: функции, для которых существуют алгоритмы вычисления, называют рекурсивными функциями[i72]. Рекурсивная функция называется частично рекурсивной[i73], если она определена не на всем множестве целых положительных чисел и общерекурсивной[i74], если она определена на всем множестве целых положительных чисел.

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

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

Второй тип модели алгоритма основывается на символьных алгоритмах. В частности, сюда также можно отнести формальные грамматики. Однако сначала рассмотрим стандартного представителя данного типа алгоритмической модели – нормальный алгоритм Маркова (НАМ). [i105] Он связывает понятие алгоритма с элементарными преобразованиями слов произвольного алфавита, замещая части или всего слова другим словом. Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

Одним из уточнений понятия алгоритма является НАМ, введенный советским математиком А. А. Марковым. НАМ работает над конструктивными объектами [i106] — словами (цепочками символов), построенными из букв конечного алфавита. Принцип нормализации[i107], предложенный А. А. Марковым, гласит:

а) объекты любой природы могут быть представлены (закодированы) словами в подходящем алфавите;

б) сколь угодно сложный процесс преобразования слов может быть представлен в виде НАМ.

Определение всякого нормального алгоритма состоит из двух частей[i108]: определения алфавита алгоритма V_t (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма [i109] называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки [i110] называются слова вида , где и — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки[i111] называются слова вида , где и — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма V_t (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Для организации последовательного и упорядоченного просмотра формул или правил они должны быть индексированы i {1, 2, 3,...}.

Если слово Р_i есть цепочка вида (γ1[i112] αI[i113] γ2[i114]) в алфавите Vт[i115], где γ1[i116] и γ2[i117] – слова в этом же алфавите и среди множества правил первым в упорядоченном списке есть правило α_I→β_I[i118], то нужно выполнить подстановку (γ₁α_iγ₂) → (γ₁β_i γ₂).

Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в «начало» алгоритма и вновь проверяется на подстановку правил в соответствии с протоколом.

Среди множества правил выделяют заключительное αi[i119] → • β i[i120], результатом подстановки которого формируется слово Q и дается указание об окончании работы алгоритма.

Процесс может оборваться на некотором слове Р_i, для которого нет соответствующего правил. Тогда это слово направляется в «тупик».

Для того чтобы построить модель алгоритма, необходимо выделить упорядоченную последовательность левых частей правил подстановки, так называемых распознавателей вхождения слов α_i в слово P_i, и множество соответствующих операторов подстановки слова β_I[i121] в слово P_i+1.

На схеме алгоритма (смотри Рисунок 1.2) эти блоки обозначены так:

• распознаватели вхождения - PB_i;

• операторы подстановки - ОП_i.

Распознаватели вхождения соединяются последовательно в соответствии с заданной последовательностью правил. Второй выход распознавателя вхождения при обнаружении α_i в слове Р_i передает информацию о слове P_i=γ₁α_iγ₂ в ОП_i, где выполняется соответствующая замена слова α_i на слово β_i, т. е. γ₁α_iγ₂[i122] ⇒ γ₁β_iγ₂=P_i+1.

Оператор подстановки направляет слово P_i+1 в «начало» алгоритма, если применена простая подстановка, и в «конец» алгоритма, если применена заключительная подстановка.

Рисунок 1.2 – Схема нормального алгоритма Маркова

Примером схемы нормального алгоритма в пятибуквенном алфавите может служить схема

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

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

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгоритму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть «принципом нормализации».

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

На основе НАМ развивается одно из самых мощных и современных направлений в программировании — продукционное программирование[i123].

Формальная [i124] грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики[i125] — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет. В рассматриваемый алгоритмический тип отнесем порождающие грамматики. Распознающие грамматики будут являться представителями следующего типа алгоритмов, к которому мы и перейдем.