Изменения

== 7. Динамическое программирование ==:0. '''в процессе проверки!!!''' 7. [[Динамическое программирование]] :# Добавить известную цитату про ДП:# Интервики на NP-полноту:# Картинки криво расположены:# Добавить больше примеров:# Добавить описание принципа оптимальности на подмножествах:# Оформить правильно источники информации:# Добавить про мемоизацию (и желательно что-нибудь разумное)=== Классические задачи динамического программирования ===# '''!!!''' [[Кратчайший путь в ациклическом графе]]## в тексте d, i, j Добавить интервики## Переменные и т.п. обернуть константы взять в латех, а то страшно смотритсяTex## Отформатировать псевдокод оформить как функцию## Написать в примере, принимающую матрицу что дана матрица смежности ## Перерисовать картинку на нормальную## Оформить правильно источники информации и возвращающую кратчайший путьсм. также## Добавить пару слов про то, без всяких inputData и writeDataчто эту задачу можно решить поиском в ширину# [[Задача о расстановке знаков числе путей в выраженииациклическом графе]]## "с использованием принципа оптимальности на подотрезке" — внутреннюю ссылку на оптимальность на подотрезкеВзять задачу в шаблон## Отформатировать псевдокод## ссылка просто на "динамическое программирование" Обернуть имя функции в тексте в википедии не нужнаmathrm## доказать оптимальностьЗаменить дефисы на тире## нет номера страницы в источникеДобавить см. также и источники информации# '''!!!''' [[Задача о наибольшей общей подпоследовательностирасстановке знаков в выражении]]# # Взять задачу в шаблон## Исправить знаки неравенств## Ссылку примечанием оформить нормально## Взять все переменные и константы в тексте в Tex## Отформатировать псевдокод## Табличку нормально оформить## Описать восстановление ответа## Источники информации правильно оформить# '''!!!''' [[Задача о порядке перемножения матриц]]# # Взять переменные и константы в Tex## Обернуть задачу в шаблон## Интервики на конспект правильных скобочных последовательностей## Написать, почему нас не устраивает число Каталана в асимптотике## Отформатировать псевдокоды## Оформить правильно источники информации## Убрать про мемоизацию# '''!!!''' [[Задача о наибольшей возрастающей общей подпоследовательности]]# # Англоязычные термины правильно оформить## Взять задачу в шаблон## Заменить НОП на LCS в тексте## Отформатировать псевдокоды## Оформить правильно источники информации## Добавить примеры решения различных задач с использованием LCS# '''!!!''' [[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на деревенаибольшей возрастающей подпоследовательности]]# [[Метод четырех русских для умножения матриц]]# Оформить правильно англоязычные термины## Исправить знаки неравенств## Заменить дефисы на тире## Отформатировать псевдокод и исправить в нём ошибку## Взять задачу в шаблон# [[Применение метода четырех русских # Взять все переменные и константы в задачах ДП Tex## Заменить max на \max## Решение через табло Юнга вообще криво оформлено## Правильно оформить источники информации и см. также## Заменить дефисы на примере задачи о НОП]]тире# '''!!!''' [[Задача коммивояжера, ДП по подмножествам]]## указать страницы Оформить правильно англоязычные термины## Задачу взять в источникахшаблон# [[Задача о выводе # Интервики на NP-полноту## Угловые скобки в контекстнопаре сделать правильно## Отформатировать псевдокоды## Оформить правильно источники информации и см. также## Добавить какие-свободной грамматике, алгоритм Кока-Янгера-Касами]]нибудь способы оптимизации## Можно добавить фактов про шахматные доски и обход конём# '''!!!''' [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]# # Англоязычные термины## Исправить знаки неравенств## Взять переменные и константы в Tex## Пояснить про eps в функции## Отформатировать псевдокоды## Оформить правильно источники информации# '''!!!''' [[Задача о расстоянии Дамераурюкзаке]]## Взять задачу в шаблон## Отформатировать псевдокоды## Заменить дефисы на тире## Исправить знаки неравенств## Написать, что метод динамического программирование всё равно не повзволяет решать задачу за полиномиальное время и написать почему## Сделать итоговую формулу для А c помощью фигурной скобки## Предложить вариант замены картинок на вики-Левенштейнатаблички с сохранением обозначения пути## Понизить уровень заголовков первого уровня## Оформить правильно источники информации=== '''в процессе проверки''' Способы оптимизации методв динамического программирования ===<ol><li value="10">[[Метод четырех русских для умножения матриц]] </li><li>[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]</li># <li>[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]</li># <li>[[Задача о наибольшей подпоследовательностиMeet-in-the-палиндромеmiddle]]</li></ol># === '''!!!в процессе проверки''' Другие задачи ===<ol><li value="14">[[Задача о расстоянии Дамерау-Левенштейна]] </li><li>[[MeetЗадача о выводе в контекстно-inсвободной грамматике, алгоритм Кока-theЯнгера-middleКасами]]</li>## можете попробовать вспомнить какую<li>[[Задача о наибольшей подпоследовательности-нибудь интересную задачу, решаемую этим методом, если вспомните, напишите, посмотрим, можно ли сделать по этому конспект.палиндроме]] </li># <li>[[Динамическое программирование по профилю]]</li># [[Задача о рюкзаке]]## разделы первого уровня должны быть ==# <li>[[Динамика по поддеревьям]]## разделы первого уровня должны быть ==|Динамика по поддеревьям, а не =## '''эээ, а вообще-то статья про задачо о паросочетание максимального веса в дереве уже есть''']] </li></ol>