?

Log in

No account? Create an account

Previous Entry | Next Entry

Интересный вопрос, на который я не смог ответить, обсуждая одну задачу (задание 1. 19 из sicp) с учеником. Пресловутый «детский вопрос». Впрочем, начнем по порядку.

Как вы помните, числа Фибоначчи определяются через суммирование предыдущих членов в ряду: каждое число равно сумме двух предыдущих, а первые два равны 1. Таким образом, получается ряд натуральных чисел { 1; 1; 2; 3; 5; 8; 13; 21; … }. Обозначим n-ный член этого ряда через F(n). Мы можем определить рекуррентную формулу для F(n):

F(n) = F(n − 1) + F(n − 2)
F(1) = F(2) = 1

Попытка применить эту формулу для практического вычисления неэффективна до нелепости: например, чтобы вычислить F(5), мы сначала вычислим F(4) и F(3), a вычисляя F(4), мы должны вычислить F(3) и F(2). F(3) уже вычисляется дважды. Легко видеть, что при вычислении для больших n число повторов растет, будто лавина.

Естественно упростить вычисление, двигаясь от начала ряда. Если мы каждый раз будем помнить только 2 числа в их порядке, по ним мы можем вычислить третье, «забыть» первое — оно больше не нужно — и повторять эту операцию с оставшимися двумя, пока не сделаем нужного числа шагов. Этот метод гарантирует вычисление F(n) за число шагов n−2, то есть, как об этом говорится, порядка n, и общепринято записывается как O(n).

Новое рекуррентное соотношение для F потребует введения вспомогательной функции, которая будет «помнить» два числа в своих аргументах. Третий аргумент нужен только, чтобы завершить вычисления, не забыть, где нам остановиться, идя вдоль ряда Фибоначчи: он задает число оставшихся шагов:



А теперь приходит добрый волшебник Хэл Абельсон и говорит: я знаю, как значительно ускорить это вычисление! Можно модифицировать алгоритм, чтобы «перескакивать» в ряду шагами, кратными 2n. Тут он достает из широких В условии задачи приводится отображение

ψ (p, q) (a, b) → ψ (p, q) ((a + b)p + aq, ap + bq)

Хорошо видно, что

φ = ψ (1, 0)

Теперь аналитически применим функцию ψ дважды к данным a и b



Обратите внимание, что форма этого выражения соответствует однократному применению ψ, но только с иными значениями p и q:

pp² + 2pq
qp² + q²

Таким образом, рекуррентная самотождественность ψ сохранилась, и мы можем удваивать наши шаги каждый раз, когда обнаружим, что до нашего F(n) их остается четное число: просто заменим p и q на новые, соответствующие двойному шагу, и при этом вдвое уменьшим число оставшихся шагов. Полное решение можно записать так:



Очевидно, что перед каждым удвоенным шагом мы будем делать не более одного неудвоенного, так что число шагов будет падать вдвое на каждые не более двух сделанных, так что новый алгоритм вычисляет F(n) за логарифмическое число шагов O(log n).

А вот и детский вопрос, поставивший меня в тупик: как именно добрый волшебник Хэл Абельсон пришел именно к такой форме функции ψ? Признаюсь, я с размаху сел в лужу. Давайте меня коллективно из нее доставать. Как определить, что для данного рекуррентного отношения существует самоподобное решение для перепрыгивания через 2 или несколько шагов? И, конструктивно, — как его отыскать?

___________________________
LaTeX to image conversion
CodeCogs - An Open Source Scientific Library

Tags:

Comments

Anatoly Borodin
Jul. 10th, 2011 10:34 pm (UTC)
Не совсем так. Следующий член ряда должен линейно, с постоянными коэффициентами зависеть от предыдущих членов. Тогда можно построить соответствующую матрицу A, и ассоциативность будет уже в A^(n-1).
aamonster
Jul. 11th, 2011 06:08 am (UTC)
Переход не обязан описываться именно матрицей - можно обобщить.
Т.е. для ряда a[0], a[1], ... (для чисел фибоначчи член ряда - вектор из двух чисел) и функции f:
a[n+1] = f(a[n]) должна быть определена операция "умножения" <*> такая, что:
(f <*> g) a = f(g(a))
(f <*> g) <*> h = f <*> (g <*> h)
Ну и нужна "единица" I
f <*> I = I <*> f = f

Примеры:
a[0] = ""
a[n+1] = a[n] ++ "!"
(++ - операция слияния строк)

a[0] = 1
a[n+1] = a[n]+1 (случай, не описывающийся матрицей, хе-хе)

a[0] = 1
a[n+1] = a[n]*2

Хотя я не все требуемые условия выписал... Еще "произведение" функций должно эффективно вычисляться - так что мой первый пример, скорее всего, не проходит.
Anatoly Borodin
Jul. 11th, 2011 11:55 am (UTC)
Композиция уже ассоциативна :)

Для любой последовательности a_n = (f ^ (n - 1)) (a_1), вопрос в том, для каких f можно эффективно вычислять степени.

Ещё есть фокус через изоморфизм:
g = (h^-1) . f . h
(h^-1) . a_n . h = (g ^ (n - 1)) ((h^-1) . a_1 . h)

Так вычисление чисел Фибоначчи сводится к возведению в степень диагональной матрицы с собственными значениями (1 ± sqrt 5) / 2

> a[n+1] = a[n]+1 (случай, не описывающийся матрицей, хе-хе)

Ну матрицей и вектором, беда какая :)

> Еще "произведение" функций должно эффективно вычисляться

Собственно.