Процедуры как преобразователи предикатов

Процедуры как функции на множестве состояний.

Мир задачи как автомат.

О формальной спецификации.

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

Мир=<состояния, переменные >

Можно воспринимать такую модель как автомат.

Аппликация: состояние ´ переменные → состояние

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

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

Найти процедуру P такую, что:

{а – произвольный массив}={a=A₀ & A₀[1..10]®real}

¯ P

{a – упорядоченный массив}={a=A₁ & "iÎ1..9 a[i]¹a[i+1]}& перестановка (A₀,A₁)

"iÎ1..10 (A₁[i]ÎA₀) & "jÎ1..10 (A₀[j]ÎA₁)

Постановка спецификации есть функция на множествах состояний. Решение есть процедура, то есть функция на состояние.

Задача поиска. Задан массив…

{a=AÎN®real} & xÎReal;

P-?

{xÎÛ$i: x=A[i]}

Любая P, удовлетворяющая этому свойству (находящая значение i с заданным свойством), будет решением.

Вернёмся к нашим обезьянам…

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

1) Состояние обезьяны относительно комнаты.

Содержательное описание:

- имя переменной: обезьяна ХУ;

- множество значений: {у двери, у окна, в середине}

2) Обезьяна относительно ящика:

- имя переменной: обезьяна Z;

- множество состояний: {на ящике, на полу}

3) Ящик относительно комнаты:

- имя переменной: ящик ХУ;

- множество состояний: {совпадает с множеством значений обезьяна ХУ}

4) Банан относительно обезьяны:

- имя переменной: банан;

- множество значений: {висит, у обезьяны}

Состояние мира задачи определяется совокупностью состояний отдельных объектов, значениями переменных, соответствующих объектам.

Мир в этом случае – 4 переменные:

1) Обезьяна ХУ ® {у двери, у окна, в середине};

2) Обезьяна Z ® {на ящике, на полу};

3) Ящик ХУ ® {у двери, у окна, в середине};

4) Банан ® {висит, у обезьяны}.

Множество состояний – именованное декартово произведение.

Множество исходных состояний: любое состояние мира, в кот. мир(банан)=висит.

Множество конечных состояний: любое состояние, в кот. мир(банан)=у обезьяны.

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

type wState=record

ОбезьянаХY: tОбезьянаХY;

ОбезьянаZ: tОбезьянаZ;

ЯщикXY: tЯщикХY;

Банан: tБанан;

end;

procedure Схватить(var s:wState);

begin

with s do

if (банан=висит) and (обезьянаXY=середина) and (обезьянаZ=на ящике)

then банан:=у обезьяны;

end;

procedure Залезть(var s:wState);

begin

with s do

if ящикXY=обезьянаXY…

procedure Подвинуть(var s:wState; p1,p2:tОбезьяна);

{Подвинуть ящик из точки p1 в точку p2}

{Очевидно, соответствует более компактному описанию семейства функций}

begin

with s do

begin

if (ящикXY=обезьянаXY) and (обезьянаXY=p1) then

begin

обезьянаXY:=p2;

ящикXY:=p2;

end;

end;

procedure Перейти(var s:wState; p1,p2:обезьянаXY);

{Обезьяна переходить из точки p1 в точку p2}

begin

with s do

if обезьянаXY=p1 then обезьянаXY:=p2;

end;

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

2) Как решать задачу?

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

Дата добавления: 2014-01-05