nextupprevious

Next:1.1.4 Упражнения
Up:1.1 Алгоритмы и функции
Previous:1.1.2 Что такое компьютер?

1.1.3 Как можно определять функции?

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

В этих определениях, прежде всего, разрешается употреблять произвольные выражения языка математики, например:

$Sqr(z) = z*z$ или

Сумма$(x,y,z) = x + y + z$ или

ЧислоПи=$4 * \sum_{n=0}^\infty \frac{(-1)^n}{2n+1}$

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

Определения функции могут строиться иерархически, например,

Сумма4(x,y,z,u) = Сумма2(Сумма2(x,y), Сумма2(z,u)),

где

Сумма2(x,y) = x + y, или

Герон$(a,b,c)$ = Гер$(a,b,c,(a + b + c) /2)$,

где Гер$(a,b,c,s) = \sqrt{s*(s-a)*(s-b)*(s-c)}.$

Часто определения функций задаются в форме разбора случаев, например:

или

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

Такое определение называется рекурсивным.

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

-- во-первых, если при задании функции разбором случаев условия всех вариантов ложны для этого набора параметров (скажем, значение Факториал$(-1)$ не определено);

-- во-вторых, если вычисление значения выражения из правой части определения функции никогда не заканчивается (например, значение $f(1)$,
где

не определено);

-- в-третьих, если вычисление значения выражения приводит к применению базовой операции (или определяемой функции) к такому набору значений аргументов, для которого она не определена (скажем, $\sqrt{-1},$$\ln(-1)$ и 1/0 не определены).

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

Факт$(n) = h(n,1)$,

где

эквивалентна функции Факториал, поскольку по определению имеем

Факт$(n) = h(n,1)= h(n-1,1*n) = h(n-2, 1*n*(n-1)) = \ldots =$
$= h(n-i, 1*n*(n-1)*\ldots *(n-i+1)) = \ldots =h(0,n!) = n!$ = Факториал$(n)$

для неотрицательных $n$, а области определений этих функций совпадают.

Приведем еще три рекурсивных определения функций.

а) Длина слова

Вычислим значение Длина(010):

Длина(010) = Длина(10) + 1 = (Длина(0) + 1) + 1 = ((Длина$(\Lambda)$ +1) + 1) + 1 = ((0 + 1) +1)+1 = 3.

б) Наибольший общий делитель двух натуральных чисел

Вычислим значение НОД(34, 55):

НОД(34,55) = НОД(55,34) = НОД(34,21) = НОД(21,13) = НОД(13,8) = НОД(8,5) =

НОД(5,3) = НОД(3,2) = НОД(2,1) =НОД(1,1) = 1.

в) Двоичное представление целого неотрицательного числа:


где

$Mod(n,m) = n - (n\div m)*m,$
а "$\div$" -- это операции целочисленного деления.

Вычислим значение ДвПредст(5): ДвПредст(5) = Транс(5) = Транс$(5\ \div \ 2)\parallel Mod(5,2)$= Транс(2) $\parallel Mod(5,2)$= Транс(2) $\parallel (5-(5\div 2)*2)$= Транс(2) $\parallel (5-2*2)$= Транс$(2) \parallel (5-4)=$Транс$(2) \parallel 1 =$ (Транс$(2\ \div \ 2)\parallel Mod(2,2))\parallel 1=$ (Транс$(1)\parallel Mod(2,2))\parallel 1=$ (Транс$(1)\parallel (2-(2\div 2)*2))\parallel 1=$ (Транс$(1)\parallel (2- 1*2))\parallel 1=$ (Транс$(1)\parallel (2-2))\parallel 1=$ (Транс$(1) \parallel 0) \parallel 1$ = ((Транс (0)$ \parallel 1) \parallel 0)\parallel 1=((\Lambda \parallel 1) \parallel 0) \parallel 1=( 1 \parallel 0) \parallel 1=10 \parallel 1 = 101$.

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

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

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

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

В) Из всех обращений к функциям, имеющимся в выражении, для развертки выбирается "самое левое самое внутреннее". Например, при вычислении выражения $f(f(0) + f(1))$ первым нужно раскрыть обращение $f(0)$, а самое внешнее обращение к функции $f$ следует раскрывать только после того, как в нем не останется никаких обращений к функциям.

Next:1.1.4 Упражнения
Up:1.1 Алгоритмы и функции
Previous:1.1.2 Что такое компьютер?


© В.Н. Касьянов, Е.В.Касьянова, 2004