Задача
В этом разделе будет описано очень умное усовершенствование алгоритма выравнивания последовательностей, с которым работа будет выполняться за вре- мя O(mn), тогда как затраты памяти будут составлять только O(m + n). Другими словами, затраты памяти сокращаются до линейных, тогда как время выполнения возрастает не более чем с постоянным множителем. Для простоты изложения шаги алгоритма будут описываться в контексте путей на графе GXY — естественного эквивалента задачи выравнивания последовательностей. Таким образом, задача поиска пар в оптимальном выравнивании может быть сформулирована как задача поиска ребер в кратчайшем пути из угла в угол графа GXY.
Сам алгоритм является удачным практическим применением принципа «раз- деляй и властвуй». В его основе лежит один важный факт: при делении задачи на несколько рекурсивных вызовов память, необходимая для вычислений, может использоваться для других вызовов. Впрочем, эта идея применяется достаточно нетривиальным образом.
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
- Основные задачи МПП.
- Задачи и упражнения
- Задачи
- Трудная задача
- 1.1. Предмет и задачи криминалистики