Построение и анализ КДА. ДИПЛОМНАЯ РАБОТА

сел Фибоначчи в натуральном ряду = g(1); g(2); : : : ; g(i); : : : содержит не более 5 единиц.

Доказательство. Поскольку каждая единица в последовательностях k îïðå-

деляется числами являющимися членами геометрической прогрессии со зна-

p

менателем a = 1+ 5 , è a5 11; 09 > 10, то не меньше, чем через каждые

2

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

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

Далее в работе проверена гипотеза об f -представимости исследуемой последовательности функциями двоичной логики. Рассматривается f -пред- ставимость функциями двоичной логики с порядком рекурентности до 7000 на начальных префиксах длины до 1000000. Заметим, что длина префикса выбрана из соображений необходимой достаточности для того, чтобы вклю- чить f -представимую последовательность максимальной длины на заданном ограничении порядков рекуррентности. Будем брать подпоследовательности wi = suf i;m( ), первые (m 1) знаков объявляются аргументами, m-й зна- чением функции. В таблицу истинности функции добавляется соответствующая строка. Таким способом весь выбранный префикс просматривается для w0; w1; w2; : : : до первого противоречия, возникающего начиная с префикса некоторой длины, причем такое противоречие будет достигнуто всегда, поскольку такова природа иррациональных чисел их невозможно задать функцией от конечного числа переменных.

Обозначим prf (w) количество знаков, на которое удалось продлить подпоследовательность w функцией следования f . Таким образом на префиксе длины n = m + prf (w0) возникает prf (w0)+1 попарно различных подпоследовательностей длины m, и соответственно префикс suf 0;n( ) является f -представимым функцией двоичной логики от m 1 переменных.

10

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

В таблице 1 представлены результаты исследования:

Таблица 1: Зависимость параметров f -представления от порядка рекуррентности

Где m это порядок рекурентности функции, r число аргументов на которых функция определена, n длина f -представимой подпоследовательности, prf (w) количество знаков, на которое можно продлить подпоследовательность w = suf 0;r+1( ). Порядки рекурентности, на которых происходит увеличение длины подпоследовательности выделены жирным шрифтом.

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

Теорема об аналитическом задании характеристической последовательности распределения чисел Фибоначчи в натуральном ряду.

Для любого начального отрезка n = suf0;n( ) последовательностисовершенная дизъюнктивная нормальная форма (СДНФ) f -представляю- щей функции определяется не более чем на 5dlog10 ne числе наборов.

11

Доказательство. Поскольку в начальный отрезок n войдет не более dlog10 ne подпоследовательностей g(10k); : : : ; g(10k+1 1), где k = 0; n, в каждой из которых, по теореме о числе единичных элементов характеристической последовательности чисел Фибоначчи, найдется не более 5 единиц. Следовательно, в СДНФ войдет не более 5dlog10 ne наборов.

Таблица 2: Функция f1, заданная по начальному отрезку 1

В качестве примера, рассмотрим начальный отрезок последовательности длины 28 (начальный отрезок длины 4000 привед¼н в приложении), который имеет следующий вид:

1 = 1110100100001000000010000000

Последовательность 1 f -определима функцией f1, которая приведена в таблице 2. Функция f1 при е¼ доопределении эффективным для мини-

= x1 & x2 & x3 & x5 & x6 & x7 & x8

12

Таким образом, функция от шести переменных минимизирована до одного неполного набора.

Следовательно, в соответствии с теоремой об аналитическом задании характеристической последовательности распределения чисел Фибонач- чи в натуральном ряду, показана эффективность минимизации функций f - представляющих исследуемую последовательность на большом числе переменных.

13

6Исследование зависимостей параметров f -представи- мости характеристической последовательности чисел Фибоначчи

Для построенного начального отрезка длины 24475 последовательности характеристической функции распределения чисел Фибоначчи в натуральном ряду были решены следующие вопросы:

1.Для каждого порядка рекуррентности f -представляющей функции от 1 до 6765 найдены представления начальных отрезков последовательности. Результаты представлены в таблице 1

2.Для каждой из f -представляющих функций указанных в пункте 1, определено число наборов значений переменных, на которых функция задана. Результаты приведены в таблице 1

3.Для каждого начального отрезка длины от 2 до 5000 определена f -представляющая его функция с минимальным порядком рекуррентности и числа наборов, на которых она определена. Результаты приведены на графике представленном на рисунке 5.

На рисунках 3 и 4 представлены графики, на которых даны общие характеристики отношений порядка рекуррентности f -представимой функции к длине f -представимого отрезка и к числу наборов, на которых определена эта функция.

На первом графике четко прослеживается ступенчатая динамика изменения числа наборов, на которых определена функция следования от порядка рекурентности. Обозначим rm число наборов, на которых определена функция следования с порядком рекурентности m. Во время исследования была замечена следующая закономерность. Длина f -представимой подпоследовательности, в зависимости от числа переменных, растет скачками. То есть в некоторых случаях, с увеличением числа переменных, длина f - представимого префикса не увеличивается. Причем, при последовательном увеличении порядка рекурентности, скачки возникают тогда, когда это число становится равным очередному числу Фибоначчи, при этом число ар-

14

r=m

2

1.5

1

0.7

0.5

m

