ДСо18-09-Динамическое-программирование (1238948)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Carnegie MellonДинамическоепрограммированиеАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 9, 02 ноября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771Метод динамического«программирования»1. Ричард Беллман 1953 год2. Пользуется свойствами задачи1.2.3.Оптимальная подструктураАддитивно перекрывающиеся подзадачиВозможность запоминания решений подзадач3.

Эффективнее рекурсии и/или перебора4. Примеры задач1.2.3.4.5.Числа ФибоначчиО наибольшей подпоследовательностиО редакционном расстоянииО порядке перемножения матрицО ранце2Два подхода динамическогопрограммированияНисходящее ДПВосходящее ДП1. Задача разбивается нанужные подзадачи2. Нужные подзадачирешаются3. Решения подзадачкомбинируются врешение задачи1.

Решаются «все полезные»подзадачи.2. Результаты подзадачнакапливаются исохраняются.3. Решения подзадачкомбинируются в решениезадачи3Классический пример:поиск n-ого числа Фибоначчиint Fibo(int n) {if(n<2)return 1;elsereturnFibo(n-1) + Fibo(n-2);}int fibo(int a[], int n) {if(n<2) return 1;if(a[n])Задействоватьreturn a[n];elseСохранитьreturn (a[n] =fibo(a,n-1) + fibo(a,n-2));}4Сколько слов длины n в алфавите{0,1}, не содержащих две идущиеподряд единицы?K(1) = 2 : 0 и 1K(2) = 3 : 00, 01 и 10K(n) = K(n-1) + K(n-2)00 15На прямоугольном поле размером n x m можнодвигаться на одно поле вниз или вправо.Сколькими способами можно попасть из левойверхней клетки в правую нижнюю?#include <iostream>using namespace std;int main() {int **a,n,m;cin >> n >> m;a = new int* [n];1 1 1 1 111j-11j1i-1 ifor(int i=0; i<n; i++) { a[i] = new int [m];for(int j=0; j<m; j++) a[i][j]=((!i || !j)?1:0); }for(int i=1; i<n; i++) for(int j=1; j<m; j++)a[i][j] = a[i-1][j] + a[i][j-1];cout << a[n-1][m-1] << endl;return 0;}6Задача про последовательностиИз последовательности целых чиселвыбрать самую длинную строговозрастающую подпоследовательность.7Задача про последовательности1.

Массив A[N] для чисел последовательности2. Массив L ={lk} длин строго возрастающихподпоследовательностей, заканчивающих элементом сномером k ≤ N. Наибольший элемент массива L будетдлиной искомой подпоследовательности3. Для предъявления искомой подпоследовательности,ещё один массив B={bk}, номеров предпоследнегоэлемента подпоследовательности, длина которойзаписана в lk.4. lk = max (lj) + 1 для j от 1 до k-1 таких, что aj < ak.8ввод в стексоздание массивовперенос из стека в массивизмерениепоиск максимальной9Нахождение палиндромаНайти длину P наибольшегопалиндрома, который может бытьсоставлен из букв заданной строки S.10Нахождение длины палиндрома P(S)1. Любая строка S, состоящая из одного символа,- это палиндром длины 1.2.

Строка S из двух символов,1. если символы совпадают – это палиндром длины 2,2. если различаются – удаляем любой символ и P(S) = 1.3. Для строки S = s1…sL длины L:1. если начальный и конечный символы совпадают, тоP(S) = P(s2…sL-1) + 2;2. если различаются, то:P(S) = max(P(s2…sL),P(s1…sL-1))длина максимального палиндрома,1. либо из строки без первого символа2. либо из строки без последнего символа1112Задача о хрустальном шаре.Ищем условия разбивания хрустального шара,сброшенного с высоты.Имеем m одинаковых хрустальных шаровЗа какое минимальное число попытокгарантированно найдём этаж N-этажного здания,начиная с которого этажа шары будут разбиваться ?13Задача о хрустальном шаре.¢¢¢m =1Неизбежно бросание скаждого следующего вверхэтажаОтвет: N попытокm=2¢ Кажется уместно делениепополам.

Сбросим первыйшар с ⎣N/2⎦ этажа.1. Если первый шар разбит,то хватит ⎣N/2⎦ попытокниже.2. Если первый шар цел, тохватит ⎣N/2⎦ попытоквыше.¢ Ответ: ⎣N/2⎦ ?¢14Задача о хрустальном шаре(подход на основе ДП)Пусть, для первой попытки оптимален этаж T.Количество попыток F(m,N) зависит от результатаПервый шар разбит:F(m-1, T-1) + 1Первый шар цел:F(m, N-T) + 1На этаже T:F(m,N) = max(F(m-1, T-1),F(m, N-T)) + 1В здании:F(m, N) = minT ( 1 + max(F(m-1, T-1),F(m, N-T)) );F(1,N)=N; F(m,0)=0; F(m,1)=1; F(m,2)=215Нисходящее ДП16Восходящее ДП17Задача о минимальной сдачеИмеется неограниченное количество монетдостоинств V={v1,…,vK}. "i: vi<vi+1Какое минимальное количество монет D(S)потребуется чтобы набрать заданную сумму S ?D(S) = mink( D(S – Vk) )1819Задача о вариантах сдачиИмеется неограниченное количествомонет достоинств V={v1,…,vK}.

"i: vi<vi+1Сколькими способами можно набратьзаданную сумму?2021Код ХаффманаИспользуется для сжатия данныхпутем кодирования более частыхсимволов более короткимипоследовательностями битов.2223Код Хаффмана¢¢Более частые символы последовательности должны иметьболее короткий код, а более редкие – более длинныйЧтобы исключить проблема декодирования символов,кодированых двоичными кодами разной длины, естьпрефиксное кодирование:Код никакого символа не является началом кодадругого.¢Кодирование – бинарное дерево, где листья содержатсимволы, а набор ребер (левое – 0, правое – 1), входящих в путьот корня дерева к листу, порождает код символа.2425Кодирование26Декодирование27.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций