Компьютерное задание

3.2.1 Компьютерное задание

Дана последовательность символов a1, a2, …, an. С применением рекурсии реализовать процедуру инверсии данной последовательности, то есть процедуру получения последовательности b1, b2, …, bn такой, что b1 = an, b2 = an-1, …, bn-1 = a2, bn = a1.

3.3 l-исчисление

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

В выражении

буква x может быть заменена любой другой буквой (за исключением t или f) и смысл выражения от этого не изменится в любом контексте, где это выражение может быть использовано.

В определении функции вида:

… где g(x) = a sin(px + q)

буква x также пуста.

С точки зрения вычислительной математики возникает проблема, является ли x именем объекта (областью рабочей памяти) или нет; или x – это объект, значением которого является другое имя. Этот вариант может иметь дальнейшее развитие, когда фактический параметр в g(x) является выражением отличным от простой переменной, например, как в записи g(t² + 2).

Очевидно, что в основе лежит вопрос определения функций. Для этих целей в 1941 году Черчем было введено l -исчисление. Задать функцию – это означает указать закон соответствия, приписывающий значение функции каждому допустимому значению аргумента. Пусть M – некоторая формула, содержащая x в качестве свободной переменной. Тогда lx.[M] есть функция, значение которой для любого аргумента получается подстановкой этого аргумента в M вместо x. Операцию образования выражения lx.[M] из M и x называют l - операцией или функциональной абстракцией.

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

Основным понятием является понятие функции f, которая сопоставляет по крайней мере один объект f(x₁, …, x_n) (ее значение) с каждой n – кой объектов x₁, …, x_n (ее аргументов, которые сами могут рассматриваться как функции). l - исчисление позволяет учитывать специфику вычисления функции в зависимости от используемых аргументов, то есть от того какой из аргументов рассматривается как связанная переменная.

Например, в дифференциальном исчислении выражение x-y может рассматриваться как функция f от x, либо как функция g от y. Для того, чтобы их различать будем записывать:

f = lx.[x-y], g = ly.[x-y].

Говорят, что префикс lx абстрагирует функцию lx.[x-y] от выражения x-y.

Аналогичные обозначения применяются для функций от многих переменных. Например, x-y отвечает функциям от двух переменных h и k: h(x, y) = x-y, k(y, x) = -y+x. Это можно записать:

h = lxy.[x-y], k = lyx.[x-y].

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

Например, определим функцию:

s = lx.[ly.[x-y]],

которая для каждого числа a превращается в

s(a) = lx.[ly.[x-y]](a) = ly.[a-y],

а для каждой пары a, b в

s(a (b)) = s(a, b) = lx.[ly.[x-y]](a, b) = a-b.

Предположим, что имеется бесконечная последовательность переменных и конечная или бесконечная последовательность констант. Атом определяется как переменная или константа. Множество l - термов определяется индуктивно:

1.   Каждый атом есть l - терм.

2.   Если X и Y - l - термы, то (XY) - l - терм.

3.   Если Y - l - терм, а x – переменная, то lx.[Y] - l - терм.

 Приведенное выше определение функции g(x) в этом исчислении записывается следующим образом:

g = l(x).[a* sin(p * x + q)],

а вместо g(t² + 2) можно записать:

l(x).[a* sin(p * x + q)] (t² + 2).

За символом l следует еще несколько синтаксических конструкций: вначале идет список связанных переменных, затем выражение, в которое входят эти переменные (тело l - выражения). Если остановиться здесь, то будем иметь функцию без операндов, такую как sin (заголовок функции). Но далее может следовать список фактических операндов. В этом случае имеем результат: взятие функции от этих операндов.

Важное значение приобретает сочетание l - исчисления и рекурсии. Предположим, что существует функция «следующий» - назовем ее next(x) – для каждого целого положительного числа и нуля. На самом деле – это функция x + 1, но будем считать, что + пока не определен.

Используя next, можем задать функцию «предыдущий» - prior(x) (после определения – эта функция будет иметь вид x –1). Определим эту функцию следующим образом:

prior(x) = previous(x, 0) Where previous(y, z) = iif(next(z) = y, z, previous(y, next(z))).

Процесс вычисления prior(x) начинается при z = 0, далее последовательно вычисляются последовательно функции next до тех пор, пока следующий для z не будет равен x. Это значение z и является ответом. Теперь можем определить сумму и разность двух чисел.

Sum(x, y) = iif(y = 0, x, Sum(next(x), prior(y))),

Diff(x, y) = iif(y = 0, x, Diff(prior(x), prior(y))).

Обратим внимание, что если y>x, то при вычислении Diff настанет такой момент, когда потребуется вычисление prior(0), а среди положительных чисел нет предшественника нуля. Поэтому говорят, что Diff вычислимо только частично для положительных чисел.

Теперь представим Sum в l - исчислении:

Sum = l(x, y).[iif(y = 0, x, Sum(next(x), prior(y)))]

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

Sum =lf.l(x, y).[iif(y = 0, x, Sum(next(x), prior(y)))](Sum),

а затем можно совсем убрать объект определения из правой части за счет введения оператора Y такого, что если F – функция, то YF – решение уравнения y = F(x).

Sum = Ylf.l(x, y).[iif(y = 0, x, f(next(x), prior(y)))].

В этом определении f – связанная переменная, которая при разрешении уравнения может быть заменена на что-либо другое. Следовательно, при замене на Sum получим:

Sum = YlSum.l(x, y).[iif(y = 0, x,.Sum(next(x), prior(y)))].

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

Говорят, что l - исчисление используется для того, чтобы выполнить операцию l - редукции и упростить выражение.

Учитывая, что выражение lx.[Px](a) может быть редуцировано к Pa, выражение:

lf.ly.lx.[f(x, y)],

сформулированное:

lf.ly.lx.[f(x, y)](подсистема)

сводится к

ly.lx.[подсистема(x, y)],

ly.lx.[подсистема(x, y)](ЭВМ)®lx.[подсистема(x, ЭВМ)], а

lx.[подсистема(x, ЭВМ)](процессор)®подсистема(процессор, ЭВМ).

Похожие работы

Общая терминология программирования

Скачать

71422

1

0

... программирование [application programming] — разработка и отладка программ для конечных пользователей, например бухгалтерских, обработки текстов и т. п.   Системное программирование [system programming] — разработка средств общего программного обеспечения, в том числе операционных систем, вспомогательных программ, пакетов программ общесистемного назначения, например: автоматизированных систем ...

Программирование и достижения компьютерной техники

Скачать

60551

0

0

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

Графические возможности программирования в курсе информатики

Скачать

110612

10

19

... набор процедур и функций языков программирования Basic и Pascal, позволяют управлять графическим режимом работы экрана, создавать разнооборазные графические изображения и выводить на экран текстовые надписи. ГЛАВА 2. ГРАФИЧЕСКИЕ ВОЗМОЖНОСТИ ЯЗЫКА ПРОГРАММИРОВАНИЯ В КУРСЕ ИНФОРМАТИКИ БАЗОВОЙ ШКОЛЫ (НА ПРИМЕРЕ BASIC И PASCAL)   2.1 Разработка мультимедиа курса «Графические возможности языков ...

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

Скачать

11287

1

10

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