🗊Презентация Динамическое программирование. Лекция 20

Нажмите для полного просмотра!
Динамическое программирование. Лекция 20, слайд №1Динамическое программирование. Лекция 20, слайд №2Динамическое программирование. Лекция 20, слайд №3Динамическое программирование. Лекция 20, слайд №4Динамическое программирование. Лекция 20, слайд №5Динамическое программирование. Лекция 20, слайд №6Динамическое программирование. Лекция 20, слайд №7Динамическое программирование. Лекция 20, слайд №8Динамическое программирование. Лекция 20, слайд №9Динамическое программирование. Лекция 20, слайд №10Динамическое программирование. Лекция 20, слайд №11Динамическое программирование. Лекция 20, слайд №12Динамическое программирование. Лекция 20, слайд №13Динамическое программирование. Лекция 20, слайд №14Динамическое программирование. Лекция 20, слайд №15Динамическое программирование. Лекция 20, слайд №16Динамическое программирование. Лекция 20, слайд №17Динамическое программирование. Лекция 20, слайд №18Динамическое программирование. Лекция 20, слайд №19Динамическое программирование. Лекция 20, слайд №20Динамическое программирование. Лекция 20, слайд №21Динамическое программирование. Лекция 20, слайд №22Динамическое программирование. Лекция 20, слайд №23Динамическое программирование. Лекция 20, слайд №24Динамическое программирование. Лекция 20, слайд №25Динамическое программирование. Лекция 20, слайд №26Динамическое программирование. Лекция 20, слайд №27Динамическое программирование. Лекция 20, слайд №28Динамическое программирование. Лекция 20, слайд №29Динамическое программирование. Лекция 20, слайд №30Динамическое программирование. Лекция 20, слайд №31Динамическое программирование. Лекция 20, слайд №32Динамическое программирование. Лекция 20, слайд №33Динамическое программирование. Лекция 20, слайд №34Динамическое программирование. Лекция 20, слайд №35Динамическое программирование. Лекция 20, слайд №36Динамическое программирование. Лекция 20, слайд №37Динамическое программирование. Лекция 20, слайд №38Динамическое программирование. Лекция 20, слайд №39Динамическое программирование. Лекция 20, слайд №40Динамическое программирование. Лекция 20, слайд №41Динамическое программирование. Лекция 20, слайд №42Динамическое программирование. Лекция 20, слайд №43Динамическое программирование. Лекция 20, слайд №44Динамическое программирование. Лекция 20, слайд №45Динамическое программирование. Лекция 20, слайд №46Динамическое программирование. Лекция 20, слайд №47Динамическое программирование. Лекция 20, слайд №48Динамическое программирование. Лекция 20, слайд №49Динамическое программирование. Лекция 20, слайд №50Динамическое программирование. Лекция 20, слайд №51Динамическое программирование. Лекция 20, слайд №52Динамическое программирование. Лекция 20, слайд №53Динамическое программирование. Лекция 20, слайд №54Динамическое программирование. Лекция 20, слайд №55Динамическое программирование. Лекция 20, слайд №56Динамическое программирование. Лекция 20, слайд №57Динамическое программирование. Лекция 20, слайд №58Динамическое программирование. Лекция 20, слайд №59Динамическое программирование. Лекция 20, слайд №60

Содержание

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

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


Слайд 1





Динамическое программирование 
Лекция 20
Описание слайда:
Динамическое программирование Лекция 20

Слайд 2





План лекции
Понятие динамического программирования
Примеры
Сумма геометрической прогрессии
Суммирование набора
Задача о рюкзаке
Произведение матриц
Алгоритм Флойда-Уоршалла
Описание слайда:
План лекции Понятие динамического программирования Примеры Сумма геометрической прогрессии Суммирование набора Задача о рюкзаке Произведение матриц Алгоритм Флойда-Уоршалла

Слайд 3





Понятие динамического программирования
Ричард Беллман ~1940
Какой алгоритм назван в честь этого ученого?
Описание процесса решения задачи, при котором решение одной задачу вычисляется на основании решения "предшествующих" задач
Один из методов численного решения задач оптимизации
Первоначально часть системного анализа
Описание слайда:
Понятие динамического программирования Ричард Беллман ~1940 Какой алгоритм назван в честь этого ученого? Описание процесса решения задачи, при котором решение одной задачу вычисляется на основании решения "предшествующих" задач Один из методов численного решения задач оптимизации Первоначально часть системного анализа

Слайд 4





Понятие динамического программирования
Термин «динамическое программирование» происходит от термина «математическое программирование», который является синонимом слова «оптимизация»
Слово «программирование» в словосочетании «динамическое программирование» к традиционному программированию почти никакого отношения не имеет
Слово «программа» в Д.П. означает оптимальную последовательность действий для получения решения задачи
Расписание событий на выставке называют программой и понимают как допустимую последовательность событий
Описание слайда:
Понятие динамического программирования Термин «динамическое программирование» происходит от термина «математическое программирование», который является синонимом слова «оптимизация» Слово «программирование» в словосочетании «динамическое программирование» к традиционному программированию почти никакого отношения не имеет Слово «программа» в Д.П. означает оптимальную последовательность действий для получения решения задачи Расписание событий на выставке называют программой и понимают как допустимую последовательность событий

Слайд 5





Понятие динамического программирования
Последовательность действий в Д.П. имеет вид
Разбиение задачи на подзадачи меньшего размера 
Нахождение оптимального решения подзадач рекурсивно
Вычисление оптимального решения исходной задачи на основании оптимальных решений подзадач
Деление на подзадачи происходит до тех пор, пока не получатся тривиальные задачи, решаемые за константное время
В общем случае требование оптимальности может отсутствовать (Д.П. с постоянной целевой функцией)
Например, вычисление n! можно рассматривать как задачу Д.П. с постоянной целевой функцией и тривиальными задачами 1! = 1 и 0! = 1
Описание слайда:
Понятие динамического программирования Последовательность действий в Д.П. имеет вид Разбиение задачи на подзадачи меньшего размера Нахождение оптимального решения подзадач рекурсивно Вычисление оптимального решения исходной задачи на основании оптимальных решений подзадач Деление на подзадачи происходит до тех пор, пока не получатся тривиальные задачи, решаемые за константное время В общем случае требование оптимальности может отсутствовать (Д.П. с постоянной целевой функцией) Например, вычисление n! можно рассматривать как задачу Д.П. с постоянной целевой функцией и тривиальными задачами 1! = 1 и 0! = 1

Слайд 6





Понятие динамического программирования
Простая рекурсивная реализация будет расходовать время на вычисление решений для задач, которые уже один раз решались
Чтобы избежать такого хода событий будем сохранять в таблице решение каждой решенной подзадачи
Когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто возьмем его из таблицы
Этот прием называется кэширование
Описание слайда:
Понятие динамического программирования Простая рекурсивная реализация будет расходовать время на вычисление решений для задач, которые уже один раз решались Чтобы избежать такого хода событий будем сохранять в таблице решение каждой решенной подзадачи Когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто возьмем его из таблицы Этот прием называется кэширование

Слайд 7





Понятие динамического программирования
Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи, вычисление идет от малых подзадач к большим, решения подзадач запоминаются в таблице и используются при решении больших задач
Заполнение таблицы в Д.П. называется прямым ходом
Исходные данные подзадач называются параметрами
Задачу можно рассматривать как функцию, аргументами которой являются параметры задачи
Например, при нахождении суммы набора чисел параметрами задачи будут количество чисел и их значения
Описание слайда:
Понятие динамического программирования Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи, вычисление идет от малых подзадач к большим, решения подзадач запоминаются в таблице и используются при решении больших задач Заполнение таблицы в Д.П. называется прямым ходом Исходные данные подзадач называются параметрами Задачу можно рассматривать как функцию, аргументами которой являются параметры задачи Например, при нахождении суммы набора чисел параметрами задачи будут количество чисел и их значения

