Методическое пособие для подготовки к государственному экзамену по информатике для студентов специальности «Прикладная математика»

5. 
   Абстрактные типы. Совершенно иной смысл имеет условное разделение абстрактных и конкретных типов. Абстрактные типы - типы, точно определяемые как математические объекты (объекты некоторого языка спецификаций), но не как объекты данного языка программирования. Пример - комплексные числа и точки плоскости не есть тип Паскаля, тип record x,y: real end - тип Паскаля. Установление соответствия между (значениями и операциями) абстрактного и конкретного типов называется реализацией (определением, моделированием или представлением) абстрактного типа.
   
6. 
   Тесно связано с понятием реализации (как способа определения) деление типов по способам доступа. На практике, программисту важен именно способ определения, задания объекта/функции. Другое дело, что такие определения можно снова точно сформулировать в терминах функций/операторов. Существует три важных вида таких определений: реккурентное (данные последовательного доступа, пример - файлы и списки, язык описания - функции следования), явное (данные прямого доступа, пример - массивы и записи, язык описания - оператор аппликации) и рекурсивное (пример - деревья и графы, язык описания - функции на последовательностях)
   

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

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;

stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);

while not stop do

begin

{подготовка переменных к следующему проходу}

Уничтожить(v);

stop:= КончилисьСлова(f); v:=Oчередное слово(f); l:= Длина(v);

end;

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

var v:slovo;

begin

lmax:=0;

ОпределиКончилисьСловаЕслиНетОпределиОчередноеСловоИЕгоДлину(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;
Замечание. Если есть трудности с реализацией порождения, уничтожения и копирования списков - см. "Абстрактные линейные типы данных"

1. 
   Написание (спецификация) формул может быть само по себе достаточно сложной задачей. Математическая логика располагает множеством стратегий таких спецификаций в виде алгоритмов записи любого предиката в некоторой канонической (нормальной) форме. Наиболее простые из таких форм для бескванторных формул - днф (дизъюнкция элементарных коньюнкций), кнф (конъюнкция элементарных дизъюнкций); по определению, элементарные формулы могут содержать отрицание, но не знаки бинарных логических операций.
   
2. 
   Для кванторных формул канонической является т.н. предваренная нормальная форма вида Q₁x₁… Q_n x_n B(x_1,…,x_n,z) ( где Q_i - либо  либо , причем каждые два соседних квантора можно считать различными, а B уже не содержит кванторов).
   

Решение - стратегия днф.

а) Точка принадлежит к фигуре, если она принадлежит одному из колец.

type

tRing=?

begin

ПринадлежитКольцу(p,figure[1]) or

ПринадлежитКольцу(p,figure[2]) or

ПринадлежитКольцу(p,figure[3])

end

b) Точка принадлежит кольцу, если она находится одновременно внутри внешнего и вне внутреннего окружностей кольца.

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;

4. 
   Принадлежность точки P с заданными координатами Px,Py к окружности O c центром Ox,Oy и радиусом Oradius описывается атомарной формулой
   

function ПринадлежитОкружности(p:tPoint,center:tPoint; radius:real):boolean;

begin

ПринадлежитОкружности:= sqr(P.x-Center.x)+sqr(P.y-Center.y)<=sqr(radius)

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

1. 
   y:=not b  if b=true then y:=false else y:=true
   
2. 
   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;
   
3. 
   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
   

Задача (линейный поиск)

type

tIndex=1..MaxLen;

procedure Poisk(x:T; a:ArrayOfT; LenA:tIndex; var found:boolean; var index:tIndex);

begin

index:=1;

found:= index<=LenA

end;

При быстром означивании формула (index<=LenA) and (x<>a[index]) при index=LenA+1 дает false (программа верна), при классическом - значение неопределено (программа неверна). Совет: желательно избегать неопределенных значений -

while (index<=LenA) and not found do if x=a[index] then found:=true else inc(index);

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

1. 
   y:= x X (B(x))
   

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)

Спецификация

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

tArray:array[tIndex] of T;

