2009 → Выпуск 3

Рекурсия + мемоизация = динамическое программирование

Дмитрий Астапов

Аннотация: Статья рассказывает о том, как ленивая модель вычислений, принятая в языке Haskell, помогает кратко и эффективно реализовывать алгоритмы с использованием метода динамического программирования.


The article shows how lazy evaluation combined with memoization leads to succinct and efficient implementations of various dynamic programming algorithms



Обсуждение статьи ведётся по адресу
http://community.livejournal.com/fprog/4277.html.

1  Введение

Сложно найти программу на функциональном языке, которая не использовала бы рекурсивные или взаиморекурсивные вызовы функций. Циклические вычисления (которые в императивном языке требуют управляющих конструкций типа for, while, foreach) записываются либо с помощью функций высших порядков, либо рекурсивно. Сложные структуры данных часто обрабатываются рекурсивно (это называется «структурная рекурсия»). Кроме того, нередко используются и рекурсивно порождаемые структуры данных, классический учебный пример — треугольник Паскаля.

Однако при реализации и использовании рекурсивных алгоритмов легко допустить одну популярную ошибку: одни и те же вычисления могут без необходимости повторяться многократно. Рассмотрим для примера простейшую реализацию на Haskell функции, вычисляющей числа Фибоначчи:

fib 0 = 1 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

Если мы попробуем вычислить с ее помощью 100 первых чисел Фибоначчи, то обнаружим, что с каждым следующим числом скорость вычисления ощутимо падает. Происходит это потому, что для получения каждого последующего числа выполняется вычисление всех предыдущих чисел, причем многих — по несколько раз, и общая временная сложность алгоритма получается Θ(φn), где φ = 1+√5/2.

Данная статья (с примерами на Haskell) посвящена тому, как эффективно — со сложностью порядка Θ(n) или Θ(n logn) — реализовывать подобные рекурсивные алгоритмы.

В качестве примеров для этой статьи взяты задачи из отборочного раунда ежегодного конкурса программистов Google Code Jam 2009.

Полные исходные тексты программ, описываемых в этой статье, можно найти на сайте журнала.

2  Задача 1: Подсчет числа подпоследовательностей

Дана текстовая строка. Необходимо посчитать, сколько раз в ней встречается подпоследовательность символов «welcome to code jam». Для этого необходимо найти в исходной строке одну из букв «w», правее нее — букву «e», и так далее до буквы «m». Говоря более формально, для данной строки input необходимо посчитать, сколькими способами можно выбрать индексы s0, s1, … ,s18 так, что s0 < s1 < … < s18 и конкатенация input[s0], input[s1], … , input[s18] дает строку «welcome to code jam»1.

В оригинальном решении авторы просят вывести только последние четыре цифры получившегося значения, то есть расчеты можно вести по модулю 10000. В этом есть практический смысл: даже для относительно небольших строк количество вариантов может представлять 20-значное число, что затрудняет чтение и проверку результатов. Примеры, иллюстрирующие статью, также будут использовать модульную арифметику.

Подобные задачи встречаются в реальной жизни: выравнивание последовательностей (англ. sequence alignment) генов в биоинформатике (см. [5], [10, стр. 539]), компьютерный анализ и генерация текстов на естественных языках (см. [8]), метод «критического пути» (англ. critical path method) для оценки длительности проектов.

2.1  Наивное решение

Попробуем дать простое словесное описание алгоритма, позволяющего подсчитать, сколько раз строка-шаблон встречается как подпоследовательность в другой строке (области поиска).

Если область поиска пуста, то количество вхождений, очевидно, равно нулю. Если же пуст шаблон, то результат положим равным единице — считаем, что пустой шаблон можно «совместить» с концом строки и таким образом он входит в произвольную строку ровно один раз.

Если же и шаблон, и область поиска не пусты, то необходимо: найти первую букву шаблона в области поиска; посчитать, сколькими способами можно разместить остаток шаблона правее этой точки; прибавить количество способов, которыми можно разместить весь исходный шаблон правее этой точки (то есть, начиная с другой стартовой позиции).

Таким образом, имеем рекурсивное определение, которое можно практически дословно перевести в код на Haskell:

occurs :: String -> String -> Int occurs [] str = 1 occurs pattern [] = 0 occurs (p:ps) (c:cs) | p == c = ( occurs ps cs + occurs (p:ps) cs ) `mod` 10000 | otherwise = occurs (p:ps) cs

