Информатика и компьютерные науки (стр. 2 из 14)

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

Простейшие базовые функции:

Функция произвольного количества аргументов тождественно =0. Знак функции jn - где n - количество аргументов.
Сопутствующий алгоритм: если знак функции jn то значение функции 0.
Например: j1(3)=0, j3(4, 56, 78)=0;

Тождественная функция. Знак функции yn,i . 0<i<=n. n - количество аргументов, i - номер аргумента. Сопутствующий алгоритм: если знак функции yn,i то значение функции - значение i-го аргумента, считая слева направо.
Например: y3,2(3,22,54)=22;

Функция получения последователя. Функция одного независимого аргумента. Знак функции - l. Сопутствующий алгоритм: если знак функции l то значение функции - число, следующее за значением аргумента.
Например: l(5)=6 или 5'=6.

3 приема построения сложных РФ.

Оператор подстановки. F(f1, …, fn).
Вычисляются значения функций f1, …, fn и используются как аргументы при вычислении F.
t(y)= l(l(y))= l(y')=y''.

Оператор рекурсии R. f::= R[f1, f2, x(y)].

f - функция n аргументов, f1 - n-1 аргумента, f2 - n+1 аргумента, причем n-1 аргументов функций совпадают, а 2 следующих аргументов называются дополнительными. Один из них - х - называется главным доп. аргументом(ГДЭ). Он войдет в определяющую функцию. Другой y - вспомогательный доп. аргумент(ВДЭ), использующийся при построении новой функции.

Говорят, что оператор рекурсии строит новую функцию по 2 условиям:

f(0)=f1, f(i')=f2(i, f(i)).

Значением искомой функции при нулевом значении ГДЭ считать значение функции f1, а значением новой функции для каждого последующего значения ГДЭ считать значение функции f2 для предыдущего значения ГДЭ и для значения ВДЭ, совпадающего со значением искомой функции на предыдущем шаге.

Например:

PR(x) ::= R[j0,y2,1(x,y),x(y)]

PR(0) = j0 = 0

PR(1) = y2,1(0,PR(0))= 0

PR(2) = y2,1(1,PR(1)) = 1

Оператор минимизации или построение по первому нулю.

f ::=m[f1, (x)] f(x1, …, xn)=m(f1(x1, …, xn, y), (y))

с помощью функции f1 n+1 аргументов и дополнительного исчезающего аргумента.

Придавать последнему аргументу значения начиная с нуля, вычисляя при этом значение функции f1. Как только значение функции f1=0 значение дополнительного аргумента принимаем за значение искомой функции для тех главных аргументов, для которых вычислялось значение функции f1.

Например:

r(x)::=m(y2,1(x, y), (y)]

r(0)=0

r(i) = y2,1(i, y) - не определено для i<>0.

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

Например:

y=x+1 - совпадает с базовой.

w=x+y - подстановка в (z+1) вместо z функции y3,3 (x, y, z). Получим f*(x, y, z)

Затем воспользуемся следующим:

S(x, y) ::= f1[y1,1(x), f*(x, y, z); y(z)]

S(x, 0) =y1,1 (x) = x

s(x, 1) = f*(x, 0, S(x, 0)) = s(x, 0) + 1

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

. Формальное описание алгоритма через замену текстов

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

Одной из простейших концепций элементарных шагов переработки последовательностей знаков является замена определенных подслов (образцов) в обрабатываемом слове другими словами. Эта концепция ведет к алгоритмам в форме систем текстовых замен на последовательностях знаков.

Пусть V - запас знаков. Пара (v, w) e V* х V* называется заменой над V. Замена часто записывается в виде

v ® w

Конечное множество R замен будем в дальнейшем называть системой текстовых замен (СТЗ) над V. Элементы этой системы будем называть также правилами текстовых замен (ПТЗ). СТЗ служат для представления алгоритмов. Отдельные шаги этих алгоритмов состоят, таким образом, в применении правил замен.

Замена

s ® t

называется применением правила v ® w, если имеются слова a, v, w, z Î V* такие, что справедливо

s = а ° v ° z, t = а ° w ° z.

Слово s Î V* называется терминальным (или терминалом} в R, если не существует слова t Î V* такого, что справедливо следующее: замена

s®t

является применением какого-либо правила из R. Таким образом, к терминальному слову s нельзя больше применить никакого правила замены.

Через повторное применение ПТЗ, исходя из начально заданного слова t0, возникают вычисления. Если t0, t1, ..., tn принадлежат V* и

ti-->ti+1

есть применение правила г из R для всех i,0<=i<=n, то последовательность (tj) 1<=i<=n называют (конечным) вычислением (последовательностью вычислении) над R для t0. Часто вычисление записывается следующим образом:

t0 ® t1 ®…® tn

Слово t0 называется также входом для вычисления. Если tn есть терминал, то вычисление называется завершающимся (конечным) с результатом tn. Слово tn называется также выходом для R при входе t0. Бесконечное вычисление (последовательность вычислений) (ti)iÎN из слов ti ÎV*, для которых ti-->ti+1 есть применение правил замен из R для всех i Î N, называется незавершающимся (бесконечным) вычислением.

Пример (вычисления по СТЗ).

(1) Для системы текстовых замен Q над множеством символов {L, О}, которая состоит из следующих правил:

LL ® е, О ® е, через последовательность

LOLL ® LO ® L

задается завершающееся вычисление для входного слова <LOLL> с результатом <L>.

(2) Для СТЗ над {L, О}, состоящей из правил О ® OO, О® L,

для входа <O> последовательность вычислений О ® OO ® OL ® LL

является завершающимся вычислением с выходом <LL>, а последовательность

о ->. оо -> ооо ->. оооо ->...

является незавершающимся вычислением.

Система текстовых замен R в силу следующего предписания определяет алгоритм текстовых замен (АТЗ), который использует слова над V в качестве входа и выхода. Для входного слова t Î V* алгоритм работает следующим образом:

"Если одно из правил множества R применимо к слову t (т. e. существует слово s Î V*, для которого имеет место: l -» s есть применение правила из R), то примени правило к t и затем примени снова этот же алгоритм к слову s; в противном случае прекрати выполнение алгоритма".

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

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

Примеры (алгоритмы текстовых замен).

(1) Сложение двух натуральных чисел, представленных в виде количества штрихов

Натуральное число представляется в виде количества штрихов с ограничительными скобками, т. e. число nÎN представляется словом <| |...|>, причем внутрь скобок входит n штрихов. В этом случае алгоритм состоит из одного единственного правила замены (е обозначает пустое слово):

> + < ® е

Для входа <|...|> + <|...|> алгоритм дает сумму штрихов.

(2) Умножение двух натуральных чисел (в таком же представлении)

Применяются вспомогательные знаки d, e, m. Алгоритм состоит из следующих правил замен:

|>*< ® >*<d

d| ®. |md

dm ® md

d> ® >

<>*< ® <e

e| ® e

em ® |e

e> ® >

Для входного слова <|...|> * <|...|> с п1 штрихами в первом операнде и п2 штрихами во втором операнде алгоритм дает выходное слово <|...1> с п1 * п2 штрихами.

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

Для входа <||> * <|||> возникает показанный на рисунке граф возможных вычислении. Все вычисления заканчиваются получением слова <|||||| >. Этот алгоритм подстановки недетерминистический, но детерминированный, т. е. дает, несмотря на различные вычисления, всегда один и тот же результат.

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