Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Саратовский государственный университет им. Н.Г. Чернышевского

Предмет:

Информационные технологии

Файл:

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

.pdf

Скачиваний:

Добавлен:

09.06.2015

Размер:

372.96 Кб

Скачать

☆

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>

Рис. 6: Диаграмма Мура автономного автомата, порождающего начальный отрезок ха-

рактеристической последовательности чисел Фибоначчи

В ходе исследования, для начальных отрезков характеристической последовательности распределения чисел Фибоначчи в натуральном ряду, построены автономные КДА, порождающие эти последовательности. Общий вид диаграммы Мура построенных автоматов представляет собой цепь завершающуюся циклом или петл¼й (Рис. 6). Появление цикла указывает на противоречие возникшее при нахождениии f -представимой последовательности приближения исследуемой иррациональной последовательности.

Построение КДА по f -представлению проводится следующим обра-

çîì:

1.Каждому набору аргументов, на которой определена функция следования, сопоставлялось состояние автомата;

2.Переход из каждого построенного состояния определяется порядком расположения аргументов функции следования в f -представ- ленной последовательности, таким образом определяется функция переходов;

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

Поскольку по приведенная схема построения КДА полностью задает автомат, то f -представимой последовательности однозначно соотвествует

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

Рассмотрим, в качестве примера построение автономного КДА для начального префикса последовательности длины 520. Для f -представле- ния этого отрезка требуется двоичная функция от 144 переменных, определенная только на 288 аргументах из 2144. При этом СДНФ, для доопределенной эффективным для минимизации образом функции, определяется только на двух наборах. Поскольку построение автономного КДА требует в каче- стве состояний полного набора значений аргументов, на которых определена функция следования, то эффективность аналитического задания этой функции не влияет на мощность множества состояний автономного КДА. Таким образом, для найденного f -представления показано эффективное задание функции следования в аналитическом виде. Следовательно, для построения автономного КДА в структурном виде определено эффективное задание комбинационной части, память данного автомата представлена набором аргументов функции комбинационной части, на которых определена соотвествующая f -представляющая функция. В результате показано эффективное задание КДА в структурном виде по начальным отрезкам исследуемой последовательности. По теореме об аналитическом задании характеристи- ческой последовательности распределения чисел Фибоначчи в натуральном ряду, эффективное задание КДА в структурном виде существует для любого отрезка исследумой последовательности.

8Выводы

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

Результатом работы являются:

1.Нахождение свойств характеристического распределения последовательности чисел Фибоначчи в натуральном ряду;

2.Подтверждение гепотезы об f -представимости начальных отрезков исследуемой последовательности длины 24475;

3.Определение закономерностей связи параметров f -представляющих функций исследуемой последовательности;

4.Задание КДА порождающих начальные отрезки приближения исследуемой последовательности.

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

Результат проведенного исследования интересен в плане найденных закономерностей (14) и (15), выступающих в качестве критерия задания функции следования необходимого порядка рекурентности для расматриваемых последовательностей.

При проведении исследования были разработаны и реализованы следующие алгоритмы:

вычисления чисел Фибоначчи заданного номером и неограниченного (кроме как размером памяти) размеронстю числа десятичных знаков;

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

построения и анализа функций двоичной логики на f -представля- ющих префиксах;

построение КДА

Программная реализация задачи представляет собой набор программ и библиотек классов, предназначенных для получения и анализа характеристиче- ской последовательности, f -представляющих функций и автоматов. В разработке определены два типа компонент: бибилиотеки, содержащие реализацию базовых объектов и алгоритмов над ними и утилиты, реализующие непосредственные задачи текущего исследования. Разработка велась под Linux в среде KDevelop 3.0. Для обеспечения целостности взаимодействия отдельных программ и библиотек, созданный набор программных компонент собран в отдельный проект с использованием набора утилит GNU Autotools.

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

[1]Воробьев Н. Н. Числа Фибоначчи. Наука. М., 1978, с. 24-27.

[2]Гилл А. А. Введение в теорию конечных детерминированных автоматов. Наука, М., 1966.

[3]Яблонский С. В. Введение в дискретную математику. Наука, М., 1988.

[4]Богомолов А. М., Твердохлебов В. А. Диагностика сложных систем. УССР "Наукова Думка", Киев, 1974.

[5]Твердохлебов В. А. Универсальные генераторы тестов и системы диагностирования / сб. Техническая диагностика, Ростов на Дону, 1982.

[6]Твердохлебов В. А. Дискретные пространства в задачах управления и диагностирования / изд. Академии Военных Наук, сборник статей, 2003.

[7]Твердохлебов В А. Дискретное пространство для образов поведения конечных автоматов / Теоретические проблемы информатики и ее приложений, Выпуск 5, Изд-во Саратовского университета, 2003, с. 163-175.

[8]Твердохлебов В А., Путятинский С. Е., Ер¼менко Р. Н. Основные свойства геометрических образов автоматов / Проблемы точной механики, сборник научных трудов ИПТМУ РАН, Саратов, 2004, с. 187-196.

