Технология программирования.
Параметры-переменные и значения. Глобальные и локальные объекты. Семантика обращений. Побочные эффекты. Демонстрация технологии на примере.
Возможны 2 естественных порядка (стратегии, принципа) определения процедур. Принцип композиции - от данных средств реализации (т.е. языка программирования ЯП) к желаемой цели (логике, языку спецификаций) - восходящее программирование – первоначально кажется наиболее естественным, поскольку следует порядку порождения процедур в ЯП и их последующего применения к данным (порядку вычисления). Однако, в силу связанного с таким порождением быстрого роста числа рассматриваемых случаев, такой подход, скорее - локальная тактика, применимая для разработки относительно небольших и несложных программ. Стратегия нисходящего программирования- цель (логика) важнее средств (реализации) - основана на принципе декомпозиции, последовательного перехода от определения на некотором исходном языке спецификации к более детальным определениям той же процедуры на все более бедных языках спецификаций. Это - чисто семантический принцип, не зависящий по существу от конкретного языка программирования. (В реальности же, как всегда, успех обеспечивает лишь сочетание стратегии и тактики!)
Термин "технология" предполагает наличие некоторого языка фиксации, описания этапов процесса собственного мышления при разработке сложной программы. Аппарат определения пользовательских типов данных и пользовательских процедур позволяет определять нужные языки спецификации средствами самого языка программирования, реализовывая принцип упреждающего именования - возможности обращения, т.е. формального использования имен ("заголовков") функций (операторов) прежде, чем они фактически определяются как выражения языка программирования.
Определение пользовательской процедуры есть сопоставление пользовательскому имени функции (оператора) выражения ЯП, называемого телом процедуры. На уровне семантики, это разграничение определяют как различие между интерфейсом и реализацией процедуры.
Единственной - но критичной! - сложностью такого предварительного определения (объявления) имени является выделение (именование и определение типа) входных и выходных значений - (возможно, совпадающих) имен аргументов и результатов процедуры как функции а также, возможно,именглобальных значений - т.е. его параметров как функции (в общематематическом, а не узко-программистском смысле термина). В реальности, существующая традиция предполагает выделение непересекающихся множеств имен - т.н. формальных параметров-значений - "собственно" входов, не являющихся выходами, и параметров-переменных - всех выходов, т.е. изменяемых значений. Имена глобальных объектов при этом никак не выделяются. Последующее фактическое определение тела процедуры, как правило, также требует введения вспомогательных объектов, удовлетворяющих локальным, т.е. временным определениям.
Пример порядка разработки при нисходящей стратегии (восходящая предполагает обратный порядок!).
Задача. Вычисление значения комплексного многочлена a степени Deg(a). Спецификация-постусловие (неявно, предполагает знание типа "арифметика комплексных чисел"): y(a,x):=S{ai*xi:iÎ[1..Deg(a)]}, xÎComplex, "iÎ[1,Deg(a)](aiÎComplex).
1) Решаем задачу в терминах ее постановки (спецификации). Объявляем имена нужных пользовательских типы и процедур.
type
tIndex=? ; {номера коэффициентов}
tComplex=?; {комплексные числа}
tComplexPolynom=? {комплексные многочлены}
procedure SetZero(var c:tComplex); {c:=0} ?
function Degree(p:tPolynom):tIndex; {определить степень полинома}?
function Element(p:tPolynom,i:tIndex):tComplex;{определить значение коэффициента}?
procedure Mult(a,b:tComplex;var c:tComplex); {c:=a ´ b} ?
procedure PolynomValue(Polynom: tComplexPolynom; var y: tComplex);
var
Coefficient:tComplex; { коэффициент полинома }
i, {его номер}
DegA:tIndex; {степень полинома}
begin
SetZero(y);{y:=0}
DegA:=Degree(Polynom);
for i:=1 to DegA do
begin
Coefficient:= Element(Polynom,i); { Coefficient := ai }
Mult(y, Coefficient,y);{y:=y*x+ai;}
end; {for}
end; {procedure PolynomValue }
Выделены операторы типа "арифметика комплексных чисел" - или, в более программистской терминологии, "подзадачи"
2) Даем фактическое определение пользовательских объектов - желательно такое, чтобы обеспечить наиболее эффективное вычисление основного алгоритма (при восходящем программировании, наоборот, реализация типов управляет их логикой). Если такое определение тривиально, можно, исходя из соображений эффективности, сразу подставить значение (а именно - модифицированное тело, см. далее) в исходный текст.
tIndex=1..100; {строго говоря - ограничиваем постановку}
tComplex=record x,y:real end;
tComplexPolynom=record Coefficient:array[tIndex] of tComplex; Degree:tIndex end;
procedure SetZero(c:tComplex); beginc.x:=0;c.y=0end;
{function Degree(p:tPolynom):tIndex; = p.Degree}
{function Element(p:tPolynom,i:tIndex):tComplex;=p.Coefficient[i]}
procedure Mult(a,b:tComplex;c:tComplex);
begin
c.x:=a.x*b.x-a.y*b.y;
c.y:= a.x*b.y+a.y*b.x;
end;
procedure PolynomValue(Polynom: tComplexPolynom; var y: tComplex);
var
{Coefficient:tComplex; = Polynom.Coefficient[i]}
i:tIndex; {номер коэффициента}
{DegA:tIndex; =Polynom.Degree}
begin
SetZero(y);{y:=0}
for i:=1 to Polynom.Degree do Mult(y,Polynom.Coefficient[i],y);{y:=y*x+ai;}
end; {PolynomValue }
Выделена реализация операторов языка спецификации. Понятно, реализовали полином "псевдодинамическим" массивом (а не, скажем файлом или списком) для того, чтобы быстрее и компактнее вычислить функции Degree и Element. Несмотря на то, что пришлось фактически ограничить постановку исходной задачи.
Формальная семантика обращения к (не рекурсивным) процедурам может быть точно описана в терминах 3-х правил преобразования (изменения) тела процедуры - построения модифицированного тела процедуры - функционально эквивалентного данному обращению фрагмента программы, уже не использующего обращений.
1) Избавление от конфликта (коллизии) имен. В случае совпадения имен формальных параметров и имен локальных объектов с именами глобальных объектов - замени их на новые, уже не несовпадающие.
2) Формальная семантика параметров-значений. Перед телом процедуры проставь операторы присваивания V:=E, V - имя формального параметра, E - соответствующее ему в обращении выражение (фактический параметр-значение)
3) Формальная семантика параметров-переменных. Замени в тексте процедуры все вхождения имен параметров на соответствующие им при обращении имена переменных (фактический параметр-переменная).
Пример построения модифицированного тела процедуры.
{процедура линейного поиска значения в массиве}
{спецификация: found:=x Îa » $ iÎ [1..LenA] (x=ai) }
procedure poisk(x:T;A:tArray;LenA:tIndex; var found:boolean);
var i:tIndex;
begin
found:=false; i:=1;
while (i<=LenA) and not found do if A[i]=x then found:=true else inc(i)
end;
Построим обращение для poisk(2*i,X,10,b) » ?
1) (Избавление от коллизии имен)
found:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then found:=true else inc(i1)
2) (Присваивание значений параметров-значений)
x1:=2*i; a:=x;LenA:=10; found:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then found:=true else inc(i1)
3) (Замена имен параметров-переменных)
4) x1:=2*i; a:=x;LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)
т.е. poisk(2*i,X,10,b) » x1:=2*i; a:=x; LenA:=10; b:=false; i1:=1; while (i1<=LenA) and not found do if A[i1]=x1 then b:=true else inc(i1)
Побочный эффект - фактическое изменение значений глобальных объектов в теле процедуры, не отражаемое формально, т.е. синтаксически, при обращении к процедуре - а потому, неявное для программиста - пользователя процедуры.
Пример побочного эффекта. Пусть процедура линейного поиска теперь реализована так
procedure poisk(x:T;A:tArray; var found:boolean);
{found:=$iÎ[1..LenA](x=ai)}
{var i:tIndex; - сэкономили память!}
begin
found:=false; while (LenA>=0) and not found do if A[i]=x then found:=true else dec(Len)
end;
В отличие от параметров процедуры, глобальные объекты никак не участвуют в модификации тела процедуры, потому обращение вида poisk(x,a,b) не только найдет правильное значение b, но и обнулит значение глобальной переменной LenA, содержащую по смыслу фактическую длину массива а и тем самым "закроет" его элементы для дальнейшей обработки.
Потому - либо а) (правило полной локализации) вообще не используй локально (т.е. в теле процедуры) глобальные объекты, либо, как минимум б) не изменяй их значений в теле процедуры. В любом случае использования глобальных объектов помечай такое использование синтаксически (в виде комментария).
Классификация типов данных.
(Начни с определения понятия абстрактного типа данных как области - пары <A,F>, FÍAàA – см. §1).
Примеры базовой семантики конкретных типов языка Паскаль (в реальности, как мы хорошо знаем, каждый тип обогащен множеством других функций)
Real, integer - арифметика вещественных и целых чисел,
string - полугруппа слов относительно операции конкатенации (сцепления слов),
array[I] of T - множество всех функций IàT, c операцией App применения (аппликации) функции к аргументу, App(a,i)=a[i],
record n1:T1;…;nm:Tm end - именованное декартово произведение (определение см. §1) основных множеств типов T1,…,Tm с конечным множеством имен {n1,…,nm}, с операцией аппликации, App(r,n)=r.n,
file of T - множество всех последовательностей NàT, c операторами:
reset(f) » маркер(f)=0; режим(f):=чтение;
read(f,x) » inc(маркер(f));x:=f(маркер(f))
область определения: (режим(f)=чтение)& (маркер(f)Î Dom(f))
rewrite(f) » маркер(f)=0; режим(f):=запись;f:=<> (пустая последовательность)
write(f,e) » inc(маркер(f));f(маркер(f)):=e;
область определения: (режим(f)=запись)
eof(f) » маркер(f)Î Dom(f) » компонента f(маркер(f)) определена
где маркер(f), режим(f) - некоторые вспомогательные системные (т.е. предопределенные, не определяемые пользователем) переменные.
(В отличие от объектного подхода), классический процедурный стиль склоняется к раздельному описанию
а) способов определения основного множества значений А, при фиксированном классе функций F (собственно, и относимых к определению типа) и
б) способов определения класса F - преобразований значений типа (см. § 2).
Это определяет и соответствующую классификацию типов по способу определений значений основного множества.
1) Разделение между скалярными и производными типами уже проведено в §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}
Примеры порядковых типов Паскаля -
integer - succ(n)=n+1,
char, - succ(ci)= ci+1 (ci - - i-ый символ в предопределенном языком фиксированном алфавите, таблице символов)
Boolean - false<true
Значения производных типов (array T1 of T2, record, file of T) обычно не считаются порядковыми, но нужный порядок можно (до)определить, если соответствующие базовые типы - порядковые (см. перечисление последовательностей в §10 и §11). Очень интересны примеры
- типа real, на котором определено обычное сравнение чисел, но из теоретических «мощностных» соображений не может быть определена соответствующая функция следования - не существует наименьшего вещественного числа, большего данного.
- множества всех бесконечных последовательностей, с теми же свойствами. (см. "Перечисление последовательностей").
Они не являются порядковыми типами, но могут быть приближены таковыми с любой наперед заданной степенью точности. Так, вещественные числа приближаются рациональными, бесконечные последовательности - конечными (подробнее - вспомни. курс мат. анализа)
4) Динамические и статические производные типы. Значения производных типов - функции. Область их определения может быть фиксирована (статический тип) - пример - множество всех функций [1,n]àT для фиксированного n, либо нет (динамический тип), пример - множество всех функций [1,n]àT для произвольного n. Примеры статических типов - record, статический array (в стандартном Паскале); динамических - file, string, динамический array ( в Object Pascal).
В последнем случае определение типа предполагает явное или неявное наличие соответствующих операторов расширения и сужения области определения. Примеры - оператор Паскаля SetLength явного установления области определения динамических массивов; оператор write увеличивает длину файла неявно.
Практический интерес представляют типы, которые можно назвать псевдодинамическими. Это функции, область определения которых не фиксирована, но содержится в некотором фиксированном множестве значений. Пример: множество всех последовательностей f с длиной менее заданной, f:[1..n]àT, n<nMax. В практическом программировании необходимо учитывать конечность памяти - в реальности, все динамические типы являются псевдодинамическими!
5) Абстрактныетипы. Совершенно иной смысл имеет условное разделение абстрактных и конкретных типов. Абстрактные типы - типы, точно определяемые как математические объекты (объекты некоторого языка спецификаций), но не как объекты данного языка программирования. Пример - комплексные числа и точки плоскости не есть тип Паскаля, тип record x,y: real end - тип Паскаля. Установление соответствия между (значениями и операциями) абстрактного и конкретного типов называется реализацией (определением, моделированием или представлением) абстрактного типа.
6) Тесно связано с понятием реализации (как способа определения) деление типов по способам доступа. На практике, программисту важен именно способ определения, задания объекта/функции. Другое дело, что такие определения можно снова точно сформулировать в терминах функций/операторов. Существует три важных вида таких определений: реккурентное (данные последовательного доступа, пример - файлы и списки, язык описания - функции следования), явное (данные прямого доступа, пример - массивы и записи, язык описания - оператор аппликации) и рекурсивное (пример - деревья и графы, язык описания - функции на последовательностях)
Пояснить классификацию типов на конкретном примере.
Задача: найти длину lmax самого длинного слова w (в текстовом файле f) и само это слово w; (слова представлены символьным списком.)
С абстрактной (логической) точки зрения, дана последовательность слов, с точки зрения реализации - динамический тип файл (последовательность символов). Здесь, постановка задачи уже фиксирует реализацию значений - но не операторов! Задача легко решается в терминах абстрактного типа (слова и их длины), основная сложность - реализовать соответствующие операции.
type
{список - абстрактный динамический пользовательский тип последовательного доступа}
slovo=^component;
component=record letter:char;next:slovo end;
{аналогично - найди место в каждой классификации для остальных типов, используемых в спецификации и реализации программы}
procedure P(var f:text; var lmax:integer; var w:slovo);
var v:slovo;
begin
lmax:=0;
w:=ПустоеСлово;
stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);
while not stop do
begin
if l>lMax then begin lmax:=l; Копировать(w,v) end;
{подготовка переменных к следующему проходу}
Уничтожить(v);
stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);
end;
Внимание - хитрость примера - обратное влияние или "побочный" эффект реализации - независимое определение функции КончилисьСлова (» остаток файла содержит хотя бы одно слово » хотя бы один не пробел) делает практически невозможным (точнее, сильно неэффективным) реализацию процедур OчередноеСлово и Длина. Отдельные, с точки зрения логики, операторы, могут быть реализованы только совместно.
procedure P(var f:text; var lmax:integer; var w:slovo);
var v:slovo;
begin
lmax:=0;
w:=nil; {w:=ПустоеСлово}
ОпределиКончилисьСловаЕслиНетОпределиОчередноеСловоИЕгоДлину(f,stop,v,l);
{читай файл до непробела/начала слова, если таковое есть - читай все непробелы в список v, одновременно подсчитывая их число в l}
while not stop do
begin
if l>lMax then begin lmax:=l; Копировать(w,v) end;
{подготовка переменных к следующему проходу}
Уничтожить(v);
ОпределиКончилисьСловаЕслиНетОпределиОчередноеСловоИЕгоДлину(f,stop,v,l);
end;
Замечание. Если есть трудности с реализацией порождения, уничтожения и копирования списков - см. "Абстрактные линейные типы данных"
Вычисление предикатов.
Предикат (свойство, условие) - произвольная функция с областью определения Boolean={true,false}. Пример (двуместных) предикатов - бинарные отношения, в частности, отношения сравнения <,>,=,<>.
Вычисление предикатов облегчается тем, что существует общематематический язык логики (исчисления предикатов) - исключительно выразительный и одновременно компактный - содержащий бинарные операции & (and, в синтаксисе Паскаля), Ú (or), Ø (not) - их относят к операциям алгебры логики, а также два квантора (оператора над множествами) " и $ (отсутствуют в Паскале). Перевод формулы из языка ИП в программу на структурном языке программирование - техническая задача, при учете следующих основных моментов.
1. Написание (спецификация) формул может быть само по себе достаточно сложной задачей. Математическая логика располагает множеством стратегий таких спецификаций в виде алгоритмов записи любого предиката в некоторой канонической (нормальной) форме. Наиболее простые из таких форм для бескванторных формул - днф (дизъюнкция элементарных коньюнкций), кнф (конъюнкция элементарных дизъюнкций); по определению, элементарные формулы могут содержать отрицание, но не знаки бинарных логических операций.
2. Для кванторных формул канонической является т.н. предваренная нормальная форма вида Q1x1… Qn xn B(x1,…,xn,z) ( где Qi - либо $ либо ", причем каждые два соседних квантора можно считать различными, а B уже не содержит кванторов).
Пример. Определить принадлежность точки p(x,y) к фигуре, составленной из 4 колец. Каждое кольцо задаваемется центром и длинами внутреннего и внешнего радиусов.
Решение - стратегия днф.
а) Точка принадлежит к фигуре, если она принадлежит одному из колец.
type
tPoint=record x,y:real end;
tRing=?
tFigure=array[1..n] of tRing;
function ПринадлежитФигуре(p: tPoint; figure:tFigure):boolean;
begin
ПринадлежитФигуре:=
ПринадлежитКольцу(p,figure[1]) or
ПринадлежитКольцу(p,figure[2]) or
ПринадлежитКольцу(p,figure[3])
end
b) Точка принадлежит кольцу, если она находится одновременно внутри внешнего и вне внутреннего окружностей кольца.
type
tRing =record center:tPoint; radius1,radius2:real end;
function ПринадлежитКольцу(p:tPoint; Ring:tRing):boolean;
begin
ПринадлежитКольцу:=
ПринадлежитОкружности(p,Ring.center,Ring.radius1) and
not ПринадлежитОкружности(p,Ring.center,Ring.radius2)
end;
d) Принадлежность точки P с заданными координатами Px,Py к окружности O c центром Ox,Oy и радиусом Oradius описывается атомарной формулой
(Px-Ox)2+(Py-Oy)2£ Oradius2
function ПринадлежитОкружности(p:tPoint,center:tPoint; radius:real):boolean;
begin
ПринадлежитОкружности:= sqr(P.x-Center.x)+sqr(P.y-Center.y)<=sqr(radius)
end;
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
Внимание - указанные эквивалентности верны лишь для определенных значений b1,b2. Программы 1) определенные значения y при неопределенном значении b2, программы 2) - нет. Семантика 1) соответствует т.н. быстрому означиванию операций и определяют т.н. условные коньюнкцию и дизъюнкции - строго говоря, отличных от классических (семантика 2). В Паскале эта неоднозначность ("темное" место языка) разрешается директивой компилятора $B. Разные значения директивы может сделать одну и ту же программу верной или неверной!
Задача (линейный поиск)
type
tIndex=1..MaxLen;
ArrayOfT=array[tIndex] of T;
procedure Poisk(x:T; a:ArrayOfT; LenA:tIndex; var found:boolean; var index:tIndex);
begin
index:=1;
while (index<=LenA) and (x<>a[index]) do inc(index);
found:= index<=LenA
end;
При быстром означивании формула (index<=LenA) and (x<>a[index]) при index=LenA+1 дает false (программа верна), при классическом - значение неопределено (программа неверна). Совет: желательно избегать неопределенных значений -
index:=1; found:=false;
while (index<=LenA) and not found do if x=a[index] then found:=true else inc(index);
4. Вычисление кванторных формул.
a) y:=$ xÎ X (B(x))
Рассмотрим частный (для классической логики), но наиболее важный для программирования (и конструктивной логики) случай. X - множество значений порядкового динамического типа, для которого определены функция следования (перебора) и предикат конца перебора значений - заданный, например, в виде сравнения. Тогда $ xÎ X (B(x)) - это кратная дизъюнкция, а y есть первый true в реккурентной последовательности y0=false, yi+1= yi or B(xi) (либо false, если такового нет). Поэтому, можно воспользоваться общей схемой вычисления членов реккурентных последовательностей:
y:= $ xÎ X (B(x)) »
y:=false; i:=1; while (i<=LenX) and not y do if B(xi) 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(xi) then y:=false else inc(i)
Пример вычисления кванторной формулы. Последовательность A длины LenA (строго) периодическая (или, попросту - кратная), если оно состоит из двух или более одинаковых "сцепленных" подпоследовательностей некоторой длины k, называемой в этом случае периодом A. Выяснить, является ли данная последовательность строго периодической.
Спецификация
b:=A - строго периодическая »
b:=$ k Î [1,LenA div 2] ( k - период A) »
b:=$ k Î [1,LenA div 2] ( LenA mod k =0 à " iÎ [1..LenA-k] (A[i]=A[i+k]))
type
tIndex:1..MaxLen;
tArray:array[tIndex] of T;
function Period(k:tIndex; a:tArray; LenA:tIndex):boolean;
var b2:boolean; UpperLimit2:tIndex; {= LenA-k }
begin
b2:=LenA mod k; UpperLimit2:= LenA-k; i:=1;
while (i<= UpperLimit2) and b do
if A[i]<>A[i+k] then b2:=false else inc(i)
Period:=b2
while
end;
function Periodic(a:tArray; LenA:tIndex):boolean;
var UpperLimit1:tIndex; {=LenA div 2} b1:boolean;
begin
b:=false; k:=1; UpperLimit:=LenA div 2;
while (k<=UpperLimit) and not b do
if period(k,A.LenA) then b:=true else inc(k);
Periodic:=b;
end;
§5. Поиск.
Основной интуитивный смысл структур данных - "хранилище" данных, обеспечивающее операции доступа (чтения) и записи, что, при формальном определении этих структур как функций соответствует вычислению следующих основных операторов
- аппликация (по хранилищу f и указателю/имени x определить значение f(x)),
- (пере)определению значения функции f в точке x новым значением y, и
- (для динамических типов) расширению/сужению области определения функции.
Понятие хранилища данных тесно связано по смыслу, но существенно шире по объему понятия структуры (производного типа). В качестве хранилища, при фиксации кодирования, могут выступать и скалярные значения. Так, например, по основной теореме арифметики, любое n,nÎ N, есть некоторое произведение степеней простых чисел P p(i) a(i) (p(i) i-е простое число). Следовательно, его можно рассматривать как хранилище последовательности а, т.е. потенциальную или "виртуальную", т.е. воображаемую структуру.
Важно уточнить, что фактически может храниться не сама функция (в табличном виде, пример - данные прямого доступа - массивы и записи), но способ ее определения - реккурентный (данные последовательного доступа, пример - файлы) или рекурсивный (пример - деревья)
Задача поиска формулируется в двух внешне различных формулировках.
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}
К задаче поиска легко сводяться многие важные задачи
- выяснить, храниться ли в структуре f значение с заданным свойством, в частности,
- выяснить, храниться ли в структуре f значение почти равное заданному (т.е. хорошее приближение заданного значения)
- определить все "имена", под которым храниться данное значение (значение с заданным свойством) и т.п.
В любом случае, решение предполагает наличия некоторого порядка перебора на Dom(f)={x1,..,xn,..}.Тривиальное решение задачи - линейный поиск - мгновенно следует из схемы вычисления $-свойств (см. "Вычисление свойств") в данном случае основанном на реккурентном отношении:
(*) $ x Î {x1,..,xn,..} (f(x)=y) »(f(x1)=y) or $ x Î {x2,..,xn,..} (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(xi)=y then begin b:=true;x:=xi end else inc(i)
end;
Понятно, это схема. Пересчет tDom и условие его окончания может выглядеть совершенно иначе.
Пример (поиск в конечном дереве и графе). Дерево (граф) в качестве хранилища - функция вида A*àT, A - некоторый алфавит, A* - множество всех конечных последовательностей (ветвей дерева), а T - тип вершин дерева (графа). Для решения задачи поиска достаточно определить некоторый порядок перебора ветвей.
procedure LinearSearch(f:tTree;y:tVal;var b:boolean;var x:tDom);
begin
b:=false; x:=ПервоеСлово; {естественно взять в качестве первого пустое слово - других может и не быть!}
while not КончилисьСлова(f) and not b do
if f(x)=y then begin b:=true else x:=Следующее(x)
end;
Окончание решения - см. "Перечисление последовательностей".
Очевидно, в худшем случае алгоритм линейного поиска требует полного перебора всех элементов tDom. Можно ли ускорить поиск? Да, если предполагать наличие некоторого сравнения (линейного порядка) < на tDom (в отличие от tDom, это не обязательно порядок перебора) и рассматривать в качестве хранилищ упорядоченные последовательности (или, в общем случае, монотонные функции) f: tDomàtVal
" x,x'Î tDom (x£x' à f(x)£.f(x'))
Ограниченный поиск. Первая идея "сокращения пространства поиска" основана на простом наблюдении - в случае монотонности f бесполезно проверять равенство f(x)=y для тех x, для которых f(x)>y :
$ x Î tDom (f(x)=y)» $ x Î {x1,…, xk} (f(x)=y), где k=min {k': f(xk) ³ y}.
{предусловие - f монотонна (упорядочена)}
procedure RestrictedSearch(f:tOrderedStructure;y:tVal;var b:boolean;var x:tDom);
var UpperLimitFound:boolean; {$ x Î tDom (f(x) ³ y)}; y1:tVal;
begin
{найди первое x, что f(x) ³ y}
UpperLimitFound:=false; i:=1;
while (i<=LenDom) and not UpperLimitFound do
begin y1:=f(xi); if y1>=y then begin UpperLimitFound:=true;x:=xi end else inc(i); end;
if UpperLimitFound then b:=y1=y else b:=false
end;
Пример применения схемы - поиск в упорядоченном файле
{предусловие - f монотонна (упорядочена)}
procedure RestrictedSearch(f:tOrderedFile;y:tVal;var b:boolean;var n:Cardinal);
var UpperLimitFound:boolean; {$ x Î tDom (f(x) ³ y)}; i:Cardinal;
begin
{найди первое x, что f(x) ³ y}
UpperLimitFound:=false;
reset(f); {j:=1} i:=0;
while not eof(f) {(i<=LenDom)} and not UpperLimitFound do
begin read(f,y1); {y1:=f(j);inc(j)}
if y1 >=y then begin UpperLimitFound:=true;n:=i end else inc(i);
end;
if UpperLimitFound then b:=y1=y else b:=false
end;
Идея дихотомического поиска (поиска методом деления пополам) также предполагает упорядоченность f и основана на соотношении
(*) $ x Î {xn1,..,xn2} (f(x)=y) »
$ x Î {xn1,..,xm} (f(x)=y)) xor $ x Î {xm+1,..,xn2} (f(x)=y)), где m=(n1+n2) div 2 »
(для монотонной f)
(f(xm)=y) xor
(f(xm)<y) & $ x Î {xn1,..,xm-1} (f(x)=y)) xor
(f(xm)>y) & $ x Î {xm+1,..,xn2} (f(x)=y))
(т.е. в реальности делим Dom(f) на 3 части, не на 2)
{предусловие - f монотонна (упорядочена)}
procedure Dichotomy(f:tOrderedStructure;y:tVal;var b:boolean;var x:tDom);
UpperLimit, LowerLimit:tDom; {верхняя и нижняя границы пространства поиска}
begin
b:=false; UpperLimit:=1; LowerLimit:=LenDom;
while (UpperLimit>LowerLimit) and not b do
begin
m:= (UpperLimit+LowerLimit) div 2;
if f(xm)=y
then b:=true
else if f(xm)<y then LowerLimit:=m else UpperLimit:=m
end; {while}
end; { procedure Dichotomy }
Традиционно дихотомический поиск считается быстрым поиском, поскольку позволяет найти ответ не более, чем за ln2 n сравнений, в то время как верхняя оценка линейного поиска - n сравнений (где n=Card(Dom) - число элементов в пространстве поиска Dom). Однако, нельзя забывать, что, в отличие от линейного поиска, этот алгоритм требует вычисления f(xm), которое может оказаться неоправданно дорогим - например, в случае поиска в файле.
Идея дихотомии (как и ограниченного поиска!) непосредственно продолжается на деревья (и графы) специального вида - деревья поиска. Дерево в качестве хранилища есть некая функция f, f:A*àT, где A* - множество путей (ветвей) дерева, а Т - содержимое его вершин. Разберем самый простой случай бинарных деревьев - A={0<1} (кратное обобщение на случай произвольного конечного A={a1<…< an} - техническая задача).
Функция f, f:{0<1}*à<T,<T > - дерево поиска, если оно f монотонна относительно лексикографического порядка << на словах (см. "Перечисление последовательностей") : " v1,v2 Î {0,1}* (v1<<v2 à f(v1)<T f(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;
end;
Здесь Å - операция приписывания (конкатенации) буквы к слову. В случае реализации деревьев ссылками (см. обозначения в "Нелинейные типы данных"):
v:=ПустоеСлово » p:=Root;
v:=vÅ0 » p:=p^.left
v:=vÅ1 » p:=p^.right
vÎ Dom » p<>nil
где Root, p - ссылки на корень и текущую вершину дерева.
§ 6. Упорядоченные типы.
Термин “(структурный) упорядоченный тип” по сути отсутствует в современных языках программирования как языковое понятие. Однако, логическая естественность определения и практическая польза часто вынуждает рассматривать упорядоченные последовательности (и монотонные функции, в целом) как абстрактный тип данных.
Естественные операции, призванные сохранять упорядоченность – вставка и удаление компонент, объединение (слияние), пересечение, разность последовательностей имеют явные теоретико-множественные корни:
С=Вставка(A,b) » " iÎ Dom(C) (ci Î A or ci =b) & Упорядочена(С)
С=Удаление(A,b) » " iÎ Dom(C) (ci Î A and ci ¹b) & Упорядочена(С)
С=A È B » " iÎ Dom(C) (ci Î A or ci Î B) & Упорядочена(С)
С=A Ç B » " iÎ Dom(C) (ci Î A and ci Î B) & Упорядочена(С)
С=A \ B » " iÎ Dom(C) (ci Î A and ci Ï B) & Упорядочена(С)
где xÎ f » $ iÎ Dom(f) (x=f(i))
Практическая мотивация их использования - в отличие от алгоритмов сортировки (см. след. тему), все следующие ниже алгоритмы однопроходные, т.е. сохранять упорядоченность легче, чем сортировать (особенно – для типов с последовательным доступом!)
Направляющая общая идея реализации - кратный ограниченный поиск в упорядоченной последовательности - для ответа на вопрос x Î a, достаточно найти “барьер”, т.е. первый ai такой, что x£ai. (Подробнее см. "Поиск").
1. Разность упорядоченных файлов. Здесь и далее TInfo – произвольный тип, на котором определен некоторый линейный порядок <.
Type
TFile=file of tInfo;
{предусловие – удобнее считать, что файл B не пуст}
procedure Разность( var A,B:tFile;
var C:tFile); {c:=a\b}
var
cA,cB:tInfo;{текущие элементы последовательностей}
BarrierFound, {= $i (сA<= bi)}
found:boolean; {cAÎ b}
begin
reset(A); reset(B);rewrite(C);
read(B,cB); {по условию файл B не пуст }
{ в противном случае, решение очевидно – скопировать A в C}
while not eof(A) do
begin
read(A,cA); BarrierFound:= cA<=cB ;
while not eof(B) and not BarrierFound do
begin
read(B,cB); if cA<=cB then BarrierFound:=true
end;
found:=false; if BarrierFound then if cA=cB then found:=true;
if not found then write(C,cA)
end;
end; { Разность }
2. Слияние массивов
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 Слияние }
3. Вставка в упорядоченный список
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;
§ 7. Сортировка.
Сортировка- преобразование данной последовательности x в упорядоченную (далее » монотонно неубывающую) последовательность, содержащую те же компоненты.Чуть более формальная спецификация-
Предусловие: VAL(x)=XÎ NàT
Постусловие:
VAL(x)=X’Î NàT & X’ монотонна & X’ – перестановка X
Мотивация - упорядоченность последовательностей обеспечивает более быстрый поиск (см. "Поиск").
Все излагаемые ниже алгоритмы сортировки основываются на простом факте: если F - некая процедура, применение которой к массиву увеличивает длину отсортированной части массива (скажем, максимального упорядоченного начального его фрагмента), то кратное применение F обязательно упорядочит весь массив.
 | |||
 |
Задача - найти такой оператор F - по возможности, с достаточно быс