Чтобы получить решение изначальной задачи, необходимо реализовать чтение исходных данных из файла и вывод правильно отформатированных результатов вычислений, но этот код не имеет непосредственного отношения к теме статьи и тут не приведен. Полный текст программы можно найти в файле naive.hs в директории welcome_to_code_jam архива с исходными текстами.

2.2  Проблемы с производительностью

Посмотрим, как будет работать указанная функция при поиске шаблона «jam» в строке «jjaamm». Поскольку первые буквы шаблона и области поиска совпадают, результат будет состоять из суммы двух значений (взятие результата по модулю 10000 для простоты опущено):

1 occurs "jam" "jjaamm" = 2 occurs "am" "jaamm" 3 + occurs "jam" "jaamm" = ...

Распишем следующий шаг рекурсии. Чтобы вычислить выражение в строке 2, нужно пропустить следующую букву области поиска, а чтобы вычислить выражение в строке 3, нужно снова вычислить сумму результатов рекурсивных вызовов:

1 ... = occurs "am" "aamm" 2 + ( occurs "am" "aamm" 3 + occurs "jam" "aamm" ) = ...

Значение в строке 3 будет равно нулю, так как остаток области поиска больше не содержит букв «j». Выражения в строках 1 и 2 полностью совпадают, что в будущем приведет к многократному вычислению одних и тех же значений. Посмотрим, что произойдет на следующем шаге:

... = ( occurs "m" "amm" + occurs "am" "amm" ) + ( occurs "m" "amm" + occurs "am" "amm" )

Полностью последовательность вызовов для этого примера представлена на рисунке 1, при этом там изображены только значения параметров, а имя функции occurs опущено. Легко заметить, что по мере продвижения к концу области поиска объем повторяющихся вычислений очень быстро растет (временная сложность реализации Θ(Cnm), где n — длина области поиска, а m — длина шаблона).

Рис. 1: Вычисление occurs "jam" "jjaamm"

Таким образом, налицо разбиение исходной задачи на перекрывающиеся подзадачи, причем оптимальное решение задачи размера N можно вычислить на основании решений задач размера N−1.

Если бы подзадачи не имели перекрытий, то использованный подход (разбить задачу на подзадачи, рекурсивно их решить, а решения — объединить) был бы оптимальным по скорости. Такой способ решения называется «разделяй и властвуй» (англ. divide and conquer). Однако в нашем случае подзадачи перекрываются, и это является прямым показанием для применения метода динамического программирования (см. [12], [1], [7]).

2.3  Решение с использованием динамического программирования

Ключевой идеей динамического программирования является запоминание решений подзадач и дальнейшее их использование без дополнительных повторных вычислений. Применительно к нашей задаче это означает, что нужно запоминать значения occurs p s для разных значений p и s, начиная с самых коротких. Например, для эффективного вычисления occurs "jam" "jjaamm" наверняка необходимо запомнить результаты вычисления occurs "m" "m", occurs "m" "mm", occurs "am" "amm" и так далее.

При использовании языков с энергичной моделью вычислений (англ. eager evaluation) переход от наивного решения к решению с использованием динамического программирования почти всегда заключается в полном или существенном переписывании кода для того, чтобы он работал «от конца к началу». То есть, сначала вычисляются подзадачи минимального размера и запоминается их результат, а затем запомненные значения используются для вычисления подзадач большего размера, и так далее. В нашей задаче, например, необходимо изменить порядок сканирования шаблона и области поиска так, чтобы он происходил от последних символов к первым. Из-за этого многие начинающие программисты не могут написать решение задачи с использованием динамического программирования «с нуля» — им тяжело переиначить «в уме» интуитивно понятный наивный подход к решению.

Кроме того, далеко не всегда требуется вычислять результаты всех возможных подзадач для того, чтобы найти решение исходной задачи. Однако определение того, какие именно подзадачи можно пропустить, может быть достаточно нетривиально.

Благодаря тому, что в Haskell используется ленивая модель вычислений, можно обойтись без переписывания кода и размышлений о том, что и в каком порядке надо вычислять и запоминать. Решение общей задачи может ссылаться на сохраненные решения более мелких подзадач еще до того, как они фактически будут вычислены.

Вот как это выглядит на практике: предположим, что у нас есть ассоциативный массив cache, ставящий в соответствие паре строк (p, s) искомое количество вхождений p в s. Тогда функция occurs сведется к тривиальному поиску нужного значения в этом массиве:

import qualified Data.Map as Map cache :: Map.Map (String, String) Int cache = undefined occurs pat str = fromJust $ Map.lookup (pat,str) cache