Слайд 8





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

Слайд 9





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

Слайд 10





Пример  -- геометрическая прогрессия
Рассмотрим пример. Требуется вычислить сумму s следующего ряда при  x ≠ 0:   s=1 +1/x+ 1/x2+ 1/x3+…+ 1/xn.  
Параметры подзадач:
	k <= n, x != 0
Подзадачи для k , x:
	Вычисление сумм S(k) = 1 +1/x+ 1/x2+ 1/x3+…+ 1/xk
	Вычисление степеней P(k, x) = 1/xk
Соотношения:
	S(0) = 1, P(0) = 1
	S(k+1) = S(k)+P(k)/x, P(k+1) = P(k)/x
Описание слайда:
Пример -- геометрическая прогрессия Рассмотрим пример. Требуется вычислить сумму s следующего ряда при x ≠ 0: s=1 +1/x+ 1/x2+ 1/x3+…+ 1/xn. Параметры подзадач: k <= n, x != 0 Подзадачи для k , x: Вычисление сумм S(k) = 1 +1/x+ 1/x2+ 1/x3+…+ 1/xk Вычисление степеней P(k, x) = 1/xk Соотношения: S(0) = 1, P(0) = 1 S(k+1) = S(k)+P(k)/x, P(k+1) = P(k)/x

Слайд 11





Пример – суммирование набора
Имеется n неделимых предметов, вес i-го предмета есть wi 
Найти список предметов, суммарный вес которых равен W кг. (если это возможно)
Обозначим T(n, W) =	1, если искомый набор имеется
				0, если искомого набора нет
Подзазача – вычисление T(i, j), где i -- макс. номер предмета, j – требуемый суммарный вес и 0 ≤ i ≤  n, 1 ≤  j ≤ W
Параметры -- количество предметов и требуемый суммарный вес
Описание слайда:
Пример – суммирование набора Имеется n неделимых предметов, вес i-го предмета есть wi Найти список предметов, суммарный вес которых равен W кг. (если это возможно) Обозначим T(n, W) = 1, если искомый набор имеется 0, если искомого набора нет Подзазача – вычисление T(i, j), где i -- макс. номер предмета, j – требуемый суммарный вес и 0 ≤ i ≤ n, 1 ≤ j ≤ W Параметры -- количество предметов и требуемый суммарный вес

Слайд 12





Пример – суммирование набора
Начальные значения функции T
T(0, j) = 0 при  j ≥ 1
нельзя без предметов набрать массу j > 0
T(i, 0) = 1 при i ≥ 1
всегда можно набрать вес, равный 0
Описание слайда:
Пример – суммирование набора Начальные значения функции T T(0, j) = 0 при j ≥ 1 нельзя без предметов набрать массу j > 0 T(i, 0) = 1 при i ≥ 1 всегда можно набрать вес, равный 0

Слайд 13





Пример – суммирование набора
Для оптимального решения из двух возможных вариантов нужно выбрать наилучший
i-ый предмет в набор не берется
T(i,  j) = T(i - 1,  j)
Решение задачи с i предметами сводится к решению задачи с i – предметом
i-ый предмет в набор берется
T(i,  j) = T(i -1,  j - wi)
Масса оставшихся предметов уменьшается на величину wi
Эта ситуация возможна, если масса i-го предмета не больше значения j
Соотношения
T(i,  j)= T(i -1,  j) при  j < wi  
T(i,  j)= max (T(i -1,  j),  T(i -1,  j - wi))  при  j ≥  wi.
Описание слайда:
Пример – суммирование набора Для оптимального решения из двух возможных вариантов нужно выбрать наилучший i-ый предмет в набор не берется T(i, j) = T(i - 1, j) Решение задачи с i предметами сводится к решению задачи с i – предметом i-ый предмет в набор берется T(i, j) = T(i -1, j - wi) Масса оставшихся предметов уменьшается на величину wi Эта ситуация возможна, если масса i-го предмета не больше значения j Соотношения T(i, j)= T(i -1, j) при j < wi T(i, j)= max (T(i -1, j), T(i -1, j - wi)) при j ≥ wi.

Слайд 14





Пример – суммирование набора
W = 16
w1 = 4, w2 = 5, w3 = 3,  w4 = 7, w5 = 6
Результат прямого хода
Описание слайда:
Пример – суммирование набора W = 16 w1 = 4, w2 = 5, w3 = 3, w4 = 7, w5 = 6 Результат прямого хода

Слайд 15





Пример – суммирование набора
Обратный ход
Решение нашего примера определяется  T[5, 16] = 1
T[5, 16] = T[4, 16] -- 5-ый предмет в набор не включаем
T[4, 16] ≠ T[3, 16] – 4-ый предмет включаем, оставшийся вес 16-w4 = 16-7 = 9
T[3, 9] =T[2, 9] – 3-ый предмет в набор не включаем
T[2, 9] ≠ T[1, 9] ] – 2-oй предмет включаем, оставшийся вес равен 9-w2 = 9 - 5 = 4
T[1, 4] ≠ T[0, 4] – 1-oй предмет включаем, оставшийся вес равен 0
Описание слайда:
Пример – суммирование набора Обратный ход Решение нашего примера определяется T[5, 16] = 1 T[5, 16] = T[4, 16] -- 5-ый предмет в набор не включаем T[4, 16] ≠ T[3, 16] – 4-ый предмет включаем, оставшийся вес 16-w4 = 16-7 = 9 T[3, 9] =T[2, 9] – 3-ый предмет в набор не включаем T[2, 9] ≠ T[1, 9] ] – 2-oй предмет включаем, оставшийся вес равен 9-w2 = 9 - 5 = 4 T[1, 4] ≠ T[0, 4] – 1-oй предмет включаем, оставшийся вес равен 0

Слайд 16





Задача о рюкзаке
Определить наиболее ценную выборку из n предметов, подлежащих упаковке в рюкзак, вмещающий W килограммов
Предмет i стоит сi  и весит wi
Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W, а суммарная стоимость была максимальна
Описание слайда:
Задача о рюкзаке Определить наиболее ценную выборку из n предметов, подлежащих упаковке в рюкзак, вмещающий W килограммов Предмет i стоит сi  и весит wi Необходимо выбрать из этих предметов такой набор, чтобы суммарная масса не превосходила заданной величины W, а суммарная стоимость была максимальна

Слайд 17





Пример -- задача о рюкзаке
Если перебирать все возможные подмножества данного набора из n предметов, то получится решение сложности не менее чем O(2n)
В настоящее время неизвестен алгоритм решения этой задачи, сложность которого является полиномом от n
Построим с помощью Д.П. алгоритм со временем работы O(nW) для решения данной задачи, когда все входные данные – целые числа
Описание слайда:
Пример -- задача о рюкзаке Если перебирать все возможные подмножества данного набора из n предметов, то получится решение сложности не менее чем O(2n) В настоящее время неизвестен алгоритм решения этой задачи, сложность которого является полиномом от n Построим с помощью Д.П. алгоритм со временем работы O(nW) для решения данной задачи, когда все входные данные – целые числа

Слайд 18





