Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Построение и анализ алгоритмов. Динамическое программирование. Оптимальные деревья поиска. (Лекция 4)

Содержание

16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало в Лекции 3.См. также раздел 2.8 пособия «Деревья кодирования и поиска»
16.02.2016Динамическое программированиеПостроение и анализ алгоритмовЛекция 4Динамическое программированиеОптимальные деревья поиска 16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало в Лекции 3.См. также раздел Оптимальные деревья поискаРанее при рассмотрении БДП, как правило, предполагалось, что для поиска 16.02.2016Динамическое программированиеПример дерева поиска из трёх элементов a1  Заданы вероятности предъявления элемента x для поиска: P (x = a1) = α; P (x = a2) = β; P Постановка задачиПоиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1  Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0  Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в виде Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с задачей Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных деревьев Конец повторения прошлой лекции16.02.2016Динамическое программирование Построение оптимальных деревьев поискаДано: набор элементов a1  Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода динамического ИдеяTij -поддерево БДП из элементов(при 0 ≤ i ≤ j ≤ n). корнем поддерева может быть ОбозначенияПусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,nL(X) - Вклад поддерева Tij в стоимость C0,nгдеCij - стоимость поддерева Tij. wij - вес поддерева Tij.16.02.2016Динамическое программирование Идея: структура дерева + принцип оптимальности16.02.2016Динамическое программирование Преобразование+wij не зависит от структуры поддерева Tij 16.02.2016Динамическое программирование Cii = 0разности индексов k – 1 − i  и j – k  в слагаемых Ci,k−1  и  Ck,j  меньше, чем Таблица (аналогия с задачей о перемножении цепочки матриц)16.02.2016Динамическое программирование for (i =0; i См. пример в файле «2_08_ОДП.doc»С.67,68-…16.02.2016Динамическое программирование Построение БДП по таблице значений numBinT MakeOptBST (int i, j ){ int k; ElemBinT root; Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j 16.02.2016Динамическое программированиеВместо k = (i +1) .. j ⇒ k См. с.72 Так в ранее рассмотренном примере на последнем шаге при вычислении 16.02.2016Динамическое программированиеКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ
Слайды презентации

Слайд 2 16.02.2016
Динамическое программирование
Пример 3. Оптимальные деревья поиска
См. начало в

16.02.2016Динамическое программированиеПример 3. Оптимальные деревья поискаСм. начало в Лекции 3.См. также

Лекции 3.
См. также раздел 2.8
пособия «Деревья кодирования и

поиска»


Слайд 3 Оптимальные деревья поиска
Ранее при рассмотрении БДП, как правило,

Оптимальные деревья поискаРанее при рассмотрении БДП, как правило, предполагалось, что для

предполагалось, что для поиска различные ключи предъявляются с равной

вероятностью.

Пусть теперь заранее известно, что некоторые ключи предъявляются чаще других.
Тогда расположение «частых» ключей ближе к корню дерева сократит время их поиска и, возможно, среднее время поиска (по разным предъявлениям ключей).

16.02.2016

Динамическое программирование

Слайд 4 16.02.2016
Динамическое программирование
Пример дерева поиска из трёх элементов a1 

16.02.2016Динамическое программированиеПример дерева поиска из трёх элементов a1 

Слайд 5 Заданы вероятности предъявления элемента x для поиска: P

Заданы вероятности предъявления элемента x для поиска: P (x = a1) = α; P (x = a2) = β;

(x = a1) = α; P (x = a2) = β; P (x = a3) = γ.
16.02.2016
Динамическое программирование
Среднее (по всем

предъявлениям x) число сравнений (стоимость) в случаях успешного поиска как функция переменных α, β и γ,

Слайд 6 Постановка задачи
Поиск будет осуществляться среди набора данных a1, a2, …, an–1, an.

Постановка задачиПоиск будет осуществляться среди набора данных a1, a2, …, an–1, an. Пусть последовательность упорядочена: a1 


Пусть последовательность упорядочена:
a1 

успешных исходов поиска, 
т. е.  Ai : (x = ai) для i ∈ 1..n,
B0, …, Bn - события, соответствующие вариантам неудачных исходов поиска,
 т. е.  Bi : (ai < x < ai+1) для i ∈ 0..n.
Здесь для упрощения записи событий B0 и Bn добавлены фиктивные элементы a0 = −∞ и an+1 = +∞, которые не должны использоваться в алгоритме.

16.02.2016

Динамическое программирование

Слайд 7 Все эти 2n + 1 событий (исходов поиска)


Все эти 2n + 1 событий (исходов поиска) могут быть упорядочены: B0 

могут быть упорядочены:
B0 


pi = P (Ai) для i ∈ 1..n, и qi = P (Bi) для i ∈ 0..n.
При этом Σi∈1..n pi + Σi∈0..n qi = 1.

События Ai соответствуют внутренним узлам расширенного дерева поиска, а события Bi – внешним узлам (листьям) расширенного дерева поиска.

16.02.2016

Динамическое программирование

Постановка задачи (продолжение)



Слайд 8 Тогда среднее число (математическое ожидание) сравнений при поиске

Тогда среднее число (математическое ожидание) сравнений при поиске можно записать в

можно записать в виде



где l (x) – уровень узла

x (или длина пути от корня до узла x) в БДП.
Здесь уровень узла определён так, что l (корень) = 0.

16.02.2016

Динамическое программирование


Постановка задачи (продолжение)

Итак, задача состоит в том, чтобы по заданным весам


построить БДП, минимизирующее значение C0,n .


Слайд 9 Такое дерево называют оптимальным БДП.

Есть ли сходство

Такое дерево называют оптимальным БДП. Есть ли сходство этой задачи с

этой задачи с задачей построения оптимального префиксного кода ?
В

чём сходство, в чём различие?
Ответ.


16.02.2016

Динамическое программирование

Постановка задачи (продолжение)

Слайд 10 Очевидное решение поставленной задачи состоит в переборе всех

Очевидное решение поставленной задачи состоит в переборе всех структурно различных бинарных

структурно различных бинарных деревьев с n узлами и выборе

дерева с наименьшей стоимостью C0,n .
Однако поскольку (см. лекции про БДП) число bn структурно различных бинарных деревьев с n узлами есть



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

16.02.2016

Динамическое программирование


Слайд 11 Конец повторения прошлой лекции
16.02.2016
Динамическое программирование

Конец повторения прошлой лекции16.02.2016Динамическое программирование

Слайд 12 Построение оптимальных деревьев поиска
Дано:
набор элементов a1 

Построение оптимальных деревьев поискаДано: набор элементов a1 

набор весов

Σi∈1..n pi + Σi∈0..n qi = 1.

Требуется: по заданным весам построить БДП, минимизирующее значение

C0,n.





16.02.2016

Динамическое программирование


Слайд 13 Пусть имеется оптимальное дерево.
Согласно принципу оптимальности, лежащему

Пусть имеется оптимальное дерево. Согласно принципу оптимальности, лежащему в основе метода

в основе метода динамического программирования, левое и правое поддеревья

этого дерева в свою очередь также должны быть оптимальны.

16.02.2016

Динамическое программирование

Идея

Слайд 14 Идея
Tij -поддерево БДП из элементов
(при 0 ≤ i ≤ j ≤ n).

ИдеяTij -поддерево БДП из элементов(при 0 ≤ i ≤ j ≤ n). корнем поддерева может












корнем поддерева может быть любой из элементов , т. е.

k ∈ i +1..j.

16.02.2016

Динамическое программирование









Слайд 15 Обозначения
Пусть
l = l(rij)- уровень корня rij поддерева Tij

ОбозначенияПусть l = l(rij)- уровень корня rij поддерева Tij в дереве T0,nL(X)

в дереве T0,n

L(X) - уровень узла, соответствующего событию X,

в поддереве Tij . ( L(rij)=0 )

Тогда l(X) = L(X) + l, где X ∈{Bi, Ai+1, …, Bj}.

16.02.2016

Динамическое программирование


l = l(rij)

rij

L(X)

l(X)

Слайд 16 Вклад поддерева Tij в стоимость C0,n




где


Cij - стоимость

Вклад поддерева Tij в стоимость C0,nгдеCij - стоимость поддерева Tij. wij - вес поддерева Tij.16.02.2016Динамическое программирование

поддерева Tij.
wij - вес поддерева Tij.
16.02.2016
Динамическое программирование



Слайд 17 Идея: структура дерева + принцип оптимальности











16.02.2016
Динамическое программирование









Идея: структура дерева + принцип оптимальности16.02.2016Динамическое программирование

Слайд 18 Преобразование
+
wij не зависит от структуры поддерева Tij
16.02.2016
Динамическое

Преобразование+wij не зависит от структуры поддерева Tij 16.02.2016Динамическое программирование

программирование



Слайд 19
Cii = 0
разности индексов k – 1 − i  и j – k  в слагаемых Ci,k−1 

Cii = 0разности индексов k – 1 − i  и j – k  в слагаемых Ci,k−1  и  Ck,j  меньше,

и  Ck,j  меньше, чем разность индексов j – i  в Cij.
L

= j – i , L=0..n

16.02.2016

Динамическое программирование

Слайд 20 Таблица (аналогия с задачей о перемножении цепочки матриц)
16.02.2016
Динамическое

Таблица (аналогия с задачей о перемножении цепочки матриц)16.02.2016Динамическое программирование

программирование

Слайд 21 for (i =0; i

for (i =0; i

первая строка
for (L=1; L

i++) {
j = i + L; // заполнение T(i, j):
w[i][ j] = w[i][j −1] + (p[j]+q[j]);
c[i][j] = +∞;
for (k =i +1 ; k< j-1; k++) { s = c[i][k −1] + c [k][j];
if (s < c[i][j] ){
c[i][j] = s;
num[i][j] = k
};
}
c[i][j] = c[i][j] + w[i][j];
}
}

16.02.2016

Динамическое программирование

n 2/2 элементов памяти и n 3/3 выполнений тела внутреннего цикла

Вычисление таблицы

Слайд 22
См. пример в файле «2_08_ОДП.doc»
С.67,68-…
16.02.2016
Динамическое программирование

См. пример в файле «2_08_ОДП.doc»С.67,68-…16.02.2016Динамическое программирование

Слайд 23 Построение БДП по таблице значений num
BinT MakeOptBST (int i, j

Построение БДП по таблице значений numBinT MakeOptBST (int i, j ){ int k; ElemBinT

)
{ int k; ElemBinT root;
BinT L, R;
k  = num[i ][j

];  root  = a[k];
if (i < k −1) L = MakeOptBST (i, k −1);
else L = NULL;
if (k < j ) R  = MakeOptBST (k, j);
else R  = NULL;
return  ConsBT (root, L, R);
} //MakeOptBST
 
со стартовым вызовом T = MakeOptBST (0, n).

16.02.2016

Динамическое программирование

Слайд 24 Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j
16.02.2016
Динамическое программирование


Вместо k = (i +1) .. j

Модификация Д.Кнута ri,j −1 ≤ rij ≤ ri +1,j 16.02.2016Динамическое программированиеВместо k = (i +1) .. j ⇒ k =

⇒ k = num[i ][j −1]  .. num[i +1][j ]



Слайд 25 См. с.72
Так в ранее рассмотренном примере
на последнем

См. с.72 Так в ранее рассмотренном примере на последнем шаге при

шаге при вычислении C0,4 
вместо рассмотрения четырёх кандидатов на роль

корня дерева (см. с.70)
ak (k = 1, 2, 3, 4)
можно ограничиться лишь двумя (a1 и a2), поскольку
num[0, 3] ≤ k ≤ num[1, 4],
а num[0, 3] = 1 и num[1, 4] = 2.

16.02.2016

Динамическое программирование

  • Имя файла: postroenie-i-analiz-algoritmov-dinamicheskoe-programmirovanie-optimalnye-derevya-poiska-lektsiya-4.pptx
  • Количество просмотров: 100
  • Количество скачиваний: 0
- Предыдущая Сочинение на тему Какие события и впечатления в жизни, помогают человеку взрослеть
Следующая - Аттестационная работа. Географические методы изучения истории на примере реконструкции боёв Гражданской войны под Екатеринбургом

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

Виды графических планшетов 1 Виды графических планшетов 1 244
Модели жизненного цикла разработки программного продукта. (Тема 5) Модели жизненного цикла разработки программного продукта. (Тема 5) 140
Олимпиада Олимпиада 109
Русские народные сказки в композиции слайдов PowerPoint Русские народные сказки в композиции слайдов PowerPoint 97
Новая почта. Что такое РРО Новая почта. Что такое РРО 104
SYSmark 2014. Тестирование процессоров SYSmark 2014. Тестирование процессоров 116
История интернета История интернета 182
Информация. Знания. Информационные процессы Информация. Знания. Информационные процессы 85
Общение в социальных сетях и правильное их использование. Общение в социальных сетях и правильное их использование. 138
Математические модели Математические модели 116
Весёлая информатика Весёлая информатика 119
Технические средства информационных технологий Технические средства информационных технологий 123
Презентация по информатике по теме Биометрические системы защиты (11класс) Презентация по информатике по теме Биометрические системы защиты (11класс) 125
История развития компьютерной техники История развития компьютерной техники 422
Голосовая почта Голосовая почта 103
Изучение социально-политического значения проекта НЭБ для развития в России информационного общества и информационной экономики Изучение социально-политического значения проекта НЭБ для развития в России информационного общества и информационной экономики 85
Форматирование и редактирование текста Форматирование и редактирование текста 95
Информационно-психологическая безопасность личности, общества и государства Информационно-психологическая безопасность личности, общества и государства 109
Средства передачи информации Средства передачи информации 143
Вред сотовых телефонов Вред сотовых телефонов 105
Принцип работы телевидения Принцип работы телевидения 151
Влияние интернета и компьютера на здоровье человека Влияние интернета и компьютера на здоровье человека 111
Антивирус орнату Антивирус орнату 105
Презентация Первые шаги в Blender Презентация Первые шаги в Blender 253
Локальные компьютерные сети Локальные компьютерные сети 95
Знакомство с программированием Знакомство с программированием 98
Для чего нужна программа Power Point Для чего нужна программа Power Point 103
Процедуры и функции на языке Pascal Процедуры и функции на языке Pascal 105
Алгоритмы и исполнители Алгоритмы и исполнители 121
Уточнение ИС (развитие, проектирование - Elaboration) в RUP Уточнение ИС (развитие, проектирование - Elaboration) в RUP 86