Инф Пользовательские процедуры как аппарат технологии программирования.

Инф Основные понятия процедурного программирования.

Формально-математическим средством моделирования объектов реальности служит понятие типа данных - пары < A, F> - где A - некоторое основное множество значений, отражающее совокупность состояний объекта, и класса функций F, FÍ Aà A, описывающих совокупность его возможных преобразований во времени.

В самом простом случае компоненты множества А считаются " атомами", не имеющими, внутренней структуры - такие типы называют скалярными.

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

В программировании обычно используется принцип именования - сопоставления значений не номерам, но именам характеристик. В качестве основного множества типа выступает подмножество именованного декартового произведения множеств A₁, …, A_n- класса всех функций значения, т.е. определенных на некотором множестве имен Name всех функций f таких, что f(k)Î A_i(k), k Î Name.

Функции " высших порядков", аргументами и значениями которых являются функции, называют операторами или процедурами, а их определение на некотором формально-математическом языке называют - спецификацией.

Языки процедурного программирования - языки прямых определений, задающие способы определения новых основных множеств и процедур в терминах уже построенных к этому времени типов данных. Этот базовый рекуррентный принцип отражается и в основном для таких языков способе обозначения процедур - операторе присваивания вида s: =e(s'), где s, s' - списки имен переменных, а e - выражение, задающее функциональную зависимость новых значений переменных (с именами из s) от старых значений переменных (с именами из s').

Программа - итоговое определение процедуры на заданном языке программирования, программирование - такое определение как происходящий во времени процесс.

Классическим примером конструктивного построения языка являются языки структурного программирования, выделяющие в качестве основных три общематематических способа определения новых процедур:

a) композиция (S1; S2, в синтаксисе языка Паскаль) - суперпозицияпроцедур S1 и S2 как функций на состояниях: (S1; S2)(s)=S2(S1(s))

b) структуру условного оператора (if B then S1 else S2), соответствующую определению функции разбором случаев

c) структуру оператора цикла с предусловием (while B do S), соответствующую итогу вычисления первого члена рекуррентно определяемой последовательности, обладающем заданным свойством: если s₀=s и s_i+1=S(s_i), то (while B do S)(s)=s_k, где k=min {i: B(s_i)=false} и (while B do S)(s) неопределено, если {i: B(s_i)=false}=Æ.

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

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

Инф Однопроходные алгоритмы объединения(слияния), пересечения и разности массивов.

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

С=Вставка(A, b) » " iÎ Dom(C) (c_i Î A or c_i =b) & Упорядочена(С)

С=Удаление(A, b) » " iÎ Dom(C) (c_i Î A and c_i ¹ b) & Упорядочена(С)

С=A È B » " iÎ Dom(C) (c_i Î A or c_i Î B) & Упорядочена(С)

С=A Ç B » " iÎ Dom(C) (c_i Î A and c_i Î B) & Упорядочена(С)

С=A \ B » " iÎ Dom(C) (c_i Î A and c_i Ï B) & Упорядочена(С)

где xÎ f » $ iÎ Dom(f) (x=f(i))

Все следующие ниже алгоритмы однопроходные, т.е. сохранять упорядоченность легче, чем сортировать. Направляющая общая идея реализации - кратный ограниченный поиск в упорядоченной последовательности - для ответа на вопрос x Î a, достаточно найти “барьер”, т.е. первый a_i такой, что x£ a_i.

TInfo – произвольный тип, на котором определен некоторый линейный порядок <

Слияние массивов

Type tIndex=1..MaxIndex;

tArray=array[tIndex] of tInfo;

procedure Слияние(A, B: tArray; LenA, LenB: tIndex; var C: tArray; var LenC: tIndex); {c: =aÈ b}

var i, j: tIndex; BarrierFound: boolean; {= B[j]£ A[i] }

begin LenC: =0; j: =1;

for i: =1 to LenA do

begin

{каждый элемент А[i] должен попасть в С, но до этого}

{скопируй все элементы B[j], B[j]£ A[i] в С }

BarrierFound: =false;

while (j< =LenB) and not BarrierFound do

begin

if B[j]£ A[i]

then begin C[LenC]: =B[j]; inc(LenC); inc(j) end

else BarrierFound: =true;

end;

C[LenC]: =A[i]; inc(LenC)

end; {while} end {procedure Слияние }

