Задания для лабораторной работы

1. Написать программу, реализующую алгоритм А и алгоритм В, для проведения экспериментов, в которых можно выбирать:

• количество n элементов в исходном массиве a,

• верхнюю q и нижнюю w границы для значений элементов массива,

• заполнение массива a:

• псевдослучайное,

• автоматическое по неубыванию,

• автоматическое по невозрастанию.

Выходом данной программы должен быть отсортированный массив a, а также бвремя работы Т_А алгоритма А и время работы Т_В алгоритма В в секундах (или других подходящих единицах времени).

2. Провести эксперименты на основе следующих данных:

   1. q=1, w=10⁹, n=1, … ,10⁵+1 с шагом 10³, заполнение массива a:

• псевдослучайное,

• по возрастанию,

• по убыванию.

(привести в отчёте графики функций T_А(n) и Т_В(n) для всех трех случаев).

2. q=1, w=1, … ,100 с шагом 1, n=10⁵, заполнение массива a:

• псевдослучайное,

• по возрастанию,

• по убыванию.

(привести в отчёте графики функций T_А(w) и Т_В(w) для всех трех случаев).

Приведенные параметры экспериментов являются лишь отправной точкой и предназначены для проведения на компьютерах 2-3 летней давности. Если получается, что T_А(n) и Т_В(n) (или T_А(w) и Т_В(w)) чрезмерно близки или наблюдается не тот порядок роста этих функций, то следует увеличить один из параметров до устранения нежелательных эффектов.

Предлагаемые варианты для алгоритмов А и B:

Вариант 1.

• A – Быстрая сортировка,

• B – Сортировка 3-кучей.

Вариант 2.

• A – Сортировка слиянием,

• B – Сортировка 3-кучей.

Вариант 3.

• A – Пузырьковая сортировка,

• B – Сортировка 3-кучей.

Вариант 4.

• A – Сортировка 2-кучей,

• B – Сортировка 3-кучей.

Вариант 5.

• A – Быстрая сортировка,

• B – Сортировка 15-кучей.

Вариант 6.

• A – Сортировка слиянием,

• B – Сортировка 15-кучей.

Вариант 7.

• A – Пузырьковая сортировка,

• B – Сортировка 15-кучей.

Вариант 8.

• A – Сортировка 2-кучей,

• B – Сортировка 15-кучей.

Вариант 9.

• A – Сортировка 14-кучей,

• B – Сортировка 15-кучей.

Вариант 10.

• A – Пузырьковая сортировка,

• B – Быстрая сортировка.

Вариант 11.

• A – Пузырьковая сортировка,

• B – Сортировка слиянием.

Вариант 12.

• A – Быстрая сортировка

• B – Сортировка слиянием.

4. Лабораторная работа «Построение выпуклой оболочки системы n точек на плоскости» Постановка задачи

Для точек a₁, …, a_n, где n≥1, a_i=(a_i,1, a_i,2)R² при i=1, …, n, требуется указать вершины b₁, …, b_m выпуклой оболочки Conv(a₁, …, a_n) в порядке их встречи при движении по ее границе. Заметим, что в общем случае Conv(a₁, …, a_n) будет многоугольником, а в вырожденных случаях может получиться отрезок или точка. В случае отрезка выходом решающего поставленную задачу алгоритма должны быть две являющиеся его концами точки, а в случае точки  сама эта точка.

Построение выпуклой оболочки с помощью сортировки

Для решения задачи (см. [3]) построения Conv(a₁, …, a_n) мы из точек a₁, …, a_n выберем точки с минимальной первой координатой, среди которых затем найдем точку c, имеющую минимальную вторую координату. Таким образом, точка c = lexmin(a₁, … ,a_n) является лексикографическим минимумом точек a₁, … ,a_n и поэтому представляет собой вершину выпуклой оболочки Conv(a₁, …, a_n). Именно с неё мы и начнём обход границы против часовой стрелки, положив b₁=c и осуществив перед этим для удобства промежуточных вычислений параллельный перенос системы координат так, чтобы её начало совпало с точкой с. После такого переноса на точках a₁, …, a_n удается определить такой линейный порядок (≤), что для c₁,c₂ {a₁-c, … ,a_n–c}имеет место c₁ ≤ c₂, если либо det(c₁,c₂)>0, либо (det(c₁,c₂)=0)&( (c_1,1)²+(c_1,2)²) < (c_2,1)²+(c_2,2)² ).

Геометрический смысл такого упорядочения можно проиллюстрировать, если ввести полярную систему координат φ, r (-<φ ≤, r0) с центром в точке c и далее положить, что c₁ ≤ c₂, если (φ₁,r₁) лексикографически не превосходит (φ₂,r₂), где числа φ_i, r_i являются полярными координатами точки c_i, i = 1,2.

Таким образом, c₁ ≤ c₂, если либо φ₁ < φ_2, либо (φ₁ = φ₂)&(r₁ ≤ r₂). Как только линейный порядок на элементах (точках) a₁, …, a_n определен, немедленно можем воспользоваться сортировкой, для того чтобы отсортировать эти элементы по неубыванию в соответствии с введенным линейным порядком. После этого мы произведем за время O(n) просмотр отсортированного массива с целью получения итоговых точек b₁, …, b_m исходя из того условия, что точка b_i+1 располагается строго слева от вектора, идущего из точки b_i-1 в точку b_i, что эквивалентно требованию того, чтобы det(b_i-b_i-1,b_i+1-b_i)>0.

Описанные действия конкретизируются алгоритмом, представляемым процедурой CONV_SORT (a, n), на вход которой подается массив точек a[1], …, a[n]. Итоговые точки b₁, …, b_m, являющиеся решением задачи, будут представлены в той же последовательности в первых m элементах a[1], …, a[m] массива a. Отметим также, что в процедуре CONV_SORT используется подпрограмма сортировки СОРТИРОВКА (a, n), выдающая отсортированный по неубыванию массив a.

procedure CONV_SORT (var a, n);

begin

c:= a[1]; m:= 1;

for i:= 2 to n do if a[i][1]<c[1] then begin c:= a[i]; m:= i;

end else if a[i][1]=c[1] then if a[i][2]<c[2] then begin

c:= a[i]; m:= i;

end;

a[1]a[m]; m:= 1;

for i:= 1 to n do a[i]:= a[i]-c;

СОРТИРОВКА(a, n);

for i:= 2 to n do if a[i]  a[m] then begin

if m  2 then while (m  2)&(det(a[m]-a[m-1],a[i]-a[m]) 0) do m:= m-1;

m:= m+1; a[m]a[i];

end;

for i:= 1 to m do a[i]:= a[i]+c;

end;

Временная сложность алгоритма построения выпуклой оболочки точек в случае, если используется сортировка с помощью d–кучи или сортировка слиянием, есть величина O(nlog n), если же используется быстрая сортировка, то временная сложность алгоритма в худшем случае O(n²), а в среднем алгоритм выполняется за время O(nlog n).