Пример готовой курсовой работы по предмету: Программирование
Содержание
Введение……………………………………………………………………………………………2
Раздел
1. Основные понятия и обозначения……………………………..3
1.1 История…………………………………………………………..3
1.2 Задачи оптимизации…………………………………………….4
1.3 Идея динамического программирования………………………7
Раздел
2. Разновидности задач, решаемых методом динамического программирования…………………..……………………………………..11
2.1 Пример решения задач……….…………………………….…..11
2.2 Задача о Черепашке…..……………………………….………..14
2.3 Задача о рюкзаке……….……..…………………………………17
Раздел
3. Применение метода динамического программирования……..22
3.1 Степень числа………….………………………………………..22
3.2 «Алгоритм Нудельмана- Вунша»……….……………………..23
3.3 Задача о камнях……………………….………….……………..24
3.4 «Разбиение выпуклого N- угольника»…………………………26
Заключение…………………………………..………………………………28
Список литературы………………………………………………………… 29
Выдержка из текста
Повышение эффективности вычислений при решении определенного класса задач математического программирования может быть достигнуто путем использования методов динамического программирования. Особенностями методов динамического программирования являются использование для их реализации принципов инвариантного погружения и оптимальности. Принцип инвариантного погружения предполагает замену общей задачи на эквивалентную совокупность более простых (пошаговых) задач. Принцип оптимальности определяет возможность получения глобально-оптимальных стратегий (решений) на основе решений пошаговых задач оптимизации. Методы динамического программирования позволяют существенно сократить (по сравнению с полным перебором) число анализируемых вариантов решений в процессе определения глобально-оптимального решения за счет учета априорной информации о решениях, не являющихся допустимыми, и использования информации, полученной на предыдущих шагах оптимизации. Кроме того, достоинством методов динамического программирования является их инвариантность к классу целевой и ограничительных функций.
Цель работы: Изучить методы динамического программирования, ознакомиться со сферами применения данных методов.
Задачи работы:
1. Изучить профессиональную литературу по постановке задачи и реализации метода динамического программирования.
2. Показать на практике способы решения задач методом динамического программирования.
Все задачи разрабатываются на языке программирования Pascal.
Список использованной литературы
1. Искусство программирования –Кнут Д. Э. Пер. с англ. Т.3: Сортировка и поиск/ Кнут Дональд Эрвин;KnuthDonaldE./ Под общ.ред. Ю. В. Козаченко.- 2-е изд., испр. идоп.-М.: Вильямс, 2014.
2. Динамическое программирование [Электронный ресурс]
/ С. М. Окулов, О. А. Пестов. — Эл.изд. М. : БИНОМ. Лаборатория знаний, 2012.
3. Программирование в алгоритмах / С. М. Окулов. —М.: БИНОМ. Лаборатория знаний, 2002.
4. Алгоритм+ структуры данных= Программы./ Вирт Н.- М.: Наука, 1989.
5. Информация. Алгоритмы. ЭВМ./ Касаткин В. Н.- М.: Просвещение, 1991.