Пример -- задача о рюкзаке
Обозначим через T(n, W) функцию, значение которой  соответствует решению нашей задачи.  Аргументами функции является количество предметов n, по которому можно определить стоимость и массу каждого предмета, и ограничение по весу W. 
Подзадачи – вычисление значений функции T(i, j) = max стоимость предметов, которые можно уложить в рюкзак с ограничением по весу j килограмм, если можно использовать только первые i предметов из заданных, где 0 ≤ i ≤  n, 0 ≤  j ≤  n.
Что является параметрами подзадачи?
Начальные значения функции T :
T(0, 0) = 0,  
T(0, j) = 0 при  j ≥ 1 (нет предметов, максимальная стоимость равна 0), 
T(i, 0) = 0 при i ≥ 1 (можно брать любые из первых i предметов, но ограничение по весу равно 0).
Описание слайда:
Пример -- задача о рюкзаке Обозначим через T(n, W) функцию, значение которой соответствует решению нашей задачи. Аргументами функции является количество предметов n, по которому можно определить стоимость и массу каждого предмета, и ограничение по весу W. Подзадачи – вычисление значений функции T(i, j) = max стоимость предметов, которые можно уложить в рюкзак с ограничением по весу j килограмм, если можно использовать только первые i предметов из заданных, где 0 ≤ i ≤ n, 0 ≤ j ≤ n. Что является параметрами подзадачи? Начальные значения функции T : T(0, 0) = 0, T(0, j) = 0 при j ≥ 1 (нет предметов, максимальная стоимость равна 0), T(i, 0) = 0 при i ≥ 1 (можно брать любые из первых i предметов, но ограничение по весу равно 0).

Слайд 19





Пример -- задача о рюкзаке
Для решения подзадачи, соответствующей функции T(i, j), 
рассмотрим два случая. 
i-ый предмет не упаковывается в рюкзак
Решение задачи с i предметами сводится к решению задачи с i – 1 предметом:
T(i,  j) = T(i - 1,  j). 
i-ый предмет упаковывается в рюкзак
Масса оставшихся предметов  уменьшается на величину wi, а при добавлении i-го предмета  стоимость выборки увеличивается на ci:
T(i,  j) = T(i -1,  j - wi) + ci. 
При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j.
Описание слайда:
Пример -- задача о рюкзаке Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. i-ый предмет не упаковывается в рюкзак Решение задачи с i предметами сводится к решению задачи с i – 1 предметом: T(i, j) = T(i - 1, j). i-ый предмет упаковывается в рюкзак Масса оставшихся предметов уменьшается на величину wi, а при добавлении i-го предмета стоимость выборки увеличивается на ci: T(i, j) = T(i -1, j - wi) + ci. При этом нужно учитывать, что эта ситуация возможна только тогда, когда масса i-го предмета не больше значения j.

Слайд 20





Пример -- задача о рюкзаке
Для оптимального решения из двух возможных вариантов упаковки рюкзака нужно выбрать наилучший 
Соотношение при i ≥ 1 и  j ≥ 1:
		T(i,  j)= T(i -1,  j) при  j < wi  
		T(i,  j)= max (T(i -1,  j),  T(i -1,  j - wi) + ci)  при  j ≥  wi.
Описание слайда:
Пример -- задача о рюкзаке Для оптимального решения из двух возможных вариантов упаковки рюкзака нужно выбрать наилучший Соотношение при i ≥ 1 и j ≥ 1: T(i, j)= T(i -1, j) при j < wi T(i, j)= max (T(i -1, j), T(i -1, j - wi) + ci) при j ≥ wi.

Слайд 21





Пример -- задача о рюкзаке
W = 16,
c1  = 5,   
w1 = 4;
c2   = 7,  
w2 = 5;
c3   = 4,  
w3 = 3;
c4  = 9,  
w4 = 7;
c5  = 8,  
w5 = 6.
Описание слайда:
Пример -- задача о рюкзаке W = 16, c1 = 5, w1 = 4; c2 = 7, w2 = 5; c3 = 4, w3 = 3; c4 = 9, w4 = 7; c5 = 8, w5 = 6.

Слайд 22





Пример -- задача о рюкзаке
Алгоритм обратного хода
Требуется определить набор предметов, которые подлежат упаковке в рюкзак
Сравним значение T[n, W] со значением T[n-1, W]
Если  T[n, W] ≠ T[n-1, W], то предмет c номером n обязательно упаковывается в рюкзак, после чего переходим к сравнению элементов T[n-1, W - wn] и T[n-2, W- wn]  и т.д. 
Если T[n-1, W] = T[n-1, W], то n-ый предмет можно не упаковывать в рюкзак. В этом случае следует перейти к рассмотрению элементов T[n-1, W] и T[n-2, W] .
Описание слайда:
Пример -- задача о рюкзаке Алгоритм обратного хода Требуется определить набор предметов, которые подлежат упаковке в рюкзак Сравним значение T[n, W] со значением T[n-1, W] Если T[n, W] ≠ T[n-1, W], то предмет c номером n обязательно упаковывается в рюкзак, после чего переходим к сравнению элементов T[n-1, W - wn] и T[n-2, W- wn] и т.д. Если T[n-1, W] = T[n-1, W], то n-ый предмет можно не упаковывать в рюкзак. В этом случае следует перейти к рассмотрению элементов T[n-1, W] и T[n-2, W] .

Слайд 23





Пример -- задача о рюкзаке
T[5, 16] = T[4, 16] -- 5-й предмет не кладем в рюкзак
T[4, 16] != T[3, 16] – 4-й предмет кладем в рюкзак, свободный вес равен 16 – w4= 16 – 7 = 9
T[3, 9] = T[2, 9] – 3-й предмет не кладем в рюкзак
T[2, 9] != T[1, 9] -- 2-й предмет кладем в рюкзак, свободный вес равен 9 - w2 = 9 – 5 = 4
T[1, 4] != T[0, 4] – 1-й предмет кладем в рюкзак
Итак, для нашего примера в рюкзак упакуются предметы с номерами 1, 2, 4
Описание слайда:
Пример -- задача о рюкзаке T[5, 16] = T[4, 16] -- 5-й предмет не кладем в рюкзак T[4, 16] != T[3, 16] – 4-й предмет кладем в рюкзак, свободный вес равен 16 – w4= 16 – 7 = 9 T[3, 9] = T[2, 9] – 3-й предмет не кладем в рюкзак T[2, 9] != T[1, 9] -- 2-й предмет кладем в рюкзак, свободный вес равен 9 - w2 = 9 – 5 = 4 T[1, 4] != T[0, 4] – 1-й предмет кладем в рюкзак Итак, для нашего примера в рюкзак упакуются предметы с номерами 1, 2, 4

Слайд 24