var b2:boolean; UpperLimit2:tIndex; {= LenA-k }

begin

b2:=LenA mod k; UpperLimit2:= LenA-k; i:=1;

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;

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(i) ^a(i) (p(i) i-е простое число). Следовательно, его можно рассматривать как хранилище последовательности а, т.е. потенциальную или "виртуальную", т.е. воображаемую структуру.

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

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

1. 
   b:=y  Val(f)  x  Dom(f) (f(x)=y) - выяснить, храниться ли данное значение y в структуре f.
   
2. 
   x:=min{x': f(x')=y} определить первое (в некотором порядке) "имя", под которым храниться данное значение.
   

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

• 
  выяснить, храниться ли в структуре f значение с заданным свойством, в частности,
  
• 
  выяснить, храниться ли в структуре f значение почти равное заданному (т.е. хорошее приближение заданного значения)
  
• 
  определить все "имена", под которым храниться данное значение (значение с заданным свойством) и т.п.
  

В любом случае, решение предполагает наличия некоторого порядка перебора на 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

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

end;

Понятно, это схема. Пересчет tDom и условие его окончания может выглядеть совершенно иначе.

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

begin

b:=false; x:=ПервоеСлово; {естественно взять в качестве первого пустое слово - других может и не быть!}

if f(x)=y then begin b:=true else x:=Следующее(x)

end;

Окончание решения - см. "Перечисление последовательностей".

 x,x' tDom (xx'  f(x).f(x'))

• 
  x  tDom (f(x)=y)  x  {x₁,…, x_k} (f(x)=y), где k=min {k': f(x_k)  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}

while (i<=LenDom) and not UpperLimitFound do

begin y1:=f(x_i); if y1>=y then begin UpperLimitFound:=true;x:=x_i 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}

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;

end;
Идея дихотомического поиска (поиска методом деления пополам) также предполагает упорядоченность 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)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)
{предусловие - f монотонна (упорядочена)}

procedure Dichotomy(f:tOrderedStructure;y:tVal;var b:boolean;var x:tDom);

UpperLimit, LowerLimit:tDom; {верхняя и нижняя границы пространства поиска}

begin

while (UpperLimit>LowerLimit) and not b do

begin

m:= (UpperLimit+LowerLimit) div 2;

then b:=true

else if f(x_m)

end; {while}

end; { procedure Dichotomy }
Традиционно дихотомический поиск считается быстрым поиском, поскольку позволяет найти ответ не более, чем за ln₂ n сравнений, в то время как верхняя оценка линейного поиска - n сравнений (где n=Card(Dom) - число элементов в пространстве поиска Dom). Однако, нельзя забывать, что, в отличие от линейного поиска, этот алгоритм требует вычисления f(x_m), которое может оказаться неоправданно дорогим - например, в случае поиска в файле.
Идея дихотомии (как и ограниченного поиска!) непосредственно продолжается на деревья (и графы) специального вида - деревья поиска. Дерево в качестве хранилища есть некая функция f, f:A*T, где A* - множество путей (ветвей) дерева, а Т - содержимое его вершин. Разберем самый простой случай бинарных деревьев - A={0<1} (кратное обобщение на случай произвольного конечного A={a₁<…< a_n} - техническая задача).
Функция f, f:{0<1}*T > - дерево поиска, если оно f монотонна относительно лексикографического порядка << на словах (см. "Перечисление последовательностей") :  v1,v2  {0,1}* (v1<T f(v2))
procedure OrderedTreeSearch(f:tOrderedTree; y:tVal; var b:boolean; var x:tDom);

begin

while (v  Dom) and not b do

begin

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

end;

Здесь  - операция приписывания (конкатенации) буквы к слову. В случае реализации деревьев ссылками (см. обозначения в "Нелинейные типы данных"):

v:=ПустоеСлово  p:=Root;

v:=v0  p:=p^.left

v:=v1  p:=p^.right

v Dom  p<>nil

где Root, p - ссылки на корень и текущую вершину дерева.