Тема данной курсовой работы

Скачать 257.85 Kb.

Название	Тема данной курсовой работы
страница	1/5
Дата публикации	30.04.2015
Размер	257.85 Kb.
Тип	Документы

100-bal.ru > Право > Документы

1 2 3 4 5

Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

Аннотация

Тема данной курсовой работы – " Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости". Для сравнения взяты четыре алгоритма: обход методом Грэхема, быстрый метод, метод “разделяй и властвуй” и динамический метод. Задача этой работы – раскрыть эти алгоритмы и провести исследования эффективности их.

Программная часть для курсовой работы выполнена на Borland Delphi 4.
Оглавление

Аннотация 2

Введение 4

Предварительная разработка алгоритма построения выпуклой оболочки 7

Метод обхода Грэхема 9

Быстрые методы построения выпуклой оболочки. 11

Алгоритмы типа “разделяй и властвуй”. 12

Динамические алгоритмы построения выпуклой оболочки 14

Сравнительный анализ алгоритмов построения выпуклой оболочки 17

Выводы 20

Заключение 21

Приложение Unit1.pas 22

Литература 34

Введение

Множество различных задач вычислительной геометрии связано с построением выпуклой оболочки. В настоящий момент эта задача хорошо исследована и имеет широкое применение в распознавании образов^¹, обработке изображений^², а так же в задачах в задаче раскроя и компоновки материала^³.

Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки. Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O(N log N).

Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки. Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O(N log N).

Для начала, несколько определений:
Определение 1. Область D принадлежащая пространству E², будет называться выпуклой, если для любой пары точек q₁иq₂из D отрезок q₁q₂ целиком принадлежит D.
Определение 2. Выпуклой оболочкой множества точек S, принадлежащих пространству E², называется граница наименьшей выпуклой области в E², которая охватывает S.
Далее будем иметь дело только с множествами, состоящими из конечного числа точек. Поэтому чтобы охарактеризовать структуру выпуклой оболочки нам нужно обобщить понятия выпуклого многоугольника.
Определение 3. Полиэдральным множеством или политопом называется пересечение конечного множества замкнутых полупространств.
Следующая теорема характеризует выпуклые оболочки в нужном нам плане.
Теорема 1^⁴. Выпуклая оболочка конечного множества точек в E^d является выпуклым политопом. Наоборот, каждый выпуклый политоп является выпуклой оболочкой конечного множества точек.
Прежде чем переходить к описанию алгоритмов следует произвести постановку задач и определить нижние оценки для решения их. Так как алгоритмы имеют дело с границей выпуклой оболочки множества L conv(L), то введем для нее обозначение CH(L) и будем ее также называть выпуклой оболочкой.

Сформулируем две основные задачи:
Задача ВО1. (Выпуклая оболочка). В E² задано множество S, содержащее N точек. Требуется построить их выпуклую оболочку (т.е. полное описание границы CH(S)).
Задача ВО2. (Открытый алгоритм для выпуклой оболочки). На плоскости задана последовательность из N точек p₁, …, p_N. Требуется найти выпуклую оболочку таким образом, чтобы, после обработки точки p_i имелась CH({p₁, …, p_i}).
Рассмотрим ВО1. То, что вершины многоугольника, являющегося выпуклой оболочкой, следуют в определенном порядке, указывает на связь с задачей сортировки. В самом деле, следующая теорема показывает то, что решение ВО1 должно быть в состоянии выполнить сортировку.
Теорема 2. Задача сортировки за линейное время сводится к задаче построения выпуклой оболочки, и, следовательно, для нахождения упорядоченной выпуклой оболочки для N точек на плоскости требуется время (N log N).
Доказательство. Сведем задачу сортировки N положительных действительных чисел x₁,.., x_N к задаче ВО1. Поставим в соответствие числу x_i точку (x_i, x_i²) и присвоим ей номер i. Выпуклая оболочка этого множества, представленная в стандартном виде будет представлять собой упорядоченное относительно значения абсциссы множество всех точек из исходного. Из него за линейное время можно получить отсортированный список.
Очевидно, что если мы можем решать ВО2, то мы можем решить и ВО1, по-этому задача ВО1 может быть сведена к ВО2 за линейное время. Следовательно, нижняя оценка для ВО2 не ниже (N log N).

1 2 3 4 5

Добавить документ в свой блог или на сайт

Похожие:

	Рекомендации по написанию курсовой работы При подготовке курсовой... Затем студент приступает к сбору информации. Первоначальное представление о теме и структуре работы можно составить по учебникам,...		Рекомендации студенту по выполнению рефератА (курсовой работы) Процесс... Выбор темы является весьма ответственным этапом выполнения реферата (курсовой работы), тема выбирается студентами самостоятельно...
	Отчетной работы) Курсовой проект (вид работы) По дисциплине «Теория антикризисного управления» Титульный лист курсовой работы (проекта), контрольной работы, домашнего задания, реферата, отчета о практике		Методические указания к выполнению курсовой работы по дисциплине... Рассматриваются вопросы, связанные с условиями и порядком выполнения курсовой работы. Даны общие требования к курсовой работе, выбору...
	Методические указания по выполнению курсовой работы 1 Содержание и структура работы Задание на выполнение курсовой работы по дисциплине «стратегический менеджмент», тематика курсвых работ		Выдержки из курсовой работы ...
	Методические указания по самостоятельной подготовке к практическим... Представлены методические указания по дисциплине «Маркетинг» к выполнению курсовой работы, проведению практических занятий, библиографический...		Каково целевое назначение курсовой работы как вида учебного процесса? В какой последовательности следует осуществлять подготовку дипломной (курсовой) работы?
	Методические указания к выполнению курсовой работы по дисциплине... Основными задачами, решаемыми студентами при выполнении курсовой работы являются		1. Экономическая сущность амортизации ос Темой данной курсовой работы является учет амортизации и методы ее начисления в условиях рынка
	Методические рекомендации по написанию курсовой работы по дисциплине... Цель курсовой работы состоит в том, чтобы развить у студентов навыки самостоятельной творческой работы, углубленно изучить какую-либо...		Методические указания к выполнению курсовой работы по дисциплине... Целью курсовой работы является закрепление теоретических знаний и выработка у студентов практических навыков по калькулированию себестоимости...
	Курсовая работа По курсу “Теория управления” Тема курсовой работы:... Тема курсовой работы: «Анализ и синтез оптимальной одноконтурной сау при использовании непрерывного и цифрового регуляторов»		Указания по оформлению курсовой работы по «Технологии профессиональной деятельности» Курсовая работа оформляется в виде электронного файла и пересылается преподавателю на электронную почту не позднее чем за 2 дня до...
	Рекомендации по выполнению курсовой работы Цель и значение курсовой... При разработке учебно – методического комплекса учебной дисциплины в основу положены		Методические указания по выполнению курсовой работы для студентов... Целью курсовой работы является систематизация, углубление и закрепление теоретических знаний по дисциплине, развитие навыков самостоятельной...

Школьные материалы