Вставка в упорядоченный список

Type {определение списка}

pList=^tList; tList=record

info: tInfo; {некий тип со сравнением < }

next: pList

end;

Procedure Вставка( var pA: pList; {А - исходная упорядоченная последовательность с барьером} pX: pList; {ссылка на вставляемое значение x} );

var x: tInfo;

This, Prev, {ссылки на текущую и предыдущую компоненты списка}

Begin x: =pX^.info;

{найди ссылку This на первую компоненту со значением info, не меньшим x}

Prev: =nil; This: =pA; found: =false

While (This< > nil) and not found do

If This^.info> =x

then found: =true

else begin Prev: =This; This: =This^.next end;

{found=true и This< > nil, по определению барьера}

{вставляем между Prev и This}

pX^.next: =This; if Prev< > nil then Prev^.next: =pX

End;

Реализация структурных типов.

Достаточно иметь в нашем языке единственную переменную - с некоторым стандартным именем Memory (память) - указывая все нужные значения как некоторые подстроки Memory[i, l] этой переменной. Далее мы используем обычные имена переменных вместо непривычных имен вида Memory[i, l].

Индекс i называется адресом значения Memory[i, l]. Понятно, что когда длина поля l заранее известна, то по значению i можно однозначно восстановить содержимое поля Memory[i, l]. Таким образом, каждое имя переменной имеет числовое значение - адрес начала поля соответствующей этой переменной.

Значения структурных типов представляется в виде совокупности полей. Так, массив array[1..n] of T - это последовательность n битовых полей, каждое длины Len(T) - т.е. некоторое битовое поле Memory[AdrA, L] длины L=Len(T)*n

Аналогично, запись record N₁: T₁; …; N_m: T_mend - последовательность m битовых полей разных длин Len(T₁), …, Len(T_m) - т.е. снова некоторое битовое поле Memory[AdrRec, L] длины L= Len(T₁)+…+Len(T_m). Нетрудно вычислить AdrRec+ Len(T₁)+…+Len(T_k-1) - адрес начала поля, содержащего значение r. N_k и таким образом реализовать операцию доступа по имени, для каждого имени N_k.

Алгоритм полного перебора раскрасок

function Правильная(r: tРаскраска): boolean;

begin

b: =true;

i: =ПерваяВершина;

while (i< =pred(ПоследняяВершина)) and not b do

begin j: =succ(i);

while (j< =ПоследняяВершина) and not b do

if Coседи(i, j) and (Цвет(r, i)=Цвет(r, j))

then b: =false else j: =succ(j);

i: =succ(i)

end;

procedure ПолныйПеребор (graph: tGraph; var found: boolean);

var r: tРаскраска; exists: boolean; {}

begin

r: =ПерваяРаскраска; found: =false; exists: =true;

while exists (= not КончилисьРаскраски} do

begin if Правильная(r) then begin found: =true; Печать(r) end

Следующая(r, exists) {r: =Следующая(r)}

end;

Дальнейший анализ.

Тип tВершины должен быть порядковым. Тип tGraph хорошо бы реализовать так, чтобы было легко вычислять функцию Соседи - задать граф матрицей инциндентности. Тип tРаскраска хорошо бы реализовать так, чтобы было легко вычислять цвет каждой вершины r - реализовать раскраски как стек. Алгоритм прост, но малоэффективен. Перебор всех mⁿ раскрасок - функций/последовательностей [1..n]à [1..m] - дело долгое.

11. Инф Алгоритм перебора с возвратом на примере задачи о перечислении всех правильных раскрасок графа.

Идея сокращения области перебора проста - рассматривать неполные раскраски - динамические последовательности, т.е. функции [1..k]à [1..m], k£ n. Основание - если неполная раскраска r уже не правильна, нет никакого смысла терять время на перебор раскрасок большей длины.

Для этого доопределим лексикографический порядок на последовательностях Seq произвольной длины, Seq= È {Seq(L): LÎ N}. Пусть a, b Î Seq - разной длины LenA и LenB, a¹ b и N=N(a, b)=min {n: a(n) ¹ b(n)}- наименьший номер i, на котором они различаются. Тогда a< b, если

a) Либо NÎ Dom(a) (N £ LenA), NÎ Dom(b) (N £ LenB) и a(N)< _Tb(N).