Как же сформировать массив cache? Если взять реализацию примитивного алгоритма из предыдущего раздела (изменив имя функции на occurs’), то можно построить cache таким образом:

cache :: Map.Map (String, String) Int cache = Map.fromList [ ( (p,s), occurs' p s) | p <- tails pattern , s <- tails str ]

В cache будут помещены результаты вычисления occurs’ для всех возможных суффиксов (окончаний) строк pattern и str. Благодаря тому, что модель вычисления — ленивая, такое объявление помещает в ассоциативный массив только код для отложенного вызова occurs’. В англоязычной литературе этот служебный код называют thunk. Когда функция occurs обратится за значением конкретного элемента ассоциативного массива, thunk выполнится и будет заменен на результат вычисления. Все последующие обращения к этому элементу массива будут возвращать готовый результат без дополнительных вычислений.

Раз уж cache содержит все возможные результаты occurs’, можно использовать его для того, чтобы ускорить работу самой функции occurs’:

occurs' [] str = 1 occurs' _ [] = 0 occurs' (p:ps) (c:cs) | p == c = ( occurs ps cs + occurs (p:ps) cs ) `mod` 10000 | otherwise = occurs (p:ps) cs

Таким образом, получаем косвенную рекурсию: функция occurs извлекает значения из cache, куда они попадают в результате вычисления функции occurs’, которая обращается к occurs.

Базой рекурсии являются два первых уравнения функции occurs’ — именно к ним рано или поздно сойдутся все рекурсивные вызовы.

Полностью код, вычисляющий решение поставленной задачи, будет выглядеть так:

solve :: String -> String solve str = printf "%04d" $ occurs pattern str where pattern = "welcome to code jam" occurs :: String -> String -> Int occurs pat str = fromJust $ Map.lookup (pat,str) cache cache :: Map.Map (String, String) Int cache = Map.fromList [ ( (p,s), occurs' p s) | p <- tails pattern , s <- tails str ] occurs' :: String -> String -> Int occurs' [] str = 1 occurs' _ [] = 0 occurs' (p:ps) (c:cs) | p == c = ( occurs ps cs + occurs (p:ps) cs ) `mod` 10000 | otherwise = occurs (p:ps) cs

Обратите внимание, что объявление cache не имеет параметров, а вместо этого обращается к именам str и pattern, определенным в той же самой области видимости (блоке where). Это сделано для того, чтобы вызовы solve с любым значением параметра str использовали один и тот же cache и не создавали его заново каждый раз. Таким образом могут быть ускорены вызовы solve для значений str, содержащих одинаковые подстроки. По той же причине значение pattern не передается параметром в solve, а статически определено локально.

Получается, что значение любого элемента ассоциативного массива cache — это либо 0, либо 1, либо ссылка на другой элемент массива, либо сумма из каких-то двух других элементов массива. Полная схема связей между элементами cache при вычислении occurs "jam" "jjaamm" представлена на рисунке 2. Вычислительная сложность этой реализации — Θ(n2 logn), так как требуется n операций доступа к Map, каждая из которых имеет сложность Θ(n logn).

Рис. 2: Связи между элементами cache при вычислении occurs "jam" "jjaamm"

Подобная техника запоминания («кэширования») результатов работы функции имеет название «мемоизация» и используется не только для реализации задач динамического программирования, но и везде, где происходят регулярные вызовы «тяжелых» функций с одними и теми же аргументами (см. [4], [12], [9]).

В качестве классического примера мемоизации можно привести способ быстрого вычисления чисел Фибоначчи, встречающийся во множестве учебных материалов по Haskell:

fib n = fiblist !! n where fiblist = 1:1:(zipWith (+) fiblist (tail fiblist))

Полный текст программы можно найти в файле memoized.hs в директории welcome_to_code_jam архива с исходными текстами.

В качестве самостоятельного упражнения по дальнейшей оптимизации программы читателю предлагается дописать в определение функции occurs еще одно уравнение, возвращающее 0 в случае, если первый символ шаблона не входит в область поиска.

3  Задача 2: Водосборы

Помимо рекурсивных вычислений (вычисление чисел Фибоначчи, вычисление факториала, решение первой задачи из этой статьи) существует целый класс задач, для решения которых требуется рекурсивное создание какой-либо сложной структуры данных. В качестве примера рассмотрим еще одну задачу из отборочного тура Code Jam 2009.

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

Полностью текст условия доступен на сайте Code Jam.

Все клетки, вода из которых стекает в один и тот же водосток, принадлежат одному бассейну водосбора, и обозначаются одной и той же буквой латинского алфавита. Бассейны водосбора отмечаются буквами, начиная с ’a’, в порядке, в котором они встречаются при просмотре карты сверху вниз, слева направо. Необходимо превратить карту высот в карту бассейнов водосбора, например: 

1 2 3 4 5      a a a a a
2 9 3 9 6      a a b b a
3 3 0 8 7  ->  a b b b a
4 9 8 9 8      a b b b a
5 6 7 8 9      a a a a a

Подобные задачи встречаются в реальной жизни при программировании роботов (отыскание пути при помощи «волнового алгоритма» или карты потенциалов — см. [11]), компьютерных игр (навигация по карте), отыскании оптимального способа выбрать несколько предметов из большого набора (задачи «упаковки рюкзака» и «набора суммы минимальным количеством банкнот»).

Типичным примером подобной задачи будет отыскание пути на доске с квадратными (шестиугольными) клетками из точки A в точку B с минимальными затратами ресурса R, если для всех возможных переходов между клетками карты известно количество ресурса, которое придется израсходовать.

3.1  Наивное решение

Легко видеть, что решение задачи можно разбить на три простых этапа: Для каждой клетки карты определить, в какую сторону с нее стекает вода. В процессе идентифицировать водостоки. Для всех найденных водостоков определить, какие клетки (прямо или косвенно) доставляют в них воду и сгруппировать клетки по этому признаку. Отсортировать группы клеток по координатам самой левой верхней клетки и пометить их буквами.

Поиск клеток, прямо или косвенно доставляющих воду в выбранный водосток, можно производить с помощью одной из разновидностей «волнового алгоритма» (см. [6]). Получается, что для отыскания решения будут выполнены несколько итераций по всем клеткам карты, с просмотром и анализом непосредственных соседей каждой клетки.

На первой итерации будут идентифицированы направления стока воды (обозначенные буквами «n», «w», «e», «s»), а также клетки-водостоки, обозначенные буквой «S»: 

1 2 3 4 5      S w w w w
2 9 3 9 6      n n s w n
3 3 0 8 7  ->  n e S w n
4 9 8 9 8      n n n n n
5 6 7 8 9      n w w w n

На второй — отнесены к тому или иному бассейну водосбора клетки, непосредственно соседствующие с водостоками (цифры обозначают принадлежность к тому или иному бассейну): 

S w w w w      1 1 w w w
n n s w n      1 n 0 w n
n e S w n  ->  n 0 0 0 n
n n n n n      n n 0 n n
n w w w n      n w w w n

На следующей итерации к бассейнам будут присоединены клетки, отстоящие от водостоков на два шага: 

1 1 w w w      1 1 1 w w
1 n 0 w n      1 1 0 0 n
n 0 0 0 n  ->  1 0 0 0 n
n n 0 n n      n 0 0 0 n
n w w w n      n w w w n

И так далее, пока не будут классифицированы все имеющиеся клетки: 

1 1 1 w w      1 1 1 1 w      1 1 1 1 1            1 1 1 1 1
1 1 0 0 n      1 1 0 0 n      1 1 0 0 n            1 1 0 0 1
1 0 0 0 n  ->  1 0 0 0 n  ->  1 0 0 0 n  -> .. ->  1 0 0 0 1
n 0 0 0 n      1 0 0 0 n      1 0 0 0 n            1 0 0 0 1
n w w w n      n w w w n      1 w w w n            1 1 1 1 1

Если реализовывать «волновой алгоритм» нерекурсивно, то количество итераций будет прямо пропорционально размеру самого большого бассейна водосбора. Временная сложность такого наивного решения будет Θ(n4).

А можно ли обойтись всего одной итерацией по карте для того, чтобы сгруппировать все клетки по бассейнам водосбора?

3.2  Решение с одной итерацией и мемоизацией

Итак, мы хотим для каждой клетки карты вычислить координаты ее водостока. Можно сформулировать простой и медленно работающий рекурсивный алгоритм: для данной клетки определить направление стока воды. Далее, определить куда стекает дальше вода на следующем шаге — и так до тех пор, пока мы не дойдем до водостока.

Естественно, что для карты большого размера такое решение будет работать недопустимо медленно. Однако легко видеть, что его можно ускорить при помощи динамического программирования. Достаточно запоминать результаты для всех клеток, которые были пройдены в ходе рекурсивного поиска.

Определим несколько простых типов данных для хранения информации о координатах клеток, карты высот и карты водостоков:

type Coord = (Int,Int) type HeightMap = Array Coord Int type SinkMap = Array Coord Coord

Почему для хранения карты был взят обычный массив (Array), а не ассоциативный (Map)? У Array есть четко определенные границы, которые можно узнать с помощью функции bounds. Если же хранить карту в виде Map, то потребуется отдельно хранить, передавать и обрабатывать информацию о размере — например в виде пары координат левого верхнего и правого нижнего углов ((Int,Int),(Int,Int)).

Реализация описанного алгоритма с использованием динамического программирования будет выглядеть так:

-- Для получения результата необходимо определить водосток -- для каждой клетки карты. Это делается с помощью свертки -- (foldr) списка всех координат (range \$ bounds arr) -- функцией setSink. -- -- Эта функция сохраняет вычисленные координаты водостоков в -- ассоциативном массиве cache, содержимое которого и будет -- результатом свертки и результатом работы функции flow. flow :: HeightMap -> SinkMap flow arr = foldr setSink cache (range $ bounds arr) where nothing = (-1,-1) cache :: SinkMap cache = listArray (bounds arr) (repeat nothing) -- Если для клетки coord водосток уже определен в ходе -- рекурсивного обхода в фукнции findSink, то пропускаем -- эту клетку. Иначе, выполняется поиск водостока при -- помощи findSink, которая вернет список пройденных -- клеток и координаты найденного водостока. Этот -- результат сразу заносится в cache. setSink :: Coord -> SinkMap -> SinkMap setSink coord cache = if cache!coord /= nothing then cache else cache//(findSink coord) -- Если для указанной клетки уже есть закэшированный -- результат, то он сразу возвращается. Иначе, -- исследуется список соседних клеток (neighbors -- coord), имеющих высоту ниже текущей. findSink :: Coord -> [(Coord,Coord)] findSink coord | cache!coord /= nothing = [(coord,cache!coord)] | otherwise = let ns = neighbors coord in if null ns -- Если клеток ниже текущей нет, то текущая клетка -- является водостоком, возвращаются ее координаты then [(coord, coord)] -- Если воде есть, куда течь, то выполняется вызов -- findSink для клетки, в которую стекает вода с -- текущей. Из результатов этого вызова извлекается -- информация о найденном водостоке и подставляется -- в качестве координат водостока для текущей клетки. else let (next:rest) = findSink (snd (minimum ns)) in (coord, snd next):rest -- Функция neighbors возвращает список пар (высота, -- координата) для всех клеток, соседних с указанной. neighbors :: Coord -> [(Int,Coord)] neighbors (x,y) = [ (arr!n, n) | n <- [(x+1, y), (x-1, y), (x, y-1), (x, y+1)] , inRange (bounds arr) n , arr!n < arr!(x, y) ]

Казалось бы, вычислительная сложность этой реализации должна быть Θ(n2). Но сложность функции (//) для стандартного типа Array составляет Θ(m), где m — длина массива. Соответственно, общая временная сложность получается по-прежнему Θ(n4). В Haskell есть изменяемые (англ. mutable) массивы с обновлением элементов за Θ(1), но сравнение различных подходов к реализации массивов на функциональных языках выходит за рамки этой статьи.

В следующем разделе будет показано, как можно упростить приведенное решение и избавиться от необходимости обновлять cache.

Полный текст этой программы можно найти в файле single-pass.hs в директории watersheds архива с исходными текстами.

3.3  Решение без использования cache

Видно, что значения элементов cache вычисляются на основании значений других элементов cache — наподобие того, как это происходило в задаче «Welcome To Code Jam». Однако взаимные рекурсивные обращения друг другу функций setSink, findSink и cache достаточно сложно проследить без детального анализа кода. Можно ли сократить и упростить программу, избавившись от явного упоминания cache — так, чтобы рекурсивная природа setSink и findSink была более очевидна?

Вспомним, что результат flow arr — это свертка исходного массива функцией setSink, при этом суть свертки заключается в том, чтобы породить искомый массив водостоков путем заполнения элементов cache.

Предположим, что мы можем непосредственно вычислить все элементы искомого массива и таким образом исключить создание cache и свертку arr для заполнения cache значениями. Тогда функция flow будет выглядеть так:

flow arr = let result = listArray (bounds arr) [ sink | coord <- range (bounds arr) , let sink = f coord result ] in result

Функция, которой тут дано имя f, должна заменить собой и setSink, и findSink.

Как именно выглядит f, пока не ясно, но можно с уверенностью сказать, что она будет использовать в своих вычислениях result — так как и setSink, и findSink нужны результаты поиска водостоков для соседних с обрабатываемой клеток.

Выясняется, что если использовать данное ранее определение neighbors, то функцию f можно реализовать с помощью одного условного выражения:

flow :: HeightMap -> SinkMap flow arr = -- Результатом работы функции flow будет создаваемый из -- списка значений массив (listArray (bounds arr) [...]), -- в котором каждой клетке исходной карты высот -- поставлены в соответствие координаты ее водостока. let result = listArray (bounds arr) [ sink | coord <- range (bounds arr) , let ns = neighbors coord -- Координаты водостока - это либо координаты самой -- клетки, если у нее нет соседей, ниже ее самой, -- либо координаты водостока той клетки, куда -- стекает вода с текущей. , let sink = if null ns then coord else result ! snd (minimum ns) ] in result where neighbors = ...

Подобный подход используется достаточно часто, и для упрощения написания кода в таком стиле в модуле Data.Function даже определена специальная функция fix с определением:

fix f = let x = f x in x

С ее использованием функция flow может быть переписана так:

import Data.Function (fix) flow :: HeightMap -> SinkMap flow arr = fix attachToSink where attachToSink :: SinkMap -> SinkMap attachToSink result = listArray (bounds arr) [ sink | coord <- range (bounds arr), let ns = neighbors coord, let sink = if null ns then coord else result ! snd (minimum ns) ] neighbors (x,y) = ...

Временная сложность решения составляет Θ(n2).

Посмотрим, как работает это определение flow для простой карты высот из двух элементов: arr = array ((1,1),(1,2)) [20,10]:

-- По определению flow: flow arr = fix attachToSink -- По определению fix: flow arr = let x = attachToSink x in x -- По определению attachToSink: flow arr = let x = listArray ((1,1),(1,2)) [ ... ] in x -- Поскольку 20 > 10, вода из клетки (1,1) будет -- стекать в клетку (1,2): flow arr = let x = listArray ((1,1),(1,2)) [ (x!1,2): ... ] in x -- Поскольку клетка x!(1,2) — водосток: flow arr = let x = listArray ((1,1),(1,2)) [ (x!(1,2)):(1,2) ] in x -- По определению x: flow arr = listArray ((1,1),(2,2)) [ (1,2):(1,2) ]

Странное на первый взгляд имя функции fix объясняется тем, что она является реализацией на Haskell так называемого комбинатора неподвижной точки (см. [3], [2]). Полезные свойства этого комбинатора не исчерпываются упрощением записи рекурсивного кода, однако, всестороннее его описание требует серьезного экскурса в теорию и выходит за рамки данной статьи.

Полный текст программы можно найти в файле with-fix.hs в директории watersheds архива с исходными текстами.

В качестве самостоятельного упражнения читателю предлагается переписать решение первой задачи с использованием fix.

4  Заключение

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

Список литературы

[1]
Divide and conquer. Статья в Wikipedia (en), http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm.
[2]
Fix and recursion. Раздел в Wiki-книге Haskell, http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion.
[3]
Fixed point combinator. Статья в Wikipedia (en), http://en.wikipedia.org/wiki/Fixed_point_combinator.
[4]
Memoization. Статья в Haskell Wiki, http://www.haskell.org/haskellwiki/Memoization.
[5]
Sequence alignment. Статья в Wikipedia (en), http://en.wikipedia.org/wiki/Sequence_alignment.
[6]
Волновой алгоритм. Статья на сайте algolist.manual.ru, http://algolist.manual.ru/maths/graphs/shortpath/wave.php.
[7]
Динамическое программирование. Статья в Wikipedia (ru), http://ru.wikipedia.org/?oldid=18970272.
[8]
Sequence learning - paradigms, algorithms, and applications, 2001.
[9]
Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on Strings. Cambridge University Press, New York, NY, USA, 2007.
[10]
Stephen A. Krawetz and David D. Womble. Introduction to Bioinformatics: A Theoretical and Practical Approach. Humana Press, 2003.
[11]
Roland Siegwart and Illah R. Nourbakhsh. Introduction to Autonomous Mobile Robots. Bradford Book, 2004.
[12]
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы. Построение и анализ. Издание 2-е. Вильямс, 2007.
1
При наличии учетной записи в Google с оригинальным авторским условием можно ознакомиться на сайте Code Jam.
Этот документ был получен из LATEX при помощи HEVEA