автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Оценка сложности методов сортировки данных

НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ЦЕНТР МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРИ ИНСТИТУТЕ ФИЗИКИ И МЕХАНИКИ ГОРШХ ПОРОД

РГ6 ол

Г"

На правах рукописи АРКАБАЕВА' ГУЛЬЗЫЛНАТ НАСЫРБЕКОВНА

ошнка сложности методов СОЕЭТМООВ1СИ данным

05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

БИШКЕК 1996

НАУЧНО-ИСОЕДОЕАТЕЛЬСКИЙ ЦЕНТР МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРИ' ИНСШГУТЕ ФИЗИКИ И МЕХАНИКИ ГОРНЫХ ПОРОД

На правах рукописи

АРКАБАЕВА ГУЛЬЗЫИНАТ НАСЫРБЕКОВНА

опьенгса сложности методов согзтигэовгсм данным:

05.13.1Б - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

БИШКЕК 1893

Работа выполнена на кафедре программирования и АСУ Факультета информатики и прикладной математики Кыргызского Государственного Национального университета

Научные руководители: доктор технических наук, профессор,

чден-ксрр. HAH Ж. ffl. Шаршеналиев,

кандидат физико-математических наук, профессор Н. А.Аркабаев

Официальные оппоненты: доктор физико-математических наук,

профессор ¡0.3. Алежов, доктор Физико-математических наук, профессор Р. Рафатов.

Ведущая организация: Республиканский центр новых информационных. технологий при министерстве народного образования КР

Зашита диссертации состоится 1йяй г.

в " " часов на заседании Специализированного совета К 05.95.37 НИЦ ММ при ИФ и МГП НАН РК по адресу: г.Бишкек, просп. Чуй 265-а. в комнате N 315

С диссертацией можно ознакомится в библиотеке HAH KP. г.Бишкек, просп. Чуй, 265-а

Автореферат разослан:

Ученый секретарь ' кандидат физ.-мат- наук , IJ/У^ю^сСС^О-^ 0. В. Матюхин.

ОбЩАЯ ХАРАКТЕРИСТИКА РАООТЫ

АКТУАЛЬНОСТЬ ТЕШ. Созданная во второй половине 20 века, быстродействующая вычислительная машина открыла новую страницу в истории математики, т.е. явилась началом новой эры развития математической науки.

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

A.Н.Колмогоров, А.Д.Александров, А.Н.Тихонов, А.А.Самарский,

B.Г.Карманов, О.И.Дегтярев, В.Б.Кудрявцев, Э.ДеЙкстра, К.Хоор, О.Дал, Р.Большая, Джон фон Нэйман, Д.Кнут, Н.Вирт и т.д.

Из многочисленных, работ в области программирования весомое значение имеет признанная во всем мире энциклопедическая многотомная монография выдающегося американского ученого. математика Д.Кнута "Искусство программирования для ЭВМ", которая охватывает-почти весь спектр рассматриваемого вопроса.

В данной работе проблема программирования разбивается на семь частей:

I. Основание алгоритмов , которое состоит из двух направлений: основные понятия и информационные структуры, общий объем составляет 46 печатных листов.

II. Получислекные алгоритмы. В этом разделе, освещаются следующие два вопроса: случайные числа и арифметические операции, объем данного раздела состоит из 51 печатного листа.

III. Сортировка и поиск. Этод раздел посвящен методам сортировки и поиска, общий объем составляет 53 печатных листа.

IV. Комбинаторные алгоритмы. Включает комбинаторный поиск и рекурсию.

VI. Теория языков о математической лингвистике.

VII.Комлеляторы, т.е. перевод языков программирования.

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

