пере: последовательность -> элемент

: - выбирает первый элемент последовательности пере {х-{- Х)х ост: последоеательность-* последоеательность :-выдает остаток последовательности

ост {х + Х)Х [ ]: множестео-* последоеательность

: - начальный отрезок последовательности натуральных чисел, равный по длине мощности данного множества

[Х]={1, 2, мощность X) последоеательность X целое-* последоеательность : - начальный отрезок последовательности, длина которого равна данному целому

(Пь П2, . . ., nif{nu П2.....Hk)

Nk- последоеательность X целоепоследоеательность : - остаток последовательности

П2, . . ., ni)k = {tk+l.....til).

Мы будем использовать следующие операции над функциями, понимаемыми как множества пар:

Область, Образ: функция-*множестео

: - Область (f) s {х \ (ху) е f} :-0браз{П{у\{ху)П -зн- функция X элемент -> функция

: - / -зк г = {{ху)\{ху) ! м у1 Ф у).

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

Можно представлять себе, что эти функции задают более привычные программистам массивы или списки; так, например, функция {</&>, <2а>, <5с>} задает массив [бас].

Использование такого «математического» представления для обычных структур данных делает наши алгоритмы более податливыми к формальным манипуляциям. Окончательные алгоритмы легко переводятся в более привычную форму с помощью «соотношения представлений» (Берстелл и Дарлингтон [1]) с помощью отображения множества упорядоченных пар в списки или массивы.

4. СТРУКТУРА И СПОСОБ ОПИСАНИЯ 4.1. Структура процессов синтеза

Вначале определим Перест - множество всех перестановок данного множества. Использование функций для представления массивов дает нам возможность определить Перест(X) просто как множество всех биективных (взаимно-однозначных и «на») функций из [X] в X. Как мы видели раньше, функции легко определить как фильтр на множестве всех подмножеств декартова произведения, и, таким образом, мы имеем

nepecT(X){f\f[X]XX и БиектЦ, [X], X)}

Биект if, Y, X)f есть тотальная взаимно однозначная функция из У на X.

Заметим, что данное определение типа «породить и проверить». Из этого определения высокого уровня, которое мы назовем Р, можно синтезировать рекурсивные алгоритмы, которые вычисляют Перест гораздо эффективнее. Производя синтез тремя различными способами, мы получим три различных алгоритма порождения перестановок, которые мы назовем Р1, Р2, РЗ.

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

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

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

Упоряд {X){f\fX и Упор if)}

ynopif)\/(nlxl)f, (n2x2)Gf, nl < п2х1 < х2.

Мы опять возьмем это определение типа «породить и проверить» и попытаемся произвести фильтрование- Для каждого из трех алгоритмов перестановок PI, Р2 и РЗ синтезируем два алгоритма сортировки, соответственно получая версии алгоритмов Быстрой Сортировки, Сортировки Выбором, Сортировки Слиянием, Сортировки Вставками, Сортировки Взбалтыванием и Сортировки Обменом.

Структура синтеза выглядит следующим образом:

4 i \

Р1 Р2 РЗ

i i i i i i

Быстрая Выбором Слиянием Вставками Обменом Взбалтыванием

Способы выведения первых четырех алгоритмов сортировки обладают приятной симметрией, тогда как характер вывода РЗ, Обмена и Взбалтывания иной. Разница в синтезе Р1 и Р2 состоит в том, что в Р1 работа по проверке биективности производится во время декомпозиции при прямом ходе рекурсии, тогда как в Р2 она выполняется на этапе восстановления при обратном ходе рекурсии.

При декомпозиции множества S возможен выбор: либо расчленить его на два подмножества 5/ и 52, такие, что 5/ П 52 = = Ф и 5/U52 = 5, либо на элемент s и множество SI, такие, что 5=={s}U5/. Именно эти варианты приводят от Р1 либо к Быстрой Сортировке, либо к Сортировке Выбором, а от Р2- либо к Сортировке Слиянием, либо к Сортировке Вставками. В сортировках Быстрой и Слиянием рекурсия осуществляется декомпозицией множества на непересекающиеся подмножества, в то время как в сортировках Выбором и Вставками декомпозиций на элемент и множество. РЗ же по существу бесконечный алгоритм, работающий циклически в пространстве всех перестановок. Обмен и Взбалтывание различаются по способу движения в этом пространстве на пути к упорядоченной перестановке.

Идея определить сортировку как выбор упорядоченной перестановки уже использовалась Бобом Ковальским и Мартеном ван Емденом в их работе по программированию с использованием логики предикатов.

4.2. Способ описания процессов синтеза

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