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

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

Содержание ▲

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

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

Слайд 1

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

Построение и анализ алгоритмов Лекция 4.3 = 5.1 Динамическое программирование АНАЛОГИИ

Слайд 2

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

АНАЛОГИИ Решение методом динамического программирования Задачи: Перемножение цепочки матриц Оптимальные БДП Задача Х и т.п.

Слайд 3

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

Оценка количества узлов дерева Оценить количество узлов дерева в общем случае можно подсчетом всех возможных вариантов расстановок скобок в произведении матриц. Пусть pn – число вариантов расстановок скобок в произведении n сомножителей (включая самые внешние скобки). Например, для трех сомножителей abc имеем два варианта (a(bc)) и ((ab)c), а следовательно, p3 = 2. В общем случае, считая, что «последнее» по порядку умножение может оказаться на любом из n –1 мест, запишем следующее рекуррентное соотношение: pn = p1 pn –1 + p2 pn –2 + … + pn –2 p2 + p n –1 p1.

Слайд 4

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

Начальное условие p1 = 1. Далее Начальное условие p1 = 1. Далее p2 = p1 p1 = 1, p3 = p1 p2 + p2 p1 = 2, p4 = p1 p3 + p2 p2 + p3 p1 = 5. Оказывается [7, с. 393], что решением этого рекуррентного уравнения являются так называемые числа Каталана pn = Сn –1, где Сn =(2 k | k) / (k +1), а запись (n | m) обозначает биномиальный коэффициент (n | m) = n!/(m! (n – m)!). При больших значениях n справедливо

Слайд 5

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

Слайд 6

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

Слайд 7

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

b2 = b0 b1 + b1 b0 = 2, b2 = b0 b1 + b1 b0 = 2, b3 = b0 b2 + b1 b1 + b2 b0 = 5, b4 = b0 b3 + b1 b2 + b2 b1 + b3 b0 = = 5 + 2 + 2 + 5 = 14 Решением рекуррентного уравнения являются так называемые числа Каталана Сn, т. е. bn = Сn. Ранее (Лекция 13, слайды хх, хх) были приведены: общая формула для чисел Каталана и асимптотическое соотношение

Слайд 8

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

Решение методом динамического программирования Структура оптимального решения Рекуррентное соотношение Вычисление оптимальной стоимости (по рекуррентному соотношению) Построение оптимального решения Проиллюстрировать на предыдущих примерах

Слайд 9

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

Задача: оптимальная триангуляция выпуклого многоугольника

Слайд 10

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

Задача: оптимальная триангуляция выпуклого многоугольника Триангуляция (диагонали не пересекаются внутри многоугольника)

Слайд 11

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

Задача: оптимальная триангуляция многоугольника На треугольниках определена весовая функция w(vivjvk) Например, w(v1v2v3) = v1v2+v2v3 +v2v3

Слайд 12

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

Количество способов триангуляции

Слайд 13

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

Количество способов триангуляции

Слайд 14

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

Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 1

Слайд 15

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

Динамическое программирование Вычисление таблиц: mi,i+1 = 0, {при i=1..n-1} mi,i+2 = w(i,i+1,i+2), {при i=1..n-2} mi,i+3 =… … mi,i+n-2  m1,n-1 , m2,n {при i=1, 2} mi,i+n-1 = m1n {при i=1} Время С1n3, память С2n2

Слайд 16

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

Рекуррентная формула для веса оптимальной триангуляции многоугольника (ОТМ), 2

Слайд 17

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

Упражнения Доказать что триангуляция n – угольника содержит n-2 треугольника и n-3 диагоналей. Пусть вес треугольника = его площади. Можно ли упростить алгоритм поиска ОТМ? Весовая функция определена на множестве диагоналей многоугольника. ОТМ – сумма весов диагоналей минимальна. Как свести эту задачу к рассмотренной?

Слайд 18

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

Связь задач

Слайд 19

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

Связь задач

Слайд 20

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

Слайд 21

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

Слайд 22

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

Преобразование «Ползущий червь»

Слайд 23

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

Литература Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ : учеб./ М.: МЦМНО, 1999. – 960 с. (Классические учебники: Computer science). (Доп. тираж 2000 г., 2001 г., 2002 г.) [Опт.Трианг.] Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2007, 2009. – 1296 с. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 3-е издание.: Пер. с англ. – М.: ООО «И.Д. Вильямс», 2013. – 1328 с.