Сложность алгоритмов сортировки на частично упорядоченных множествах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1 Введение

1.1 Краткие исторические сведения.

1.2 Постановка задачи

1.3 Основные результаты.

2 Сортировка декартовых произведений частично упорядоченных множеств

2.1 Автоморфизмы декартовых произведений частично упорядоченных множеств.

2.2 Нижняя оценка L{M\ х . х Мп).

2.3 Верхняя оценка L(M\ х . х Мп).

3 Сортировка сумм частично упорядоченных множеств

3.1 Нижняя оценка L(M + N).

3.2 Верхняя оценка L(M + N).

3.3 Нижняя оценка L{nM).

3.4 Верхняя оценка L(nM).

3.5 Анализ качества полученных оценок L(nM)

3.5.1 Анализ нижней оценки

3.5.2 Асимптотическая оценка L(mL.

3.5.3 Анализ верхней оценки.

4 Сложность извлечения информации из частично упорядоченных множеств

4.1 Возможность достижимости минимума сложности извлечения информации из частично упорядоченных множеств

4.1.1 Достижимость в среднем

4.1.2 Оценка для семейства Мп т ь

4.2 Плотность сложности извлечения информации из частично упорядоченных множеств.

4.3 Достижимость максимума сложности извлечения информации из частично упорядоченных множеств.

4.4 Неустойчивость сложности извлечения информации к удалению элементов из частично упорядоченного множества

1.1 Краткие исторические сведения

Задача сортировки является одной из известнейших задач теории алгоритмов. Как пишет Кнут в своей монографии [5]: ". история сортировки была тесно связана со многими нехоженными тропами в вычислениях: с первыми машинами для обработки данных, первыми запоминаемыми программами, первым программным обеспечением, первыми методами буферизации, первой работой по анализу алгоритмов и сложности вычислений."

В классической постановке задача сортировки состоит в поиске для данных п чисел xi,.,xn перестановки 7г £ S(n), при которой последовательность чесел 2^(1),., Хп(п) упорядочена по восрастанию. Под сложностью алгоритма сортировки подразумевают количество необходимых ему сравнений в худшем случае. Из мощностных соображений сложность произвольного алгоритма сортировки оценивается снизу через log2 (п!).

Впервые потребность в быстрой сортировке больших объемов информации возникла в связи с переписью населения в Соединенных Штатах. И уже в конце XIX века появились первые электромеханические сортировочные машины. Таким образом, исторически первой возникла поразрядная сортировка. Как только в начале 40-х годов на сцене появились ЭВМ — разработка методов сортировки тесно переплелась с их развитием. Стали появляться различные модификации сортировки слиянием и вставками сложности O(nlogn) для п элементов, а также возникло естественное разделение на внутреннюю и внешнюю сортировки. Расцвет борьбы за качество алгоритмов решения задачи сортировки приходится на 50-е и 60-е годы. Именно тогда были изобретены столь широко известный метод Шелла, быстрая сортировка Хоара, пирамидальная сортировка и сортировка вставками в дерево.

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

Во-первых, это работы по улучшению качества классических алгоритмов сортировки. Исследователи старались более тонко подогнать параметры уже известных методов [21] или умело скомбинировать несколько методов в одном алгоритме (например, цифровой сортировки и сортировки слиянием) [16, 24].

Во-вторых, изучались различные подклассы входных последовательностей, на которых время работы алгоритмов сортировки существенно меньше, чем в общем случае. В качестве входного набора брали последовательность сумм чисел из ограниченного множества [17] или, например, класс частично отсортированных последовательностей [19].

Третьим, наиболее интенсивно развивающимся направлением является решение задачи сортировки в классе параллельных алгоритмов. Для модели PRAM были придуманы как оригинальные алгоритмы [22], так и обобщения ранее известных парадигм (например, сортировки слиянием [14]). Кроме того, алгоритмы сортировки конструировались для сортирующих сетей [25] и многомерных вычислительных решеток [15, 23].

Относительно недавно стали появляться работы, в которых задача сортировки исследуется на частично упорядоченных множествах [6, 7, 8, 9, 10, 20]. Были сформулированы три смежные задачи: задача сортировки частично упорядоченного множества М (используя результаты попарных сравнений элементов множества М установить порядок его элементов зная, что множество М изоморфно известному образцу Mq, ) задача распознавания частично упорядоченного множества М (определить, является ли множество М изоморфным множеству Mq) и задача определения порядка на множестве М (без априорной информации). Приведем основные результаты по задаче сортировки частично упорядоченных множеств за этот период.

Для нескольких семейств частично упорядоченных множеств были получены точные значения сложности сортировки. В частности было доказано, что если множество М состоит из п — 2 попарно несравнимых элементов и одной 2-х элементной цепи, то сложность его сортировки равна 2

-Цр1 [20]. Была установлена асимптотика п2п сложности сортировки для n-мерного двоичного куба Вп [6, 20]. Кроме того в [20] было показано, что сложность сортировки частично упорядоченного множества М мощности п и ширины w заключена между п log3 п — п log3 w — 5п и 2wn log2 n + 3wn.

1.2 Постановка задачи

Поставим задачу сортировки для частично упорядоченных множеств (далее — ЧУМ). Множество М = {х\,., хт} называется частично упорядоченным [2], если на его элементах задано отношение частичного порядка

R. Далее мы будем использовать для ЧУМ обозначение (М, R). Результатом применения отношения R к паре элементов Х( и Xj (т.е. результатом операции x^Rxj) может быть одно из четырех значений: больше (>), меньше (<), равны (=) или несравнимы (?). Отношение R естественным образом порождает четыре отношения >,<,=,? со значениями истина или ложь.

Пусть (х > у) = (х > у) У (х = у). Диаграммой Хассе ЧУМ (M,R) [2] называется ориентированный граф G = (V,E), для которого существует взаимно однозначное отображение / : М —>• V такое, что (/(ж), f(y)) Е Е тогда и только тогда, когда \{z : (х > z) Л (z > ?/)}| = 2. Таким образом, выполнение отношения х > у равносильно существованию в графе G невырожденной ориентированной цепи из вершины f(x) в вершину f(y).

Определим задачу сортировки ЧУМ следующим образом. Пусть задано множество М = {^1,., хт} с отношением частичного порядка R и ориентированный граф G = (V,E) диаграммы Хассе ЧУМ (M,R). Задача сортировки состоит в построении отображения : М —V V, при котором для любых i,j G {1,. ,ш} имеем: Х( > Xj тогда и только тогда, когда в графе G существует невырожденная ориентированная цепь из (р(х{) в (fi{xj). Далее мы будем называть отображение сборкой. Две сборки цэ и ср' мы будем называть изоморфными, если на графе G существует такой автоморфизм ф : V —»• V, что у/ = ф(р.

Алгоритмом сортировки ЧУМ (М, R) назовем произвольный алгоритм решения задачи сортировки для данного ЧУМ, использующий результаты последовательного применения отношения R к парам различных элементов из множества М. При этом результатом сравнения двух элементов из М может быть одно из трех значений: больше, меньше или несравнимы. Время работы алгоритма сортировки при заданном входе равно количеству обращений к отношению R. Сложность алгоритма сортировки равна времени работы алгоритма в худшем случае (максимальному времени работы по всевозможным входам). Алгоритм, который в худшем случае делает минимальное число сравнений, мы назовем оптимальным. Сложность оптимального алгоритма сортировки множества М обозначим через L(M).

Описанная задача сортировки для ЧУМ является обобщением задачи сортировки линейно упорядоченного множества по убыванию [1, 5] (для данного линейно упорядоченного множества Lm = {х\,.,хт} с отношением порядка " > " найти такую перестановку тг Е S(m), чтобы тогда и только тогда, когда г < j). Особенностью задачи сортировки для ЧУМ в нашей постановке является неоднозначность получаемого отображения ip в случае существования нетривиальных автоморфизмов множества М. Таким образом, отображение <р не всегда совпадает с отображением / из определения диаграммы Хассе.

1. Ахо А.В., Хопкрофт Дж., Ульман Дж., Построение и анализ вычислительных алгоритмов, М., 1979

2. Биркгоф Г., Барти Т., Современная прикладная алгебра, М., 1976

3. Боровков А.А., Теория вероятности, М., 1986

4. Ильин В.А., Садовничий В.А., Сендов Б.Х., Математический анализ, М., 1979

5. Кнут Д., Искусство программирования для ЭВМ. Том 3: Сортировка и поиск, М., 1978

6. Морозенко В.В., О сложности сортировки булевой алгебы, Дискретная математика, Том 3, выпуск 1, 1991, с.42-47

7. Никитин Ю.Б., О сложности извлечения информации из частично упорядоченных множеств, Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики" (Нижний Новгород, 1999), часть II, М., 1999, с.172

8. Никитин Ю.Б., О возможностях достижимости минимума сложности извлечения информации из частично упорядоченных множеств, Математические вопросы кибернетики, выпуск 8, М., 1999, с.135-146

9. Никитин Ю.Б., Точная оценка сложности алгоритма сортировки для одного семейства частично упорядоченных множеств, Вестн. Моск. ун-та. Сер. 15, Вычислительная математика и кибернетика, 2000, N.4, с.45-48

10. Никитин Ю.Б., О плотности сложности извлечения информации из частично упорядоченных множеств, Труды IV Международной конференции "Дискретные модели в теории управляющих систем" (Крас-новидово, 2000), М., 2000, с.91-94

11. Рыбников К.А., Введение в комбинаторный анализ, М., 1985

12. Хорари Ф., Теория графов, М., 1973

13. Яблонский С.В., Введение в дискретную математику, М., 1986

14. Richard Cole, Parallel Merge Sort, Information and Control 68, 1986, p.511-516

15. Peter F.Corbett, Isaac D.Scherson, A Unified Algorithm for Sorting on Multidimensional Mesh-Connected Processors, Information Processing Letters 37, 1991, p.225-231

16. Devai F., M. van der Nat, Distributive Merge Sorting, Proc. Fourht Hung. Computer Sci. Conf., 1985, p.331-338

17. Martin Dietzfelbinger, Lower Bounds for Sorting of Sums, Theoretical Computer Science 66, 1989, p.137-155

18. Konrad Engel, Sperner Theory, Cambridge University Press, 1997

19. Vladimir Estivill-Castro, Derick Wood, A New Measure of Presortedness, Information and Control 83, 1989, p.111-119

20. Faigle U., Turan G., Sorting and recognition problems for ordered sets, SIAM J.Comput, 1988, V.17, N.l, p.100-113

21. Janet Incerpi, Robert Sedgewick, Improved Upper Bounds on Shellsort, Information Processing Letters 14, 1983, p.48-55

22. Kruskal C., Searching, merging and sorting in parallel computation, IEEE Trans. Сотр., Vol.C-32, No.10, p.942-946

23. Kunde M., Optimal Sorting on Multi-Dimensionally Mesh-Connected Computers, Information Processing Letters 20, 1985, p.408-419

24. Manacher G.K., Bui T.D., Mai Т., Optimum Combinations of Sorting and Merging, Journal of the Association for Computing Machinary, Vol. 36., No. 2., April 1989, p.290-304

25. Ronce C., Networks for Sorting with Fusion, Philips J. Res. 39, 1984, p.305-316

26. Turan P., Eine extremalaufgabe aus der graphentheorie, Mat. Fiz. Lapok, 48, 1941, p.436-452