Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте www.za4et.net.ru

Математика Математика

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

Гуашь "Классика", 12 цветов.
Гуашевые краски изготавливаются на основе натуральных компонентов и высококачестсвенных пигментов с добавлением консервантов, не
170 руб
Раздел: 7 и более цветов
Фонарь желаний бумажный, оранжевый.
В комплекте: фонарик, горелка. Оформление упаковки - 100% полностью на русском языке. Форма купола "перевёрнутая груша" как у
87 руб
Раздел: Небесные фонарики
Мыло металлическое "Ликвидатор".
Мыло для рук «Ликвидатор» уничтожает стойкие и трудно выводимые запахи за счёт особой реакции металла с вызывающими их элементами.
197 руб
Раздел: Ванная

Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости Аннотация Тема данной курсовой работы – " Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости". Для сравнения взяты четыре алгоритма: обход методом Грэхема, быстрый метод, метод “разделяй и властвуй” и динамический метод. Задача этой работы – раскрыть эти алгоритмы и провести исследования эффективности их. Программная часть для курсовой работы выполнена на Borla d Delphi 4. ОглавлениеАннотация 2Введение 4Предварительная разработка алгоритма построения выпуклой оболочки 7Метод обхода Грэхема 9Быстрые методы построения выпуклой оболочки. 11Алгоритмы типа “разделяй и властвуй”. 12Динамические алгоритмы построения выпуклой оболочки 14Сравнительный анализ алгоритмов построения выпуклой оболочки 17Выводы 20Заключение 21Приложение U i 1.pas 22Литература 34 Введение Множество различных задач вычислительной геометрии связано с построением выпуклой оболочки. В настоящий момент эта задача хорошо исследована и имеет широкое применение в распознавании образов, а так же в задачах в задаче раскроя и компоновки материала. Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки. Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O( log ). Само понятие выпуклой оболочки является довольно простым и интуитивно понятным. Если представить резиновый шнур, натянутый на множество точек, то это и будет выпуклая оболочка для данного множества точек. Но, не смотря на свою простоту, оно не конструктивно, поэтому далее будут рассмотрены способы построения эффективных алгоритмов для построения выпуклой оболочки. Так как алгоритмы для решения нашей задачи, как правило, являются подзадачами других, более сложных задач, то интерес представляют только алгоритмы имеющие сложность O( log ). Для начала, несколько определений: Определение 1. Область D принадлежащая пространству E2, будет называться выпуклой, если для любой пары точек q1 и q2 из D отрезок q1q2 целиком принадлежит D. Определение 2. Выпуклой оболочкой множества точек S, принадлежащих пространству E2, называется граница наименьшей выпуклой области в E2, которая охватывает S. Далее будем иметь дело только с множествами, состоящими из конечного числа точек. Поэтому чтобы охарактеризовать структуру выпуклой оболочки нам нужно обобщить понятия выпуклого многоугольника. Определение 3. Полиэдральным множеством или политопом называется пересечение конечного множества замкнутых полупространств. Следующая теорема характеризует выпуклые оболочки в нужном нам плане. Теорема 1. Выпуклая оболочка конечного множества точек в Ed является выпуклым политопом. Наоборот, каждый выпуклый политоп является выпуклой оболочкой конечного множества точек.