Пример -- задача о рюкзаке
void print_item(int i, int j)
{
  if (T[i][j]==0) return;   		// набор предметов построен
  if (T[i-1][j] == T[i][j]) 
           Print_item (i-1,j);		//i-й предмет не берем
  else {                               
           print_item(i-1,j-w[i]);		// i-й предмет берем
           printf("%d ", i);   		// печать i-го предмета 
   }
}
Описание слайда:
Пример -- задача о рюкзаке void print_item(int i, int j) { if (T[i][j]==0) return; // набор предметов построен if (T[i-1][j] == T[i][j]) Print_item (i-1,j); //i-й предмет не берем else { print_item(i-1,j-w[i]); // i-й предмет берем printf("%d ", i); // печать i-го предмета } }

Слайд 25





Пример -- умножение матриц
Рассмотрим вычисление произведения n матриц 
		M = M1 x M2 x ... x Mn.		 (1)
Порядок, в котором матрицы перемножаются, может
cущественно сказаться на общем числе операций, требуемых для вычисления матрицы М, независимо от алгоритма, применяемого для умножения матриц. 
Умножение матрицы размера [р  q] на матрицу размера
[q r] требует pqr операций.
Описание слайда:
Пример -- умножение матриц Рассмотрим вычисление произведения n матриц M = M1 x M2 x ... x Mn. (1) Порядок, в котором матрицы перемножаются, может cущественно сказаться на общем числе операций, требуемых для вычисления матрицы М, независимо от алгоритма, применяемого для умножения матриц. Умножение матрицы размера [р  q] на матрицу размера [q r] требует pqr операций.

Слайд 26





Пример – умножение матриц
Рассмотрим произведение  матриц:
    М   =   M1        М2       М3      М4      
           [1020]  [2050]  [501]  [1 100]
Если вычислять матрицу М в порядке:  M1   ( М2   ( М3    М4,)), то 
потребуется 125 000 операций. 
(50*1*100)  [50 100], 5000; (20*50*100)  [20 100], 100000;
(10*20*100)  [10 100], 20000. 
Вычисление же в порядке: ( M1  (М2  М3 )) М4  требует  лишь 
2 200 операций.   
(20*50*1)  [20 1], 1000; (10*20*1)  [10 1], 200;
(10*1*100)  [10 100], 1000.
Описание слайда:
Пример – умножение матриц Рассмотрим произведение матриц: М = M1  М2  М3  М4 [1020] [2050] [501] [1 100] Если вычислять матрицу М в порядке: M1  ( М2  ( М3  М4,)), то потребуется 125 000 операций. (50*1*100)  [50 100], 5000; (20*50*100)  [20 100], 100000; (10*20*100)  [10 100], 20000. Вычисление же в порядке: ( M1  (М2  М3 )) М4 требует лишь 2 200 операций. (20*50*1)  [20 1], 1000; (10*20*1)  [10 1], 200; (10*1*100)  [10 100], 1000.

Слайд 27





Пример -- умножение матриц
Перебор с целью минимизировать число операций имеет экспоненциальную сложность.
На первом этапе определим за какое минимальное количество операций можно получить матрицу М из равенства (1). 
Будем считать подзадачами вычисление минимального количества операций при перемножении меньшего, чем n, количества матриц.
В качестве параметров рассматриваемой задачи возьмем индексы i и  j (1 i  j  n),  обозначающие номера первой и последней матриц в цепочке Mi   Мi+1   ...  Мj . 
Сначала решим поздачи, когда j=i+1, т.е. когда перемножаются две рядом стоящие матрицы. Решения – количество затраченных операций, запишем в ячейке таблицы T с номерами (i. j). 
Tij будет содержать число, равное количеству операций при умножении цепочки матриц Mi  Мi+1,  где 1 i  3.
Описание слайда:
Пример -- умножение матриц Перебор с целью минимизировать число операций имеет экспоненциальную сложность. На первом этапе определим за какое минимальное количество операций можно получить матрицу М из равенства (1). Будем считать подзадачами вычисление минимального количества операций при перемножении меньшего, чем n, количества матриц. В качестве параметров рассматриваемой задачи возьмем индексы i и j (1 i  j  n), обозначающие номера первой и последней матриц в цепочке Mi  Мi+1  ...  Мj . Сначала решим поздачи, когда j=i+1, т.е. когда перемножаются две рядом стоящие матрицы. Решения – количество затраченных операций, запишем в ячейке таблицы T с номерами (i. j). Tij будет содержать число, равное количеству операций при умножении цепочки матриц Mi  Мi+1, где 1 i  3.

Слайд 28





Пример -- умножение матриц
Описание слайда:
Пример -- умножение матриц

Слайд 29





Пример -- умножение матриц
Обозначим через tij  минимальную сложность умножения цепочки матриц Mi   Мi+1   ...  Мj ,  где  1 i  j  n.  Ее можно получить следующим образом:
Описание слайда:
Пример -- умножение матриц Обозначим через tij минимальную сложность умножения цепочки матриц Mi  Мi+1  ...  Мj , где 1 i  j  n. Ее можно получить следующим образом:

Слайд 30





Упражнение
Задана строка, состоящая из вещественных чисел, разделенных арифметическими операциями
Требуется расставить в строке скобки таким образом, чтобы значение полученного выражения было максимальнвым
Описание слайда:
Упражнение Задана строка, состоящая из вещественных чисел, разделенных арифметическими операциями Требуется расставить в строке скобки таким образом, чтобы значение полученного выражения было максимальнвым

Слайд 31





Кратчайшие пути между всеми парами вершин
Строим матрицу стоимостей:
				w(i, j),  если ребро (i, j)E 
M[i, j] =		+∞ ,  если ребро (i, j)E 
				0, если i = j
Обозначим через d [i, j] матрицу кратчайших
путей между всеми вершинами.
Вершины занумеруем числами от 1 до n.
Описание слайда:
Кратчайшие пути между всеми парами вершин Строим матрицу стоимостей: w(i, j), если ребро (i, j)E M[i, j] = +∞ , если ребро (i, j)E 0, если i = j Обозначим через d [i, j] матрицу кратчайших путей между всеми вершинами. Вершины занумеруем числами от 1 до n.

Слайд 32





Алгоритм Флойда-Уоршолла
Обозначим через dij(k)  стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}.
	
			 M[i, j] , если k = 0,
	dij(k)  = 	 
			min(dij(k-1) , dik(k-1) + dkj(k-1) ), если k1
D(n) содержит искомое решение
Описание слайда:
Алгоритм Флойда-Уоршолла Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M[i, j] , если k = 0, dij(k) = min(dij(k-1) , dik(k-1) + dkj(k-1) ), если k1 D(n) содержит искомое решение

Слайд 33





Алгоритм Флойда-Уоршолла
Floyd-Warshall(M, n) {
	D(0)  M;
	for (k = 0; k<n; k++)
 		for (i = 0; i<n; i++) 
			for j  1 to n do
				dij(k)  min(dij(k-1), dik(k-1) + dkj(k-1) );
	return D(n);
}
Описание слайда:
Алгоритм Флойда-Уоршолла Floyd-Warshall(M, n) { D(0)  M; for (k = 0; k<n; k++) for (i = 0; i<n; i++) for j  1 to n do dij(k)  min(dij(k-1), dik(k-1) + dkj(k-1) ); return D(n); }

Слайд 34





Заключение
Понятие динамического программирования
Примеры
Сумма геометрической прогрессии
Суммирование набора
Задача о рюкзаке
Произведение матриц
Алгоритм Флойда-Уоршалла
Описание слайда:
Заключение Понятие динамического программирования Примеры Сумма геометрической прогрессии Суммирование набора Задача о рюкзаке Произведение матриц Алгоритм Флойда-Уоршалла

Слайд 35





На какое минимальное количество квадратов можно разложить число n?
На какое минимальное количество квадратов можно разложить число n?
     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
dp==[0,1,2,3,1,2,3,4,2,1, 2, 3, 3, 4, 3, 4, 1, 2, 2 …] 
dp[0] = 0; 
for (int i = 1; i <= n; i++) { 
	dp[i] = INT_MAX; 
	for (int j = 1; j * j <= i; j++) { 
		dp[i] = min(dp[i],dp[i-j*j] + 1); 
	}
}
(j – размер квадрата)
Описание слайда:
На какое минимальное количество квадратов можно разложить число n? На какое минимальное количество квадратов можно разложить число n? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 dp==[0,1,2,3,1,2,3,4,2,1, 2, 3, 3, 4, 3, 4, 1, 2, 2 …] dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] = INT_MAX; for (int j = 1; j * j <= i; j++) { dp[i] = min(dp[i],dp[i-j*j] + 1); } } (j – размер квадрата)

Слайд 36





Алгоритм Ахо (редакционное расстояние)
Пусть даны две строки S1 и S2. Необходимо за минимальное число допустимых операций преобразовать строку S1 в строку S2. Допустимой операцией являются следующие операции удаления символа из строки и вставки символа в строку: 
DEL(S, i) – удалить i-ый элемент строки S;
INS(S, i, c) – вставить символ c после i-го элемента строки S.
Обозначим через S [i..j]  – подстроку от i-го символа до j-го.
Пусть M(i,j) – минимальное количество операций, которые требуются, чтобы преобразовать начальные i символов строки S1 в  начальные j символов строки S2:  S1[0..i] –> S2[0..j].
 