b) Либо NÎ Dom(a) (N £ LenA) и NÏ Dom(b) (N > LenB), т.е. a - начальный отрезок последовательности b

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

procedure ПереборCВозвратом (graph: tGraph; var found: boolean);

var r: tРаскраска; exists: boolean;

begin

r: =ПерваяРаскраска; {заметь - теперь это пустая последовательность! }

found: =false; exists: =true;

while exists {= not КончилисьРаскраски длины менее n} do

begin if Правильная(r)

then if Полная(r) {т.е. длины n}

then begin found: =true; Печать(r) end

else {дополнить - добавить первое значение в T}

Push(r, Первый)

else {не правильная} Возврат(r, exists) {=Следующая(r, exists)}

end;

12. Инф Обход дерева «в глубину» (с использованием стека) и «в ширину (с использованием очереди)».

Автомат Go - дерево, если существует корневая вершина (начальное состояние автомата) Æ,

a) в которую не ведет ни одно ребро, " aÎ Nodes (Go(r, a)=Æ à a=Æ ),

b) но из которой существует путь в любую вершину,

" aÎ Nodes $ rÎ Arrows (Go(r, Æ )=a),

причем этот путь - единственный, " r, r'Î Arrows (Go(r, Æ )=Go(r', Æ ) à r=r').

Go - бинарное дерево, если, к тому же, множество стрелок состоит из лишь из двух стрелок, далее обозначаемых как левая (left) и правая (right), Arrows={left, right}.

{реализация бинарного дерева ссылками}

pTree=pNode; {дерево задается ссылкой на корень}

pNode=^tNode;

tNode=record

Content: T; {содержимое вершины}

left, right: pNode;

end;

Задача обхода дерева заключается в переборе его вершин в некотором порядке, т.е. построении некоторой функции следования на Arrows*´ Nodes.

Самый простой класс таких порядков связан с лексикографическим порядком на множестве " слов" /путей Arrows*, связанных со всеми возможностями определения такого порядка на " алфавите" - множестве Arrows.

{пример обхода " в глубину" }

{» более короткие ветки идут в перечислении раньше более длинных}

procedure КЛП(root: pTree);

var

pt: pNode; {ссылка на текущую вершину}

stack: pStack;

begin

Create(stack);

if root< > nil then push(stack, root);

while not empty(stack) do

begin

pop(stack, pt); {подъем наверх}

with pt^ do

begin

{ какая-то обработка содержимого текущей вершины pt^.value}

if left< > nil {можешь идти налево? }

then {тогда иди, но сохрани правую ссылку}

begin pt: =left; if right< > nil then push(stack, right) end

else {налево нельзя}

if pt^.right< > nil {- можно ли направо? }

then pt: = pt^.right

end;

Destroy(Stack)

end;

{пример обхода в ширину - ветви одинаковой длины (" буквы" left, right) соседствуют в перечислении}

procedure (root: pTree);.

var

Queue: pQueue;

pt: pNode; {ссылка на текущую вершину}

begin

Create(Queue); {создать очередь}

if root< > nil then Put(Queue, root); {Поставить В Очередь }

while not Empty(Queue) {очередь не пуста} do

begin

Get(Queue, pt); {Вывести Из Очереди}

{обработать содержимое pt^.value вершины pt}

if pt!.left< > nil then Put(Queue, pt!.left);

if pt!.right< > nil then Put(Queue, pt!.right);

end;

Destroy(Queue)

end;

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

1) либо термом, т.е.

a) либо именем константы вида b₁… b_n.c₁… c_m, где

(n> 0) & (m> 0) & " iÎ [1, n](b_iÎ ['0', '9']) & " jÎ [1, m](c_jÎ ['0', '9'])

b) либо именем переменной вида d₁… d_k, где

(k> 0) & (d₁Î ['a', 'z']) & " iÎ [2, k](d_iÎ ['0', '9']È ['a', 'z'])

2) либо строкой вида (E₁)f(E₂), где E₁, E₂ - выражения, а f - один из знаков +, -, *, /

Определим также дерево выражения E как дерево над базовым типом string, состоящее из единственной вершины, содержащей Е, если Е - терм или же дерево вида

если Е - выражение вида (E₁)f(E₂).

Задача вычисления дерева выражения. Найти результат выражения при заданных значениях переменных, если выражение представлено деревом.

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

{вычисление элементарного выражения}

function AtomVal(root: pExpr): T;