Прежде чем переходить к описанию алгоритмов следует произвести постановку задач и определить нижние оценки для решения их. Так как алгоритмы имеют дело с границей выпуклой оболочки множества L co v(L), то введем для нее обозначение CH(L) и будем ее также называть выпуклой оболочкой. Сформулируем две основные задачи: Задача ВО1. (Выпуклая оболочка). В E2 задано множество S, содержащее точек. Требуется построить их выпуклую оболочку (т.е. полное описание границы CH(S)). Задача ВО2. (Открытый алгоритм для выпуклой оболочки). На плоскости задана последовательность из точек p1, , p . Требуется найти выпуклую оболочку таким образом, чтобы, после обработки точки pi имелась CH({p1, , pi}). Рассмотрим ВО1. То, что вершины многоугольника, являющегося выпуклой оболочкой, следуют в определенном порядке, указывает на связь с задачей сортировки. В самом деле, следующая теорема показывает то, что решение ВО1 должно быть в состоянии выполнить сортировку. Теорема 2. Задача сортировки за линейное время сводится к задаче построения выпуклой оболочки, и, следовательно, для нахождения упорядоченной выпуклой оболочки для точек на плоскости требуется время (( log ). Доказательство. Сведем задачу сортировки положительных действительных чисел x1,., x к задаче ВО1. Поставим в соответствие числу xi точку (xi, xi2) и присвоим ей номер i. Выпуклая оболочка этого множества, представленная в стандартном виде будет представлять собой упорядоченное относительно значения абсциссы множество всех точек из исходного. Из него за линейное время можно получить отсортированный список. Очевидно, что если мы можем решать ВО2, то мы можем решить и ВО1, по- этому задача ВО1 может быть сведена к ВО2 за линейное время. Следовательно, нижняя оценка для ВО2 не ниже (( log ). Предварительная разработка алгоритма построения выпуклой оболочки Для начала рассмотрим несколько малопродуктивных алгоритмов построения выпуклой оболочки. Определение 3. Точка p выпуклого множества S называется крайней, если не существует пары точек a, b ( S таких, что p лежит на открытом отрезке ab. Очевидно, что подмножество крайних точек E является наименьшим подмножеством S, выпуклая оболочка которого, является выпуклой оболочкой множества S, или co v(E)=co v(S). Поэтому нам необходимо для нахождения выпуклой оболочки выполнить два шага: Определить крайние точки. Упорядочить эти точки так, чтобы они образовали выпуклый многоугольник. Теорема 3. Точка p не является крайней точкой множества S только тогда когда она лежит в некотором треугольнике, вершинами которого принадлежат S, но сама она не является вершиной этого треугольника. Эта теорема дает возможность построить алгоритм проверки крайности точки. Если мы имеем дело с множеством S мощности , то можно построить O( 3) треугольников. Проверка принадлежности точки треугольнику выполняется за постоянное количество операций. Следовательно, за время O( 3) можно определить, является ли точка крайней, а за O( 4) и для всех точек. Следующая теорема показывает, – в каком порядке должны быть точки в конечном множестве. Теорема 4. Последовательные вершины выпуклого многоугольника располагаются в порядке, соответствующем изменению угла относительно любой внутренней точки.

Упорядочить крайние точки множества можно относительно их центроида. Центроид множества для точек вычисляется за время O( ) арифметических операций. Грэхем предложил использовать для этого только три любые неколлинеарные точки множества S. В худшем случае это требует время O( ), но почти всегда это первые три точки. Упорядочить их можно за время O( log ). Таким образом, мы решаем задачу ВО1 за время O( 4). Метод обхода Грэхема Приведенный выше алгоритм является неэффективным, поэтому необходим способ более быстрого построения выпуклой оболочки. Для этого нам необходим другой подход. Грэхэм в одной из первых своих работ сумел показать, как можно, предварительно отсортировав точки относительно полярного угла с центром в какой-нибудь внутренней точке, можно найти крайние точки за линейное время. Пусть центр координат в какой-нибудь внутренней точке. Упорядочим точки относительно полярного угла, а если таковые совпадают относительно расстояния от центра координат. Так как обе точки лежат на одной прямой проходящей через центр координат, то для сравнения нам нет необходимости вычислять расстояние, а можно сравнивать сумму абсолютных значений координат. Отсортированные точки следует поместить в двусвязный список. Так как внутренние точки принадлежат некоторому треугольнику (Opq), где p и q – соседние вершины точке выпуклой оболочки. Суть алгоритма в последовательном просмотре отсортированного списка и удалении внутренних вершин. Оставшиеся точки будут являться вершинами выпуклой оболочки. Просмотр начнем с точки являющейся вершиной ВО. Для этого можно взять точку с минимальной абсциссой, а если их несколько, то и минимальной ординатой и пометить как начальную. После чего, обходим список, начиная с нее, против часовой стрелки и проверяем внутренний угол для текущей точки. Если он больше либо равен (, то удаляем вершину, а иначе переходим к следующей. Так как за каждый просмотр мы или удаляем одну вершину, или переходим к следующей, а просмотр заканчиваем при достижении вершины начало, которая не удалится, то мы выполняем не более шагов. Рассмотренный метод называют методом обхода Грэхема. Теорема 5. Выпуклая оболочка точек на плоскости может быть найдена за время O( log ) при памяти O( ) с использованием только арифметических операций и сравнений. Доказательство. Из предыдущего алгоритма видно, что в нем используются только арифметические операции и сравнения. Для нахождения внутренней точки и обхода требуется линейное время, а на сортировку уходит O( log ). Для представления списка нам достаточно O( ) памяти. Так как выше было доказано, что нижняя оценка для алгоритма решающего эту задачу равна O( log ), то получаем, что обход Грэхема имеет оптимальное время выполнения. Но он является оптимальным в худшем случае, а поведение его в среднем мы не изучили. Этот алгоритм имеет несколько недостатков. В нем используются тригонометрические функции, а так как их вычисление связано с большими затратами по времени, то желательно от них избавиться. Эндрю предложил метод решения этой проблемы. Если на плоскости заданы точек, то существует самая левая и самая правая точки, и они являются вершинами выпуклой оболочки.

Фундаментальные каталоги Фундамента'льные катало'ги, звёздные каталоги , фиксирующие на небе с максимальной точностью фундаментальную систему небесных экваториальных координат — основу для изучения движений небесных светил и определения астрономических координат, времени и азимута для точек на поверхности Земли. Фундаментальная система координат задаётся совокупностью данных Ф. к., включающей для некоторого числа равномерно распределённых по небесной сфере звёзд средние экваториальные координаты (прямые восхождения и склонения) для выбранной начальной эпохи и изменения этих координат как вследствие прецессии, так и вследствие собственных движений звёзд. Это позволяет воспроизводить фундаментальную систему для любой эпохи, отличной от эпохи каталога. Ф. к. получаются в результате совместной обработки многих звёздных каталогов, результатов наблюдений на разных обсерваториях в разные эпохи. Сравнительный анализ исходных каталогов позволяет ослабить систематические и случайные ошибки данных, приводимых в Ф. к. Нульпункты фундаментальной системы (ориентация плоскости экватора и положения точки весеннего равноденствия) определяются по наблюдениям тел Солнечной системы

1. Построение решения задачи Гурса для телеграфного уравнения методом Римана

2. Организация, методы и программы селекции пчел

3. Решение задач на построение сечений в многогранниках методом следов

4. Методы и алгоритмы построения элементов систем статистического моделирования

5. Методы построения эмпирического знания в теории и методике физического воспитания

6. Построение экономической модели c использованием симплекс-метода
7. Построение экономической модели c использованием симплекс-метода
8. Один метод построения полигональных изображений

9. Новый подход к построению методов межпроцедурного анализа программ

10. Модификация метода построения тестов для конечных автоматов относительно неразделимости

11. Построение эвольвентных профилей зубьев колес методом обкатки

12. Изменение географической оболочки при добыче полезных ископаемых на примере Рускеальской мраморной ломки

13. Принцип построения налога на добавленную стоимость

14. Структуры экономического дискурса во французском языке. Роль коннекторов в построении аргументации

15. Методы исследования литературы

16. Национальное самосознание - главный фактор в построении могущественной и процветающей России

Сундук-бар, 40x30x75 см.
Такой бар не займет много места. А поэтому он гармонично впишется в интерьер абсолютно любого помещения. Сундук-бар будет лучшим подарком
8493 руб
Раздел: Аксессуары для вина
Фоторамка "Clip" (70x100 см).
Рамка настенная может располагаться как вертикально, так и горизонтально. Для фотографий размером: 70x100 см. Материал: стекло.
456 руб
Раздел: Размер 50x60 и более
Набор фломастеров "Korellos", 20 цветов.
Фломастеры с тонким стержнем. В наборе 20 ярких и насыщенных цветов. Тонкий стержень прекрасно подходит для точного и аккуратного
377 руб
Раздел: 13-24 цвета

17. Построение локальной компьютерной сети масштаба малого предприятия на основе сетевой ОС Linux

18. Построение сети передачи данных

19. Построение verilog-модели ber-тестера для проверки каналов связи телекоммуникационных систем

20. Телекоммуникационные компьютерные сети: эволюция и основные принципы построения

21. Построение систем распознавания образов

22. Разработка программы на языке LISP для построения кривых Серпинского i-го порядка
23. Построение формального языка L
24. Построение реалистичных изображений предметов сервировки стола (стакана, фужера, рюмки, заполненных напитками) ([Курсовая])

25. Построение функции предшествования по заданной КС-грамматике

26. Инсталляция Windows XP. Конфигурирование оболочки Windows XP, оптимизация работы

27. Структура исчисления предикатов построение логического вывода

28. История болезни - Сообщающаяся водянка оболочек правого яичка

29. Построение, разработка версий и планирование расследования

30. Комплексное исследование глобальных экологических проблем: от понятийного аппарата до модельных построений

31. Теплопроводность через сферическую оболочку

32. Расчет тепловой схемы парогенератора ПГВ-1000 с построением диаграмм t-Q, тепловой и гидродинамический расчеты

Счеты большие "Mapacha".
Благодаря этим красочным счётам малыш очень быстро научится считать! Счёты оснащены 10-ю осями, на каждой из которых расположено по 10
800 руб
Раздел: Счетные наборы, веера
Доска магнитно-маркерная.
Доска напольная в деревянной некрашеной раме, азбука и цифры на магнитах, маркер. Доска двухсторонняя, с одной стороны "белая"
1619 руб
Раздел: Доски магнитно-маркерные
Кружка керамическая "FIFA 2018", 650 мл.
Объем: 650 мл. Материал: керамика.
880 руб
Раздел: Кружки, посуда

33. Изучение построения робототехнических комплексов для нанесения лакокрасочных материалов в мебельной промышленности

34. Построение ГМССБ и развитие радиосвязи на морском флоте

35. Теплопроводность через сферическую оболочку

36. Проблемы построения теории сознания

37. Концепция построения системы управления Московского представительства японской корпорации

38. Построение и совершенствование систем управления
39. Овладение методикой построения экономико-математических моделей, решение конкретных задач по стратегическому планированию и прогнозированию
40. Античная программа построения наук

41. Основы построения телекоммуникационных систем

42. Особенности построения текстов Ремона Кено

43. Мастерство в построении сюжета. (По одному из произведений русской драматургии XX века. — А.В.Вампилов. «Утиная охота».)

44. Овалы Кассини и пузыри в моделировании мягких оболочек

45. Геометрические построения

46. Построение линии пересечения 2-х конусов и цилиндра

47. Воспалительные заболевания коньюнктивы и оболочек глаза

48. Строение оболочки клетки

Набор мисок с синими крышками, 5 предметов.
Разные по размерам и объему миски незаменимы на любой кухне, в них можно не только готовить и хранить салаты и закуски, но также красиво
346 руб
Раздел: Наборы
Планшет для пастелей "Сладкие грезы", А3, 18 листов.
Планшет для пастелей замечательно подходит для художественных техник, таких как пастель, масляная пастель, мел, карандаш или уголь,
420 руб
Раздел: Папки для акварелей, рисования
Багетная рама "Mia" (серебро), 30х40 см.
Багетные рамы предназначены для оформления картин, вышивок и фотографий. Оформленное изделие всегда становится более выразительным и
450 руб
Раздел: Размер 30x40

49. Литература - Педиатрия (Книга Методы УЗИ в невропатологии и нейрохирургии

50. Литература - Терапия (СОВРЕМЕННЫЕ МЕТОДЫ ОБСЛЕДОВАНИЯ ФУНКЦИИ ПОЧЕК)

51. Литература - Фармакология (методичка)

52. Слизистая оболочка полости рта при заболеваниях эндокринной системы

53. Построение управления в современном предприятии

54. Новые требования к построению организаций будущего
55. Построения коллектива с акцентом на решение задач или на поддержание отношений в нем
56. Построенные навечно: основные элементы структуры успешной организации

57. Москва и Московская губерния в годы построения социализма

58. Основные черты построения налоговой системы Франции

59. Построение бетонной плотины

60. Родина, как семья народов: построение тематических циклов занятий для старших дошкольников и младших школьников

61. Развитие логического мышления младших школьников при обучении построению вспомогательных моделей в процессе решения текстовых задач

62. Речевые построения, выдающие ложь

63. Методологические подходы к построению и объяснению истории психологии: перспективы содержательного синтеза.

64. Кольцевая регуляция и уровни построения движений

Глобус Земли физико-политический, рельефный, с подсветкой, 320 мм.
Глобус Земли физико-политический, рельефный, с подсветкой, питание от сети. Диаметр: 32 см. Материал: пластмасса. Крым в составе РФ.
1452 руб
Раздел: Глобусы
Качели подвесные Edu-play "До-Ре-Ми".
Качели подвесные Edu Play "До-Ре-Ми". Легкие по весу, простые в сборке. Устанавливать возможно дома и на улице. Надежные канаты
2535 руб
Раздел: Качели
Фоторамка "Вращающийся куб".
Декоративная фоторамка, выполненная в виде куба. На гранях куба вы сможете разместить шесть фотографии формата 10 см х 10 см. Куб
330 руб
Раздел: Мультирамки

65. К построению психофизической феноменологии в психиатрии (нейротрансмиттерная диссоциация и расстройства психики)

66. Цифровая первичная сеть - принципы построения и тенденции развития

67. К построению качественной регрессионной модели этнической идентичности

68. Построение новой железнодорожной линии

69. Построение эффективной системы управления персоналом организации

70. Построение и структура учебно-тренировочного занятия
71. Философское введение в "Основы построения систем искусственного интеллекта"
72. Религиозные построения авиаконструктора Сикорского

73. Влияние народного хозяйства на географическую оболочку

74. Банковская система. Особенности построения банковской системы в России

75. Бюджетная система России и принципы ее построения

76. Построение функции импорта Швеции

77. Построение дерева решений проекта

78. О возможности построения русской грамматики смыслов

79. Бухгалтерский баланс: назначение, принципы построения ,техника составления

80. Построение эффективных систем управления документами на предприятиях нефтегазовой отрасли

Набор для творчества "Свечи".
С помощью этого набора дети научатся делать настоящие восковые свечи своими руками. Оригинальные свечи будут красивым дополнением к
894 руб
Раздел: Наборы по изготовлению свечей
Набор кастрюль Nadoba "Maruska" (малый).
Вся посуда серии Maruska изготовлена из высококачественной нержавеющей стали 18/10. Толщина стенок - 0,6 мм. Прочное трехслойное
3393 руб
Раздел: Наборы кастрюль
Набор крепированной бумаги, 10 рулонов.
Крепированная бумага прекрасно подходит для воплощения творческих идей не только детей, но и взрослых. Насыщенный цвет бумаги сделает
359 руб
Раздел: Самоклеящаяся, флуоресцентная, перламутровая и прочие

81. Построение геологической модели и прогнозного разреза

82. Построение моделей виртуальной реальности по цифровых моделям открытых горных работ

83. Строение газовой оболочки Земли

84. Геометрические построения на местности

85. Проблемы построения правового государства в России

86. Построение местных сетей связи
87. Методология построения ЭС
88. Общие принципы построения систем отображения навигационной информации используемые в электронной картографии .

89. Опыт построения обучающей среды, основанной на гипертексте

90. Построение циклических кодов

91. Выбор оптимальных сетевых решений на базе многозадачных операционных систем для построения компьютерной сети вуза

92. Основы построения сетей

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

94. Примеры построения АСУ-СВЯЗЬ

95. Особенности построения корпоративных систем связи для крупных предприятий

96. ASP.NET: пример построения круговой диаграммы

Набор цветных карандашей Trio, 18 цветов, утолщенные.
В наборе 18 цветных утолщенных карандашей, пластиковый футляр. Карандаши утолщенной трехгранной формы особенно удобны для детской руки,
783 руб
Раздел: 13-24 цвета
Мольберт "Ника растущий", со счетами (синий).
Двусторонний мольберт для детей прекрасно подойдет для обучения и для развлечения. Одна сторона мольберта - магнитная доска для работы с
1790 руб
Раздел: Буквы на магнитах
Шкатулка РТО, 35.5х25.5х20 см (арт. 3678-RT-60).
1937 руб
Раздел: Шкатулки для рукоделия

97. Java: Средства построения отчётов для Java-приложений

98. Разработка файловой оболочки

99. Построение многооконных приложений для Windows


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.