computational complexity

The article is devoted to the estimation of computational complexity of a genetic algorithm as one of the key tools for solving optimisation problems. The theoretical aspects of computational complexity of algorithms and the interrelation of elements of a genetic algorithm are considered. The main types of computational complexity of algorithms are described: time, simple and asymptotic. Five basic rules for calculating the asymptotic complexity are given.

Comparative analysis of the effectiveness of monolithic and cyclic noise protective codes built on "Ideal Ring Bundles" (IRBs) as the common theoretical basis for synthesis, researches and application of the codes for improving technical indexes of coding systems with respect to performance, reliability, transformation speed, and security has been realized. IRBs are cyclic sequences of positive integers, which form perfect partitions of a finite interval of integers. Sums of connected IRB elements enumerate the natural integers set exactly R-times.

A model of parallel sorting neural network of discrete-time has been proposed. The model is described by system of difference equations and by step functions. The model is based on simplified neural circuit of discrete-time that identifies maximal/minimal values of input data and is described by difference equation and by step functions. A bound from above on a number of iterations required for reaching convergence of search process to steady state is determined. The model does not need a knowledge of change range of input data.

The methods of improving the cyclic codes efficiency constructed on the basis of combinatorial configurations of the type "ideal ring bundles" (IRB) s by three factors – correction ability, power of coding method and complexity of the decoding procedure are considered. The method is based on the principle of combinatorial optimization, grounded on the algebraic theory of ordered integer sequences with a circular structure, all the numbers, as well as all sums of consecutive numbers exhaust the value sofnatural row numbers.

Using the analogue neural circuit of maximal value signals from signal set identification is proposed for information retrieval in data sets. The circuit is fast, it has simple structure and can be implemented in a modern hardware. A resolution of the circuit is theoretically infinite and it is not dependent on a value of its parameter. An average time necessary for trajectory convergence of the circuit state variable to a steady state is not dependent on a dimension of input data.

The design of mathematical models and corresponding functional block-diagrams of discrete-time neural networks for Internet information retrieval, parallel sorting, and rankorder filtering is proposed. The networks are based on the discrete-time dynamical K-winnerstake-all (KWTA) neural circuits which can identify the K largest from N input signals, where 1£ < K N is a positive integer. Implementation prospects of the networks in an up-to date digital hardware are outlined.

The problem of rank-order filtering is solved on the base of analogue neural circuit which determines maximal value signals among signal set. The filter is described by system of algebra-differential equations and combines such properties as high accuracy and speed, low computational and hardware implementation complexity, and independency on initial conditions. The filter can be used for processing of constant signals, variable signals, and also equal signals. The filter simulation examples confirming theoretical statements are provided.