Фибоначчиевые алгоритмы измерения

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

Возвратимся снова к математической модели измерения, основанной на "индикаторных элементах", и попытаемся ввести в эту модель "Принцип Асимметрии Измерения", сформулированный выше. Из этого принципа вытекает следующее "ограничение" на движение ИЭ вдоль отрезка AB. Пусть ИЭ приложен к точке C (Рис. 1) на первом шаге n-шагового алгоритма измерения.

Первый шаг 'фибоначчиевого' алгоритма измерения
Рисунок 1. Первый шаг "фибоначчиевого" алгоритма измерения.

Тогда может возникнуть две ситуации (a) и (b), показанные на Рис.1. Ясно, что в ситуации на Рис.1-a мы можем прикладывать ИЭ к некоторой точке отрезка CB уже на следующем шаге. Однако для ситуации на Рис.1-b мы не имеем права прикладывать ИЭ к точкам отрезка AC, потому что рычажные весы, которую в нашей модели заменяет "Индикаторный элемент", должны возвратиться в исходное положение в течение p единиц дискретного времени. Таким образом, ограничение S, вытекающие из "Принципа Асимметрии Измерения", состоит в том, что для ситуации на Рис.1-b запрещено прикладывать ИЭ к точкам отрезка AC в течение p последующих шагов алгоритма.

И снова мы не хотели бы утомлять наших читателей тонкостями математических рассуждений и приводим окончательный результат. Доказано, что для заданного p (p = 0, 1, 2, 3, ...) функция "эффективности" Fp(n) выражается следующим рекуррентным соотношением:

(1)

Рассмотрим некоторые специальные случаи формулы (1). Пусть p = 0. Для этого случая формула (1) сводится к следующему:

F0(n) = 2 F0(n - 1);(2)
F0(0) = 1.(3)

Ясно, что рекуррентная формула (2) с учетом начальных условий (3) "порождает" двоичную последовательность:

1, 2, 4, 8, 16, ... , F0(n) = 2n-1.

Алгоритм измерения, соответствующий этому случаю, сводится к классическому "двоичному" алгоритму измерения.

Пусть p = ¥. Для выше сформулированной задачи это означает, что ИЭ "выходят из игры", как только они оказываются справа от точки X. Для этого случая формула (1) принимает форму Fp(n) = n + 1, что соответствует классическому "алгоритму счета".

Рассмотрим теперь случай p = 1. Для этого случая рекуррентная формула (1) принимает следующий вид:

F1(n) = F1(n - 1) + F1(n - 2) для n > 2;(4)
F1(1) = 2, F1(2) = 3.(5)

Если теперь вычислить функцию "эффективности" F1(n) согласно (4), (5), то получим следующую числовую последовательность: 2, 3, 5, 8, 13, 21, 34, ..., которая представляет собой ни что иное, как ряд Фибоначчи! Именно этот факт стал причиной, почему рассматриваемые алгоритмы измерения были названы "фибоначчиевыми" алгоритмами измерения.

В Таблице 1 заданы значения функции "эффективности" Fp(n) оптимальных "фибоначчиевых" алгоритмов для различных значений p.

Таблица 1.

n123456789
F0(n)248163264128256512
F1(n)23581321345589
F2(n)2346913192841
F3(n)2345710141926
..............................
F¥(n)2345678910

А теперь перейдем к системе гирь для "фибоначчиевых" алгоритмов измерения. Доказано, что для этого случая "оптимальная" система гирь Wp(n) задается следующей формулой:

Wp(n) = Wp(n - 1) + Wp(n - p - 1) для n > p + 1;(6)
Wp(1) = Wp(2) = ... = Wp(p + 1) = 1.(7)

Таблица 2 задает различные варианты "оптимальных" систем гирь, соответствующих различным значениям p.

Таблица 2.

n123456789
W0(n)1248163264128256
W1(n)112358132134
W2(n)1112346913
W3(n)111123457
..............................
W¥(n)111111111

Анализ выражений (6), (7) и Таблицы 2 показывает, что числа Wp(n) совпадают с обобщенными числами Фибоначчи или p-числами Фибоначчи, которые мы обнаружили при исследовании Треугольника Паскаля, в частности, с классическим числами Фибоначчи для случая p = 1.