Считаем, что S1[0..0] и S2[0..0] –  пустые строки.
Описание слайда:
Алгоритм Ахо (редакционное расстояние) Пусть даны две строки S1 и S2. Необходимо за минимальное число допустимых операций преобразовать строку S1 в строку S2. Допустимой операцией являются следующие операции удаления символа из строки и вставки символа в строку: DEL(S, i) – удалить i-ый элемент строки S; INS(S, i, c) – вставить символ c после i-го элемента строки S. Обозначим через S [i..j] – подстроку от i-го символа до j-го. Пусть M(i,j) – минимальное количество операций, которые требуются, чтобы преобразовать начальные i символов строки S1 в начальные j символов строки S2: S1[0..i] –> S2[0..j]. Считаем, что S1[0..0] и S2[0..0] – пустые строки.

Слайд 37






Заметим, что для преобразования пустой строки в строку длины j требуется j операций вставки, т.е.  M (0, j) = j . 
Аналогично для преобразования строки длины i в пустую строку требуется i операций удаления, т.е. M (i, 0) = i.
Пусть  мы  решили  подзадачу c  параметрами  i –1 и j – 1.
Это означает, что из строки S1[0..i–1] построена строка S2[0..j–1] за минимальное число допустимых операций M(i –1, j –1). 
I) Пусть S1[i] = S2[j]. Тогда для получения строки S2[0..j] из строки S1[0..i] не требуется никаких дополнительных операций. Следовательно, M (i, j) = M (i – 1, j – 1).
Описание слайда:
Заметим, что для преобразования пустой строки в строку длины j требуется j операций вставки, т.е. M (0, j) = j . Аналогично для преобразования строки длины i в пустую строку требуется i операций удаления, т.е. M (i, 0) = i. Пусть мы решили подзадачу c параметрами i –1 и j – 1. Это означает, что из строки S1[0..i–1] построена строка S2[0..j–1] за минимальное число допустимых операций M(i –1, j –1). I) Пусть S1[i] = S2[j]. Тогда для получения строки S2[0..j] из строки S1[0..i] не требуется никаких дополнительных операций. Следовательно, M (i, j) = M (i – 1, j – 1).

Слайд 38






II) Пусть S1[i] ≠ S2[j]. Возможны два способа получения строки S2[0..j].  
1. Пусть из строки S1[0..i–1] построена строка S2[0..j] за минимальное количество операций  M (i–1, j ). Тогда для получения строки S2[0..j] из строки S1[0..i] требуется удалить i-ый символ из строки S1.  
2. Пусть из строки S1[0..i] построена строка S2[0..j–1] за минимальное количество операций M (i, j–1).  Тогда для получения строки S2[0..j] из строки S1[0..i] потребуется одна операция вставки i-го символа строки S1  после символа S2[j–1]. 
Из 2-х возможностей выбраем лучшую и получаем следующие рекуррентные соотношения:
Описание слайда:
II) Пусть S1[i] ≠ S2[j]. Возможны два способа получения строки S2[0..j]. 1. Пусть из строки S1[0..i–1] построена строка S2[0..j] за минимальное количество операций M (i–1, j ). Тогда для получения строки S2[0..j] из строки S1[0..i] требуется удалить i-ый символ из строки S1. 2. Пусть из строки S1[0..i] построена строка S2[0..j–1] за минимальное количество операций M (i, j–1). Тогда для получения строки S2[0..j] из строки S1[0..i] потребуется одна операция вставки i-го символа строки S1 после символа S2[j–1]. Из 2-х возможностей выбраем лучшую и получаем следующие рекуррентные соотношения:

Слайд 39






M (0, j) = j; 	M (i, 0) = i;
M (i, j) = min (M (i – 1, j – 1), M (i – 1, j ) + 1, M (i , j – 1) +1), 
			если S1[i] = S2[j]; 
M (i, j) = min (M (i – 1, j ), M (i , j – 1)) + 1, 
			если S1[i] ≠ S2[j];
Решением задачи будет значение M(m,n), 
где m — длина строки S1, а n — длина строки S2.
Описание слайда:
M (0, j) = j; M (i, 0) = i; M (i, j) = min (M (i – 1, j – 1), M (i – 1, j ) + 1, M (i , j – 1) +1), если S1[i] = S2[j]; M (i, j) = min (M (i – 1, j ), M (i , j – 1)) + 1, если S1[i] ≠ S2[j]; Решением задачи будет значение M(m,n), где m — длина строки S1, а n — длина строки S2.

Слайд 40





Пример
 S1 = ”abc”, S2 = ”aabddc”
Построим таблицу M, нумерация строк и столбцов которой начинается с нуля 
и элементами которой будут числа, равные значениям функции,  описанной
выше.
Описание слайда:
Пример S1 = ”abc”, S2 = ”aabddc” Построим таблицу M, нумерация строк и столбцов которой начинается с нуля и элементами которой будут числа, равные значениям функции, описанной выше.

Слайд 41





Обратный ход
М[1,3] = 2, означает, что из строки “a” можно получить строку “aab”, используя две допустимых операции. В примере за три допустимых операции можно преобразовать строку S1 в S2. Для определения операций нужно встать на последний символ строки S1 и начать движение по таблице от правого верхнего  угла.  В примере движение начнется с ячейки М[3,6]. 
Находясь в ячейке М[i, j], будем рассматривать два случая. 
1) Если М[-1, i] = М[j, -1], то будем сдвигаться по диагонали влево-вниз, попадая в ячейку М[i-1, j-1]. При этом будем  перемещаться по строке S1  на один символ влево, т.е. сделаем текущим в строке символ, находящийся в i-1 позиции. 
2) Если М[-1, i] ≠ М[j, -1], то будем сдвигаться по таблице  на одну позицию либо влево, попадая в ячейку  М[i, j-1],  либо  вниз в ячейку  М[i-1, j]. Этот выбор будет зависеть от того, какой из элементов, находящихся в этих ячейках, меньше. При движении влево будем удалять i-ый символ в строке S1,  перемещась  на один символ влево. При движении вниз будем вставлять после i-го символа в строке S1 символ S2[j].
Описание слайда:
Обратный ход М[1,3] = 2, означает, что из строки “a” можно получить строку “aab”, используя две допустимых операции. В примере за три допустимых операции можно преобразовать строку S1 в S2. Для определения операций нужно встать на последний символ строки S1 и начать движение по таблице от правого верхнего угла. В примере движение начнется с ячейки М[3,6]. Находясь в ячейке М[i, j], будем рассматривать два случая. 1) Если М[-1, i] = М[j, -1], то будем сдвигаться по диагонали влево-вниз, попадая в ячейку М[i-1, j-1]. При этом будем перемещаться по строке S1 на один символ влево, т.е. сделаем текущим в строке символ, находящийся в i-1 позиции. 2) Если М[-1, i] ≠ М[j, -1], то будем сдвигаться по таблице на одну позицию либо влево, попадая в ячейку М[i, j-1], либо вниз в ячейку М[i-1, j]. Этот выбор будет зависеть от того, какой из элементов, находящихся в этих ячейках, меньше. При движении влево будем удалять i-ый символ в строке S1, перемещась на один символ влево. При движении вниз будем вставлять после i-го символа в строке S1 символ S2[j].

Слайд 42





Последовательность действий для примера
Изначально текущим в строке S1 является последний символ  –символ c.
Так как М[-1, 3] = М[6, -1], то осуществляем переход в ячейку М[5, 2] и текущим в S1 становится предпослений символ – b.
Далее, так как М[-1, 2] ≠ М[5, -1], передвигаемся в ячейку М[4, 2]. При этом вставим после текущего символа b символ S2 [5] = d (j=5).
Продолжая этот процесс  вставим символ S2 [4] = d,  затем в строке S1 сделаем текущим сивол a,  вставим  в строку S1 символ a.
Процесс продолжается до тех пор, пока не достигнем ячейки M[0,0]. Для нашего примера последовательность операций будет следующая: 
		            INS(S1, 2, ‘d’), INS(S1, 2, ‘d’),          INS(S1, 1, ‘a’).
