Реферат Курсовая Конспект
Рекурсивные схемы - раздел Программирование, Математические основы программирования. Теория схем программ. Семантическая теория программ 1.5.1. Рекурсивное Программирование Среди Упомянутых Выше Методов Фо...
|
1.5.1. Рекурсивное программирование
Среди упомянутых выше методов формализации понятия вычислимой функции метод Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего используются абстрактные «машины», описанные в точных математических терминах. Другой подход (метод Черча — Клини) основан на понятии рекурсивной функции, рекурсивная функция задается с помощью рекурсивных определений. Рекурсивное определение позволяет связать искомое значение функции для заданных аргументов с известными значениями той же функции при некоторых других аргументах. Эта связь устанавливается с помощью универсального механизма рекурсии, дающего механическую процедуру поиска значений функции. Двум подходам к определению вычислимых функций соответствуют два метода программирования этих функций — операторное и рекурсивное программирование. При операторном методе программа представляет собой явно выписанную последовательность, описаний действий гипотетической вычислительной машины (последовательность операторов, команд и т. п.).
Язык Фортран — типичный представитель операторных языков. С другой стороны, рекурсивная программа — это совокупность рекурсивных определений, задающих рекурсивную функцию, для которой аргументами служат начальные данные программы, а значением — результат выполнения программы. Известный язык рекурсивного программирования — язык Лисп — предназначен для обработки символьной информации. В других зыках комбинируют оба метода программирования. Так, Паскаль — операторный язык с возможностью рекурсивного программирования, предоставляемой механизмом рекурсивных процедур и функций.
Примером рекурсивно определяемой функции является факториальная функция FACT: Nat → Nat:
FACT(х) = 1,если х = 0, FACT(х) = х ´ FACT(х — 1), если х > 0.
Операторные программы, вычисляющие значения этой функции, приведены в п. 1.1.3. Эту же функцию можно запрограммировать в некотором рекурсивном языке, базирующемся на механизме рекурсивных функций языка Паскаль:
FACT(a),
FACT(х) = ifх = 0 then 1 elseх ´ FACT(х - 1),
где а — некоторое целое неотрицательное число.
Выполнение этой программы для некоторого значения а (пусть а = 4) может быть осуществлено следующим образом. В обе части рекурсивного определения вместо х подставляется 4, после чего вычисляется правая часть определения. Вычисление правой части начинается с вычисления логического выражения. Если его значение 1 (истина), то вычисляется левое функциональное выражение (стоящее после то), а если его значение 0 (ложь) — вычисляется правое выражение (стоящее после else).Вычисление функционального выражения сводится к его упрощению, т. е. выполнению всех возможных вычислений. Если в упрощенном выражения остается вхождение символа определяемой функции FACT, то осуществляется переход к новому шагу выполнения программы. На этом шаге вхождение FACT(m), где m — значение внутри скобок после упрощения, заменяется левым (т = 0) или правым (m > 0) функциональным выражением, в котором все вхождения х заменены на m. Упрощения продолжаются до тех пор, пока не будет получено выражение, не содержащее FACT (в нашем случае это выражение — число).
Вычисление рекурсивной программы может завершиться за конечное число шагов с результатом, равным значению запрограммированной функции для заданных аргументов (начальных значений переменных), но может и продолжаться бесконечно. В последнем случае значение функции не определено.
1.5.2. Определение рекурсивной схемы
Рекурсивная схема (РС) так же, как СПП определяется в некотором базисе. Полный базис РС, как и базис ССП, включает четыре счетных множества символов: переменные, функциональные символы, предикатные символы, специальные символы.
Множества переменных и предикатных символов ничем не отличаются от ССП. Множество специальных символов - другое, а именно: {if, то, else,(,),,}. Отличие множества функциональных символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество базовых функциональных символов и множество определяемых функциональных символов (обозначаются для отличия прописными буквами, например, F(1),G(2), и т.д.).
В базисе РС нет множества операторов, вместо него – множество логических выражений и множество термов.
Простые термы определяются так же, как термы–выражения в СПП. Среди простых термов выделим базовые термы, которые не содержат определяемых функциональных символов, а также вызовы-термы вида F(n)(t1,t2,…tn), где t1,t2,…t n - простые термы, F(n) - определяемый функциональный символ.
Логическое выражение- слово вида
p(n)(t1,t2,…tn),
где p(n) - предикатный символ, а t1,t2,…tn - базовые термы.
Терм - это простой терм, или условный терм, т.е. слово вида ifpthent1elset2,
где p - логическое выражение, t1, t2 - простые термы, называемые левой и соответственно правой альтернативой.
Примеры термов:
− f(x, g(x, y)); h(h(a)) - базовые термы;
− f(F(x), g(x, F(y))); H(H(a)) - простые термы;
− F(x); H(H(a)) - вызовы;
− ifp(x, y) then h(h(a)) else F(x) - условный терм.
Используется бесскобочная форма представления:
ifpxy then hha else Fx - условный терм.
Расширим в базисе В множество специальных символов символом "=".
Рекурсивным уравнением, или определением функции F назовем слово вида
F(n)(x1,x2,…xn) = t(x1,x2,…xn),
где t(x1,x2,…xn) - терм, содержащий переменные, называемые формальными параметрами функции F.
Рекурсивной схемойназывается пара (t, М), где t - терм, называемый главным термом схемы (или ее входом). М - такое множество рекурсивных уравнений, что все определяемые функциональные символы в левых частях уравнений различны и всякий определяемый символ, встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней функции, причем ровно одно.
Примеры РС:
RS1: F(x); F(x) = ifp(x) then a else g(x, F(h(x))).
RS2: A(b, c); A(x, y) = ifp(x) then f(x) else B(x, y);
B(x, y) = ifp(y) then A(g(x), a) else C(x, y);
C(x, y) = A(g(x), A(x, g(y))).
RS3: F(x); F(x) = ifp(x) thenx else f(F(g(x)), F(h(x))).
Пара (RS, I), где RS - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной программой. При этом заметим, что определяемые функциональные символы не интерпретируются.
Протоколы выполнения программы (RS1, I1) и (RS1, I2), где I1 и I2 - интерпретации из п. 1.2.3 (рисунок 1.2, б, в), выглядят следующим образом:
№ п/п | Значение терма для (RS1, I1) | Значение термадля (RS1, I2) |
F(4) 4*F(3) 4*(3*F(2)) 4*(3*(2*F(1))) 4*(3*(2*(1*F(0)))) 4*(3*(2*(1*1)))=24 | F(a,b,c) CONSCAR(abc, F(b,c)) CONSCAR(abc, CONSCAR(bc, F(c))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, F(ε)))) CONSCAR(abc, CONSCAR(bc, CONSCAR(c, ε)))=abc |
– Конец работы –
Эта тема принадлежит разделу:
Следуя А П Ершову мы употребляем термин теоретическое программирование в качестве названия математической дисциплины изучающей синтаксические... В настоящее время сложились следующие основные направления исследований... Математические основы программирования Основная цель исследований развитие математического аппарата...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Рекурсивные схемы
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов