Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
| Код |
321866 |
| Дата создания |
08 июля 2013 |
| Страниц |
22
|
Мы сможем обработать ваш заказ (!) 23 декабря в 12:00 [мск] Файлы будут доступны для скачивания только после обработки заказа.
|
Содержание
Содержание
Теория динамического программирования
Задача 1. Задача распределения капиталовложений
Задача 2. Задача календарного планирования трудовых ресурсов
Задача 3. Задача о замене оборудования
Список литературы
Введение
Менеджмент машиностроительных предприятий
Фрагмент работы для ознакомления
Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).
Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F3 = F2 + F1 и F4 = F3 + F2 — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F2 дважды. Если продолжать дальше и посчитать F5, то F2 посчитается ещё два раза, так как для вычисления F5 будут нужны опять F3 иF4. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.
Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование. Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.
Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:
- перекрывающиеся подзадачи;
- оптимальная подструктура;
- возможность запоминания решения часто встречающихся подзадач.
Динамическое программирование обычно придерживается двух подходов к решению задач:
Список литературы
Список литературы
1.Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с.
2.Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960. – 462с.
3.Габасов Р., Кириллова Ф. М. Основы динамического программирования. — Мн.: Изд-во БГУ, 1975. — 262 с.
4.Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс
5.Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19., 2005. — 1296 с.
6.Щербина О. А. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. — c.21-36.
7.Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms = Algorithms. — 1-е изд. — McGraw-Hill Science/Engineering/Math, 2006. — С. 336.
8.Bertele U., Brioshi F. Nonserial dynamic programming. — N.Y.: Academic Press, 1972. — 235 pp.
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
bmt: 0.00475