abc –> abc –> abdc –> abddc –> abddc –> aabddc
Описание слайда:
Последовательность действий для примера Изначально текущим в строке S1 является последний символ –символ c. Так как М[-1, 3] = М[6, -1], то осуществляем переход в ячейку М[5, 2] и текущим в S1 становится предпослений символ – b. Далее, так как М[-1, 2] ≠ М[5, -1], передвигаемся в ячейку М[4, 2]. При этом вставим после текущего символа b символ S2 [5] = d (j=5). Продолжая этот процесс вставим символ S2 [4] = d, затем в строке S1 сделаем текущим сивол a, вставим в строку S1 символ a. Процесс продолжается до тех пор, пока не достигнем ячейки M[0,0]. Для нашего примера последовательность операций будет следующая: INS(S1, 2, ‘d’), INS(S1, 2, ‘d’), INS(S1, 1, ‘a’). abc –> abc –> abdc –> abddc –> abddc –> aabddc

Слайд 43





Отметим, что решений в данной задаче может быть несколько.
Отметим, что решений в данной задаче может быть несколько.
Движение по таблице представлено ниже.
Описание слайда:
Отметим, что решений в данной задаче может быть несколько. Отметим, что решений в данной задаче может быть несколько. Движение по таблице представлено ниже.

Слайд 44





Итак, tij вычисляются в порядке возрастания разностей нижних 
Итак, tij вычисляются в порядке возрастания разностей нижних 
индексов. Процесс начинается с вычисления tii для всех i, затем
ti,i+1 для всех i, потом ti,i+2 и т. д. При этом tik и tk+1,j будут уже
 вычислены, когда мы приступим к вычислению tij. 
 Оценка сложности данного алгоритма есть О (п3).
В результате работы алгоритма для примера из четырех матриц
будет построена следующая таблица T:	
Порядок, в котором можно произвести эти умножения, легко определить,
приписав каждой клетке то значение k, на котором достигается минимум.
Описание слайда:
Итак, tij вычисляются в порядке возрастания разностей нижних Итак, tij вычисляются в порядке возрастания разностей нижних индексов. Процесс начинается с вычисления tii для всех i, затем ti,i+1 для всех i, потом ti,i+2 и т. д. При этом tik и tk+1,j будут уже вычислены, когда мы приступим к вычислению tij. Оценка сложности данного алгоритма есть О (п3). В результате работы алгоритма для примера из четырех матриц будет построена следующая таблица T: Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке то значение k, на котором достигается минимум.

Слайд 45





Алгоритм
for (i=0; i<n; i++)   mi,i = 0;
for (l=1; l<n; l++)
	for (i=0; i<n; i++) {
		j = i + l;
		for (k = 0; k < j; k++)
			mij = min(mi,k+ mk+1,j + ri-1*rk* rj)
	}
ri-1 – количество строк в M’
rk – количество столбцов в M’
rj – количество столбцов в M˝
Описание слайда:
Алгоритм for (i=0; i<n; i++) mi,i = 0; for (l=1; l<n; l++) for (i=0; i<n; i++) { j = i + l; for (k = 0; k < j; k++) mij = min(mi,k+ mk+1,j + ri-1*rk* rj) } ri-1 – количество строк в M’ rk – количество столбцов в M’ rj – количество столбцов в M˝

Слайд 46





Задача  "Divisibility“  1999-2000 ACM NEERC  (подключена в системе тестирования NSUTS в школьных тренировках)
Consider an arbitrary sequence of integers. One can place + or – 
operators between integers in the sequence, thus deriving different
arithmetical expressions that evaluate to different values. 
Let us, for example, take the sequence: 17, 5, –21, 15. 
There are eight possible expressions: 
	17+5+ – 21+15=16    	  17+5+–21–15=–14 
	17+5– –21+15=58            17+5– –21–15=28 
     17–5 + –21+15=6              17–5+–21–15=–24 
     17–5– –21+15=48             17–5– –21–15=18 
We call the sequence of integers divisible by K if + or – operators can be placed
between integers in the sequence in such way that resulting value is divisible by K.
In the above example, the sequence is divisible by 7 (17+5+–21–15=–14) but is not
divisible by 5. You are to write a program that will determine divisibility of sequence
of integers. 
The first line of the input file contains two integers, N and K (1 ≤ N ≤ 10000,
2 ≤ K ≤ 100) separated by a space. 
The second line contains a sequence of N integers separated by spaces. Each integer
 is not greater than 10000 by its absolute value.
Описание слайда:
Задача "Divisibility“ 1999-2000 ACM NEERC (подключена в системе тестирования NSUTS в школьных тренировках) Consider an arbitrary sequence of integers. One can place + or – operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, –21, 15. There are eight possible expressions: 17+5+ – 21+15=16 17+5+–21–15=–14 17+5– –21+15=58 17+5– –21–15=28 17–5 + –21+15=6 17–5+–21–15=–24 17–5– –21+15=48 17–5– –21–15=18 We call the sequence of integers divisible by K if + or – operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+–21–15=–14) but is not divisible by 5. You are to write a program that will determine divisibility of sequence of integers. The first line of the input file contains two integers, N and K (1 ≤ N ≤ 10000, 2 ≤ K ≤ 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by its absolute value.

Слайд 47





Задача  "Gangsters" (подключена в системе тестирования NSUTS в школьных тренировках)
N gangsters are going to a restaurant. The i-th gangster comes at the time Ti 
and has the prosperity Pi. The door of the restaurant has K+1 states of openness
expressed by the integers in the range [0, K]. The state of openness can change
by one in one unit of time; i.e. it either opens by one, closes by one or remains
the same. At the initial moment of time the door is closed (state 0). The i-th
gangster enters the restaurant only if the door is opened specially for him, i.e.
 when the state of openness coincides with his stoutness Si. If at the moment of
time when the gangster comes to the restaurant the state of openness is not
equal to his stoutness, then the gangster goes away and never returns.
The restaurant works in the interval of time [0, T].
The goal is to gather the gangsters with the maximal total prosperity in the
restaurant by opening and closing the door appropriately.
The first line of the input file contains the values N, K, and T, separated by spaces. 
(1≤N,K≤100 ). he second line of the input file contains the moments of time when
gangsters come to the restaurant T1, T2, ..., TN, separated by spaces. The third line of the
input file contains the values of the prosperity of gangsters P1, P2, ..., PN, separated by 
spaces. The forth line of the input file contains the values of the stoutness of gangsters
S1, S2, ..., SN, separated by spaces. All values in the input file are integers.
Описание слайда:
Задача "Gangsters" (подключена в системе тестирования NSUTS в школьных тренировках) N gangsters are going to a restaurant. The i-th gangster comes at the time Ti and has the prosperity Pi. The door of the restaurant has K+1 states of openness expressed by the integers in the range [0, K]. The state of openness can change by one in one unit of time; i.e. it either opens by one, closes by one or remains the same. At the initial moment of time the door is closed (state 0). The i-th gangster enters the restaurant only if the door is opened specially for him, i.e. when the state of openness coincides with his stoutness Si. If at the moment of time when the gangster comes to the restaurant the state of openness is not equal to his stoutness, then the gangster goes away and never returns. The restaurant works in the interval of time [0, T]. The goal is to gather the gangsters with the maximal total prosperity in the restaurant by opening and closing the door appropriately. The first line of the input file contains the values N, K, and T, separated by spaces. (1≤N,K≤100 ). he second line of the input file contains the moments of time when gangsters come to the restaurant T1, T2, ..., TN, separated by spaces. The third line of the input file contains the values of the prosperity of gangsters P1, P2, ..., PN, separated by spaces. The forth line of the input file contains the values of the stoutness of gangsters S1, S2, ..., SN, separated by spaces. All values in the input file are integers.

Слайд 48





Пример
t = 1  2  3  4  5  6
S = 1  2  3  4  5  1
P = 1  1  1  1  1  100
Описание слайда:
Пример t = 1 2 3 4 5 6 S = 1 2 3 4 5 1 P = 1 1 1 1 1 100

