Задача

В этом разделе мы зададимся следующим вопросом: следует ли удовольствоваться границей затрат памяти O(mn)? Если приложение сравнивает слова (или даже предложения) английского языка, такие затраты вполне приемлемы.
Однако в биологических задачах выравнивания последовательностей часто приходится сравнивать очень длинные строки и в таких ситуациях затраты памяти θ(mn) могут стать гораздо более серьезной проблемой, чем время θ(mn). Например, допустим, что сравниваются две строки, каждая из которых состоит из 100 000 символов. В зависимости от процессора перспектива выполнения примерно 10 миллиардов примитивных операций вызывает меньше беспокойства, чем перспектива работы с одним 10-гигабайтным массивом.

В этом разделе будет описано очень умное усовершенствование алгоритма выравнивания последовательностей, с которым работа будет выполняться за вре- мя O(mn), тогда как затраты памяти будут составлять только O(m + n). Другими словами, затраты памяти сокращаются до линейных, тогда как время выполнения возрастает не более чем с постоянным множителем. Для простоты изложения шаги алгоритма будут описываться в контексте путей на графе GXY — естественного эквивалента задачи выравнивания последовательностей. Таким образом, задача поиска пар в оптимальном выравнивании может быть сформулирована как задача поиска ребер в кратчайшем пути из угла в угол графа GXY.

Сам алгоритм является удачным практическим применением принципа «раз- деляй и властвуй». В его основе лежит один важный факт: при делении задачи на несколько рекурсивных вызовов память, необходимая для вычислений, может использоваться для других вызовов. Впрочем, эта идея применяется достаточно нетривиальным образом.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения
  18. Задачи
  19. Трудная задача
  20. 1.1. Предмет и задачи криминалистики