begin

with root^ do

case Name of

'+': AtomVal: =left^.Val+right^.Val;

'-': AtomVal: =left^.Val-right^.Val;

'*': AtomVal: =left^.Val*right^.Val;

'/': AtomVal: =left^.Val/right^.Val;

{для простоты, опускаем обработку исключения - деления на 0}

end; end;

{выяснение типа вершины}

function NodeType(pt: pNode): char;

begin

with pt^ do

if (right=nil) and (left=nil)

then NodeType='t' {терм}

else NodeType='f' {выражение}

end;

{поиск атома, лежащего ниже данной вершины}

{идея: вычисление $-свойства found: =$ ptÎ pNode (pt¹ nil & pt^.left¹ nil & pt^.right¹ nil) }

procedure FindAtom(var pt: pNode; var stack: pStack);

Синтаксический анализ выражения, представленного деревом. Проверить, является ли произвольное бинарное символьное дерево деревом выражения. Задача синтаксического анализа очевидно распадается на анализ 1) термов и 2) сложных выражений. Анализ термов прост и напрямую сводиться к задаче поиска. Центральная идея: свести задачу анализа сложного выражения к задаче вычисления.

1) Анализ термов.

{Поиск позиции " исключения" - первого символа в подстроке s[start, finish], не принадлежащего множеству alphabet }

procedure FindException

{идея: проверка свойства found=$ positionÎ [start, end] (s[position] Ï alphabet)}

{проверка имени константы}

function ConstantName(s: string): boolean;

{проверка имени переменной }

function VariableName(s: string): boolean;

Анализ (сложных) выражений.

Определим понятие расширенного ( р- ) выражения как строки вида (E₁)F(E₂), где E₁, E₂- произвольные, в том числе пустые строки, а F - произвольная непустая строка. Любому невырожденному дереву однозначно сопоставляется некоторое р-выражение.

Если р-выражение не имеет типа 'f' или 't', то оно имеет тип 'Æ '. Формальным вычислением р-выражения назовем операцию Reduce:

ì терм 'x', если Тип(E₁)=Тип(E₂)='t' и Тип(F)='f'

Reduce((E₁)F(E₂))= í

î 'Æ ', иначе

(смысл прост - результатом вычисления правильного выражения является терм, а результат вычисления неправильного выражения не определен)

Идея алгоритма: Выражение правильно » тип результата формального вычисления = терм.

{расширенный тип вершины}

function ExtentedNodeType(pt: pNode): char;

{теперь не уверены, что найдутся правильные атомы! }

{но, в таком случае, обязательно найдется не правильный }

procedure FindExtendedAtom(var pt: pNode; var stack: pStack);

{формальное вычисление расширенного элементарного выражения}

function ExtendedAtomVal(root: pExpr): string;

function ExpressionCorrect(root: pExpr): boolean;

Инф Основные понятия процедурного программирования.

Инф Пользовательские процедуры как аппарат технологии программирования.

2 естественных порядка определения процедур. Принцип композиции - от данных средств реализации к желаемой цели - восходящее программирование. Такой подход - локальная тактика, применимая для разработки относительно небольших и несложных программ. Стратегия нисходящего программирования - цель важнее средств - основана на принципе декомпозиции.

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

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

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

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

1) Избавление от конфликта (коллизии) имен .

2) Формальная семантика параметров-значений . Перед телом процедуры: V: =E, V - имя формального параметра, E - соответствующее ему в обращении выражение

3) Формальная семантика параметров-переменных. Замени в тексте процедуры все вхождения имен параметров на соответствующие им при обращении имена переменных.

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

3. Инф Типы данных и их классификация (на примере языка Паскаль).

Real, integer - арифметика вещественных и целых чисел,

string - полугруппа слов относительно операции конкатенации (сцепления слов),

array[I] of T - множество всех функций Ià T, c операцией App применения (аппликации) функции к аргументу, App(a, i)=a[i],

record n₁: T₁; …; n_m: T_mend - именованное декартово произведение основных множеств типов T₁, …, T_mс конечным множеством имен {n₁, …, n_m}, с операцией аппликации, App(r, n)=r.n,

file of T - множество всех последовательностей Nà T, c операторами:

reset(f) » маркер(f)=0; режим(f): =чтение;

read(f, x) » inc(маркер(f)); x: =f(маркер(f)). rewrite(f)

