- •Факультет вычислительной математики и кибернетики
- •Описание алгоритмов
- •Постановка задачи
- •Алгоритм построение выпуклой оболочки с помощью сортировки
- •Алгоритм сортировки с использованиемd-куч.
- •Псевдокод операций используемых надd-кучей и некоторые оценки сложности.
- •Алгоритм сортировкиk-слиянием.
- •Алгоритм сортировки вставками.
- •Обоснование теоретических оценок временной сложности алгоритмов.
- •Сложность сортировки с помощьюd-куч:
- •Сложность сортировки с помощью сортировкиk-слиянием:
- •Описание программы.
- •Проведенные эксперименты.
- •Сравнение алгоритмов
Министерство образования и науки Российской Федерации
Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»
Факультет вычислительной математики и кибернетики
Кафедра математического обеспечения ЭВМ
Построение выпуклой оболочки n-точек на плоскости
(вариант 592)
Выполнил: студент группы 8309
Лялюшкин Н. А.
Проверил: Замараев В.А.
Нижний Новгород
2012
Оглавление
1.Описание алгоритмов 3
a) Постановка задачи 3
b)Алгоритм построение выпуклой оболочки с помощью сортировки 3
c)Алгоритм сортировки с использованием d-куч. 4
d)Псевдокод операций используемых над d-кучей и некоторые оценки сложности. 4
e)Алгоритм сортировки k-слиянием. 7
f)Алгоритм сортировки вставками. 8
2.Обоснование теоретических оценок временной сложности алгоритмов. 8
Сложность сортировки с помощью d-куч: 9
Сложность сортировки с помощью сортировки k-слиянием: 13
3.Описание программы. 14
4.Проведенные эксперименты. 16
5.Сравнение алгоритмов 19
6.Выводы 20
Описание алгоритмов
Постановка задачи
Для точек a1, …, an, где n≥1, ai=(ai,1, ai,2)R2 при i=1, …, n, указать вершины b1, …, bm выпуклой оболочки Conv(a1, …, an) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a1, …, an) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки сама эта точка.
Необходимо провести попарное сравнение различных использующих сортировку алгоритмов построения выпуклой оболочки n точек на плоскости с целочисленными координатами.
Алгоритмы:
алгоритм, использующий сортировку с помощью d-кучи, d=50
алгоритм, использующий сортировку (k-50)-слиянием, k=92
Алгоритм построение выпуклой оболочки с помощью сортировки
Поиск лексикографического минимума c = lexmin(a1, … ,an) среди всего массива точек {a1, a2…, an}. Для этого выбирается подмножество точек с минимальной первой координатой, а затем в этом подмножестве выбирается точка с минимальной второй координатой. Полученная точка c будет первым элементом выпуклой оболочки.
Делаем перенос начала системы координат в полученную точку {a1-c, a2-c…, an-c}.
На точках a1, …, an определяется линейный порядок ( ≤ ), что для c1,c2 {a1-c, … ,an–c} имеет место c1 ≤ c2, если
либо det(c1,c2)>0,
либо (det(c1,c2)=0)&( (c1,1)2+(c1,2)2) < (c2,1)2+(c2,2)2 ).
Выполняется сортировка точек по введенному отношению быть не больше(≤).
Производится просмотр отсортированного массива с целью получения итоговых точек b1, …, bm исходя из того условия, что точка bi+1 располагается строго слева от вектора, идущего из точки bi-1 в точку bi, что эквивалентно требованию того, чтобы det(bi-bi-1,bi+1-bi)>0.
Выполняем обратный параллельный перенос, первые m-точек образуют выпуклую оболочку исходного набора точек.
Алгоритм сортировки с использованиемd-куч.
Из массива точек формируется завершённое d-арное дерево(каждому узлу дерева приписывается элемент массива). Для завершённого d-арного дерева выполняется:
Каждый не листовой узел, кроме, быть может, одного, должен иметь ровно d непосредственных потомков. (Узел исключения может иметь любое число потомков от 0 до d)
Если h – высота дерева, то для {0,1,..n-1} i-ый уровень дерева имеет ровно di узлов, а на последнем уровне может быть любое число узлов от 1 до dn.
Выполняется операция окучивания (применение операции diving(i) по очереди к узлам n-1,…0. Вес каждого узла не превосходит весов элементов, находящихся в его потомках.
Записываем в конец массива Sort элемент, являющийся корнем в d-куче. На место корня ставим элемент с максимальным индексом, размер кучи уменьшаем на 1 и осуществляем погружение корневого элемента кучи.
Повторение описанных операций (в пункте 2.) до тех пор, пока размер кучи не будет равен 1.
В куче останется элемент с максимальным весом, его необходимо записать в конец массива Sort.
Таким образом, получим массив Sort, отсортированный по не убыванию.