Multiset rewriting over Fibonacci and Tribonacci numbers

We show how techniques from the formal logic, can be applied directly to the problems studied completely independently in the world of combinatorics, the theory of integer partitions. We characterize equinumerous partition ideals in terms of the minimal elements generating the complementary order filters. Here we apply a general rewriting methodology to the case of filters having overlapping minimal elements. In addition to a ‘bijective proof ’ for Zeckendorf-like theorems – that every positive integer is uniquely representable within the Fibonacci, Tribonacci and k-Bonacci numeration systems, we establish ‘bijective proofs’ for a new series of partition identities related to Fibonacci, Tribonacci and k-step Fibonacci numbers. The main result is proved with the help of a multiset rewriting system such that the system itself and the system consisting of its reverse rewriting rules, both have the Church–Rosser property, which provides an explicit bijection between partitions of two different types (represented by the two normal forms).     

Huffman codes and maximizing properties of Fibonacci numbers

A contrast Huffman code (of maximum length) and the corresponding contrast sequence of positive numbers are considered. A maximizing contrast sequence, the maximum cost of a contrast Huffman code, and their relationship with Fibonacci numbers are derived.Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 10–15, May–June, 1992.     

Robust audio watermarking algorithm based on DWT using Fibonacci numbers

Multimedia Tools and Applications - This paper presents a blind and robust audio watermarking algorithm developed based on Fibonacci numbers properties and the discrete wavelet transform (DWT)...     

Fibonacci Arithmetic Expressions

In this paper, we extend the arithmetic (AR) expressions for functions on finite dyadic groups to functions used in Fibonacci interconnection topologies. We have introduced the Fibonacci-Arithmetic (FibAR) expressions for representation of these functions. We discussed the optimization of FibARs with respect to the number of non-zero coefficients through the Fixed-Polarity FibARs defined by using different polarities for the Fibonacci variables. In this way, we provide a base to extend the application of ARs and related powerful CAD design tools for switching functions to functions in Fibonacci interconnection topologies.     

Extended Fibonacci Cubes

The Fibonacci Cube is an interconnection network that possesses many desirable properties that are important in network design and application. The Fibonacci Cube can efficiently emulate many hypercube algorithms and uses fewer links than the comparable hypercube, while its size does not increase as fast as the hypercube. However, most Fibonacci Cubes (more than 2/3 of all) are not Hamiltonian. In this paper, we propose an Extended Fibonacci Cube (EFC₁) with an even number of nodes. It is defined based on the same sequence F(i)=F(i-1)+F(i-2) as the regular Fibonacci sequence; however, its initial conditions are different. We show that the Extended Fibonacci Cube includes the Fibonacci Cube as a subgraph and maintains its sparsity property. In addition, it is Hamiltonian and is better in emulating other topologies. Specifically, the Extended Fibonacci Cube can embed binary trees more efficiently than the regular Fibonacci Cube and is almost as efficient as the hypercube, even though the Extended Fibonacci Cube is a much sparser network than the hypercube. We also propose a series of Extended Fibonacci Cubes with even number of nodes. Any Extended Fibonacci Cube (EFC_k, with k⩾) in the series contains the node set of any other cube that precedes EFC_k in the series. We show that any Extended Fibonacci Cube maintains virtually all the desirable properties of the Fibonacci Cube. The EFC_ks can be considered as flexible versions of incomplete hypercubes, which eliminates their restriction on the number of nodes, and, thus, makes it possible to construct parallel machines with arbitrary sizes     

斐波那契数列算法动画

算法动画(Algorithm Animation)作为一种可视化工具,以动态交互的图形化方式来形象的表示算法的执行过程.斐波那契数列(Fibonacci sequence)作为一种重要数列,可利用MFC,GDI+等技术,使斐波那契数列以图形、图像元素动态等算法动画的形式表现出来,便于理解.算法动画界面UI设计运用了MF...     

The quantum realization of Arnold and Fibonacci image scrambling

The quantum Fourier transform, the quantum wavelet transform, etc., have been shown to be a powerful tool in developing quantum algorithms. However, in classical computing, there is another kind of transforms, image scrambling, which are as useful as Fourier transform, wavelet transform, etc. The main aim of image scrambling, which is generally used as the preprocessing or postprocessing in the confidentiality storage and transmission, and image information hiding, was to transform a meaningful image into a meaningless or disordered image in order to enhance the image security. In classical image processing, Arnold and Fibonacci image scrambling are often used. In order to realize these two image scrambling in quantum computers, this paper proposes the scrambling quantum circuits based on the flexible representation for quantum images. The circuits take advantage of the plain adder and adder modulo $N$ to factor the classical transformations into basic unitary operators such as Control-NOT gates and Toffoli gates. Theoretical analysis indicates that the network complexity grows linearly with the size of the number to be operated.     

