Задача о наибольшей общей подпоследовательности

Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения. Алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи—на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.
В типичном случае динамическое программирование применяется к задачам оптимизации. Примерами задач динамического программирования являются задача о перемножении матриц и задача о нахождении найбольшей общей подпоследовательности. Эти задачи и методы их решения будут рассмотрены в данной работе.

ВСТУПЛЕНИЕ 5
1 МАТЕМАТИЧНА ПОСТАНОВКА ЗАДАЧІ 6
2 ПРИКЛАДИ ЗМІСТОВИХ ПОСТАНОВОК ЗАДАЧІ 8
3 АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ О ПЕРЕМНОЖЕНИИ МАТРИЦ 10
3.1 Метод північно-західного кута 12
3.2 Метод найменшого часу 13
3.3 Оцінка складності алгоритмів 14
4 ПРИКЛАДИ РОЗВ’ЯЗАННЯ ЗАДАЧ «ВРУЧНУ» 15
5 РОЗВ’ЯЗАННЯ ЗАДАЧІ З ДОПОМОГОЮ EXCEL 26
6 ПРОГРАМНА РЕАЛІЗАЦІЯ АЛГОРИТМУ 31
ВИСНОВОК 33
ПЕРЕЛІК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 34
Додаток А 34
Лістинг програми 34