Слайд 49





КОНЕЦ ЛЕКЦИИ
Описание слайда:
КОНЕЦ ЛЕКЦИИ

Слайд 50





Разбиение  чисел 
Разбиением называется представление натурального числа в виде суммы натуральных слагаемых, а сами слагаемые — частями разбиения. Порядок слагаемых не играет роли. Будем записывать разбиения, перечисляя их части через запятую в невозрастающем порядке. Например, разбиение 4=2+1+1 записывается как (2, 1, 1). 
Пусть p(n) обозначает количество всех разбиений натурального числа n. Например, p(5) = 7, p(100) = 190 569 292.
p(100) было известно ещё в XIX веке. 
Задача вычисления p(n) имеет почтенный возраст. Впервые она была сформулирована Лейбницем в 1654 году, а в 1740 — предложена немецким математиком Филиппом Ноде Леонарду Эйлеру. 
Занимаясь разбиениями, Эйлер открыл целый ряд их свойств, среди которых главное место занимала знаменитая «пентагональная теорема». С исследований Эйлера начинается история теории разбиений, в развитии которой принимали участие крупнейшие математики последующих поколений.
Описание слайда:
Разбиение  чисел Разбиением называется представление натурального числа в виде суммы натуральных слагаемых, а сами слагаемые — частями разбиения. Порядок слагаемых не играет роли. Будем записывать разбиения, перечисляя их части через запятую в невозрастающем порядке. Например, разбиение 4=2+1+1 записывается как (2, 1, 1). Пусть p(n) обозначает количество всех разбиений натурального числа n. Например, p(5) = 7, p(100) = 190 569 292. p(100) было известно ещё в XIX веке. Задача вычисления p(n) имеет почтенный возраст. Впервые она была сформулирована Лейбницем в 1654 году, а в 1740 — предложена немецким математиком Филиппом Ноде Леонарду Эйлеру. Занимаясь разбиениями, Эйлер открыл целый ряд их свойств, среди которых главное место занимала знаменитая «пентагональная теорема». С исследований Эйлера начинается история теории разбиений, в развитии которой принимали участие крупнейшие математики последующих поколений.

Слайд 51





Исследования Эйлера 
Изучение функции p(n) Эйлер начинает с рассмотрения бесконечного произведения
(1 + x + x2 + ...)(1 + x2 + x4 + ...) ... (1 + xk + x2k + ...) ...
Каждый член произведения получается в результате умножения мономов, взятых по одному из каждой скобки. Если в первой скобке взять xm1, во второй — x2m2 и т.д., то их произведение будет равно xm1+2m2+3m3+....   Значит, после раскрытия скобок получится сумма сумма мономов вида xm1+2m2+3m3+.... 
Сколько раз в этой сумме встретится хn? Столько, сколькими способами можно представить n как сумму m1 + 2m2 + 3m3 + ... Каждому такому представлению отвечает разбиение числа n на m1 единиц, m2 двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при xn равен числу разбиений p(n).
Описание слайда:
Исследования Эйлера Изучение функции p(n) Эйлер начинает с рассмотрения бесконечного произведения (1 + x + x2 + ...)(1 + x2 + x4 + ...) ... (1 + xk + x2k + ...) ... Каждый член произведения получается в результате умножения мономов, взятых по одному из каждой скобки. Если в первой скобке взять xm1, во второй — x2m2 и т.д., то их произведение будет равно xm1+2m2+3m3+.... Значит, после раскрытия скобок получится сумма сумма мономов вида xm1+2m2+3m3+.... Сколько раз в этой сумме встретится хn? Столько, сколькими способами можно представить n как сумму m1 + 2m2 + 3m3 + ... Каждому такому представлению отвечает разбиение числа n на m1 единиц, m2 двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при xn равен числу разбиений p(n).

Слайд 52





d(n) = l(n)  (теорема Эйлера)
Обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) — на нечётные. Например, среди выписанных выше разбиений числа 5 различные части имеют (5), (4, 1) и (3, 2), а нечётные — (5), (3, 1, 1) и (1, 1, 1, 1, 1). Значит, d(5) = l(5) = 3. 
Тогда:
d(0) + d(1) x + d(2) x2 + d(3) x3 + ... = (1 + x)(1 + x2)(1 + x3) ... , 
l(0) + l(1) x + l(2) x2 + l(3) x3 + ... = 1 (1 – x)(1 – x3)(1 – x5) ...
.
Описание слайда:
d(n) = l(n) (теорема Эйлера) Обозначим через d(n) количество разбиений числа n на различные слагаемые, а через l(n) — на нечётные. Например, среди выписанных выше разбиений числа 5 различные части имеют (5), (4, 1) и (3, 2), а нечётные — (5), (3, 1, 1) и (1, 1, 1, 1, 1). Значит, d(5) = l(5) = 3. Тогда: d(0) + d(1) x + d(2) x2 + d(3) x3 + ... = (1 + x)(1 + x2)(1 + x3) ... ,  l(0) + l(1) x + l(2) x2 + l(3) x3 + ... = 1 (1 – x)(1 – x3)(1 – x5) ... .

Слайд 53





Изучая p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)...  Раскрывая в нём скобки, Эйлер получил удивительный результат:
Изучая p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)...  Раскрывая в нём скобки, Эйлер получил удивительный результат:
(1 – x)(1 – x2)(1 – x3) ... = 1 – x – x2 + x5 + x7 – x12 – x15 + x22 + x26 – x35 – x40 + ...
Показатели в правой части — пятиугольные числа, т.е. числа вида (3q2 ± q)/2, а знаки при соответствующих мономах равны (–1)q. 
Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема
Описание слайда:
Изучая p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)... Раскрывая в нём скобки, Эйлер получил удивительный результат: Изучая p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)... Раскрывая в нём скобки, Эйлер получил удивительный результат: (1 – x)(1 – x2)(1 – x3) ... = 1 – x – x2 + x5 + x7 – x12 – x15 + x22 + x26 – x35 – x40 + ... Показатели в правой части — пятиугольные числа, т.е. числа вида (3q2 ± q)/2, а знаки при соответствующих мономах равны (–1)q. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна следующая теорема

Слайд 54





Пентагональная теорема:
  
Используя ее:
( p(0) + p(1) x + p(2) x2 + ...)(1 – x – x2 + x5 + x7 – x12 – x15 + ...) = 1. 
формула Эйлера, позволяющую последовательно находить числа p(n): 
p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... 
+ (–1)q+1( p(n– (3q² – q)/2) + p(n– (3q² + q)/2)) 
Описание слайда:
Пентагональная теорема:    Используя ее: ( p(0) + p(1) x + p(2) x2 + ...)(1 – x – x2 + x5 + x7 – x12 – x15 + ...) = 1. формула Эйлера, позволяющую последовательно находить числа p(n): p(n) = p(n–1) + p(n–2) – p(n–5) – p(n–7) + ... + (–1)q+1( p(n– (3q² – q)/2) + p(n– (3q² + q)/2)) 

Слайд 55





Решение (динамика)
 1.  1   1  1   1     //исходный массив 
 2.  1  1  2
 3.  1  3
 4.  2  2
 5.  4
Описание слайда:
Решение (динамика) 1. 1 1 1 1 //исходный массив 2. 1 1 2 3. 1 3 4. 2 2 5. 4

Слайд 56






const nmax=120;
procedure Summ(N:integer); 
var List : array [0..nmax] of byte;{вспомогательный массив для хранения значений слагаемых}
CountVariants : longint;{количество вариантов} 
procedure Generate(k, Count, max:longint);
{номер элемента, количество,максимальное начение=числу}  
begin     {Текущее разложение}     
inc(CountVariants);  {первое разложение на единицы}     
while (List[k] < max) and (k < (Count-1)) do
  {пока значение элемента меньше числа и его номер меньше количества элементо-1}      
	 begin   dec(Count); inc(List[k]);    {уменьшаем размер, переходим в следующий разряд
					 влево, сумма не изменяется}        
                 Generate(k+1, Count, List[k]);   {генерируем следующее  разложение}      
      end;     
