Реферат на тему: Аннотация. Предварительная разработка алгоритма построения выпуклой оболочки

Введение

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

Программная часть для курсовой работы выполнена на Воrlаnd Dеlрhi 4.

Оглавление

Аннотация 2

Оглавление

- Аннотация.

- Введение.

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

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

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

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

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

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

- Выводы.

- Заключение.

- Приложение.

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

Список литературы

- Введение.

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

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