[9]Р. Грэхем, Д. Кнут, О. Паташник Конкретная математика. Мир, М., 1998, с. 108-113, 138-147, 266-269.

Приложения

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

111010010000100000001000000000000100000000000000000000100000000000000000000000000

000000001000000000000000000000000000000000000000000000000000000100000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000100000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000001000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000010000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000001000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000010000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

000000000000000000000001000000000000000000000000000000000000000000000000000000000

000000000000000000000000000000000000000000000000000000000000000000000000000000000

Исходные тексты программ

//C++ Implementation: fibfunction

//Description: This program generate n-th Fibonacci number

//by order

//Copyright: See COPYING file that comes with this distribution

#include <iostream> #include <cstdlib> #include <gmpxx.h>

mpz_class makefibonacci(const int n){ if(n < 1)

return 0; mpz_class a, b; a = b = 1;

int i = 1; while(i++ < n){

if(!(i % 10000)) std::cerr << i <<"\r"; mpz_class c = b;

b = a + b; a = c;

}

return b;

}

int main(int argc, char **argv) { int n;

if(argc > 1){

if(((n = atoi(argv[1])) == 0) || (n < 1)){ std::cerr << "error: invalid parameter\n"; return 1;

}

else{

std::cerr << "error: no parameter\n"; return 1;

}

std::cout << makefibonacci(n) << std::endl; return 0;

}

//C++ Implementation: fibnumbers

//Description: This program generate by order n Fibonacci numbers

//from first to n-th

//Copyright: See COPYING file that comes with this distribution

#include <iostream> #include <cstdlib> #include <gmpxx.h> #include <vector>

#define MAXOFNUMBER 2000

void makefibonacci(std::vector<mpz_class> &fnumbers, const int n){ if(n < 1){

fnumbers.clear();

return;

}

fnumbers.resize(n); mpz_class a, b;

a = b = 1; int i = 1;

fnumbers[0] = b;

while(i < fnumbers.size()){ mpz_class c = b;

b = a + b; a = c;

fnumbers[i++] = b;

}

int main(int argc, char **argv) { std::vector<mpz_class> fnumbers; int n;

if(argc > 1){

if(((n = atoi(argv[1])) == 0) || (n < 1)){ std::cerr << "error: invalid parameter\n"; return 1;

}

else

n = MAXOFNUMBER; makefibonacci(fnumbers, n); for(int i = 0; i < n; i++){

std::cout << fnumbers[i] << std::endl;

}

return 0;

}

//C++ Implementation: sequence

//Description: This program generate sequence characteristic

//function of Fibonacci numbers in Natural numbers

//Copyright: See COPYING file that comes with this distribution

#include <iostream>

#include <cstdlib> #include <gmpxx.h>

#define MAXOFNUMBER 38

int main(int argc, char **argv) { mpz_class fib, cur = 0;

int i; if(argc > 1){

if((i = atoi(argv[1])) == 0){

std::cerr << "error: invalid parameter\n"; return 1;

}

else

i = MAXOFNUMBER; while( i-- ){

#ifdef DEBUG

std::cerr << i << std::endl;

#endif

std::cin >> fib; if(!std::cin){

std::cerr << "error: digit incorrect\n"; return 1;

}

if(cur >= fib){

std::cerr << "error: sequence is not increase\n"; return 2;

}

for(;;){

cur++;

if( cur == fib ){ std::cout << '1'; break;

}

std::cout << '0';

}

#ifdef DEBUG std::cerr << cur;

#endif

return 0;

}

#ifndef _AUTOMATE_H #define _AUTOMATE_H

//C++ Interface: Automate

//Description: Finite States Machine Library

//Copyright: See COPYING file that comes with this distribution

#include <exception.h> #include <setstream.h> #include <set> #include <map> #include <vector> #include <utility> #include <iostream>

typedef unsigned int _state_; typedef _state_ State;

typedef unsigned int _input_; typedef _input_ Input;

typedef unsigned int _output_; typedef _output_ Output;

template<class T> class Signals: public std::set<T>{};

typedef std::set<State> States; typedef Signals<Input> Inputs; typedef Signals<Output> Outputs;

class AutomateType{ public:

AutomateType(int state_size, int input_size, int output_size): n(state_size), m(input_size), l(output_size) {}

AutomateType(const AutomateType& t): n(t.n), m(t.m), l(t.l) {}

int n; //число сотояний

int m; //число входных сигналов int l; //число выходных сигналов

friend std::ostream& operator<<(std::ostream& os, AutomateType& t){

os << '(' << t.n << ", " << t.m << ", " << t.l << ')' << std::endl; return os;

}

};

class AbstractAutomate{ public:

virtual State& Delta(const State&, const Input&) = 0; virtual Output& Lambda(const State&, const Input&) = 0; virtual AutomateType Type() = 0;

};

class AbstractAutonomousAutomate: private virtual AbstractAutomate{ public:

virtual State& Gamma(const State& s){ return Delta(s, x); } virtual Output& Mu(const State& s){ return Lambda(s, x); } virtual AutomateType Type() { return Type(); }

private:

static const Input x = 0;

<<< < Предыдущая 1 23 / 53 4 5 > Следующая >>>