write(f, e) » inc(маркер(f)); f(маркер(f)): =e; eof(f)

Классический процедурный стиль склоняется к раздельному описанию

а) способов определения основного множества значений А, при фиксированном классе функций F

б) способов определения класса F - преобразований значений типа (см. § 2).

Классификация типов по способу определений значений основного множества. 1) Разделение между скалярными и производными типами. В последнем случае, значения структурированы. Общая схема такой структуры - именованное декартово произведение, т.е. некоторый класс функций. Различие производных типов - в конкретных областях определения и значений этих функций, и операторов их обработки. integer, real, char, boolean, перечислимый, ограниченный, производных типов - string, text, array, file, record, set. 2) Стандартные и пользовательские типы. В первом случае множество значений предопределено, во втором (до)определяется программистом. Стандартные - integer, real, char, boolean, string, text; пользовательские - перечислимый, ограниченный, array, file, record, set. 3) Порядковые и непорядковые типы. Порядковые типы - те множества значений X, на которых определен порядок перебора, т.е. сравнение (линейный порядок) <, x< x' - " x' следует позже в переборе, чем x". Однако, не любое сравнение определяет порядок перебора, а лишь такое, для которого определены (доступны): функция следования (прямого перебора) succ, succ(x)=min{x': x'> x} и функции предшествования (обратного перебора) pred, pred(x)=max{x’: x’< x}

4)Динамические и статические производные типы. Значения производных типов - функции. Область их определения может быть фиксирована (статический тип) - пример - множество всех функций [1, n]à T для фиксированного n, либо нет (динамический тип), пример - множество всех функций [1, n]à T для произвольного n. Примеры статических типов - record, статический array (в стандартном Паскале); динамических - file, string, динамический array ( в Object Pascal).

5)Абстрактные типы. Абстрактные типы - типы, точно определяемые как математические объекты, но не как объекты данного языка программирования. Пример - комплексные числа и точки плоскости не есть тип Паскаля, тип record x, y: real end - тип Паскаля. Установление соответствия между значениями и операциями абстрактного и конкретного типов называется реализацией абстрактного типа.

6) Тесно связано с понятием реализации деление типов по способам доступа. На практике важен способ определения, задания объекта/функции. Существует три важных вида таких определений: реккурентное (данные последовательного доступа, пример - файлы и списки, язык описания - функции следования), явное (данные прямого доступа, пример - массивы и записи, язык описания - оператор аппликации) и рекурсивное (пример - деревья и графы, язык описания - функции на последовательностях)

4. Инф Алгоритмы вычисления логических формул. Предикат (свойство, условие) - произвольная функция с областью определения Boolean={true, false}. Пример (двуместных) предикатов - бинарные отношения, в частности, отношения сравнения <, >, =, < >.

Вычисление предикатов облегчается тем, что существует общематематический язык логики (исчисления предикатов) - содержащий бинарные операции & (and), Ú (or), Ø (not) - их относят к операциям алгебры логики, а также два квантора (оператора над множествами) " и $ (отсутствуют в Паскале). Перевод формулы из языка ИП в программу на структурном языке программирование - техническая задача, при учете следующих основных моментов.

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

2. Для кванторных формул канонической является т.н. предваренная нормальная форма вида Q₁x₁… Q_n x_nB(x_1,…, x_n, z) ( где Q_i- либо $ либо ", причем каждые два соседних квантора можно считать различными, а B уже не содержит кванторов).

3. Алгоритмическое определение операций алгебры логики.

a) y: =not b » if b=true then y: =false else y: =true

b) y: =b1 and b2 » 1) y: =false; if b1=true then if b2=true then y: =true; » 2) y: =true; if b1=false then y: =false; if b2=false then y: =false;

c) y: =b1 or b2 » 1) y: =true; if b1=false then if b2=false then y: =false 2) y: =false; if b1=true then y: =true; if b2=true then y: =true

4. Вычисление кванторных формул.

a) y: =$ xÎ X (B(x))

Рассмотрим частный случай. X - множество значений порядкового динамического типа, для которого определены функция следования и предикат конца перебора значений. Тогда $ xÎ X (B(x)) - это кратная дизъюнкция, а y есть первый true в реккурентной последовательности y₀=false, y_i+1= y_ior B(x_i) (либо false, если такового нет). Поэтому, можно воспользоваться общей схемой вычисления членов реккурентных последовательностей:

y: = $ xÎ X (B(x)) »

y: =false; i: =1; while (i< =LenX) and not y do if B(x_i) then y: =true else inc(i)

Точно также можно определить формулу " xÎ X (B(x)) как кратную конъюнкцию:

y: = " xÎ X (B(x)) »

y: =true; i: =1; while (i< =LenX) and y do if B(x_i) then y: =false else inc(i)

5. Инф Алгоритмы поиска в последовательностях.
Задача поиска формулируется в двух внешне различных формулировках.

a) b: =y Î Val(f)» $ x Î Dom(f) (f(x)=y) - выяснить, храниться ли данное значение y в структуре f.

b) x: =min{x': f(x')=y} определить первое (в некотором порядке) " имя", под которым храниться данное значение.

(задача - обратная к задаче доступа).

В реальности, эта одна задача. С конструктивной точки зрения, мы не не можем ответить на вопрос а), не предъявив такое x, что f(x)=y и не можем найти x в b), не выяснив, существует ли таковое вообще.

b, x: =y Î Val(f)» $ x Î Dom(f) (f(x)=y), min{x'Î Dom(f): f(x')=y}

Решение предполагает наличия некоторого порядка перебора на Dom(f)={x₁,.., x_n,..}.Тривиальное решение задачи - линейный поиск - мгновенно следует из схемы вычисления $-свойств (см. " Вычисление свойств" ) в данном случае основанном на реккурентном отношении:

(*) $ x Î {x₁,.., x_n,..} (f(x)=y) »(f(x₁)=y) or $ x Î {x₂,.., x_n,..} (f(x)=y))

procedure LinearSearch(f: tStructure; y: tVal; var b: boolean; var x: tDom);

begin

b: =false; i: =1;

while (i< =LenDom) and not b do if f(x_i)=y then begin b: =true; x: =x_iend else inc(i)

end;

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

Ограниченный поиск . Первая идея " сокращения пространства поиска" основана на простом наблюдении - в случае монотонности f бесполезно проверять равенство f(x)=y для тех x, для которых f(x)> y:

$ x Î tDom (f(x)=y)» $ x Î {x₁, …, x_k} (f(x)=y), где k=min {k': f(x_k) ³ y}.

Идея дихотомического поиска (поиска методом деления пополам) также предполагает упорядоченность f и основана на соотношении

(*) $ x Î {x_n1,.., x_n2} (f(x)=y) »

$ x Î {x_n1,.., x_m} (f(x)=y)) xor $ x Î {x_m+1,.., x_n2} (f(x)=y)), где m=(n1+n2) div 2 »

(для монотонной f)

(f(x_m)=y) xor

(f(x_m)< y) & $ x Î {x_n1,.., x_m-1} (f(x)=y)) xor

(f(x_m)> y) & $ x Î {x_m+1,.., x_n2} (f(x)=y))

(т.е. в реальности делим Dom(f) на 3 части, не на 2)

Дихотомический поиск считается быстрым поиском, поскольку позволяет найти ответ не более, чем за ln₂ n сравнений, в то время как верхняя оценка линейного поиска - n сравнений (где n=Card(Dom) - число элементов в пространстве поиска Dom).

Идея ограниченного поиска непосредственно продолжается на деревья (и графы) специального вида - деревья поиска. Дерево в качестве хранилища есть некая функция f, f: A*à T, где A* - множество путей (ветвей) дерева, а Т - содержимое его вершин. Самый простой случай бинарных деревьев - A={0< 1}.

Функция f, f: {0< 1}*à < T, < _T> - дерево поиска, если оно f монотонна относительно лексикографического порядка < < на словах: " v1, v2 Î {0, 1}* (v1< < v2 à f(v1)< _Tf(v2))

procedure OrderedTreeSearch(f: tOrderedTree; y: tVal; var b: boolean; var x: tDom);

begin

b: =false; v: =ПустоеСлово;

while (v Î Dom) and not b do

begin

if f(v)=y then b: =true

else if f(v)> y then v: =vÅ 0 else v: =vÅ 1;

end;

Здесь Å - операция приписывания (конкатенации) буквы к слову.

12 3 Следующая ⇒

Последнее изменение этой страницы: 2017-03-14; Просмотров: 508; Нарушение авторского права страницы