ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н.Ельцина».

Кафедра информационных технологий и автоматизации проектирования

Вычислительная геометрия

Отчёт по лабораторной работе №1

Группа: М-490702

Студент: Беланов И.Н.

Преподаватель: Кац Е.И.

Екатеринбург

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

На плоскости равномерно распределены N точек. Задан прямоугольник со сторонами параллельными осям координат. Даны два алгоритма, решающих задачу о нахождении количества точек в прямоугольнике.

1). Составить таблицу соответствия времени работы первого и второго алгоритмов количеству заданных точек.

2). На плоскости с координатами N и K, где N - количество точек, а K - количество запросов необходимо выделить область, где лучше работает соответственно первый или второй алгоритм, т.е. нужно нарисовать кривую, на которой время работы методов совпадает.

Результат работы:

Таблица результатов работы программы:

Количество точек	Время работы 1-го алгоритма (нс) *	Время работы 2-го алгоритма (нс) *	Время пред подготовки для 2-го алгоритма (нс)

* - среднее время расчёта для 100 измерений

Графики зависимости времени для обработки одного запроса первого и второго алгоритмов от количества точек N:

График зависимости времени пред-подготовки второго алгоритма от количества точек:

График зависимости K от N. Где K – количество запросов, при которых общее время работы двух методов одинаково. N – количество точек.

Из графика видно, что второй метод лучше использовать только при большом количестве запросов K (порядка миллионов). Таким образом, второй метод подойдёт для задач, условия которых выше этой кривой. Если же количество запросов не большое, то имеет смысл использовать первый метод. Область задач, для которых первый метод подойдёт лучше, находится соответственно ниже этой кривой.

Так же, стоит отметить, что второй метод требует неимоверно большого количества памяти. Для 100 000 точек необходима память порядка десятков гигабайт!

Программа:

Дата добавления: 2015-08-28