List[k] := 1;   {снова в правую крайнюю ячейку}  
end; 
begin    if (N < 1) or (N > nmax) then exit;
 FillChar(List, sizeOf(List), 1);   {заполняем массив единицами}    
CountVariants := 0;    
Generate(0, N, N);    {генерируем разбиения}   
 WriteLn('Всего вариантов: ', CountVariants); end; 
var N:integer;
 begin readln(N);   Summ(N);  end.
Описание слайда:
const nmax=120; procedure Summ(N:integer); var List : array [0..nmax] of byte;{вспомогательный массив для хранения значений слагаемых} CountVariants : longint;{количество вариантов} procedure Generate(k, Count, max:longint); {номер элемента, количество,максимальное начение=числу}   begin     {Текущее разложение}     inc(CountVariants); {первое разложение на единицы}     while (List[k] < max) and (k < (Count-1)) do {пока значение элемента меньше числа и его номер меньше количества элементо-1}       begin   dec(Count); inc(List[k]);   {уменьшаем размер, переходим в следующий разряд влево, сумма не изменяется}         Generate(k+1, Count, List[k]); {генерируем следующее разложение}       end;     List[k] := 1; {снова в правую крайнюю ячейку}   end; begin    if (N < 1) or (N > nmax) then exit;  FillChar(List, sizeOf(List), 1); {заполняем массив единицами}     CountVariants := 0;     Generate(0, N, N); {генерируем разбиения}    WriteLn('Всего вариантов: ', CountVariants); end; var N:integer; begin readln(N);  Summ(N); end.

Слайд 57





x(m) разбиений натурального числа m
Для решения исходной задачи перейдем к рассмотрению обобщенной задачи. Подсчитаем количество P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n. Ясно, что x(m)=P(m,m). 
1) P(m,1)=1 –  существует только одно разбиение m, в котором
слагаемые не превосходят единицы, а именно: m=1+1+…+1. 
2) P(1,n)=1 – число 1 имеет одно представление при любом n. 
3) P(m,n)=P(m,m) при n>m - слагаемых, больших m, в разбиениях нет
4) P(m,m)=P(m,m-1)+1 - существует лишь одно разбиение со
слагаемым, равным m. Все иные разбиения имеют слагаемые, не
превосходящие m-1. 
5) P(m,n)=P(m,n-1)+P(m-n,n) (n<m). (см. cледующий слайд)
Описание слайда:
x(m) разбиений натурального числа m Для решения исходной задачи перейдем к рассмотрению обобщенной задачи. Подсчитаем количество P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n. Ясно, что x(m)=P(m,m). 1) P(m,1)=1 – существует только одно разбиение m, в котором слагаемые не превосходят единицы, а именно: m=1+1+…+1. 2) P(1,n)=1 – число 1 имеет одно представление при любом n. 3) P(m,n)=P(m,m) при n>m - слагаемых, больших m, в разбиениях нет 4) P(m,m)=P(m,m-1)+1 - существует лишь одно разбиение со слагаемым, равным m. Все иные разбиения имеют слагаемые, не превосходящие m-1. 5) P(m,n)=P(m,n-1)+P(m-n,n) (n<m). (см. cледующий слайд)

Слайд 58





P(m,n) = P(m,n-1) + P(m-n,n) (n<m)
Все разбиения m на сумму слагаемых, не превосходящих n, можно разбить на два непересекающихся класса:
	-  суммы, не содержащие n в качестве слагаемого, 
     - суммы, содержащие n. 
Количество элементов первого класса равно P(m,n-1). 
Количество элементов второго класса:
без учета слагаемого n суммы элементов второго класса равны m-n. Значит, их общее количество равно P(m-n,n) и, следовательно, общее количество элементов второго класса также равно этой величине. 
	 
      P(5,5) = P(5,4 ) + P(1,5) = P(5,4) + 1;
      P(5,4) = P(5,3) + P(1,4) = 5 + 1.
Описание слайда:
P(m,n) = P(m,n-1) + P(m-n,n) (n<m) Все разбиения m на сумму слагаемых, не превосходящих n, можно разбить на два непересекающихся класса: - суммы, не содержащие n в качестве слагаемого, - суммы, содержащие n. Количество элементов первого класса равно P(m,n-1). Количество элементов второго класса: без учета слагаемого n суммы элементов второго класса равны m-n. Значит, их общее количество равно P(m-n,n) и, следовательно, общее количество элементов второго класса также равно этой величине. P(5,5) = P(5,4 ) + P(1,5) = P(5,4) + 1; P(5,4) = P(5,3) + P(1,4) = 5 + 1.

Слайд 59





Задача о телефонном номере  (подключена в системе тестирования NSUTS в школьных тренировках)
Если вы обратили внимание, то клавиатура
многих телефонов выглядит  как показано –> 
Использование изображенных на клавишах 
букв позволяет представить номер телефона
в виде легко запоминающихся слов. Многие
фирмы пользуются этим и стараются
подобрать себе номер телефона так, чтобы он содержал как можно больше
букв из имени фирмы.
Напишите программу, которая преобразует исходный цифровой номер телефона 
в соответствующую последовательность букв и цифр, содержащую как можно
больше символов из названия фирмы. При этом буквы из названия фирмы
должны быть указаны в полученном номере в той же последовательности, в
которой они встречаются в названии фирмы. Например, если фирма называется
IBM, а исходный номер телефона — 246, то замена его на BIM не допустима,
тогда как замена его на 2IM или В4М является правильной. 
S1= “IBM”,  S2= “246”. При этом, если в S1 встречаются буквы, которые соответствуют
цифрам номера телефона в нужном порядке, то они останутся без изменения.
Описание слайда:
Задача о телефонном номере (подключена в системе тестирования NSUTS в школьных тренировках) Если вы обратили внимание, то клавиатура многих телефонов выглядит как показано –> Использование изображенных на клавишах букв позволяет представить номер телефона в виде легко запоминающихся слов. Многие фирмы пользуются этим и стараются подобрать себе номер телефона так, чтобы он содержал как можно больше букв из имени фирмы. Напишите программу, которая преобразует исходный цифровой номер телефона в соответствующую последовательность букв и цифр, содержащую как можно больше символов из названия фирмы. При этом буквы из названия фирмы должны быть указаны в полученном номере в той же последовательности, в которой они встречаются в названии фирмы. Например, если фирма называется IBM, а исходный номер телефона — 246, то замена его на BIM не допустима, тогда как замена его на 2IM или В4М является правильной. S1= “IBM”, S2= “246”. При этом, если в S1 встречаются буквы, которые соответствуют цифрам номера телефона в нужном порядке, то они останутся без изменения.

Слайд 60






Формат входных данных:
Первая строка входного файла содержит название фирмы. Она состоит только из заглавных букв латинского алфавита, количество которых не превышает 80 символов. Вторая прока содержит номер телефона в виде последовательности цифр. Цифр в номере телефона также не более 80. 
Формат выходных данных:
В единственной строке выходного файла должно содержаться число букв из измененного номера.
Пример файла входных данных:
IBM
246
Пример файла выходных данных:
2
Описание слайда:
Формат входных данных: Первая строка входного файла содержит название фирмы. Она состоит только из заглавных букв латинского алфавита, количество которых не превышает 80 символов. Вторая прока содержит номер телефона в виде последовательности цифр. Цифр в номере телефона также не более 80. Формат выходных данных: В единственной строке выходного файла должно содержаться число букв из измененного номера. Пример файла входных данных: IBM 246 Пример файла выходных данных: 2



Похожие презентации
Mypresentation.ru
Загрузить презентацию