Аннотация
Введение 3
Глава 1. Динамическое программирование 4
1.1 Основные определения 4
1.2 Идея динамического программирования 4
Глава 2. Задачи с использованием динамического программирования 6
2.1 Задача произведения матриц 6
2.2 Задача редактирования 9
2.3 Другие методы решения задач 13
2.4 Практическое применение 14
Заключение 15
Список источников 16
Приложение 1 17
Приложение 2 18
Приложение 3 19
Приложение 4 21
Приложение 5 22
Цель исследования - показать преимущество динамического программирования по сравнению с другими алгоритмами.
Задачи:
1. изучить необходимую литературу по динамическому программированию;
2. изучить язык python;
3. оценить сложность динамического программирования и других алгоритмов для указанных задач;
4. реализовать алгоритмы на языках Python и Wolfram;
5. сравнить созданные программы по эффективности.
Методы: математические; использование языка Wolfram для программирования в системе Mathematica; использование языка Python для программирования алгоритмов.
Wolfram - язык программирования для системы Mathematica. Спроектирован как максимально универсальный язык с акцентом на символьные вычисления, функциональное и логическое программирование, с поддержкой произвольных структур данных.
Python - это высокоуровневый язык программирования общего назначения, который используется в самых различных задачах программирования. Язык ориентирован на повышение производительности разработчика и читаемости кода.
В данной работе используются определения и алгоритмы из [1] и [2].
В ходе проделанной работы было исследовано динамическое программирование. Реализованы два алгоритма с использованием динамического программирования для решения двух задач: произведения матриц и редактирования. Они были реализованы на Wolfram и Python.
По назначенным задачам можно сделать следующие выводы:
1. Была изучена литература по динамическому программированию.
2. Изучен язык программирования python.
3. Изучены алгоритмы решения двух задач, произведения матриц и редактирования. Реализованы эти алгоритмы на языках программирования wolfram и python.
4. Алгоритм произведения матриц был сравнён с методом перебора, у алгоритма выявлена проблема, связанная с объёмом хранимых данных.
5. Рассмотрены практические применения данных задач.
