Вычислительная геометрия - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Вычислительная геометрия Лекция 1 Алгоритм Джарвиса – О(nh) Алгоритм Грехэма - О(n log n) Последовательный (открытый) алгоритм - О(n2) (в перспективе О(n log n)) Какова нижняя граница задачи ВО? Далее лекция 2

Слайд 2

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

Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций, которые не более чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение О(f(n)). Запись g (n)  О(f(n)) означает, что cуществуют: вещественная константа C > 0 и натуральная константа n0 , для которых g (n)  C f (n) при всех n  n0

Слайд 3

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

Асимптотические оценки Обозначение О(f(n))

Слайд 4

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

Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций, которые не менее чем в постоянное число раз превосходят f (n) при достаточно большом n, используется обозначение (f(n)). Запись g (n)  (f(n)) означает, что существуют : вещественная константа C > 0 и натуральная константа n0 , для которых g (n)  C f (n) при всех n  n0.

Слайд 5

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

Асимптотические оценки Обозначение (f(n))

Слайд 6

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

Асимптотические оценки Обозначения О(f(n)), (f(n)), (f(n)) Для указания множества функций того же порядка, что и f (n) при достаточно большом n, используется обозначение (f(n)) Запись g (n)  (f(n)) означает, что существуют : вещественные константы C1 > 0 и C2 > 0 и натуральная константа n0 , для которых C1 f (n)  g (n)  C2 f (n) при всех n  n0

Слайд 7

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

Асимптотические оценки Обозначение (f(n))

Слайд 8

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

Преобразуемость задач Задачи A и B

Слайд 9

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

Преобразуемость задач Утв.1 (Перенос нижней оценки): (A требует не менее T(n) времени) & (A  B)  (B требует не менее T(n) – O((n)) времени). Док-во (от противного): Пусть B требует менее T(n) – O((n)) времени, тогда A может быть решена за время Меньшее, чем T(n) – O((n)) + O((n)) = T(n), что противоречит посылке

Слайд 10

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

Преобразуемость задач Утв.2 (Перенос верхней оценки): (B требует не более T(n) времени) & (A  B)  (A требует не более T(n) + O((n)) времени). ---------------------------------------------------------------- Все это при (n) = O(T(n)) ----------------------------------------------------------- О(n) – для верхних оценок, (n) – для нижних оценок, (n) – для асимптотически точных оценок

Слайд 11

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

Оценки сложности задачи ВО Задача сортировки: Вход: X = (x1,x2, …, xn). Размер задачи - n. Задача ВО: Вход: S = (p1, p2, …, pn), где pj = (xj, yj). Размер задачи - n. Выход: CH(S) - упорядоченный список вершин ВО

Слайд 12

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

Преобразование CH(S)  Sort(X) 1) Преобразование входа CH(S): Найти «нижнюю» крайнюю точку. 2) Сортировка по полярному углу – Sort 3) Преобразование выхода Sort в выход CH(S) – обход Грэхема. Отсюда – задача ВО м.б. решена за время O(n log n). Это верхняя оценка.

Слайд 13

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

Преобразование Sort(X)  CH(S) Преобразование входа XS: pj = (xj, xj2). Точки pj лежат на параболе. 2) Построение CH(S)

Слайд 14

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

Алгоритм на основе сбалансированного разделения и слияния Алгоритм на основе слияния выпуклых оболочек (1) Func MergeCH(S): List; begin if S k then Построить CH(S) прямым методом else {1:} Найти S1 и S2 – разбиение S, такое, что S1 S2; {2:} P1 := MergeCH(S1); P2 := MergeCH(S2); {3:}Return CH_Union_ConvP(P1, P2) fi end { MergeCH }

Слайд 15

$Алгоритм на основе сбалансированного разделения и слияния func CH_Union_ConvP(P1, P2): List; {Выпуклая оболочка выпуклых многоугольников P1 и P2}...$

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

Алгоритм на основе сбалансированного разделения и слияния func CH_Union_ConvP(P1, P2): List; {Выпуклая оболочка выпуклых многоугольников P1 и P2} begin Найти точку p  ] P1 [ ; {т.е. точку p – внутреннюю для P1 } if not (p  ] P2 [ ) then Найти клин upv {u, v  P2} и освещенную цепь u  v; Удалить цепь ] u  v [ из P2, т.е. P2 :=P2 \ { ] u  v [ } fi; { P1 и P2 упорядочены относительно точки p} L := Слияние списков (L(P1), L(P2)); Применить обход Грэхема к L (результат: P); Return P end { CH_Union_ConvP }

Слайд 16

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

Слайд 17

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

Общая идея метода «разделяй и властвуй» Общая идея метода «разделяй и властвуй» “Divide et impera” Три стадии: 1. Разделение – разбиение данных на две или более составляющих (части); если размер данных меньше некоторой пороговой величины, то возвращается готовый результат. 2. Рекурсия – рекурсивно решается каждая из подзадач для составляющих. 3. Слияние – полученные результаты для составляющих объединяются (сливаются) в единый результат. Быстрая сортировка – тоже пример подхода «разделяй и властвуй». Основные фазы: разделение и рекурсивные вызовы. Фаза слияния тривиальна и не требует дополнительных действий.

Слайд 18

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

Рекуррентное соотношение: Рекуррентное соотношение: T(n) = T(n/2 ) + T(n/2 ) + u(n); T(1) = b. Разделение+Слияние: u(n)  an; Тогда T(n) = O(n log2n).

Слайд 19

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

Сложность алгоритма Сложность алгоритма сбалансированного разделения и слияния (1) Итеративное решение Пусть n = 2q (для простоты). Тогда T(n) = 2T(n/2) + an; T(1) = b. T(n) = 2(2T(n/22) + an/2) + an= 22T(n/22) + 2an= = 22(2T(n/23) + an/22) + 2an= 23T(n/23) + 3an= =…= 2kT(n/2k) + kan; При k=q: T(n/2k) =T(1) = b, 2k = n, q = log2n T(n) = 2kT(n/2k) + kan = bn + an log2n  Cn log2n , где С = a + b (например). Т.о. T(n) = O(n log2n).

Слайд 20

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

Сложность алгоритма Сложность алгоритма сбалансированного разделения и слияния (2) По индукции покажем, что решение T(n) = T(n/2 ) + T(n/2 ) + u(n); T(1) = b при u(n) = O(n) есть T(n) = O(n log2n). Пусть u(n)  аn и T(k)  Ck log2k при k < n. T(n)  C n/2 log2 n/2 + C n/2 log2 n/2 + аn  x  x, x < x + 1  C n/2 log2(n/2)+ C n/2 log2 (n/2 +1) + аn 

Слайд 21

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

Анализ сложности (2 - продолжение) Анализ сложности (2 - продолжение) C n/2 log2(n/2)+ C n/2 log2 (n/2)(1 + 2/n) + аn   C n/2 log2(n/2)+ C n/2 log2 (n/2)+C n/2 log2(1 + 2/n) + аn  log2 (x +1)  x, n/2 + n/2 = n/2  C n log2(n/2)+ C n/2 (2/n) + аn   C n log2(n/2)+ C (n/2+1) (2/n) + аn   C n log2n + C (1 + 2/n) + (а – С)n  C n log2n (при C > a)

Теги Вычислительная геометрия

Похожие презентации