Рассмотрим теперь пример "оптимального" "фибоначчиевого" алгоритма, задаваемого выражением (1). Пусть p = 1 и n = 5. Рассмотрим 5-шаговый "фибоначчивый" алгоритм (Рис.2), соответствующий этому случаю.

'Оптимальный' фибоначчиевый алгоритм
Рисунок 2. "Оптимальный" фибоначчиевый алгоритм.

Из Табл. 1 вытекает, что рассмотренный выше 5-шаговый "фибоначчиевый" алгоритм разделяет исходный отрезок [0,13] на 13 равных частей. Чтобы реализовать такой алгоритм нам необходимо иметь 5 гирь, которые согласно Табл. 2 имеют следующие значения: 1, 1, 2, 3, 5.

Рассмотрим первые три шага "фибоначчиевого" алгоритма:

Первый шаг состоит в приложении ИЭ к точке 5 отрезка [0, 13] (Рис. 2). Можно видеть, что первый шаг состоит в разделении отрезка [0, 13] в "фибоначчиевом" отношении: 13 = 5 + 8. Тогда возникает 2 ситуации (a) и (b) после первого шага.

Второй шаг.

  1. Для этой ситуации мы используем следующую гирю 3 и разделим отрезок [5, 13] ИЭ в фибоначчиевом отношении: 8 = 3 + 5. Возникает две новые ситуации (c) и (d) после второго шага.
  2. Для этой ситуации второй шаг является "пустым", так как согласно "ограничению" S запрещено прикладывать ИЭ к точкам отрезка [0, 5] на втором шаге.

Третий шаг.

  1. В этой ситуации мы используем следующую гирю 2 и разделяем отрезок [8, 13] с помощью ИЭ в "фибоначчиевом" отношении: 5 = 2 + 3. Тогда возникает две новых ситуации (f) и (g) после третьего шага.
  2. Мы можем возвратиться к ситуации (b) на 3-м шаге. В соответствии с "ограничением" S мы можем прикладывать ИЭ к точкам отрезка [0, 5] на третьем шаге. Мы можем использовать гирю 2 и разделить отрезок [0, 5] с помощью ИЭ в "фибоначчиевом" отношении: 5 = 2 + 3. Тогда возникают две новые ситуации (h) и (i) после третьего шага.

Очень просто проследить действие "фибоначчиевого" алгоритма и на следующих двух шагах.

Можно усмотреть из этого примера, что сущность "фибоначчиевого" алгоритма измерения состоит в разделении "интервала неопределенности", полученного на предыдущем шаге в "фибоначчиевом" отношении. Очень просто доказать, что это - общий принцип, который действует для любого значения p. При этом деление "интервала неопределенности" осуществляется согласно рекуррентному соотношению для p-чисел Фибоначчи.

И сейчас мы имеем право восторгаться мощностью и логикой математического исследования. Когда мы начинали разрабатывать нашу "алгоритмическую теорию измерения", мы не делали никаких предположений относительно выражения для функции "эффективности". И мы неожиданно пришли к числам Фибоначчи! Как известно, Фибоначчи открыл свои знаменитые числа при решении задачи о "размножении кроликов". Но мы обнаружили числа Фибоначчи в другой задаче Фибоначчи, "задаче о гирях"!

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

Итальянский математик Леонардо Пизано Фибоначчи стал известным благодаря двум математическим задачам, а именно "задаче о гирях", которая является первой оптимизационной задачей в теории измерения, и "задаче о размножении кроликов", которая дала науке числа Фибоначчи. "Принцип Асимметрии Измерения", использованный украинским ученым А.П. Стаховым в "задаче о гирях", поставил обе задачи Фибоначчи на одну математическую основу, которой являются числа Фибоначчи! В этом и состоит первый неожиданный результат, вытекающий из "алгоритмической теории измерения"! Но на этом неожиданные результаты "алгоритмической теории измерения" не заканчиваются. И мы расскажем об этом на следующих страницах нашего Музея. Следуйте за нами!