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

Нажмите для полного просмотра!

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №2

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №3

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №4

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №5

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №6

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

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №8

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №9

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №10

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №11

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №12

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №13

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №14

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №15

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №16

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №17

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №18

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки, слайд №19

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки Рандомизированные геометрические алгоритмы Рандомизированная пошаговая конструкция: n объектов, составляющих входные данные к задаче, рассматриваются по одному в каждый момент времени в произвольном порядке, и вычисляется результат воздействия каждого добавленного объекта на решение задачи. Для многих геометрических задач этот подход похож на другие известные алгоритмы, за исключением того, что в них обычно объекты обрабатываются в порядке, существующем на входе, а не в произвольном порядке.

Слайд 3

Описание слайда:

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ Рандомизированная пошаговая сортировка Дано n чисел, которые нужно отсортировать. Схема сортировки: После i-ого из n шагов (1 < i < n) имеем i вставленных чисел в отсортированном списке. Эти i отсортированных чисел разобьют ранги (n-i) еще не отсортированных чисел на (i+1) интервалов. (i+1)-ый шаг состоит в выборе одного из (n-i) еще не отсортированных чисел случайным образом и вставки его в отсортированный список.

Слайд 4

Описание слайда:

Рандомизированная пошаговая сортировка

Слайд 5

Описание слайда:

Рандомизированная пошаговая сортировка Какая работа требуется, чтобы сохранить указатели на каждое число? Мы вставляем число х, указатель которого указывает на интервал I. При вставке х, мы имеем три задачи: найти все числа, указатели которых указывают на I; (2) обновить указатели всех чисел, чьи указатели указывают на I; (3) удалить указатель от х к I.

Слайд 6

Описание слайда:

Рассмотрим работу, проделанную на i-ом шаге Обратный анализ: представим, что алгоритм выполняется назад, начиная с того, что уже имеется отсортированный список. При анализе i-ого шага прямого алгоритма мы представляем, что удаляется одно из i чисел в отсортированном списке и обновляются указатели. Работа по обновлению указателей в этом случае такая же, как если бы алгоритм выполнялся вперед как обычно. Ключевой момент в обратном анализе: так как в первоначальном алгоритме числа были добавлены в произвольном порядке, то в обратном анализе мы можем принять, что каждое число в отсортированном списке равновероятно может быть удалено на этом шаге.

Слайд 7

Описание слайда:

Работана i-ом шаге Каково ожидаемое число указателей, которые должны быть обновлены на этом шаге? Так как у нас i интервалов и (n-i+1) указателей, оставшихся после удаления, то ожидаемое число указателей, которые были изменены на i-ом шаге - О((n-i)/i), которое есть О(n/i). Просуммируем проделанную работу по всем шагам и получим верхнюю границу математического ожидания полной работы. Так как где  - константа Эйлера, то получаем O( ) = = О(n lоg n).

Слайд 8

Описание слайда:

Рандомизированный алгоритм построения выпуклой оболочки S – множество всех точек на плоскости; conv(S) – выпуклая оболочка множества S; Для упрощения предполагаем, что в S нет трех точек лежащих на одной прямой

Слайд 9

Описание слайда:

Пример работы алгоритма

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Пошаговое описание 1. Построить выпуклую оболочку из трех точек conv(S3). 2. Найти точку р0 во внутренней области conv(S) - это центр масс треугольника conv(S3). 3. Для каждой точки p определить ребро conv(S3), пересекаемое отрезком pp0, и сформировать двунаправленный указатель от р на ребро и обратно. При это исключить из дальнейшего рассмотрения точки, находящиеся внутри conv(S3).

Слайд 12

Описание слайда:

Построение произвольного треугольника

Слайд 13

Описание слайда:

Нахождение центра масс треугольника

Слайд 14

Описание слайда:

Слайд 15

$По шаговое описание (продолжение) 4. ПОКА (S\Si-1 не пусто) { Выбрать случайным образом точку pi из S\Si-1; Найти в conv(Si-1) вершину v1, которая...$

Описание слайда:

По шаговое описание (продолжение) 4. ПОКА (S\Si-1 не пусто) { Выбрать случайным образом точку pi из S\Si-1; Найти в conv(Si-1) вершину v1, которая является левой соседней (опорной) для pi в conv(Si). В процессе поиска запомнить в списке recheck указатели от удаляемых ребер; Найти в conv(Si-1) вершину v2, которая является правой соседней (опорной) для pi в conv(Si), дополнив при этом список recheck указателями от удаляемых ребер; Вставить pi в выпуклую оболочку, сформировав conv(Si); Для каждой точки , указатель на которую содержится в списке recheck, обновить её указатель на ребро conv(Si), пересекаемое отрезком рр0, указав его на [pi,v1] или [pi,v2]. При этом исключить из дальнейшего рассмотрения точки, которые попадают внутрь conv(Si); }

Слайд 16

Описание слайда:

Нахождение соседних вершин для выбранной точки

Слайд 17

Описание слайда:

Добавление новой вершины

Слайд 18

Описание слайда:

Построенная выпуклая оболочка

Слайд 19

Описание слайда:

Теорема: Среднее время работы описанного выше рандомизированного алгоритма для вычисления выпуклой оболочки n точек на плоскости - О(n log2 n). Теорема: Среднее время работы описанного выше рандомизированного алгоритма для вычисления выпуклой оболочки n точек на плоскости - О(n log2 n).