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

Содержание

Слайд 2

Метод «разделяй и властвуй» ФПМИ БГУ

Метод «разделяй и властвуй»

ФПМИ БГУ

Слайд 3

«Разделение» Задача разбивается на независимые подзадачи, т.е. подзадачи не пересекаются (две

«Разделение»
Задача разбивается на независимые подзадачи, т.е. подзадачи не пересекаются (две задачи

назовем независимыми, если они не имеют общих подзадач).

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

3. «Комбинирование»
Из отдельных решений подзадач строится решение исходной задачи.

«Разделяй и властвуй»

ФПМИ БГУ

Слайд 4

При разбиении задачи на подзадачи полезен принцип балансировки, который предполагает, что

При разбиении задачи на подзадачи полезен принцип балансировки, который предполагает, что

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

Принцип балансировки

ФПМИ БГУ

Слайд 5

Поиск максимального и минимального элементов Разделим массив на две части (предположим,

Поиск максимального и минимального элементов

Разделим массив на две части (предположим, что

n=2k).
В каждой из частей этим же алгоритмом найдём локальные max1, min1, max2 , min2.
Полагаем max=наибольший (max1 ,max2 ), min=наименьший (min1 ,min2 ).
Если в рассматриваемой области меньше 2-х элементов, то деление не выполняем, а за 1 сравнение определим максимальный и минимальный элемент области.

 

«Разделение»
(балансировка)

«Покорение»

«Комбинирование»

Последовательный поиск

Решение на основе принципа «разделяй и властвуй»

ФПМИ БГУ

Слайд 6

def MergeSort (l,r): if l ≠ r: k = (l +

def MergeSort (l,r):
if l ≠ r:
k = (l

+ r) // 2
MergeSort (l,k)
MergeSort (k+1,r)
MergeList (l,k,r)

Делим последовательность элементов на две части (границы l и r включаем; если сортируемая последовательность состояла из n элементов, то первая часть может содержать первых элементов, а вторая часть – оставшиеся; порядок следования элементов в каждой из полученных частей совпадает с их порядком следования в исходной последовательности). Если в последовательности только один элемент, то деление не выполняем.
Сортируем отдельно каждую из полученных частей этим же алгоритмом.
Производим слияние отсортированных частей последовательности так, чтобы сохранилась упорядоченность.

«Покорение»

«Комбинирование»

Сортировка массива слиянием

«Разделение» (балансировка)

ФПМИ БГУ

Слайд 7

def QuickSort(l, r): if l Partition QuickSort(l, j) QuickSort(i, r) Быстрая

def QuickSort(l, r):
if l < r:
Partition
QuickSort(l,

j)
QuickSort(i, r)

Быстрая сортировка массива Ч. Хоара

Выбираем в качестве сепаратора x медиану рассматриваемой области (за линейное от числа элементов время). Относительно сепаратора x делим массив на три части:
в первой части - элементы, которые меньше или вравны x;
во второй части - элемент x;
в третьей части – элементы, которые больше или равны x.
Сортируем отдельно I и III части этим же алгоритмом. Если в некоторой менее одного элемента, то ничего не делаем.
Происходит слияние отсортированных сегментов в один путем присоединения сегментов.

«Покорение»

«Комбинирование»

«Разделение»
(балансировка)

ФПМИ БГУ

Слайд 8

Динамическое программирование ФПМИ БГУ

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

ФПМИ БГУ

Слайд 9

Динамическое программирование Динамическое программирование применяется к задачам, в которых нужно что-то

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

Динамическое программирование применяется к задачам, в которых нужно что-то подсчитать

или к оптимизационным задачам.

ФПМИ БГУ

Задачи оптимизации. В таких задачах существует много решений, каждому из которых поставлено в соответствие некоторое значение. Необходимо найти среди всех возможных решений одно с оптимальным (наибольшим или наименьшим) значением. Например, во взвешенном графе между заданной парой вершин существует несколько маршрутов, каждый маршрут характеризуется своей длиной, и нам необходимо найти маршрут кратчайшей длины.

 

Слайд 10

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

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

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

ФПМИ БГУ

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

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

Слайд 11

1 2 x зависимые задачи (1) и (2)

1

2

x

зависимые задачи (1) и (2)

Слайд 12

Этапы динамического программирования Задача погружается в семейство вспомогательных подзадач той же

Этапы динамического программирования
Задача погружается в семейство вспомогательных подзадач той же природы.

Возникающие подзадачи могут являться зависимыми и должны удовлетворять следующим двум требованиям:
подзадача должна быть более простой по отношению к исходной задаче;
оптимальное решение исходной задачи определяется через оптимальные решения подзадач (в этом случае говорят, что задача обладает свойством оптимальной подструктуры, и это один из аргументов в пользу применения для ее решения метода «динамического программирования»).
Каждая вспомогательная подзадача решается (рекурсивно) только один раз. Значения оптимальных решений возникающих подзадач запоминаются в таблице, что позволяет не решать повторно ранее решенные подзадачи.
Для исходной задачи строится возвратное соотношение, связывающее значение оптимального решения исходной задачи со значениями оптимальных решений вспомогательных подзадач (т. е. методом восходящего анализа от простого к сложному вычисляем значение оптимального решения исходной задачи).
Данный этап выполняется в том случае, когда требуется помимо значения оптимального решения получить и само это решение. Часто для этого требуется некоторая вспомогательная информация, полученная на предыдущих этапах метода.

ФПМИ БГУ

Слайд 13

решаем задачу v w u z ранее решённые подзадачи z, u,

решаем задачу v

w

u

z

ранее решённые подзадачи z, u, w

ДП «назад»

f(v) = G

(f(z), f(u), f(w))

задача v уже решена

НЕ решённые
подзадачи x и y (обе зависимые от x)

подформировываем решение x из v

подформировываем решение y из v

f(x) = G( f(x), f(v) )

f(y) = G( f(y) , f(v) )

ФПМИ БГУ

ДП «вперед»

v

v

x

y

Слайд 14

10 8 не решена 4 2 3 решена 1 5 ФПМИ

10

8

не решена

4

2

3

решена

1

5

ФПМИ БГУ

6

9

7

решаем задачу 10

база ДП

ДП «назад»

ДП «назад»

(«ленивое»)

w

u

z

v

Слайд 15

Задача 1. Лягушка ФПМИ БГУ

Задача 1. Лягушка

ФПМИ БГУ

Слайд 16

Ответ: 14 Заданы n кочек. Лягушка сидит на первой кочке. На

Ответ: 14

Заданы n кочек.
Лягушка сидит на первой кочке.
На каждой

кочке сидят комарики, известно их число.
За один прыжок лягушка может прыгнуть на 2 или 3 кочки вперёд:
Оказавшись на кочке, лягушка скушает всех комариков, которые сидели там.
Необходимо определить максимальное число комариков, которые скушает лягушка, которой обязательно надо приземлиться на последней кочке.

комарики

ФПМИ БГУ

Слайд 17

ДП назад (одномерное): i-1 i-2 i-3 i ФПМИ БГУ

ДП назад (одномерное):

 

i-1

i-2

i-3

i

ФПМИ БГУ

Слайд 18

array i F 2 14 18 13 6 5 ФПМИ БГУ Ответ: 14

array

i

F

2

14

18

13

6

5

ФПМИ БГУ

Ответ: 14

Слайд 19

i+3 i+2 i+1 i ДП вперёд (одномерное): ФПМИ БГУ

i+3

i+2

i+1

i

ДП вперёд (одномерное):

ФПМИ БГУ

Слайд 20

i F 2 7 17 13 6 5 18 14 Время

i

F

2

7

17

13

6

5

18

14

Время работы алгоритма, основанного на методе ДП:

ФПМИ БГУ

array

Ответ: 14

Слайд 21

Полный перебор всех вариантов описывается n-м числом Фибоначчи: Время работы алгоритма

Полный перебор всех вариантов описывается n-м числом Фибоначчи:

Время работы алгоритма для

задачи «Лягушка», основанного на методе ДП:

ФПМИ БГУ

Слайд 22

Задача 2. Задача расстановки единиц ФПМИ БГУ

Задача 2. Задача расстановки единиц

ФПМИ БГУ

Слайд 23

Задана строка длины n. Имеется k единиц ( k≤n). Необходимо определить

Задана строка длины n.
Имеется k единиц ( k≤n).
Необходимо определить количество

способов, для того, чтобы расставить k единиц в строке длины n.

 

Количество способов можно посчитать комбинаторно:

Однако при больших значениях n и k итоговое значение уже может не помещаться в целочисленные типы данных.
Например, при подсчете числа сочетаний через факториал при
n = 100, k = 1
произойдет переполнение, но в тоже время при вычислении с помощью метода ДП не возникнет проблем, так как итоговое значение равно всего лишь 100.

ФПМИ БГУ

Слайд 24

+ ФПМИ БГУ

 

 

+

 

ФПМИ БГУ

Слайд 25

Обозначим F[i, j] - количество способов, для того, чтобы в строке

Обозначим
F[i, j] - количество способов, для того, чтобы в строке длины

i расставить j единиц.

 

ДП назад (двумерное):

число единиц

длина строки

ФПМИ БГУ

j единиц

Слайд 26

2 3 3 4 6 4 Время работы алгоритма: ФПМИ БГУ ДП назад (двумерное):

2

3

3

4

6

4

Время работы алгоритма:

ФПМИ БГУ

ДП назад (двумерное):

 

Слайд 27

Обозначим через F[i,j] - количество способов, для того, чтобы расставить j

Обозначим через F[i,j] - количество способов, для того, чтобы расставить j

единиц в строке длины i.

ДП вперёд (двумерное):

число единиц

длина строки

ФПМИ БГУ

Слайд 28

2 1 1 1 1 1 1 1 1 2 3

2

1

1

1

1

1

1

1

1

2

3

3

1

4

3

3

1

1

6

4

1

Время работы алгоритма:

ФПМИ БГУ

ДП вперёд (двумерное):

Слайд 29

Время работы алгоритма «Расстановка единиц», основанного на методе динамического программирования: Количество

Время работы алгоритма «Расстановка единиц», основанного на методе динамического программирования:

Количество способов

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

ФПМИ БГУ

Слайд 30

На практике, когда результат является достаточно большим числом, в задаче предлагается

На практике, когда результат является достаточно большим числом, в задаче предлагается

найти ответ по модулю (% p).

 

ФПМИ БГУ

 

 

Свойства модульной арифметики:

Малая теорема Ферма
Если p – простое число, а – целое число, которое не делится на p, то

эквивалентные формы записи:

 

Следствие из малой теоремы Ферма (a – целое, p – простое число):

 

Если два числа сравнимы по модулю p, т.е.

 

то это записывается:

Слайд 31

Задача 3. Оптимального перемножения группы матриц ФПМИ БГУ

Задача 3. Оптимального перемножения группы матриц

ФПМИ БГУ

Слайд 32

Порядок перемножения всех s матриц неоднозначен. Чтобы устранить неоднозначность, нужно расставить

Порядок перемножения всех s матриц неоднозначен. Чтобы устранить неоднозначность, нужно расставить

скобки. Порядок расстановки скобок однозначно определит последовательность перемножаемых матриц.
Поскольку матричное произведение ассоциативно, то результат не зависит от расстановки скобок, но порядок перемножения может существенно повлиять на время работы алгоритма.

Заданы s матриц:
Определить, какое минимальное число операций умножения требуется для перемножения s матриц, причем перемножать можно любые две рядом стоящие матрицы.

ФПМИ БГУ

 

Слайд 33

Сведения из математики: при перемножении двух матриц: B [n × k]

Сведения из математики:
при перемножении двух матриц:
B [n × k] *

C [k × m]
получим матрицу D [n × m]
Выполнив n·k·m операций умножения.

ФПМИ БГУ

?

Слайд 34

Числа Каталана – это последовательность чисел, названная в честь бельгийского математика

Числа Каталана – это последовательность чисел,
названная в честь бельгийского математика

Эжен Шарля Каталана.

Сn - обозначение n-ого числа Каталана.

Количество способов расстановки скобок в произведении из (n+1) множителя.
Количество двоичных корневых деревьев с n листьями, у которых из каждого внутреннего узла выходит ровно 2 узла.
Количество правильных скобочных последовательностей длины 2n.
Количество триангуляций выпуклого (n+2)–угольника (разбиение на треугольники непересекающимися диагоналями).

Сn

Слайд 35

рекуррентная формула для Сn ФПМИ БГУ Сn аналитическая формулы для Сn

рекуррентная формула для Сn

 

 

ФПМИ БГУ

Сn

 

 

аналитическая формулы для Сn

Слайд 36

Числа Каталана в треугольнике Паскаля Если в чётных строках i от

Числа Каталана в треугольнике Паскаля

Если в чётных строках i от серединной

линии отнять соседний элемент,
то получиться Ci/2 число Каталана.

Если в треугольнике Паскаля в строке n слева направо пронумеровать числа (нумерация с 0), то m-е число есть биномиальный коэффициент: (число способов выбрать m элементов из n)

Сn

ФПМИ БГУ

Слайд 37

Количество различных способов задать однозначно порядок перемножения матриц – Сs-1 число

 

Количество различных способов задать однозначно порядок перемножения матриц – Сs-1 число

Каталана, т.е. экспоненциальная функция.

Метод динамического программирования позволит решить задачу за время :

ФПМИ БГУ

 

Задача

Слайд 38

Подзадача Обозначим через минимальное число операций умножения, чтобы перемножить матрицы с

 

Подзадача
Обозначим через минимальное число операций умножения, чтобы перемножить матрицы с номерами

от i до j включительно:

ФПМИ БГУ

Ответ:

 

Задача

Слайд 39

Так как у нас оптимизационная задача, то перемножать матрицы надо за

 

 

 

Так как у нас оптимизационная задача, то перемножать матрицы
надо за

минимально возможно число операций умножения.

ФПМИ БГУ

Слайд 40

Справедливо следующее рекуррентное соотношение: ФПМИ БГУ

Справедливо следующее рекуррентное соотношение:

ФПМИ БГУ

Слайд 41

ФПМИ БГУ 1 вариант 2 вариант i j

ФПМИ БГУ

1 вариант

2 вариант

i

j

Слайд 42

Зависимые подзадачи ФПМИ БГУ

Зависимые подзадачи

ФПМИ БГУ

Слайд 43

ФПМИ БГУ

ФПМИ БГУ

Слайд 44

Время работы алгоритма оптимального перемножения группы матриц, основанного на методе динамического

Время работы алгоритма оптимального перемножения группы матриц, основанного на методе динамического

программирования:
вычислить s(s+1)/2 элементов таблицы;
каждый элемент таблицы вычисляется ровно один раз за не более, чем s арифметических операций.

ФПМИ БГУ

Слайд 45

Пример ФПМИ БГУ

 

Пример

ФПМИ БГУ

Слайд 46

ФПМИ БГУ

 

ФПМИ БГУ

Слайд 47

ФПМИ БГУ

ФПМИ БГУ

 

Слайд 48

ФПМИ БГУ

ФПМИ БГУ

 

Слайд 49

ФПМИ БГУ

ФПМИ БГУ

 

Слайд 50

Ответ: (A1·(A2·A3))·A4 3 100 операций умножения ФПМИ БГУ (A1·A2·A3)·A4 Порядок перемножения:

Ответ:

(A1·(A2·A3))·A4

3 100 операций умножения

ФПМИ БГУ

(A1·A2·A3)·A4

Порядок перемножения:

 

Слайд 51

Задача 4. Наибольшая общая подпоследовательность (НОП) англ. longest common subsequence (LCS) ФПМИ БГУ

Задача 4.
Наибольшая общая подпоследовательность (НОП)
англ. longest common subsequence (LCS)

ФПМИ БГУ

Слайд 52

ФПМИ БГУ Крайние случаи: самая короткая - пустая подпоследовательность (удалены все

ФПМИ БГУ

Крайние случаи:
самая короткая - пустая подпоследовательность (удалены все элементы

последовательности Z);
самая длинная - совпадает с самой последовательностью (удалено нулевое множество элементов).
Слайд 53

ФПМИ БГУ

ФПМИ БГУ

 

Слайд 54

ФПМИ БГУ X=Ф,Б,П,Г,М,У,И Y=А,Ф,И,П,С,Д,М,И,Б,Г,У LCS (X,Y) = Ф,П,М,И |LCS (X,Y)|= 4

ФПМИ БГУ

X=Ф,Б,П,Г,М,У,И

Y=А,Ф,И,П,С,Д,М,И,Б,Г,У

LCS (X,Y) = Ф,П,М,И
|LCS (X,Y)|= 4

В общем случае

задача может иметь неоднозначное решение.

X=0,2,0,9,1,9,6,7,22

Y=2,5,0,1,1,9,5,5,22

LCS (X,Y)=2,0,1,9,22

|LCS (X,Y)|= 5

Пример 1.

Пример 2.

Слайд 55

ФПМИ БГУ Сколько подпоследовательностей будет сгенерировано? Задачу LCS можно решить полным

ФПМИ БГУ

 

Сколько подпоследовательностей будет сгенерировано?

 

Задачу LCS можно решить полным перебором

 

X=Ф

Б П Г М У И Р

Y=А Ф И П С Д М И Б Г Л У В

 

 

Время работы алгоритма LCS (X,Y), основанного на полном переборе:

(элементы последовательности разделяются пробелом)

Слайд 56

ФПМИ БГУ F Задачу LCS можно решить динамическим программированием Обозначим через

 

ФПМИ БГУ

F

 

Задачу LCS можно решить динамическим программированием

Обозначим через F[i,j] длину

наибольшей общей подпоследовательности для двух префиксов:

Граничные условия (один из префиксов пустой):

 

Слайд 57

ФПМИ БГУ 1 i j j k i

ФПМИ БГУ

 

 

1

i

j

j

 

 

k

 

 

 

i

 

Слайд 58

ФПМИ БГУ 1 i j i-1 j-1

ФПМИ БГУ

 

1

i

j

 

 

 

 

 

i-1

j-1

Слайд 59

ФПМИ БГУ 1 i j i-1 j i j-1

ФПМИ БГУ

 

 

1

i

j

 

 

 

 

 

 

i-1

j

 

i

 

j-1

 

Слайд 60

ФПМИ БГУ 1 i j Получаем для Случая 2 следующее рекуррентное соотношение:

ФПМИ БГУ

 

1

i

j

 

 

 

 

Получаем для Случая 2 следующее рекуррентное соотношение:

Слайд 61

ФПМИ БГУ Объединяя оба случая, получаем следующее рекуррентное соотношение:

ФПМИ БГУ

 

Объединяя оба случая, получаем следующее рекуррентное соотношение:

 

Слайд 62

ФПМИ БГУ F если не нужно восстанавливать саму подпоследовательность, то можно

ФПМИ БГУ

F

 

если не нужно восстанавливать саму подпоследовательность, то можно в памяти

хранить только предыдущую строку матрицы и текущую (предыдущий столбец и текущий)

1-й способ

2-й способ

 

Время работы алгоритма, основанного на ДП:

ДП назад

Слайд 63

ФПМИ БГУ а т м (в примере при неоднозначности движение шло вверх)

ФПМИ БГУ

 

а

т

м

 

(в примере при неоднозначности движение шло вверх)

Слайд 64

Задача 5. Максимальная подстрока-палиндром ФПМИ БГУ

Задача 5.
Максимальная подстрока-палиндром

ФПМИ БГУ

Слайд 65

Задана строка длины n. Необходимо вычеркнуть минимальное число элементов, чтобы получился

Задана строка длины n.
Необходимо вычеркнуть минимальное число элементов, чтобы получился

палиндром
(палиндром - строка, которая одинаково читается слева направо и справа налево).

Для строки: a s d f s l a
Максимальная подстрока-палиндром: a s d s a

ФПМИ БГУ

Слайд 66

ФПМИ БГУ Неявное решение задачи a s d f s l

ФПМИ БГУ

Неявное решение задачи

 

 

 

a

s

d

f

s

l

a

a

l

s

f

d

s

a

Х=a s d f s l a

 

 

a

s

d

s

a

Наибольший

палиндром
Слайд 67

Явное решение задачи Обозначим через F[i,j] длину максимального палиндрома, который можно

Явное решение задачи
Обозначим через F[i,j] длину максимального палиндрома, который можно получить,

если мы рассматриваем элементы строки от индекса i до j включительно.

i

j

i+1

j-1

string

F

n=6

ФПМИ БГУ

Ответ:

Слайд 68

Строки длины 1 Строки длины 2 Строки длины >2 ФПМИ БГУ i j i+1 j-1 string

Строки длины 1

Строки длины 2

Строки длины >2

ФПМИ БГУ

i

j

i+1

j-1

string

Слайд 69

Задачи A, B и C являются зависимыми, так как они требуют

Задачи A, B и C являются зависимыми, так как они требуют

для своего решения знать длину максимального палиндрома для строки string от индекса i до j включительно.

ФПМИ БГУ

j

j+1

i

i-1

Слайд 70

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Пример

Слайд 71

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Слайд 72

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Слайд 73

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Слайд 74

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Слайд 75

a s d f s l a a s d f

 

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

Время работы алгоритма

:
Слайд 76

a s d f s l a a s d f

a

s

d

f

s

l

a

a

s

d

f

s

l

a

a s d f s l a

ФПМИ БГУ

a

Восстановление палиндрома

a s

a

s f

a s f s a

Слайд 77

Задача 6. Наибольшая возрастающая подпоследовательность Longest increasing subsequence, LIS ФПМИ БГУ

Задача 6.
Наибольшая возрастающая подпоследовательность
Longest increasing subsequence, LIS

ФПМИ БГУ

Слайд 78

ФПМИ БГУ Х= 0, 2, 9, 1, 9, 6, 7, 22

ФПМИ БГУ

 

Х= 0, 2, 9, 1, 9, 6, 7, 22

НВП(Х)= 0,

2, 6, 7, 22
Слайд 79

ФПМИ БГУ Неявное решение задачи (двумерное ДП) 0 2 9 1

ФПМИ БГУ

Неявное решение задачи (двумерное ДП)

 

 

 

0

2

9

1

9

6

7

0

1

2

7

9

9

22

 

 

НВП (0, 2, 9, 1, 9,

6, 7, 22)=(22, 9, 9, 2,0)

 

Х= 0, 2, 9, 1, 9, 6, 7, 22
Y= 0, 1, 2, 6, 7, 9, 9, 22

22

6

Слайд 80

Явное решение задачи (одномерное ДП) 1 i i-1 F ФПМИ БГУ

Явное решение задачи (одномерное ДП)

1

i

i-1

F

ФПМИ БГУ

 

n

 

Тогда получаем следующее рекуррентное соотношение:

 

Ответ:

 

Слайд 81

ФПМИ БГУ Построить НВП для последовательности: Х= 0, 2, 9, 1,

ФПМИ БГУ

Построить НВП для последовательности:
Х= 0, 2, 9, 1, 9, 6,

7, 22, 1

НВП( 0, 2, 9, 1, 9, 6, 7, 22, 1)=(0,1,6,7,22)

Как восстановить саму НВП(Х)?

 

 

Слайд 82

ФПМИ БГУ 9 1 9 6 7 22 1 0 2

ФПМИ БГУ

 

9

1

9

6

7

22

1

0

2

Слайд 83

Х=6 i i=UpperBound (х) Время работы алгоритма построения НВП(Х):

Х=6

i

i=UpperBound (х)

 

Время работы алгоритма построения НВП(Х):

Слайд 84

Задача 7. Преобразование строк вычисление расстояния Левенштейна (редакционное расстояние) ФПМИ БГУ

Задача 7.
Преобразование строк
вычисление расстояния Левенштейна
(редакционное расстояние)

ФПМИ БГУ

Слайд 85

Заданы две строки, как сравнить их, чтобы определить насколько они похожи?

Заданы две строки, как сравнить их, чтобы определить насколько они похожи?

ФПМИ

БГУ

 

Приложения:
для исправления ошибок при наборе слова;
для сравнения текстовых файлов («символы» – строки файла; «строки» - файлы);
в биоинформатике при сравнении аминокислот.

Слайд 86

число позиций, в которых соответствующие символы двух строк одинаковой длины отличаются.

число позиций, в которых соответствующие символы двух строк одинаковой длины отличаются.

 

Если

строки имеют одинаковую длину,

то для их сравнения можно использовать следующую метрику: расстояние Хэмминга

Ричард Уэсли Хэмминг
Richard Wesley Hamming
1915-1998
США, Чикаго

 

Если расстояние Хэмминга равно 1, то говорят, что строки являются «соседними».

 

 

Слайд 87

Если строки имеют разную длину: Расстояние Левенштейна для двух строк равно

 

 

Если строки имеют разную длину:
Расстояние Левенштейна для двух строк равно

минимальному числу односимвольных «редакторских правок»:

Владимир Иосифович Левенштейн
1935-2017
СССР (Россия), Москва
доктор физ.-мат.наук

 

то для их сравнения можно использовать следующую метрику: расстояние Левенштейна (др. словами редакционное расстояние).

Слайд 88

d(Х,Y)=4

 

 

 

d(Х,Y)=4

 

 

Слайд 89

ФПМИ БГУ F Задачу можно решить динамическим программированием Граничные условия (один из префиксов пустой):

 

ФПМИ БГУ

F

Задачу можно решить динамическим программированием

 

Граничные условия (один из префиксов

пустой):

 

Слайд 90

ФПМИ БГУ

 

ФПМИ БГУ

 

 

 

 

Слайд 91

ФПМИ БГУ Время работы алгоритма: Требуемая память:

ФПМИ БГУ

 

 

Время работы алгоритма:

Требуемая память:

 

 

Слайд 92

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 93

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 94

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 95

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 96

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 97

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 98

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 99

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 100

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 101

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 102

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 103

ФПМИ БГУ

ФПМИ БГУ

 

 

 

Слайд 104

ФПМИ БГУ R(a) I(a) D D Как восстановить редакторские правки?

ФПМИ БГУ

 

 

R(a)

I(a)

D

D

Как восстановить редакторские правки?

Слайд 105

Задания Тема. Динамическое программирование 0.1 Порядок перемножения матриц 0.2 Единицы -

Задания

Тема. Динамическое программирование
0.1 Порядок перемножения матриц
0.2 Единицы - число сочетаний

из n по k 0.3. Единицы
6. Строго возрастающая без разрывов последовательнсть
20. Палиндром 25. Преобразование строк
69. Кувшинки

Выполнить в системе Insight Runner следующие общие задачи:

ФПМИ БГУ

- Предыдущая
Трагедия в Беслане
Следующая -
Артикуляционная гимнастика и гимнастика после сна для дошкольников

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

Процесс проектирования и разработки ПО Введение
Алгоритм и его свойства
Презентация "Системы счисления. Понятия, виды, развернутая форма записи числа" - скачать презентации по Информатике
Функциональная схема компьютера
Гибридная контрольно-проверочная аппаратура
Информационные технологии. Проектирование Базы данных
От индустриального общества к информационному
Концепция баз данных, понятие моделей данных
Модели жизненного цикла программного обеспечения
Разработка компьютерного сурдопереводчика непрерывной русской речи на разговорный русский жестовый язык для глухих
Компьютер
Создание базы данных в СУБД Access
Andmebaasisüsteemide Oracle ja PostgreSQL kasutamine
Проектирование реляционной базы данных. Основные принципы проектирования
Алгоритмические структуры программирования (9 класс)
Теоретические основы языков манипулирования данными
Робототехника
Теория вычислений
Презентация "Электронная таблица MS Excel" - скачать презентации по Информатике
Oператори циклу
Name of presentation. Наши страницы в соцсетях
Использование подзапросов
Презентация "Пример атаки на IP-сеть. &#039;&#039;Переполнение буфера&#039;" - скачать презентации по Информатике
Программные средства ПК. Основные понятия операционной системы
SQLite менеджер данных. Просмотр данных. (Часть 2)
Логическое программирование
Виды информации
К проекту 11 игр
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть