2 Постановка задачи: о связном предъявлении теории информатики и практики программирования в теме исполнения для теоретического мышления. 13 (стр. 7 из 25)
· Теорема о неподвижной точке
Частично упорядоченное множество называется полной структурой, если всякое его непустое подмножество имеет как точную верхнюю, так и точную нижнюю грань. Обозначим посредством ^ наименьший элемент.
Определение: Точка f называется неподвижной (фиксированной) точкой функции (функционала) j, если j(f)=f. Такая точка называется наименьшей, если " е: j(e)=e => f£e (где £ - отношение порядка (возможно частичного) на множестве определения j).
Рассмотрим класс функций, имеющих фиксированные точки, и укажем способ нахождения наименьшей.
Возьмём j: P®P - монотонное отображение на полной структуре P. Применим j к произвольному элементу a из P. К результату снова применим j и так далее. Вследствие полноты P будет существовать точная верхняя грань последовательности. Если полученная последовательность значений будет монотонной, то её и стоит подозревать на неподвижность, т.е. supk{j (a)} = a?
Следовательно,
Теорема о неподвижной точке. Если j - монотонное отображение полной структуры P в себя, то j(а) = а для некоторого аÎP.
Доказательство:
Рассмотрим множество Х = {х | j(x) ³ х, xÎP}. Минимальный элемент ^ (основание) существует в силу полноты Р и ^ÎХ, таким образом множество Х не пусто. Следовательно, существует а = sup Х. При этом для любого x Î Х, так как а ³ х и j - монотонно, то j(а) ³ j(х) ³ х, следовательно j(а) ³ а. Аналогично, т.к. j - монотонно, то j(j(а)) ³ j(а), что влечет j(а) Î Х и, значит, а ³ j(а), так как а = sup Х.
Таким образом, а ³ j(а) ³ a => а = j(а).
■
Рекурсию можно воспринимать двояко: индуктивно и через решение функционального уравнения. Эти толкования рекурсии совпадают при определенных условиях на функционал.
Монотонный функционал j называется (цепочно) непрерывным, если для монотонно возрастающей последовательности x0=^ и xi+1=j(xi)=ji(^) справедливо:
suр{j[xi]: iÎN}=j[suр{xi: iÎN}].
Теорема о совпадении наименьшей неподвижной точки с супремумом цепочки.
Если j непрерывен, то Yj совпадает с супремумом цепочки {xi: iÎN} (x0=^, xi+1=j(xi)).
Доказательство: Из непрерывности j следует, что супремум цепочки является неподвижной точкой для j:
j[suр{xi: iÎN}]=suр{j[xi]: iÎN}=suр{xi+1: iÎN}=suр{xi: iÎN}.
Осталось доказать, что точка b=sup{xi: iÎN} будет наименьшей неподвижной точкой (по индукции). Предположим, что a - также фиксированная точка j. Докажем, что b £ х. В базовом случае ^ £ a, так как ^- основание (минимальный элемент). Предположим, что jk(^) £ a, тогда jk+1(^) £ j(a) = a, так как j - монотонно, а a - фиксированная точка по предположению. Так как a ³ jk(^) для любого k, то х является верхней границей монотонной последовательности. По определению наименьшей верхней границы и b £ a.
· Применение теоремы в программировании.
Надо позаботиться о простоте восприятия монотонности и непрерывности оператора j при толковании рекурсивных объектов посредством теоретико-множественного решения подходящего уравнения. Во многих случаях подходит плоский (дискретный) порядок. Введем порядок на произвольных элементах: x£y, если (x=^)Ú(x=y). Например, для N мы, тем самым, определили дискретную решетку:
Она является полной.
Рекурсивные функции могут трактоваться как решения функциональных уравнений. Рассмотрим для простоты f: N®N. Индуцируем порядок на функциях на основании плоского порядка на N.
f £ g ÛDf "x [f(x) £ g(x)].
Таким образом, f£g, если g является продолжением (расширением) функции f (то есть на области определения f эти функции совпадают, и g может быть “шире”). В каком-то смысле g уточняет функцию f. В таблице изображены примеры функций, находящихся в таком порядке. Эти функции монотонны по определению порядка.
| F0 | F1 | F2 | F3 | ¼ | F¥ | |
| T | ^ | Т | T | T | ¼ | T |
| 0 | ^ | 0 | 0 | 0 | ¼ | 0 |
| 1 | ^ | ^ | 1 | 1 | ¼ | 1 |
| 2 | ^ | ^ | 4 | 4 | ¼ | 4 |
| ¼ | ||||||
| N | ^ | ^ | ^ | ^ | ¼ | N2 |
| ^ | ^ | ^ | ^ | ^ | ¼ | ^ |
Пример (индуктивное толкование рекурсивного соглашения о функции факториала). Рассматривается рекурсивное объявление
fсt fас = (nаt х)nаt:
if х
0 then 1 else х*fас(х-1) fi,при этом получают следующий функционал j:
В соответствии с нашим определением справедливо для хÎN^, i=0,1,¼:
fас 0(х)=^, т.е. fас 0=W.
Тем самым для функции fас i получается не рекурсивное равенство:
Это можно доказать индукцией по iÎN, i=0,1,¼:
(1) i=0, тогда утверждение тривиально.
(2) Пусть утверждение правильно для fас i
fас i+1(х)=t[fасi](х)=
Пример (наименьшая неподвижная точка для функционала функции факториала). Функция
fас: N^®N^
с fас(n)=n! есть наименьшая неподвижная точка j, т.е. наименьшее решение функционального уравнения j[f]=f с
Индуктивное толкование suр{¦i: i=0,1,¼} и толкование неподвижной точки fiх j полностью идентичны, если функционал j обладает так называемым свойством непрерывности.
Проверим j на непрерывность
j[sup{fi: i=0,1,...}](x) = j[sup{fi(x-1): i=0,1,...}] =
sup{j[fi]: i=0,1,...}](x) = sup{j[fi(x)]: i=0,1,...}] = sup{faci+1(x): i=0,1,...}=x!
Для сравнения с хорошими функционалами рекурсивных определений приведем пример немонотонного функционала. Пусть функционал j, действуя на функцию f: N®N, выглядит следующим образом:
Пусть f£g, g¹f, x0 - наибольшая точка (обычный порядок на N) области определения f. Для x¹x0 области определения f t[f]=t[g]=^.
Для x=x0 t[f](x0) = 1, а t[g](x0) = ^.
Таким образом, мы получили t[f](x0) ³ t[g](x0). Значит, построенный нами функционал не является монотонным.
Рекурсивные типы могут трактоваться как решения уравнений для множеств.
Пример (индуктивное толкование рекурсивного объявления типа). Пусть дано следующее объявление типа двоичных деревьев
sоrt m = еmрtу(еmрtу)ïсоns(m lеft, nаt rооt, m right).
Если записывать e для единственного элемента типа еmрtу, то для любого множества данных М получим:
D(М)={e}È{(l,х,r): lÎМ\{^} Ù хÎN Ù rÎМ\{^}}È{^}.
Это приводит к следующим множествам данных:
М0={^},
Мi+1={e}È{(l,х,r): lÎМi\{^} Ù хÎN Ù rÎМi\{^}}È{^},
т.е.
М1={^, e},
М2={^, e, (e,0,e), (e,1,e), ...},
М3={^, e, (e,0,e), ((e,0,e), 0, e), ...}.
Итак, получаем множество, эквивалентное множеству двоичных деревьев.
Пример (трактовка неподвижной точки для двоичных деревьев в рекурсивном объявлении типов). Пусть имеют место определения предыдущего примера. Для множества М с
М=ÈМi
имеет место
М={e}È{(l,х,r): lÎМ\{^} Ù хÎN Ù rÎМ\{^}}È{^}, (*)
т.е. М есть решение уравнения М=D(М). М является также наименьшей неподвижной точкой оператора D.
Действительно, оператор D является монотонным и непрерывным по теоретико-множественному включению.