Исторически зарождение методов машинной сортировки можно отнести еще к прошлому столетию и за столь длительное время многие специалисты успели испробовать свои силы в этой области. Анализ развитая вопроса сортировки показывает, что она тесно связана со многими нахоженными тропами в вычислениях: с первыми машинами для обработки данных, первыми, запоминаемыми программами, первым программным обеспечением, первыми методами буферизации,первой работой по. анализу алгоритмов и сложности вычислений. А также, как показал Д.Кнут в своей.блестящей всеобъемлющей монографии, исследование проблем сортировки.поиска дает основу для обсуждения широкого класса важнейших общих вопросов программирования; ■

1. Как находить "хорошие" алгоритмы?

2. Как.улучшить Емэнщився алгоритмы и программы?

3. Как. исследовать эффективность алгоритмов математически?

. 4. Как разумно выбрать один из нескольких алгоритмов для решения кошсретной задачи?

5, В каком смысле можно доказать, что некоторые алгоритмы являются "наилучшими из возможных"?

е. Как теория вычислений согласуется с практическими соображениями?

7. Как эффективно использовать различные виды внешней памяти ленты барабаны, диски для больших баз данных?

Предлагаемая диссертационная работа посвящена изучения выше указанных 3,4 и 5 вопросов, что подчеркивает ее актуальность.

Ц£ПЬ РА60ТЫ И ЗАДАЧИ ^СЛЕДОВАНИЯ. Разработать математически аппарат и исследовать сложность часто используемых. 4-х метода сортировки:

1. Метода простого включения(Bi);

2. Метода Шелла(В*);

3. Метода простого выбора(Вэ);

4. Метода пирамидальной сортировки(Б*);

Произвести сравнительный анализ и установить преимущество одних алгоритмов над другими в зависимости от конкретных конфигураций данных.

НАУЧНАЯ НОВИЗНА. Результаты диссертации являются новыми. Проблема сортировки подвергалась исследованию в целом ряде работ таких ученых, как Д.Кнут, Дж.Мочли, Д.Дж.Уилера.Д.Л.Шелла, У.Дж.Уильямса, К.З.Ботчера, Ч.Э.Хоара, А.А.Попернова, Г.В.Стасэвича, Л.В.Анксимова, Л.Р.Айрапетяна, В.Пратта.

Наиболее полное представление о сортировке дает в своей работе Д.Кнут Ш. Он описывает различные методы сортировки и анализирует возможные способы их усовершенствования.

Д.КнутШ при анализе алгоритмов оперирует производящей функцией