Рис. 3: График зависимости отношения порядка рекуррентности f -представимой функ-

ции к числу наборов от порядка рекуррентности

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

Эта закономерность представляет собой интерес в качестве критерия задания функции следования необходимого порядка рекуррентности для последовательностей заданного вида.

n=m

0.7

0.6

0.5

0.4

0.3

m

Рис. 4: График зависимости отношения порядка рекуррентности f -представимой функции к длине f -представимого отрезка от порядка рекуррентности

15

Аналогично числу наборов относительно порядков рекуррентности, длина f -представимого отрезка также изменяется скачками на значениях соответствующих числам Фибоначчи. Но в отличае от числа наборов, относительная, от порядка рекуррентонсти, величина длин f -представимых отрезков постепенно растет.

mnnrn

500 rn

20

10

5

2

1

n

Рис. 5: График зависимости минимального порядка рекуррентности и числа наборов, на

которых определена функция следования, для f -представимого отрезка от его длины

На рисунке 5 представлена зависимость минимального порядка рекуррентности f -представимого отрезка и числа наборов, на которых определена функция следования, от его длины. Ступенчатый переход к большим порядкам рекуррентности, необходимый для f -представления начальных отрезков большей длины, определяется, в соответствии со следующей закономерностью:

где n это длина начального отрезка, на котором происходит переход к новому значению порядка рекуррентности необходимому для его f -пред- ставления, rn число наборов, на которых определена функция следования, mn новое значение порядка рекуррентности равного очередному значению числа Фибоначчи.

В найденных закономерностях (14) и (15) проявляются следующие особенности f -представления исследуемой последовательности:

16

Для начальных отрезков характеристической последовательности чисел Фибоначчи увеличение значений порядков рекуррентности, относительно их длины, определяет переход к f -представлению на- чального отрезка с минимальным числом наборов, на которых определена функция следования, для данного порядка рекуррентности;

Для начальных отрезков характеристической последовательности чисел Фибоначчи увеличение значений длин, относительно минимальных порядков рекуррентности соответствующих f -представ- ляющим их функциям, определяют переход к f -представлению на- чального отрезка с максимальным числом наборов, на которых определена функция следования, для данного порядка рекуррентности.

17

7Представление иррациональных последовательностей конечными детерминированными автоматами

Анализ функционирования КДА, поведение которых задается некоторой характеристической функцией иррациональной последовательности представляет особый интерес. Последовательности длинных неповторяющихся знаков частое явление при анализе явлений природы, например, последовательности генов человека, насчитывающих, при текущем их кодировании, до тр¼хсот тысяч знаков, сложные физические, химические, органические структуры. С подобного рода последовательностями встречаются в различ- ных отраслях знаний химия, биология, геология, медицина и др. При этом за каждым иррациональным числом стоит континуум иррациональных чи- сел. Для иллюстрации этого факта можно изменить любой знак в записи иррационального числа. Полученное число также будет иррациональным. Таким образом работая с одним числом, фактически, получается оперировать с континуальным множеством.

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

Последовательности (5) и (6) при t > jSj являются периодическими, а при Y = f0; 1g соответствуют характеристическим последовательностям. Это позволяет конечные детерминированные автоматы ассоциировать с приближенным представлением иррациональных последовательностей. В процессе анализа задачи была сформулирована следующая теорема.

Теорема. О представлении иррационального числа конечным детерминированным автоматом.

Представление иррационального числа конечным детерминирован-

18

ным автоматом потребуется бесконечного множества состояний. Доказательство. Согласно основному свойству иррационального числа (отсутствие циклов), для получения каждого следующего знака необходимо знать все предыдущие знаки, т.е. необходима постоянно увеличивающаяся память. Следовательно, требуется бесконечный объем памяти, а, соответсвенно, бесконечное число состояний автомата.

В данном случае исследовалась следующая возможность построения КДА из ранее полученных f -представляющих функций. Рассматривалось построение автономного автомата A = (fs1; s2; : : : ; skg; f0; 1g; ; ) определяющего соответствующую функцию, таким образом что на каждом шаге функционирования на выходе строилась последовательность f -представимая исходной функцией. Функцию (7), в этом случае, можно задавать аналити- чески в выбранном базисе функции. Предлагается другой способ задания функции. Имеет место теорема [8]:

Теорема. Пусть:

1) последовательности (a11; a12; : : : ; a1!1 ), (a21; a22; : : : ; a2!1 ), . . . ,

(a 1; a 2; : : : ; a ! ), ãäå !j > m, 1 6 j 6 являются f -представимыми функцией k-значной логики f (z1; z2; : : : ; zm), m > 2.

2) каждый упорядоченный набор значений аргументов функции f является подпоследовательностью по крайней мере одной из указанных последовательностей.

Тогда:

1) существует конечный ориентированный граф G = (W; ), где W W и отображение вида ' : W ! f0; 1; : : : ; k 1g, такое, что для каждого пути длины m+1 (wi1 ; wi2 ; : : : wim+1 ) в графе G выполняется равенство '(wim+1 ) = f (wi1 ; wi2 ; : : : ; wim )

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

Теорема показывает, что структура диаграммы Мура автономного автомата и графа, в котором совмещаются f -представимые последовательности, совпадают. Это позволяет иррациональные последовательности приближать последовательностями автономных автоматов.

19