Слайды и текст доклада
Pic.1
Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки
Pic.2
Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки Рандомизированные геометрические алгоритмы Рандомизированная пошаговая конструкция: n …
Pic.3
РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ В ЗАДАЧАХ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ Рандомизированная пошаговая сортировка Дано n чисел, которые нужно отсортировать. Схема сортировки: После i-ого из n шагов (1 < i …
Pic.4
Рандомизированная пошаговая сортировка
Pic.5
Рандомизированная пошаговая сортировка Какая работа требуется, чтобы сохранить указатели на каждое число? Мы вставляем число х, указатель которого указывает на интервал I. При вставке х, мы имеем три …
Pic.6
Рассмотрим работу, проделанную на i-ом шаге Обратный анализ: представим, что алгоритм выполняется назад, начиная с того, что уже имеется отсортированный список. При анализе i-ого шага прямого …
Pic.7
Работана i-ом шаге Каково ожидаемое число указателей, которые должны быть обновлены на этом шаге? Так как у нас i интервалов и (n-i+1) указателей, оставшихся после удаления, то ожидаемое число …
Pic.8
Рандомизированный алгоритм построения выпуклой оболочки S – множество всех точек на плоскости; conv(S) – выпуклая оболочка множества S; Для упрощения предполагаем, что в S нет трех точек лежащих на …
Pic.9
Пример работы алгоритма
Pic.10
Рандомизированный алгоритм построения выпуклой оболочки
Pic.11
Пошаговое описание 1. Построить выпуклую оболочку из трех точек conv(S3). 2. Найти точку р0 во внутренней области conv(S) - это центр масс треугольника conv(S3). 3. Для каждой точки p определить …
Pic.12
Построение произвольного треугольника
Pic.13
Нахождение центра масс треугольника
Pic.15
По шаговое описание (продолжение) 4. ПОКА (S\Si-1 не пусто) { Выбрать случайным образом точку pi из S\Si-1; Найти в conv(Si-1) вершину v1, которая является левой соседней (опорной) для pi в conv(Si). …
Pic.16
Нахождение соседних вершин для выбранной точки
Pic.17
Добавление новой вершины
Pic.18
Построенная выпуклая оболочка
Pic.19
Теорема: Среднее время работы описанного выше рандомизированного алгоритма для вычисления выпуклой оболочки n точек на плоскости - О(n log2 n). Теорема: Среднее время работы описанного выше …
Скачать презентацию
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!