J («Va,.....вл > . •

и* = £ z 12 п •

где Z-параметр алгоритма, j(av,az,..., an) - индекс перестановки at,а2,...,an¡сумма борется по перестановкам множества, равным числам Эйлера < jj >t гда к-'®0-110 отрезков, и асскмптотическим формулам гармонических чисел:

1Ь = 1л(п) +7+0 (А), ( 7 -постоянная Эйлера}-и формулам Стирлинга: k

1п(п!)=(п+1/2)1л-п+о+г (~1> Bk + 0(1 j 1<k<™ (k-1)knk"* nm '

где k=InV/2i - , постоянная Стирлинга, B¡< - числа Бернулли; в частности для га=5 получается

In (а!)=(п+1 /2) Ln (п) -п+о+1 / (12п) -1 / (360n2 ) +0 (1 /if ).

Д.Кнут после определенных'статистических исследований для алгоритма простых включений получил ассиптотическую формулу для числа инверсий

B=(mln О, ave (ii- n)/í, max(nz-n)/2),

где n-число записей в файле.

Н.Вирт [2] для этого алгоритма простым подсчетом, считая все перестановки п ключей равновероятными получил формулы для.числа, сравнений : Cmln=n-1, Сср.= 1/4 (nZ+n-2), Сгоах=1/2 (п2+п) и числа пересылок: M«in=2(n-1)=1/4(п2+9п-10),Мглах=1/2(пг+Зп-4

Для алгоритма Шелла теоретического анализа в литературах не имеется. Д.Кнут приводит эмпирические формулы, полученные Джеймсом Патерсоном и Дэвидом Л.Расселом в Стэнфордском университете для числа инверсий:

В - ап^ или В = 7 n(Ln(ii})*4ímLn(n),

где а,р,7,ш зависят от: п и z-длина шага, например, для п=250000 при Z=2k-1 на основе 45 испытаний получим В=7900000. При этом наиболее подходящими формулами для диапазона IOOín^5QGCC оказались соответственно 1.21п'го или 1.39п(1п)г-2.33п1п(п),т.е.

а = 1.21 = 1.26 ,7= 1.39, ш = 2.33

В случае алгоритма простого выбора точный анализ величины В отсутствует и в работе Д.Кнута приводится приблизительная формула:

В = (min О, ave (n+1) Нп - 2n, mailn V4J);

Далее, Д.Кнут на основе экспериментов получил время работы пирамидальной сортировки, в среднем примерно lenLog^n+O.Sn единиц.

Как. показывает анализ литературы , даже в такой фундаментальной работе как. "Искусство программирования для ЭВМ" Д.Кнута отсутствует систематизированный, строгий математический анализ алгоритмов сортировки. -

В предлагаемой диссертации при помощи методов комбинаторного анализа, дискретной математики, теории вероятностей и математической статистики сделан■ систематизированный математический i сравнительный анализ вышеуказанных 4-х алгоритмов сортировки.

Практическая ценность. Как показывает Д.Кнут в своей энцик-лашдичвской работе, из-за неэффективного применения алгоритмоз сортировки от 25:.до более половины машинного времени систематически тратится на сортировку. Отсюда практическая ценность данной

вается меньше,чем первый, то они меняются местами, в противном случае порядок не изменяется. Затем берется третий элемент этой последовательности, который.начинает сравниваться сначала с ближайшим к нему элементом, т.е. с аг, если. аг больше, чем аэ, то а2 посылается вправо на место ¿лемента а3,а элемент а^ачинае-; сравниваться с а4,если atбольше, чем аэ,то а4посылается вправо на старое место элемента а2, а йзпомэщается на место а4..И так какды! раз берется следующий элемент исходной последовательности и поме--щатется на подходящее место, во вновь образующейся последовательности, т.е, к перестановке а применяется последовательно единичная операция "Е (a ,a4,k >, где 1=2,п, к€С1,2,...,п), к<1, приводящее ее к каноническому.виду. Например, при применении единичной операции.E(a,ajк) к перестановке а= ao,ai...an получается перестановка ¡3 = bobi,...,bn, в которой ajnpk 0 < 3 < I-k-1,(а0 = \= 0); bi.k= а,, при I-k ^ 3 £ 1 и Ь^ а} при J > 1.

При этом число к .+ 1 называется сложностью единичной операции Е(а,а, ,к).

Функция Mg (а) определяется " как сумма сложностей единичны: *

операций E(a,aitk), приводящих перестановку а = а1...ап.к каноническому виду, а функция Cg(a) определяется как сумма сложностей

. этих ке операций минус С* и плюс Са' (Со - число операций, у ко: рых k ï О, С«*. - число операций, у которых. к=0). .

Для оценки сложности метода В доказаны следующие теорема.

Теорема 1Л. Имеет место Mg (п) = (пг + п - 2) /2 • 1 ■ Теорема I.Z. Имеет место Mg .(n) = (пг - 2п 1) /4 - Бп • .где En = 1 +1/2+ 1/3 + ...

*>

1

t

%1 ^ максимальное значение функции М3. (а.), 1=1,4 Ка (п) - среднее значение функции Кв. (а), 1=1,4 К? (п) .-' мийимальное значение функции Мв, (а),: 1=1,4 (п) - максимальное 'значение фур:шп< С01(а), 4=1,4 (п) - среднее значение функции СВ1 ;а), 1-1,4 С^ (п) - минимальное значение функции С^Са), 1=1,

«

-В-

Теорема 1.3. Имеет место М^ (п) = О

Теорема 1.4. Имеет место Cgt (п) = (пг - п)/2

2 2 -

Теорема 1.5. Имеет место С0 (п) = (п + Зп)/4 - Нп,

где Нп. = 1 + 1/2 + 1/3 -I- ...

3

Теорема 1.6. Имеет место С^ (п) = п. - 1

Во второй главе, состоящей из 6 параграфов рассматривается етод 32и определяется его сложность.

Метод Бг отличается от метода Bt тем, что, сначала, сравни-аются не "соседние", а "далэко".отстоящие друг от друга элементы.

На каждом шаге "удаленность" сравниваемых элементов меньшается, пока нэ достигает единицы.

Число I = i'-i при 1<1' назовем интервалом между а и а5 з ,а. Метод Вг на первом шаге сравниваем элементы. а(и а(с интврва-

ом равным [n/2J . Возникает[n/2J слов длины 2.Каждое из которых порядочивается независимо от других с помощью метода Bj На вто-ом шаге сравниваются и переставляются элементы, интервал между оторыми равен [p/4-j .В этом случае число полученных слов длины 4 удем равно Ln/4-J .На i-ом шаге, когда рассматриваются элементы, нтервал мезду которыми равен [n/2J v получаем множество слов дли-ы 2 , состоящее из [n/2j слов и т.д. и на последнем шаге, ког-д L.= .l, метод Bt будет применен к самой перестановка а.

В §§ 1-3 данной главы исследована функция М^.(а). Доказаны

ледуздше утверждения.

Теорема 2.1. Имеет место МЛг (n) ^ п/2 (2п + 3 log2n + 2)

Теорема 2,2. Имеет место MjL (n) - (4n2- n)/1G

Теорема 2.3. Имеет место Шц (n) = G

3 §§ 4-6 исследована функция G„(a). В результате исследования

>

[xj - наибольшее целое число, нэ превосходящее X.

доказана справедливость следующих трех утверждений.

Теорема 2.4. Имеет место C¿ (11) € (4пг + 10 n log n)/¿

г г

Теорема 2.Б. Имеет место С| (и) = 0,4 п .+ 0,4 n + n lo^n - 1,55 п

э

Теорема 2.4. Имеет место Cg. (n) = n log2 п - п

Глава 3 .состоит из 4-х параграфов. В ней дается оценка ело» ности метода В3, который упорядочивает элементы следующим образок

Еа первом шаге, выбирается наименьший элемент перестановки и посылается на место первого элемента, затем выбирается наимэныни элемент из оставшихся п-1 элементов и меняется местами со вторы элементом и т.д. до тех пор, пока не останется только один элэ мент - наибольший. Таким образом будет сделано п-1 проходов, в каждом из которых определяется минимальный элемент.

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

Теорема 3.1. Имеет место МАЭ (п) = 1п/4}г + 2(п-1)

Теорема 3.2. Имеет место К^ (n) = n(ln п + у ) + 2 (п -

в •

£1/{S - 1)! S ^ t¡ ^ v=0,57721б-Эйлерова константа

i " "' «

1 К З

Теорема 3.3. Имеет место М^ (n) = п

Б 4 исследуется функция Ср (а)

-'з

В главе 4, которая состоит из 7 параграфов,. анализируется ме тод. B¿ Он является улучшенным вариантом метода Вэ.

Основной принцип этого метода такой ке как и у метода Вз, только здесь мы получаем больше информации от каждого прохода, чем просто указание на один наименьший элемент. Для этого в алгоритме В4 строится пирамида.

Сложность этого метода определяется с помощь» функций Mgja) Cgja), которые исследуются в §§ 1-4 и §§ 5-7 соответственно. Пг этом даказаны следующие утверждения.

Теорема 4.1. Имеет место Mi (n) ^ 2n log„n + 2п

Теорема 4.2. Имеет место ií|] (п) £ nlogzn((8 (п+1)log Jn/2))

/2 + 1/4) + (21og (п+1) - а (п+1) + 4), <*=c»r«»t

Теопема 4.3.'Имеет место. мД (n) ^ п

и*

Теорема 4.4. Имеет место (n) > n log2(n/2) + n = n log2n Теорема 4.5. Имеет место Ст^ (п)' > п/4- log,n Теорема 4.6. Имеет место Сд^ (п) > 2 п 3 пятой главе, дается сравнительный анализ 'методов.Б» ,Вг , • и В* я исследуются области пересечения этих алгоритмов.

В приложении приведены тексты выполненных в диссертационной эботе программ.

Из анализа литературных данных и приведенного краткого содер-ания работы следует, что методы исследования- и полученные ре~ ультата в диссертации являются новыми.

Заключение. Впервые математическим методом изучены и систе-атизированы 4 метода сортировки: метод простого включения, метод элла, метод простого выбора и метод пирамидальной сортировки и ля них получены функции характеризующие их основные свойства.

Сравнительный анализ показал, что метод Шэлла хорошо ортирует перестановки, которые наиболее упорядочены i-i яаихуд-им образом сортирует те, которые упорядочены или частично упс-ядочены в обратном порядке. Для перестановок, упорядоченных в Оратном порядке и на случайных перестановках дает лучшие эзультаты метод пирамидальной сортировки. Метод простого ключения хорошо сортирует перестановки, элементы которых асположены таким образом, что они являются соседними ео всех ловах, а также целесообразно использовать его при небольших и, .к. выигрыш по времени получается за счет простоты алгоритма. И амым неудачным среди всех методов оказался метод простого ыбора, поскольку он затрачивает пг шагов независимо от располоке-иягэлементов в перестановках. Этот метод может применятся как и етод простого включения в тех случаях, когда необходимо тсортировать небольшое количество данных.

Результы диссертации опубликованы в работах:

1.Аркабаева Г.Н. Методические указания к изучению курса "Нестарые методы сортировки".. Бишкек, 1992;

2.Аркабаева Г.Н. Среднее число проверок при двоичном поиска, езисы докладов IV.научной сессии аспирантов Ныргоснацушшерсите-а. Бишкек, 1990 г., с. 35-36;

3.Аркабаева Г.Н. Оценка числа сравнений элементов подстанов-

ки при использовании метода "Простых включений". Тезисы докладов Л научной сессии аспирантов Кыргоснацункверситета. Бишкек* '1992г., с 24-25;

4.Аркв0Бэва Г.й. Очисле присвоений при сортировке методо» простого выбора и методом Шелла. Вестник Кыргоснацункверситета, Бишкек, 1994г., с. 208-213.

5.Аркабаев , Н.А.,Аркабаева Г.Н. Слокностная характеризацш алгоритма сортировки прстыми . ключениям. Вестник Кыргоснацунивв] ситета Бишкек 1995г., с.138-144

Arkabaeva Gulsynat Naslrbekovna

The apprieel of the methods complications lor sorting date

Summary

Oiten used in practice lor sorting methods: method of simple IrJGLugions, Shell met hod, method of staple choice and pyramid method were studied in the dissertation by the tuathimatlc method and the Were received it characteristic functions.

On the bases of this' functions it- optimal ut illthation in connection with the structure of date was shown.

Аркабаева Гульзыйнат НасырОекозна Оортто ыкмаларднн татаалдыгынш Оаасы Аннотация

Диссертациялык иште коп учурларда колдонулучу 4 сорттс ыкмалары: жонокой туташтыруу ыкмаоы, Швлдын ыкмасы, зконокой тандос ыкмасы жана пирамидалык сортто ыкмасы математикалык жол мене* каралш, аларда миноздочу функциялар алынган. Ушул функцияла] аркылу горсотулгон ннмалврдан аптималдык коддонусу аныкталган ,