хотели бы использовать для наших построений как можно меньший набор фундаментальных правил преобразований, однако описать их на высоком уровне, т. е. выделяя структурные связи. Для этого мы строим каталог схем преобразований высокого уровня, которые можно использовать для обнаружения и выражения преобразований, а при необходимости выразить в виде последовательности применений фундаментальных правил. Одним из таких преобразований высокого уровня является продвижение фильтра. Таким образом, мы приняли двухуровневый подход к представлению синтеза. В разд. 5 синтез выражен в понятиях высшего уровня. Каждый вывод представлен в виде исходной содержательной догадки или леммы, предположительно выражаюш,ей некоторый факт, на котором основан конкретный алгоритм, и следующей за ней последовательности преобразований высокого уровня, улучшающих эффективность. Почти все эти преобразования являются продвижениями фильтра. В разд. 6 каждое из этих преобразований раскрывается в терминах более фундаментальных преобразований.

5. СИНТЕЗ

5.1.

Наше определение на высшем уровне задает множество всех перестановок множества.

Р Яересг(Х)ч={ = [Х]Х и Биект{!,{Х],Х)},

Биект{1, Y,.X)i=f тотальная взаимно-однозначная функция из Y ца X.

5.2. Синтез Р1, Быстрой Сортировки и Сортировки Выбором из Р 5.2.1. Р1 из Р

Повторяя Р, мы имеем

1. Перест(X)<={f\f[X]XX и БиектЦ, [Х],Х)}, которое обобщается до

2. nepecT}{N,X){f\fNXX и Биект{f,N,X)}.

Первая необходимая для синтеза лемма состоит в том, что X = [] У. Фактически нам нет необходимости рассматривать

все подмножества из X, достаточно взять только имеющие одинаковый размер. Мы обозначим это X = [} Y, что означает

все подмножества из X мощности k, I Card(X).

В этом случае легко показать, что N XX = М (iV* X)U

и {к X " ))> и, таким образом, (2) можно переписать как

3. Перест! {N,X){f\fs [} {N XY)U (N Х{Х - У)) и Би-

ект(1 N, X) .

В разд. 6.1 МЫ покажем, что фильтр Биект можно поставить перед объединением. Мы получаем

4. Перест! {N, Х) [} {flUf2\flsNXYH Биект {fl, N\ Y)

Ъ NkX{X-y) Биект {f2, N,, X - Y)} и {fl\}f2\fl nepecTl{N\Y), f2ne-

pecTl {Nk, X - Y)} Свертка с (2).

Поскольку для любого вызова) Перест1{М, Y) Card(A) = = Card(F), мы должны рассмотреть следующие основные случаи.

Ъ. Перест 1 {Ф, Ф) -{Ф} Конкретизация (1) и правило RS1.

6. Перест1 {{п}, {х}) {{{пх)}} Конкретизация (1) и вычисление.

Таким образом, мы получаем алгоритм Р1.

Р1 Перест {X) Перест1 {[X], X) Перест1 (Ф, Ф) <= {Ф} HepecTl {{п}, {х}) {{{пх)}}

Перест1 {N, Х) \] {fl U /2 I е Перест1 (Л Y)

* f2 е Перест1 {М, X - Y)}.

5.2.2. Быстрая Сортировка из Р1. Определим Сорт как

1. Сорт {Х)<= Упоряд{Перест {X)), где

Упоряд: 2-*->2-* (отфильтровывает неупорядоченные перестановки).

2. Упоряд{X){f\fX я Упор(f)}

3. Упор(/) <=\/{nlxl)f, {п2х2)е f

п1 < п2 xl < х2.

Таким образом,

4. Сорт (Х)<= Упоряд {Перест {X))

<= Упоряд {Перест 1 {[X], X)) Развертка с использованием Р1,

) Вызовом (термин из программирования) называется вхождение функции с конкретными значениями ее аргументов. - Прим. перев.

И МОЖНО определить

5. СортЦМ, X)Упоряд(Перест!{N, X)). Тогда

6. СортЦФ, Ф)-{Ф} Конкретизация (5) и развертка с использованием Р1 и (2).

7. Сорт! {{п}, {х})<={{(пх)}} Конкретизация (5) и развертка с использованием Р!, (2) и (3).

8. Сорт! (N, X)<= Упоряд( [} {fl[}f2\f!G Перест! {М\ Y) f2 е Перест! [N, X - Y)} Конкретизация (5) и развертка Р!.

Непосредственное продвижение фильтра Упоряд (6.2) позволяет получить (9).

{Y <Х - Y означает, что >/yY, х X - Y • у <х).

9. Сорт! (N, X)

и {f!Uf2lf! Перест! {N\ Y) и Упор (f!) f2 е Пе-

Y<X-Y

рест!{М,, X-Y) и Упор {f2)} и {fi и /2 I/; е Сорт! {N\ Y) f2 е Сорт! {N,, X - Y)}

Y<X-Y

Свертка с (2) и (4).

Условия на У, YcznX и Y < X-Y означают, что для каждого k имеется только одно такое Y- Поэтому предыдущее может быть переписано так:

{fl[]f2\flCopT!{N\ Y)

f2CopT!{N,, X-Y)} где k = Card(Y)

для некоторого Y такого что Y < X - Y.

В полном алгоритме Сортировки Взбалтыванием мы получаем Y, выбрав некоторый элемент из X я затем разбив X на два множества, одно из которых содержит все элементы, меньшие выбранного, а другое - все большие элементы. Это можно синтезировать, определив

10. Фильтр{X)-i=Y такое что Ycz X и Y<iX-Y).

11. Фильтр! (х, X)<=Y та.ког что Y cz X и \fyY-y < х. Если мы рассмотрим случай х + Х, где хХ, то получим

12. Фильтр (х + Х)-*=Утакое что и Y<{x + X-Y).