基于斐波那契序列的多播算法

该文提出了一种基于斐波那契序列的多播算法 ,并在 log P模型 [1 ] 下对算法的性能进行了分析 .log P模型是一种广泛使用的并行计算模型 ,它利用 L,o,g,P四个参数来分别表示发送一条消息的等待时间或最大延迟、处理器的开销、源结点发送消息的时间间隔、处理器 /存储器模块数 .在 log P模型下 ,该文所述的基于斐波那契序列的多播算法的时间复杂度为 0 .72 0 2 2· log2 K· (g m ax{ L 2· o,2· g} ) ,而传统的采用均匀二分的多播算法时间复杂度为 log2 K· (L 2· o) ,其中 K为结点数 .当 g 0 .3884· (L 2· o)时 ,基于斐波那契序列的多播算法性能将优于采用均匀二分策略的多播算法 .由于实际情况中 L 2 o g,因此 ,基于斐波那契序列的多播算法性能更优 .实验结果也验证了这一结论     

Fast Recognition of Fibonacci Cubes

Fibonacci cubes are induced subgraphs of hypercubes based on Fibonacci strings. They were introduced to represent interconnection networks as an alternative to the hypercube networks. We derive a characterization of Fibonacci cubes founded on the concept of resonance graphs. The characterization is the basis for an algorithm which recognizes these graphs in O(mlog n) time. A. Vesel supported by the Ministry of Science of Slovenia under the grant 0101-P-297.     

Fibonacci cubes-a new interconnection technology

A novel interconnection topology called the Fibonacci cube is shown to possess attractive recurrent structures in spite of its asymmetric and relatively sparse interconnections. Since it can be embedded as a subgraph in the Boolean cube (hypercube) and it is also a supergraph of other structures, the Fibonacci cube may find applications in fault-tolerant computing. For a graph with N nodes, the diameter, the edge connectivity, and the node connectivity of the Fibonacci cube are in the logarithmic order of N. It is also shown that common system communication primitives can be implemented efficiently     

用Excel公式演示斐波那契数列

介绍了Excel的教学用例及涉及到Excel的公式、函数、自动填充等知识点.     

The structure of subword graphs and suffix trees of Fibonacci words

We use automata-theoretic approach to analyze properties of Fibonacci words. The directed acyclic subword graph (dawg) is a useful deterministic automaton accepting all suffixes of the word. We show that dawg's of Fibonacci words have particularly simple structure. Our main result is a unifying framework for a large collection of relatively simple properties of Fibonacci words. The simple structure of dawgs of Fibonacci words gives in many cases simplified alternative proofs and new interpretation of several well-known properties of Fibonacci words. In particular, the structure of lengths of paths corresponds to a number-theoretic characterization of occurrences of any subword. Using the structural properties of dawg's it can be easily shown that for a string w$w$ we can check if w$w$ is a subword of a Fibonacci word in time O(|w|)$\mathrm{O}(|w|)$ and O(1)$\mathrm{O}(1)$ space. Compact dawg's of Fibonacci words show a very regular structure of their suffix trees and show how the suffix tree for the Fibonacci word grows (extending the leaves in a very simple way) into the suffix tree for the next Fibonacci word.     

On the Complexity of Fibonacci Coding

We show that converting an n-digit number from a binary to Fibonacci representation and backward can be realized by Boolean circuits of complexity O(M(n) log n), where M(n) is the complexity of integer multiplication. For a more general case of r-Fibonacci representations, the obtained complexity estimates are of the form \({2^O}{(\sqrt {\log n} )_n}\).     

Fibonacci mean and golden section mean

In this paper we show that there is a mapping D:M→DM on means such that if M is a Fibonacci mean so is DM, that if M is the harmonic mean, then DM is the arithmetic mean, and if M is a Fibonacci mean, then lim_n→∞DⁿM is the golden section mean.     

The Kolmogorov complexity of real numbers

We consider for a real number α the Kolmogorov complexities of its expansions with respect to different bases. In the paper it is shown that, for usual and self-delimiting Kolmogorov complexity, the complexity of the prefixes of their expansions with respect to different bases r and b are related in a way that depends only on the relative information of one base with respect to the other.More precisely, we show that the complexity of the length l·log_rb prefix of the base r expansion of α is the same (up to an additive constant) as the log_rb-fold complexity of the length l prefix of the base b expansion of α.Then we consider the classes of reals of maximum and minimum complexity. For maximally complex reals we use our result to derive a further complexity theoretic proof for the base independence of the randomness of real numbers.Finally, we consider Liouville numbers as a natural class of low complex real numbers.