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

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

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

• натуральные числа q и w для псевдослучайного размещения всех n точек в двух режимах:

1. в прямоугольнике со сторонами длины q и w,

2. на границе (на сторонах) этого прямоугольника.

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

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

   1. q = 10⁴, w = 10⁴, n = 1, …, 10⁵+1 с шагом 10³, размещение точек псевдослучайное:

• в режиме (1),

• в режиме (2).

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

2. q = w = 0, …, 10⁴ с шагом 100, n = 10⁶, размещение точек псевдослучайное: в режиме (1) (привести в отчёте графики функций T_А(w) и Т_В(w)),

3. q = w = 0, …, 10⁴ с шагом 100, n = 10⁴, размещение точек псевдослучайное: в режиме (2) (привести в отчёте графики функций 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 – Сортировка слиянием

5. Литература

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

2. В.Е.Алексеев, В.А.Таланов. Графы. Модели вычислений. Структуры данных. Учебник Нижний Новгород, 2005.

3. Ф. Препарата, М. Шеймос. Вычислительная геометрия: Введение. – М.: Мир, 1989.