Ýâðèñòè÷åñêèå àëãîðèòìû è ðàñïðåäåë¸ííûå âû÷èñëåíèÿ - ñòðàíèöà íà àíãëèéñêîì ÿçûêå

Scientific journal “Heuristic algorithms and distributed computing”

Home

General information

The journal covers the following topics: “Mathematical Modeling”, “Algorithms and Heuristics”, “Applied Discrete Mathematics and Automata Theory”, “Parallel and Distributed Computing”. Material of all articles is directly or indirectly connected with the subject of the journal (i.e., distributed implementation of algorithms and heuristics).

Editorial board (emails: earv@samsu.ru, earv-samara@yandex.ru):

Juraj HROMKOVIČ – honorary editor
Switzerland, Zürich, Eidgenössische Technische Hochschule, Professor

Boris MELNIKOV – editor-in-chief (email: bormel@rambler.ru)
Russia, Samara State University, Professor

Alexander KRUTOV – vice-editor-in-chief
Russia, Samara State University, Professor

Shamil ISHMUKHAMETOV
Russia, Kazan (Volga Region) Federal University, Professor

Sergey NOVIKOV
Russia, Samara State University, Professor

Sergo REKHVIASHVILI
Russia, Nalchik, Institute of Applied Mathematics and Automation, Professor

Yuri SMIRNOV
Russia, Penza State University, Professor

Andrey SOKOLOV
Russia, Petrozavodsk, Karelian Research Centre of Russian Academy of Sciences, Professor

Sergey SOLOVYEV
Russia, Moscow State Lomonosov University, Professor

Yuri TYUTYUNOV
Russia, South Research Centre of Russian Academy of Sciences, Professor

Russia, South Federal University, Professor

Alessandra CHERUBINI
Italy, Milano, Politecnico di Milano, Professor

Antal Miklós IVÁNYI
Hungary, Budapest, Eötvös Loránd Tudományegyetem, Professor

Zoltán KÁSA
Romania, Târgu Mureş, Universitatea Sapientia, Professor

Jörg KELLER
Germany, Hagen, Fernuniversität in Hagen, Professor

India, Srinagar, University of Kashmir, Professor

Ukraine, Cherkassy, Technological University, Professor

SHI-JINN HORNG
Republic of China, Taipei, National Taiwan University of Science and Technology, Professor

Sergey MAKARKIN – executive secretary
Russia, Samara State University, Associate Professor

Abstracts and references of the papers

Vol. 1, No. 1 (2014) p.p. 6–15
A. S. Andreev, O. A. Peregudova, K. V. Pahomov (Ulyanovsk State University)
emails: AndreevAS@ulsu.ru, peregudovaoa@gmail.com, pahomovkv@yandex.ru
Modeling of controlled motion of three-wheeled robot with two degrees of freedom
In the paper on the example of construction of a stabilizing motion control of three-wheeled mobile robot with two degrees of freedom is justified technique for solving the problem of stabilization of nonlinear time-varying systems with piecewise constant control on the basis of a sampling system and application of backstepping method. This method is based on the representation of the entire system as a cascade connection of subsystems and synthesis of nonlinear control law on the basis of constructing of Lyapunov functions for each subsystem. Efficient construction of the control law is that, firstly, it is applicable for a wide class of program motions, secondly, is easily implemented in software, thirdly, allows to determine for each case the most appropriate set of control parameters. The novelty of this technique is the use of Lyapunov functions of the form of vector norms and difference comparison equations, effective in constructing of laws of discrete controls for considered systems with higher speed of convergence, the expansion of the domain of attraction of solutions, simplifying the control structure in comparison with known results. We consider electromechanical model of a mobile robot moving on a horizontal surface without slipping, with two rear wheels are controlled by two independent DC electric, and front roal wheel. On the problem of synthesis of a piecewise constant control of a continuous system there is used an approach based on sampling systems with use of Euler approximation and construction of stabilizing discrete control laws for discrete model. On the basis of the recurrent procedure of backstepping method consisting in the transition from the control synthesis problem for the kinematic model to the problem of constructing controlling signals for dynamic model of the robot found a piecewise constant control law that practically stabilizes the set of unsteady motion of the robot. There are present the results of numerical simulations, confirming the effectiveness of the proposed control law.
Keywords and phrases: stabilization; wheeled mobile robot; Lyapunov function; method of backstepping.
References.
1. Yu. G. Martynenko. Motion control of mobile wheeled robots // Journal of Mathematical Sciences. – Vol. 147, No. 2, 2007. – P. 6569-6606.
2. P. V. Kokotovic. The joy of feedback: Nonlinear and adaptive // IEEE Control Systems Magazine. – Vol. 12, 1992. – P.7-17.
3. P. V. Kokotovic, M. Arcak. Constructive nonlinear control: a historical perspective // Automatica. – Vol. 37, 2001. – P.637-662.
4. H. K. Khalil. Nonlinear Systems. 3rd ed. – Upper Saddle River, N. J.: Prentice Hall, 2002. – 750 p.
5. D. Nesic, A. R. Teel. Stabilization of sampled-data nonlinear systems via backstepping on their Euler approximate model // Automatica. – Vol. 42, 2006. – P.1801-1808.

Vol. 1, No. 1 (2014) p.p. 16–24
O. I. Gorbaneva, G. A. Ougolnitsky (Southern Federal University)
emails: gorbaneva@mail.ru, ougoln@mail.ru
Resource allocation game-theoretical models of river water quality control with corruption. Part I
A resource allocation problem in hierarchical water quality control systems is considered. This problem is decomposed in two subproblems: a resource allocation problem in the hierarchical system and a river water quality control problem. Both problems are solved by finding the Stackelberg equilibrium. When the resource allocation problem is solved, the presence of two corruption mechanisms is taken into account: those assigned with resource allocation value and with resource use check value. In each case “hard” and “soft” corruption is considered. Introduction of corruption factor means that Agent gives some resource share as a bribe to Principal. The aim of giving bribe for Agent is to get any benefits from Principal. The problem is also considered by means of cooperative game theory. For all coalitions the payoffs and cooperative effects, Shapley and proportional values are found. The river water control problem is solved in three cases. In the first case the quantity of pollutant dropped into wastewater by Agent is less than the first threshold. In this case there is the only Agent's task, and Ecological Center doesn't take part in the game. In the second case the pollutant quantity dropped into wastewater by Agent is greater than the first threshold but less than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold. In the third case the pollutant quantity dropped into wastewater by Agent is greater than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold and charges another penalty for every dropped pollutant unit which is over the second threshold.
Keywords and phrases: resource allocation problem; water resource quality control; connivance; extortion; hierarchical control system.
References.
1. O. I. Gorbaneva. Kooperativno-igrovoe modelirovanie raspredeleniya resursov // Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki. Prilozhenie. – T. 2, 2006. – S. 10-16.
2. O. I. Gorbaneva. Modelirovanie raspredeleniya resursov kak igry v normal'noy forme // Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki. Prilozhenie – T. 2, 2006. – S. 16-22.
3. A. F. Kononenko. Teoretiko-igrovoy analiz dvukhurovnevoy ierarkhicheskoy sistemy upravleniya // Vychisl. matem. i matem. Fiz. – T. 5, 1974. – S. 1161-1170.
4. A. F. Kononenko. Teoriya igr i ierarkhicheskie struktury // Planirovanie i upravlenie ekonomicheskimi celenapravlennymi sistemami. – 1974. – S. 63-72.
5. J. von Neumann, O. Morgenstern. Theory of Games and Economic Behavior. – Princeton University Press, 1944.
6. G. A. Ougolnitsky. Teoretiko-igrovye principy optimal'nosti ierarkhicheskogo upravleniya ustoychivym razvitiem // Izvestiya RAN. Teoriya i sistemy upravleniya. – T. 4 (2005). – S. 72-78.
7. G. Ougolnitsky. Sustainable Management. – N. Y.: Nova Science Publ., 2011.

Vol. 1, No. 1 (2014) p.p. 25–39
A. V. Nagornov, A. V. Kats (Togliatti State University)
emails: nagornovys@yandex.ru, elfsage@mail.ru
About molecular dynamics method with parametrically temperature-dependent potential
The article examines a new approach to the choice of interatomic interaction forces in the simulation of condensed media by the method of molecular dynamics, based on selection of the pair potential in the form of slightly varying function of temperature. Method of classical molecular dynamics is based on the equations of classical mechanics, numerical methods of ab initio are based on the equations of quantum mechanics. Quantum molecular dynamics holds equations of the classical mechanics for atoms and quantum mechanics for electrons. The proposed method of molecular dynamics with temperature-dependent potential is based on the quasi-classical approximation, and is a modified method of classical molecular dynamics. Quantum-mechanical accom-identification of the proposed method is based on Ehrenfest theorem and quan-tum equations of Newton. To confirm the efficiency of the method of molecular dynam-ics with temperature-dependent potential the calculations of thermodynamic parameters of stoichiometric uranium dioxide are carried out. Uranium dioxide was chosen as a model material with high melting temperature (3120K) that allowed demonstrating the advantages of quasi-classical approach in comparison with classical mechanics.
Comparison of results with the use of temperature-dependent potential Born-Mayer with the calculations of other authors shows big gains in accuracy at low temperatures to 1100Ê. However, of special interest over a wide temperature range (up to 3120K), in which the benefits of calculations in the framework of the proposed approach becomes especially noticeable. In the work the calculations of the lattice constant, enthalpy, heat capacity at constant volume and pressure, as well as the ratio of heat capacities was carried out. The coincidence of calculations with the experimental data for all the considered temperature is not more than 0.5% while the potentials excluding temperature changes in the crystal gives a divergence with the experimental data from 2%, increasing with temperature up to 90%.

Keywords and phrases: FIFO-queues; random walks; Markov chains; optimal dynamic data structures.
References.
1. H. Wennerstrom, J. Daicic, B. W. Ninham. Temperature dependence of atom-atom interactions // Physical Review A. – Vol. 60, 1999. – P.2581-2584.
2. S. Khakshouri, D. Alfe, D. M. Duffy. Development of an electron-temperature-dependent interatomic potential for molecular dynamics simulation of tungsten under electronic excitation // Physical Review B. Vol. 78, 2008. – P.224304:1-11.
3. A. K. Subramaniyan, C. T. Sun. Engineering molecular mechanics: an efficient static high temperature molecular simulation technique // Nanotechnology. Vol. 19, 2008. – P.285706:1-5.
4. V. S. Guthikonda, R. S. Elliott. An Effective Interaction Potential Model for the Shape Memory Alloy AuCd // Continuum Mechanics and Thermodynamics. Vol. 21(4), 2009. – P.269-295.
5. D. I. Blokhincev. Osnovy kvantovoy mekhaniki. – M.: Nauka, 1976. – 664 s.
6. A. Yariv. Vvedenie v teoriyu i prilozheniya kvantovoy mekhaniki. – M.: Mir, 1986. – 360 s.
7. K. Govers, S. Lemehov, M. Hou, M. Verwerft. Comparison of interatomic poten-tials for UO2. Part I: Static calculations // J. Nuclear Materials. Vol. 366, 2007. – P.161–177.
8. H.Gould, J.Tobochnik, W.Christian. Introduction to Computer Simulation Meth-ods: Applications to Physical Systems, 3rd ed. – Addison-Wesley (2006). – 720 p.
9. S. Yamasaki, T. Arima, K. Idemitsu and others. Evalution of Thermal Conductivi-ty Hyperstoihiometric UO2+x by Molecular Dynamics Simulation // International Journal of Thermophysics. Vol. 28, No.2, 2007. – P.661-673.
10. K. Govers, S. Lemehov, M. Hou, M. Verwerft. Comparison of interatomic poten-tials for UO2. Part II: Molecular dynamics simulations // J. Nuclear Materials. Vol. 376, 2008. – P. 66-77.
11. A. M. Molodec, V. E. Fortov. Fazovye perekhody dioksida urana pri vysokikh temperaturakh i davlenii // Pis'ma v ZhETF. T. 80, ¹ 3, 2004. – C.196-199.
12. C. B. Basak, A. K. Sengupta, H. S. Kamath. Classical molecular dynamics simu-lation of UO2 to predict thermophysical properties // J. Alloys and Comp. Vol. 360, 2003. – P.210-216.
13. N.-D. Morelon, D. Ghaleb. A new empirical potential for simulating the formation of defects and their mobility in uranium dioxide // Phil. Mag. Vol. 83, 2003. – P.1533–1550.
14. K. Yamada, K. Kurosaki, M. Uno, S. Yamanaka. Evaluation of thermal properties of uranium dioxide by molecular dynamics // J. Alloys and Comp. Vol. 307, 2000. – P.10-15.
15. S. I. Potashnikov, A. S. Boyarchenkov, K. A. Nekrasov, A. Ya. Kupryazhkin. Molekulyarno-dinamicheskoe vosstanovlenie mezhchastichnykh potencialov v diokside urana po teplovomu rasshireniyu // Al'ternativnaya energetika i ekologiya. ¹8 (52), 2007. – C.43-52.
16. T. Arima, S. Yamasaki, Y. Inagaki, K. Idemitsu. Evaluation of thermal properties of UO2 and PuO2 by equilibrium molecular dynamics simulations from 300 to 2000 K // J. Alloys and Compounds. Vol. 400, No. 1-2, 2005. – P.43-50.
17. G. V. Lewis, C. R. A. Catlow. Potential models for ionic oxides // J. Phys. C: Sol. St. Phys. Vol. 18, No. 6, 1985. – P.1149-1162.

Vol. 1, No. 1 (2014) p.p. 40–52
A. V. Sokolov (Karelian research center of the Russian Academy of Sciences)
A. V. Drac (Petrozavodsk State University)
Simulation of some methods of representation of n FIFO-queues in the single-level memory
In many applications there is a problem of representation of multiple FIFO-queues in the single-level memory. In this article we research methods of n FIFO-queues allocation in the shared memory. There are two fundamentally different ways of organizing work with queues – consecutive and linked list representation. For sequential cyclic queues each of them should be allocated in its own part of memory. In this case we will have losses of memory when any queue overflow and other data structures don’t overflow. In linked representation the data structure is stored as a list. In this case any number of elements of the lists can coexist in the memory area until the free memory is exhausted. But on the other hand, this approach requires an additional link field for each element. The problem of optimal memory partition between queues in the case of consecutive circular implementation and the problem of the analysis of linked list implementation are investigated. As mathematical models we proposed random walks on the integer lattice in some regions of n-dimensional space. As the optimality criterion we considered the minimal average part of time which the system is situated in the state of “reset tail”. It is reasonably to minimize this value in order to minimize the part of lost elements. This value is reasonably minimized when the overflow queue is the standard situation. This scheme is applied , for example, in the network routers. Such behavior of the router called “reset tail”. Packet loss leads to undesirable results, so the number of such situations need to be minimized. To solve this problem we used apparatus of regular Markov chains.
Keywords and phrases: FIFO-queues; random walks; Markov chains; optimal dynamic data structures.
References.
1. D. E. Knuth. The Art of Computer Programming. Vol. 1. Addison-Wesley, Reading, MA, 2001.
2. R. Sedgwick. Algorithms in C++. Third Edition. Parts 1-4. Addison Wesley Longman, 1999.
3. V. Bollapragada, C. Murphy, R. White. Inside Cisco IOS. Software Architecture. Cisco Press, 2000.
4. A. Sokolov. About storage allocation for implementing two stacks. In: Automation of experiment and data processing. Petrozavodsk. 1980. P. 65-71 (in Russian).
5. P. Flajolet. The evolution of two stacks in bounded space and random walks in a triangle. // Lec. Notes Computer Sci. 1986. Vol. 223. P.325-340.
6. G. Louchard, R. Schott, M. Tolley, P. Zimmermann. Random walks, heat equation and distributed Algorithms. J. Comput. Appl. Math. 1994. Vol. 53. P. 243-274.
7. E. A. Aksenova, A. V. Sokolov. The optimal Management of two Parallel Stacks in Two-Level Memory // Discrete Mathematics and Applications. 2007. Vol. 17, No. 1., P. 47-56.
8. A. V. Sokolov, A. V. Tarasuk, The optimal control of cyclic FIFO-queues. Control Systems and Information Technologies, Vol, 3, No. 20, P. 29-33 (in Russian).
9. E. A. Aksenova. The optimal control of FIFO-queues for infinite time. Stochastic Optimization in Informatics, 2006. Vol. 2, P. 71-76 (in Russian).
10. E. A. Aksenova, A.V. Drac, A.V. Sokolov. The optimal control of n FIFO-queues for infinite time. Information and Control Systems. Vol. 6, P. 46-54. 2009 (in Russian).
11. A. V. Sokolov, A.V. Drac. The optimal implementation of n FIFO-queues in single-level memory. Proceedings of AMICT 2010-2011 Advances in Methods of Information and Communication Technology, Helsinki-2012, P. 51-65. Electronic resource. Access mode: https://helda.helsinki.fi/handle/10138/41066
12. A. V. Sokolov, A. V. Drac. The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory. Information Processing Letters. Elsevier Science Publishing Company Inc, 2013, Vol. 13, Iss. 19-21, P. 832-835.
13. J. G. Kemeny, J. L. Snell. Finite Markov Chains. Van Nostrand, Princeton, New Jersey, 1960.
14. Maxima, a Computer Algebra System. Electronic resource. Access mode: http://maxima.sourceforge.net/

Vol. 1, No. 1 (2014) p.p. 53–63
D. V. Ivanov (Samara State University of Railways)
email: dvi85@list.ru
Numerical algorithms of parameter estimation of linear dynamic systems fractional order with noise in the output signal
It is well known that the least-squares method gives biased estimates of the parameters for the dynamic system in a noisy observation of output signals. Currently actively developing nonlinear methods for estimating the parameters of dynamical systems. Criteria have been developed for estimating the parameters based on minimization of nonlinear functions and proved strong consistency of the resulting estimates of parameters for linear dynamical systems of fractional order with different noise models. The problem of finding the global extremum of a nonlinear function is associated with certain difficulties.
In this paper we propose a numerical algorithm that allows to solve the problem of estimating the parameters of a dynamic system of fractional order with interference in the output signal without using direct methods of finding the global extremum of a nonlinear function, and only by solving a system of linear equations.
By the proved theorem, the numerical algorithm allows:
1) to answer the question whether there is a single parameter estimation;
2) to determine the initial approximation, which guarantees the convergence of the iterative process to a single evaluation;
3) calculate with any desired accuracy assessment.
The proposed algorithm was implemented in Matlab and compared with the method of least squares. The results of simulation confirmed the high efficiency of the proposed algorithm.
Further research areas may be associated with generalization of the proposed algorithms to multidimensional and multiply system. Also, generalization of the results of structural and parametric identification methods, in case of linear dynamical systems of fractional order.

Keywords and phrases: least squares method; output-error; consistent estimators; the difference of fractional order.
References.
1. O. A. Kacyuba. Teoriya identifikacii stokhasticheskikh dinamicheskikh sistem v usloviyakh neopredelennosti. – Samara: SamGUPS, 2008. – 119 s.
2. D. V. Ivanov. Rekurrentnoe ocenivanie parametrov dinamicheskikh sistem. Modeli s oshibkami v peremennykh. – Saarbrucken: LAP Lambert Academic Publishing GmbH. 2011. – 136 s.
3. D. V. Ivanov. Identifikaciya avtoregressii necelogo poryadka s pomekhoy v vykhodnom signale. // Mezhdisciplinarnye issledovaniya v oblasti matematicheskogo modelirovaniya i informatiki. Materialy nauchno-prakticheskoy internet-konferencii. 18-19 iyunya 2013 g. / otv. red. Yu.C. Nagornov – Ul'yanovsk: SIMJET, 2013. – C. 64-67.
4. D. V. Ivanov. Identifikaciya lineynykh dinamicheskikh sistem necelogo poryadka s pomekhoy v vykhodnom signale // Vestnik Tambovskogo universiteta. Ceriya: Estestvennye i tekhnicheskie nauki. – Tom 18, ¹5-2, 2013. – C.2534-2536.
5. D. V. Ivanov. Identification discrete fractional order linear dynamic systems with output-error // Proceedings International Siberian Conference on Control and Communications (SIBCON'2013). Krasnoyarsk: Siberian Federal University. Russia, Krasnoyarsk, September 12-13, 2013. IEEE Catalog Number: CFP13794-CDR.
6. D. V. Ivanov. Identification discrete fractional order linear dynamic systems with errors-in-variables // Proceedings of IEEE East-West Design & Test Symposium (EWDTS'2013), Rostov-on-Don, Russia, September 27-30, 2013. P. 374-377.
7. D. V. Ivanov, O. A. Kacyuba. O sostoyatel'nosti ocenok parametrov ARX-sistem drobnogo poryadka s pomekhoy v vykhodnom signale. // Ctokhasticheskaya optimizaciya v informatike. – Tom 1, ¹2, 2013. – S.21-32.
8. D. Khimmel'blau. Prikladnoe nelineynoe programmirovanie. – M.: Mir, 1975. – 534 s.
9. F. R. Gantmakher. Teoriya matric. – M.: Nauka, 1966. – 575 s.
10. V. V. Engel'gardt, O. A. Kacyuba. Metod strukturno-parametricheskoy identifikacii lineynykh dinamicheskikh sistem s pomekhami na vkhode-vykhode s ispol'zovaniem geneticheskikh algoritmov // Sistemy upravleniya i informacionnye tekhnologii. – Tom 50, ¹4, 2012. – S.35-39.

Vol. 1, No. 1 (2014) p.p. 64–73
S. T. Ishmukhametov, B. G. Mubarakov (Kazan Federal University)
emails: ishm@nextmail.ru, mubbulat@mail.ru
On a class of strong pseudoprime integers
One of the most important problems in cryptography and theory of numbers is the problem of determining is a given integer n is prime or composite. A procedure solving this problem is called a primality test. It is known a number of primality tests and the most popular of them is the Miller-Rabin primality test (MRPT). This test is probabilistic and the error probability depends on a number of iterations called rounds. At each round a natural a less than a testing number n is chosen to carry out some computations that should confirms or discard the hypothesis than n is prime. These a are called bases for MRPT.
Composite numbers successfully passing the MRPT with some base a or with a collection of such bases are called strong pseudoprimes at this set of bases.
Let \psi_k be the least strong pseudoprime integer passing MRPT with first k primes as bases. Numbers \psi_k äëÿ k=1,2,3,... form an increasing sequence and if some odd n is less than \psi_k for some k then to know exactly if n is prime, or no is sufficient at k rounds MRPT with first k primes as bases. This transforms probabilistic test into deterministic one. But to build the sequence of \psi_k is hard. At present, we know only first 9 \psi_k.
In the paper we examine different algorithms of finding strong pseudoprimes and estimate their complexity. Our investigation shows than the existing algorithms are not sufficient to extend the sequence of \psi_k to limits where it can be used in cryptography.

Keywords and phrases: prime numbers; Miller-Rabin primality test; strong pseudoprimes; Jaeschke algorithm.
References.
1. M. Rabin. Probabilistic algorithm for testing primality // J. Numb. Theory. – 12, No. 1, 1980. – P. 128-138.
2. C. Pomerance, C. Selfridge, S. Wagstaff. The Pseudoprimes to 25*109 // Math. Comput. – 1980. – P. 1003-1026.
3. R. Crandall, C. Pomerance. The prime numbers: a computational perspective. – 2nd Ed., Springer-Verlag, Berlin, 2005. – 604 p.
4. S. Ishmukhametov. Factorization Methods for natural numbers. Kazan, 2011. – 190 p.
5. G. Jaeschke. On Strong Pseudoprimes to Several Bases // Math. Comput. 61. – 1993. – P. 915-926.
6. J. Jiang, Y. Deng. Strong pseudoprimes to the first 9 prime bases // ArXiv:1207.0063v1 [math.NT]. – 2012. – P.1–12.
7. S. Ishmukhametov, B. Mubarakov. On practical aspects of the Miller-Rabin Primality Test // Lobachevskii Journal of Mathematics. – Vol. 34, No. 4, 2013. – P.304–312.

Vol. 1, No. 1 (2014) p.p. 74–87
B. F. Melnikov (Samara State University)
email: bormel@rambler.ru
On the star-height of a regular language. Part I: The main definitions
The star height problem was set in 1963 and solved in 1988; up to now, only two solutions were published. The first one (of K. Hashiguchi) was called extremely difficult'' in some next papers; and the second one (of D. Kirsten, 2005) is much simpler.
In this paper we consider a new approach to this problem; the short scheme of the proof is the following one. We define the star height for an automaton, considering all the possible orders of its states and making regular expressions for each order in the usual way. We show, that we can construct corresponding automaton for each regular expression, and therefore we can do this thing for a hypothetical regular expression defining the given regular language and having minimum possible star-height.
Then there is the minimum possible value of star-hight for some hypothetical automaton defining the given regular language; let this automaton be K. We consider not only K, but also the concrete order τ of its states corresponding to the regular expression having minimum possible star-height.
Considering the states of K in the order τ, we obtain for the next state one of the three following things. Either each its loop has equivalent one which does not pass the considered state. Or there exists some other state, which has the smaller value of the order τ and defines the same loops. Or we can add some edges to obtain one of previous cases.
Using a finite sequence of such steps, we obtain the automaton, which is equivalent to the given one; moreover, we can a priory limit the number of states of such “minimum” automaton, using the knowledge of the given language only. Thus, this sequence of steps gives the nondeterministic finite automaton having a priori limited number of states, defining the given regular language and having the minimum possible star-height.

Keywords and phrases: nondeterministic finite automaton; regular language; the star height problem.
References.
1. A. Salomaa. Jewels of Formal Language Theory. -- Computer Science Press, Potomac, Maryland, 1981.
2. L. Eggan. Transitions graphs and the star height of regular events // Michigan Math. J., 10 (1963) 385--397.
3. K Hashiguchi. Algorithms for determining relative star height and star height // Inform. Comput., 78 (1988) 124--169.
4. D. Kirsten. Distance desert automata and the star height problem // Theoret. Informatics Appl., 39 (2005) 455--509.
5. D. Perrin. Finite Automata. Handbook of Theoret. Comput. Sci., Vol. A. -- Elsevier Sci. Publ., 1990.
6. S. Lombardy, J. Sakarovitch. Star Height of Reversible Languages and Universal Automata // 5th Latin American Theoretical Informatics Symposium, LNCS, Vol. 2286 (2002).
7. J. Sakarovitch. Elements of Automata Theory. -- Cambridge university press, 2009.
8. B. Melnikov, A. Melnikova. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics, Vol. 9, No. 1 (2002) 135--150.
9. B. Melnikov. Extended nondeterministic finite automata // Fundamenta Informaticae, Vol. 104, No. 3 (2010) 255--265.
10. B. Melnikov. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae, Vol. 104, No. 3 (2010) 267--283.
11. F. Harary. Graph Theory. -- Addison-Wesley, 1969.

Vol. 1, No. 1 (2014) p.p. 88–96
I. I. Gazizov, A. V. Yuldashev (Ufa State Aviation Technical University )
emails: igpooh@gmail.com, arthur@mail.rb.ru
Development of parallel linear solver for hydrodynamic modeling of oil and gas fields
The goal of this work is to develop parallel algorithms and programs for solving systems of linear algebraic equations on modern computing systems to reduce the time of hydrodynamic modeling of oil and gas fields. Creation of digital models of oil and gas fields and their practical application is a computationally intensive task, so in practice oil companies use high-performance computing systems as well as specialized software packages which support parallel computing. Recently, hybrid computing systems have become widespread, which consist of central processors and massively parallel accelerators, in particular NVIDIA graphics processors, which have high characteristics in terms of performance and energy efficiency. We are developing a parallel linear solver intended for solving sparse linear systems arising in the modeling of multiphase hydrocarbon filtration flows in porous media. We use the preconditioned biconjugate gradient stabilized method with different parallel modifications of incomplete LU factorization ILU(0) as preconditioners. The program is implemented in C with OpenMP and CUDA. Key computational operations are based on the functions of Intel MKL, NVIDIA cuBLAS and cuSPARSE libraries. Efficiency of the developed program was investigated on the modern hybrid computing system (2 x Intel Xeon E5-2680 and 2 x NVIDIA K20X) in solving some test sparse linear systems obtained from reservoir simulation of real oil and gas fields. As a result, we got the maximum speedup up to 4.8 times when solving the sparse linear systems on central processors in parallel, while the use of graphics processors has given additional speedup up to 2.7 times.
Keywords and phrases: graphics processors; hydrodynamic modeling; multi- and manycore systems; sparse matrices.
References.
1. R. K. Gazizov, V. A. Baykov et al. Opyt ispol'zovaniya vysokoproizvoditel'nykh vychislitel'nykh sistem v gidrodinamicheskom modelirovanii zalezhey nefti i gaza (S. 215-221) // Superkomp'yuternye tekhnologii v nauke, obrazovanii i promyshlennosti. – M.: Izd-vo MGU, 2009. – 232 s.
2. Y. Saad. Iterative methods for sparse linear systems (2nd ed.). SIAM, Philadelphia, 2003.
3. J. R. Wallis, R. P. Kendall, T. E. Little. Constraint residual acceleration of conjugate residual Method // SPE 13536, 1985.
4. K. Yu. Bogachev, I. G. Gorelov. Primenenie parallel'nogo predobuslavlivatelya CPR k zadache fil'tracii vyazkoy szhimaemoy zhidkosti v poristoy srede // Vychislitel'nye metody i programmirovanie. – T.9, 2008. – P. 184-190.
5. O. S. Borshchuk. O modifikacii dvukhstupenchatogo metoda predobuslavlivaniya pri chislennom reshenii zadachi mnogofaznoy fil'tracii vyazkoy szhimaemoy zhidkosti v poristoy srede // Vestnik UGATU. – T.12, No. 1, 2009. – P. 146-150.
6. J. Ruge, K. Stüben. Algebraic multigrid. In: Multigrid Methods. S. McCormick (Ed.). SIAM, 1987, 73-130.
7. R. Li, Y. Saad. GPU-accelerated preconditioned iterative linear solvers. Tech. rep., University of Minnesota, 2010.
8. M. Naumov. Parallel Solution of Sparse Triangular Linear Systems in the Preconditioned Iterative Methods on the GPU. Technical Report NVR-2011-001, NVIDIA, 2011.
9. I. I. Gazizov, A. V. Yuldashev. Issledovanie effektivnosti rasparallelivaniya resheniya nekotorykh razrezhyonnykh SLAU na mnogoyadernykh processorakh // Nauchnyy servis v seti Internet: vse grani parallelizma: Trudy Mezhdun. superk-omp. konf. (Novorossiysk, 23-28 sentyabrya 2013 g.). – M.: Izd-vo MGU, 2013. – P. 150-157.

Vol. 1, No. 2 (2014) p.p. 6–20
P. A. Velmisov, Yu. V. Pokladova, E. S. Serebryannikova (Ulyanovsk State Technical University)
Modeling of mechanical system “Pipeline – Pressure Sensor”
A resource allocation problem in hierarchical water quality control systems is considered. This problem is decomposed in two subproblems: a resource allocation problem in the hierarchical system and a river water quality control problem. Both problems are solved by finding the Stackelberg equilibrium. When the resource allocation problem is solved, the presence of two corruption mechanisms is taken into account: those assigned with resource allocation value and with resource use check value. In each case “hard” and “soft” corruption is considered. Introduction of corruption factor means that Agent gives some resource share as a bribe to Principal. The aim of giving bribe for Agent is to get any benefits from Principal. The problem is also considered by means of cooperative game theory. For all coalitions the payoffs and cooperative effects, Shapley and proportional values are found. The river water control problem is solved in three cases. In the first case the quantity of pollutant dropped into wastewater by Agent is less than the first threshold. In this case there is the only Agent's task, and Ecological Center doesn't take part in the game. In the second case the pollutant quantity dropped into wastewater by Agent is greater than the first threshold but less than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold. In the third case the pollutant quantity dropped into wastewater by Agent is greater than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold and charges another penalty for every dropped pollutant unit which is over the second threshold.
Keywords and phrases: resource allocation problem; water resource quality control; connivance; extortion; hierarchical control system.
References.
1. P. A. Vel’misov, Yu. V. Pokladova. An investigation of mathematical models of a mechanical system “Pipeline – Pressure Sensor” // Romai Journal. Pites(?????????????)ti, Romania. Vol. 2, No. 1, 2005. – Ð.214-219.
2. P. A. Vel’misov, Yu. V. Pokladova. Investigation of dynamics of an elastic element of a pressure sensor // Applications of Mathematics in Engineering and Economics. – Soft trade, Sofia, Bulgaria. 2006. – P.51-57.
3. A. V. Ankilov, P. A. Vel’misov, V. D. Gorbokonenko, Yu. V. Pokladova. Mathematical modeling of mechanical system “Pipeline – Pressure Sensor”. Ulyanovsk: ULSTU, 2008. – 188 P.
4. A. V. Ankilov, P. A. Vel’misov, Yu. V. Pokladova. Mathematical models of mechanical system “Pipeline – Pressure Sensor” // Vestnik of the Saratov State Technical University. – No. 3 (27) – 2007, v.2. – P.7-14.
5. P. A. Vel’misov, Yu. V. Pokladova. On some mathematical models of mechanical system “Pipeline – Pressure Sensor” // Proceeding of the international conference “Education, sience and economics at universities. Integration to international education area” (Poland, Plock, 20.09.10 – 25.09.10). – Plock: NOVUM, 2010. – P.492-499.
6. P. A. Vel’misov, Yu. V. Pokladova. On some mathematical models of mechanical system “Pipeline – Pressure Sensor” // Vestnik of the Samara State Technical University. – 2011. – No. 1 (29). – P.137-144.
7. P. A. Vel’misov, Yu. V. Pokladova, E. S. Serebryannikova. Mathematical modeling of systems of measurement of pressure // Proceeding of the international conference “Education, science and economics at universities. Integration to international education area” (Armenia, Yerevan, 26.09.11 – 30.09.11). – Yerevan, 2011. – P.84-86.

Vol. 1, No. 2 (2014) p.p. 21–29
O. I. Gorbaneva, G. A. Ougolnitsky (Southern Federal University)
emails: gorbaneva@mail.ru, ougoln@mail.ru
Resource allocation game-theoretical models of river water quality control with corruption. Part II
A resource allocation problem in hierarchical water quality control systems is considered. This problem is decomposed in two subproblems: a resource allocation problem in the hierarchical system and a river water quality control problem. Both problems are solved by finding the Stackelberg equilibrium. When the resource allocation problem is solved, the presence of two corruption mechanisms is taken into account: those assigned with resource allocation value and with resource use check value. In each case “hard” and “soft” corruption is considered. Introduction of corruption factor means that Agent gives some resource share as a bribe to Principal. The aim of giving bribe for Agent is to get any benefits from Principal. The problem is also considered by means of cooperative game theory. For all coalitions the payoffs and cooperative effects, Shapley and proportional values are found. The river water control problem is solved in three cases. In the first case the quantity of pollutant dropped into wastewater by Agent is less than the first threshold. In this case there is the only Agent's task, and Ecological Center doesn't take part in the game. In the second case the pollutant quantity dropped into wastewater by Agent is greater than the first threshold but less than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold. In the third case the pollutant quantity dropped into wastewater by Agent is greater than the second threshold. In this case Ecological Center charges a penalty for every dropped pollutant unit which is over the first threshold and charges another penalty for every dropped pollutant unit which is over the second threshold.
Keywords and phrases: resource allocation problem; water resource quality control; connivance; extortion; hierarchical control system.
References.
1. O. I. Gorbaneva. Kooperativno-igrovoe modelirovanie raspredeleniya resursov // Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki. Prilozhenie. – T. 2, 2006. – S. 10-16.
2. O. I. Gorbaneva. Modelirovanie raspredeleniya resursov kak igry v normal'noy forme // Izvestiya vysshikh uchebnykh zavedeniy. Severo-Kavkazskiy region. Estestvennye nauki. Prilozhenie – T. 2, 2006. – S. 16-22.
3. A. F. Kononenko. Teoretiko-igrovoy analiz dvukhurovnevoy ierarkhicheskoy sistemy upravleniya // Vychisl. matem. i matem. Fiz. – T. 5, 1974. – S. 1161-1170.
4. A. F. Kononenko. Teoriya igr i ierarkhicheskie struktury // Planirovanie i upravlenie ekonomicheskimi celenapravlennymi sistemami. – 1974. – S. 63-72.
5. J. von Neumann, O. Morgenstern. Theory of Games and Economic Behavior. – Princeton University Press, 1944.
6. G. A. Ougolnitsky. Teoretiko-igrovye principy optimal'nosti ierarkhicheskogo upravleniya ustoychivym razvitiem // Izvestiya RAN. Teoriya i sistemy upravleniya. – T. 4 (2005). – S. 72-78.
7. G. Ougolnitsky. Sustainable Management. – N. Y.: Nova Science Publ., 2011.

Vol. 1, No. 2 (2014) p.p. 30–42
J. Hromkovič (Switzerland, Zürich, Eidgenössische Technische Hochschule)
email: jhromkov@inf.ethz.ch
Deterministic Approaches to Algorithmics for Hard Computing Problems. Part I: The main definitions
This paper is a review. In some its parts we shall give the generalization of some scientific and educational articles and monographs of the author published in the past few years. The text of the paper also includes information about the latest advances in this field of theoretical computer science, i.e., in the algorithmics for hard computing problems.
The term algorithm is the central notion of computer science and algorithmics is one of the few fundamental kernels of theoretical computer science. Recent developments confirm this claim. Hardly any other area of theoretical computer science has been more lively and has achieved comparably deep progress and breakthroughs so fascinating (such as the PCP-theorem and efficient algorithms for primality testing) in recent years. The most exciting development happened exactly in the field of algorithmics for hard computing problems.
The goal of this paper is to give a transparent, systematic introduction to the concepts and to the methods for designing deterministic algorithms for hard problems. All ideas, concepts, algorithms, analysis, and proofs are first explained in an informal way in order to develop the right intuition, and then carefully specified in detail. Following this strategy we preferred to illustrate the algorithm design methods using the most transparent examples rather than to present the best, but too technical, results.
Assuming P≠NP, there is no possibility to design polynomial-time (deterministic) algorithms for solving NP-hard problems. We consider the following three approaches for designing deterministic algorithms. Firstly, we try to design algorithms for solving hard problems and we accept their (worst case) exponential complexity if they are efficient and fast enough for most of the problem instances appearing in the specific applications considered. Secondly, we design exponential algorithms for hard problems, and we even accept if their average time complexity is exponential. And thirdly, we remove the requirement that our algorithm has to solve the given problem. Note that one can combine several different approaches in order to design an algorithm for a given hard problem.

Keywords and phrases: hard computing problems; heuristic algorithms; deterministic approaches.
References.
1. J. Hromkovič. Algorithmics for Hard Computing Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. – Berlin, Springer-Verlag, 2001. – 492 p.
2. J. Hromkovič. Algorithmic Adventures: From Knowledge to Magic. – Berlin, Springer-Verlag, 2009. – 363 p.
3. M. Garey, D. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. – San Francisco, W. Freeman and Co. Ed., 1979. – 338 p.
4. A. Aho, J. Ullman. The Theory of Parsing, Translation, and Compiling (Volume I: Parsing). – N. J., Prentice Hall, 1972. – 542 p.
5. J. Hromkovič. Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. – Berlin, Springer-Verlag, 2011. – 313 p.
6. J. Littlewood. A Mathematicians Miscellany. – L., Methuen and Co. Ed., 1953. – 144 p.

Vol. 1, No. 2 (2014) p.p. 43–57
E. F. Saifullina, R. I. Semenov (Togliatti State University)
emails: elena-fairy@yandex.ru, romansemenov3@gmail.com
On some algorithms for the recovery of a graph by its vector of second-order degrees
This paper proposes a universal graph reconstruction algorithm on its vector of second-order degrees, as well as conducted a detailed examination of options for this algorithm for various applications (e.g., for a random graph with some known characteristics). This algorithm is closely connected with the observation networks and work with them and with various applied problems. Among the many examples we mention the problem of the distribution of wired connections in a localized network, and related problems of partial recovery of some lost data based on the saved data.
The main problem encountered by the development of a universal algorithm is ambiguity in the solution of the problem by restoring the graph vector degrees of order, forcing the set of feasible solutions considered as the result of heuristic algorithms, providing least time required.
To achieve the stated purpose proposed algorithms are divided into two specialized parts that perform tasks of varying complexity: the optimizer for partially restoring graph by simplified rapid algorithm and the builder – complex long algorithm that returns the correct answer of any complexity. The builder algorithm is available in two variations: for the problem of constructing a random graph and the problem of constructing a particular graph. Builder of particular graph was derived from a random graph builder and it is a complicated variation with advanced features, which include a relatively simple integration of multiple checks of the results and the ability to select the operating mode (getting all the correct answers or receive the first correct answer).
More detail in the paper presents how to recover particular graph with defined charac-teristics such as lack of availability of connected loops and – since they require developers to create the most versatile and universal algorithm. Also there are clearly describes two ways to obtain the vector of degrees of the second order on the basis of existing graphs presented in the form of drawing or adjacency matrix. No less attention was paid to the actual implementation of the proposed algorithm and the article presents the results of a single-threaded implementation of the algorithm with notes on its behavior in different situations with a table showing the dependence of the time spent on the restoration of time on the support degree gave by the optimizer. There is no the accurate assessment of the complexity of the described algorithms.

Keywords and phrases: recovery of a graph; vector of second-order degrees; heuristic algorithms.
References.
1. B. Melnikov, S. Makarkin, E. Saifullina. Nekotorie voprosi matematucheskogo modelirovaniya socialnih setei (na primere Facebooka). Yuzhno-Sibirskiy nauchniy vestnik. 2014, ¹ 1(5), P. 51-53.
2. A. Raigorodskiy. Matematicheskie modeli interneta. // Kvant, 2012, ¹ 4, p. 12-16.
3. V. Breyer. Stohasticheskie modeli socialnih setei // Upravlenie bolshimi sistemami: sbornik trudov, 2009, ¹27, p. 169-204.
4. B. Melnikov, E. Saifullina. Izvestiya visshih uchebnih zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki. 2013, ¹3(27), P. 70-83.
5. F. Harari. Teoriya grafov. – M., Mir, 1973. – 302 p.
6. L. Ostroumova. Matematicheskie ozhidaniya k vhodyashih stepeney vershin v sluchainih grafah v modeli Bollobasha-Riordana // Trudi Moskovskogo fiziko-tehnicheskogo instituta (gosudarstvennogo universiteta), 2012, tom 4, ¹ 1(13), p. 29-40.
7. P. Erdös, I. Miklós, Z. Toroczkai. A Simple Havel-Hakimi Type Algorithm to Realize Graphical Degree Sequences of Directed Graphs. Electr. J. Comb., 2010, V. 17, No. 1.
8. B. Bollobás, O. Riordan. Mathematical results on scale-free random graphs // Handbook of graphs and networks. – Weinheim, Wiley-VCH, 2003, p. 1–34.
9. B. Melnikov, S. Pivneva, O. Rogova. Reprezentativnost sluchaino sgenerirovannih nedeterminirivannih konechnih avtomatov s tochki zreniya sootvetstvuyushih ba-zisnih avtomatov // Stohasticheskaya optimizaciya v informatike, 2010, ¹ 6, p. 74–82.
10. B. Melnikov. Discrete optimization problems – some new heuristic approaches // Proc. of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region, IEEE Computer Society Washington, 2005, p. 73–80.
11. B. Melnikov. Multievristicheskiy podhod k zadacham diskretnoi optimizacii // Kibrnetika i sistemniy analiz (NAN Ukraini), 2006, ¹3, p. 32–42.

Vol. 1, No. 2 (2014) p.p. 58–68
V. V. Engelhardt, O. A. Katsjuba (Samara State University of Railways)
emails: hexware@gmail.com, katsyuba@samgups.ru
Application of genetic algorithms for structural-parametric identification of linear dynamic systems
In the paper, an approach based on the use of genetic algorithm for solving the problem of structural identification of linear dynamic systems containing noise at the input and output. The proposed method of structural-parametric identification takes place in two stages. In the first stage the model structure is encoded as a vector, and the problem of structural identification is reduced to the problem of integer programming class NP-hard. To find solutions for the implementation of genetic algorithm within integer programming, in this paper we consider the corresponding modification of the algorithm. The proposed numerical algorithm was implemented in Matlab like a modification for the library Genetic Algorithm Solver.
The second step is a parametric identification of the resultant structure. For the implementation of finding a sustainable solution in the framework of parametric identification of the model structure, the parameters are constrained as a stability criterion Routh-Hurwitz, data sufficiency and physical feasibility of the system. In numerical simulations were compared criteria for parametric identification of the method of least squares and instrumental variables, as well as our own criterion was proposed, which gives more consistent estimates. These comparisons were made for different initial conditions of the algorithm, such as the growing increase in complexity of the model, termination of identification in case of slight decrease of error with increasing model complexity.
The simulation was performed at various signal/noise on the input and output of a dynamical system. The simulation results confirm the high accuracy of the estimates of parameters and structure of the model obtained by the proposed algorithm.

Keywords and phrases: structural-parametric identification; linear dynamic system; evolutionary algorithm; genetic algorithm; integer programming.
References.
1. O. A. Katsyuba, A. I. Zhdanov. Features of application of MNK for estimation of linear differential operators in problems of identification of objects of management // Automatic equipment and telemechanics – 1979 – No. 8, p. 86-96.
2. D. V. Ivanov, O. A. Katsyuba. Recurrent parametrical identification of multidi-mensional linear dynamic systems with a car - the correlated hindrances in entrance and output signals//the Messenger of the Samara state technical university, the Physical and Mathematical Sciences of Science series, No. 4(25) (2011), p 102-109.
3. D. V. Ivanov, O. A. Uskov. Recurrent estimation of bilinear dynamic systems with hindrances in entrance and output signals // News of the Southern federal university, the Technical science No. 6 (131) (2012), p 187-192.
4. V. O. Tolcheek, T. V. Yagotkina. Methods of identification of linear one-dimensional dynamic systems. M.: Moscow power institute, 1997. – 108 p.
5. V. A. Fatuyev, A. V. Kargin, V. M. Ponyatsky. Software package of structural and parametrical identification of linear one-dimensional dynamic systems // Works of the second All-Russian scientific conference “Design of Engineering Scientific Appendices in the environment of Matlab”. M.: YIP RAHN, 2004. – p.715-762.
6. V. A. Fatuyev, A. V. Kargin, V. M. Ponyatsky. Structural and parametrical iden-tification of dynamic systems: Manual. Tula: Publishing house of TULGU, 2003. – 156 p.
7. V. A. Fatuyev, A. V. Yudayev, V. M. Ponyatsky, A. V. Kargin, M. S. Oberman. Structural and parametrical identification of multi-dimensional non-stationary dy-namic systems // Works III of the international conference “Identification of Sys-tems and Problems of Management” (SICPRO'2004). M.: YIP RAHN, 2004, p. 159-186.
8. L. Ljung. System Identification – Theory for the User, Prentice Hall, Upper Sad-dle River N.J. 2nd ed., 1999.
9. A. S. Anisimov, V. T Kononov. Identification of an order of the linear differential equation // Works of the international conference “Identification of Systems and Problem of Management” of SICPRO'2000. Ì: Institute of problems of management of V. A. Trapeznikov of the Russian Academy of Sciences, 2000. – 2534 p.
10. O. A. Katsyuba. The theory of identification of stochastic dynamic systems in the conditions of uncertainty: monograph // Samara: SamGUPS, 2008. – 119 p.
11. V. V. Yemelyanov, V. V. Kureychik, V. M. Kureychik. The theory and practice of evolutionary modeling – M: Fizmat, 2003. – 432 p.
12. M. Gary, D. Johnson. Computers and hard tasks. M.: Mir, 2012. – 420 p.
13. D. Kusum, K. Singh, M. Kansal, C. Mohan. A real coded genetic algorithm for solving integer and mixed integer optimization problems. // Applied Mathematics and Computation, 212(2), p. 505–518, 2009.
14. S. Thil. Contributions a l’identification de modeles avec des erreurs en les variables. – Thesis of Doctorat, University of Henri Poincare, Nancy 1, 2007.
15. L. Lyyung. Identification of systems. The theory for the user. – M.: Nauka, 1991. – 432 p.
16. V. V. Engelgardt, O. A. Katsyuba. Method of structural and parametrical identification of linear dynamic systems with hindrances on an entrance exit with use of genetic algorithms // Control systems and information technologies. – Vol. 50, No. 4, 2012. – P. 35-39.

Vol. 1, No. 2 (2014) p.p. 69–81
B. F. Melnikov (Samara State University)
email: bormel@rambler.ru
On the star-height of a regular language. Part II: Auxiliary constructions
In the second part of this paper we continue to consider a new approach to the star-height problem; the short scheme of the proof is the following one. We define the star height for an automaton, considering all the possible orders of its states and making regular expressions for each order in the usual way. We show, that we can construct corresponding automaton for each regular expression, and therefore we can do this thing for a hypothetical regular expression defining the given regular language and having minimum possible star-height.
Then there is the minimum possible value of star-hight for some hypothetical automaton defining the given regular language; let this automaton be K. We consider not only K, but also the concrete order τ of its states corresponding to the regular expression having minimum possible star-height.
Considering the states of K in the order τ, we obtain for the next state one of the three following things. Either each its loop has equivalent one which does not pass the considered state. Or there exists some other state, which has the smaller value of the order τ and defines the same loops. Or we can add some edges to obtain one of previous cases.
Using a finite sequence of such steps, we obtain the automaton, which is equivalent to the given one; moreover, we can a priory limit the number of states of such “minimum” automaton, using the knowledge of the given language only. Thus, this sequence of steps gives the nondeterministic finite automaton having a priori limited number of states, defining the given regular language and having the minimum possible star-height.

Keywords and phrases: nondeterministic finite automaton; regular language; the star height problem.
References.
1. B. Melnikov. On the star-height of a regular language. Part I: The main definitions // Evristicheskie algoritmy i raspredelyonnye vychisleniya, Vol. 1, No. 1 (2014) 74–87.
2. B. Melnikov. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae, Vol. 104, No. 3 (2010) 267–283.
3. F. Harary. Graph Theory. – Addison-Wesley, 1969.

Vol. 1, No. 2 (2014) p.p. 82–94
I. N. Popov (Northern (Arctic) Federal University named after M. V. Lomonosov)
email: popovivannik@yandex.ru
The algorithmization of membership of the group member to its subgroup (on the example of a group RC)
In mathematics, matrices play a big, both theoretical and practical role. Matrices have a special meaning in abstract algebra, in particular in the groups theory. Among all groups, there can be distinguished matrices, whose elements are square matrices. Such groups are investigated on the structure, in them we identify special subgroups and elements. Fixing a subgroup within a matrix group and selecting an arbitrary matrix of the group, we can consider the question of its belonging to the subgroup. This question is the main in this paper.
It is clear, that in the decision of this question plays a defining subgroups, which, in particular, can be based on determining ratios or generating matrices. In the second case, the subgroup is defined as the linear shell of certain matrices, that is, each element subgroup is equal to the sum of some matrices from a predefined set of matrices. The group RC belongs to this kind of subgroups, which is a subgroup of square matrices over the ring of classes deductions module 2 with a fixed size of matrices. Moreover, the åðómatrix group RC is finitely generated.
But, in our view, this property of the group RC for high dimensional matrices is not fundamental for the construction of the recognition algorithm for facilities of arbitrary matrix to the group RC. Based on this property group RC, considering the small number of generating matrices, finding the answer to the main question of this paper is reduced to the solution of some matrix equations. In this approach, one of the factors influencing the complexity of computations is the dimension of the matrix.
Another approach to the construction of algorithms for the solution of the main problem for the group RC which can be used to resolve the basic question in the general case, can be based on the internal structure of a subgroup on the special properties of matrices, incoming group RC. We should discover properties such that, on the one hand, on the basis of their possible unequivocally to answer this question, and, on the other hand, the algorithms constructed on these properties are easier to implement. Such an approach to the construction of the algorithm is shown in the example matrix RC.
The ability to determine, whether an arbitrary matrix group belongs to its subgroup, has the practical importance. Matrix, as we know, can play the role of transformations of separate elements or the sets of elements.
The conversion can be of the different types. In the general theory of groups, there is investigated the question about the possibility of getting a group item from another element of the same group, using a certain class of transformations of the group members. If one member of the group can be obtained from another, using a finite combination of transformations of the given class of transformations, then the elements are equivalent.
The determination of equivalence of group elements arises, for example, coding theory (in the study and construction of group codes), in the study of associative algebras (the problem of equivalence (equality) words), in game theory (in determining the opportunities for achieving the objectives of the game according to its rules).
Considering the group RC, under the transformation matrix can be considered as changes of all 0’s and 1’s row or column on the 1’s and 0’s, respectively. From the point of view of the matrix, it means, that this matrix added matrix group RC. If there are two matrix and the question of their equivalence, the question boils down to the definition of their difference to the group RC. The efficient algorithm facilities matrix to the group RC speeds up the process of getting an answer to the question of equivalence of the selected matrices.

Keywords and phrases: matrix; group; subgroup; the characteristic property of the group elements.
References.
1. M. I. Kargopolov, Yu. I. Merzlyakov. Fundamentals of the Group Theory. – Moscow, Nauka, 1982. – 288 p.
2. A. G. Kurosh. Group Theory. – Moscow, Nauka, 1967. – 648 p.
3. V. Boss. Lectures on mathematics. Vol. 10: Robin and efficient algorithms. – Moscow, LKI, 2008. – 210 p.
4. M. A. Kolchar, I. N. Popov. The algorithm for the decomposition of elements of the group RC // Modern problems of mathematics and its applied aspects. Conference abstracts, p. 169. – Perm, 2013.

Vol. 1, No. 3 (2014) p.p. 6–19
Yu. S. Nagornov (Togliatti State University)
email: Nagornov.Yuri@gmail.com
I. V. Zhilyaev (Southern Federal University)
email: Zhilyaev@mail.com
About optimization method for calculation of morphological properties of erythrocyte and its intercellular pressure
In this paper we apply the theory of elasticity and numerical optimization method with the selection of the model parameters to the modeling of morphological and functional properties of the erythrocyte. Erythrocyte model is necessary in order to provide answers to the fundamental questions: why erythrocyte takes the form of a biconcave disk provided content uniformity of erythrocyte? W hat factors affect the shape of a red blood cell and its elastic properties? How to measure intracellular pressure based on a physical model? Recently, the most interesting and complex experimental data on the structure of the erythrocyte and its cytoskeleton were obtained by atomic force microscopy, which stated that the coefficient of membrane elasticity is 1.4–1.7 kPa, with the rigidity in the center and on the edge of the erythrocyte differ by 25-40%.
The paper presents a model for the calculation of morphological properties of erythrocyte depending on intercellular pressure. The model represents the erythrocyte as a homogeneous elastic body with elastic depending on the distance to the center of symmetry of the erythrocyte. The data for modeling were taken from the experimental study, which were used by atomic force microscopy: measuring the elasticity of the membrane of erythrocytes and morphology.
In this paper, the following tasks were solved. 1) In the developed model, the elasticity of the membrane to change depending on the distance to the center within 1–1.6 kPa; 2) The calculation of the elastic properties is made by finite element analysis. 3) The selection of the parameters of the membrane is made by optimizing method. 4) In the model the dependence of erythrocyte morphology on the membrane pressure was obtained. 5) We have compared the calculated data with atomic force microscopy, which allowed determining the pressure on the membrane for different morphological forms of erythrocytes. 6) We proposed method of measuring intercellular pressure based on the optimization data.

Keywords and phrases: model of erythrocyte; atomic force microscopy; the geometric characteristics of erythrocytes; calculation of the elastic properties; intercellular morphological pressure.
References.
1. S. B. Daniyarov, À. G. Zarif'yan, Z. E. Esenbekova, O. V. Ryabova. Fiziologiya krovi. Metodicheskoe posobie k prakticheskim zanyatiyam po normal'noj fizi-ologii. Bishkek: Izd-vo Kyrgyzsko-Rossijskogo Slavyanskogo universiteta, – 2000. – 54 p.
2. E. S. Drozd, S. À. Chizhik, E. E. Konstantinova. Àtomno-silovaya mikroskopiya strukturno-mekhanicheskikh svojstv membran ehritrotsitov // Rossijskij zhurnal biomekhaniki. 2009. T.13. – No. 4 (46). – S. 22–30.
3. R. Nowakowski, P. Luckham. Imaging the surface details of red blood cells with atomic force microscopy // Surface and Interface Analysis. 2002. V. 33. – No. 2. – P. 118–121.
4. I. Dulińska, M. Targosz et al. Stiffness of normal and pathological erythrocytes studied by means of atomic force microscopy // J. Biochem. Biophys, Methods. 2006. – V. 66 (1-3). – P. 1–11.
5. Yu. S. Nagornov. Modelirovanie uprugikh svojstv kletok krovi. Monografiya: Saarbrücken: LAP Lambert Academic Publishing, – 2013. 108 s.
6. Yu. Yu. Gushhina, S. N. Pleskova, M. B. Zvonkova. Issledovanie razlichij morfologicheskikh parametrov kletok krovi cheloveka metodom skaniruyushhej zondovoj mikroskopii // Poverkhnost'. Rentgenovskie, sinkhrotronnye i nejtronnye issledovaniya. 2005. – No. 1. – S. 48–53.
7. B. N. Zaitsev, A. G. Durymanov, V. M. Generalov. Atomic force microscopy of the interaction of erythrocyte membrane and virus particles // Proc. Intern. Work-shop “Scanning Probe Microscopy-2002”, Nizhny Novgorod, – 2002. – P. 211-213.
8. M. Asghari-Khiavi, B. R. Wood, A. Mechler et al. Correlation of atomic force microscopy and Raman micro-spectroscopy to study the effects of ex vivo treatment procedures on human red blood cells // Analyst. 2010. – V. 135. – P. 525-530.
9. M. O'Reilly, L. McDonnell, J. O'Mullane. Quantification of red blood cells using atomic force microscopy.Ultramicroscopy. 2001. – V. 86(1-2). – P. 107-112.
10. Yu. S. Nagornov. Simulation of AFM data for erythrocytes membrane under femtosecond laser irradiation // Applied Cell Biology. V.3. – ¹1. – P. 1-8.
11. Yu. S. Nagornov, I. V. Zhilyaev. Modelirovanie morfofunktsio-nal'nykh svojstv membrany ehritrotsita // Vestnik SamGU – Estestvennonauchnaya seriya. 2013. – No. 9/1 (110). – S.178-191.
12. Yu. S. Nagornov, I. V. Zhilyaev. Optimizatsiya formy ehritrotsita v sootvetstvii s dannymi atomno-silovoj mikroskopii // Matematicheskaya morfologiya. EHlek-tronnyj matematicheskij i mediko-biologicheskij zhurnal. T. 12. – No. 1. 2013. http://www.smolensk.ru/user/sgma/MMORPH/N-37-html/nagornov/nagornov.htm
13. Yu.S. Nagornov. Modelirovanie morfologii i zhestkosti membra-ny ehritrotsitov posle femtosekundnogo lazernogo oblucheniya // Rossijskij zhurnal biomekhaniki. 2013. T. 17. – No. 3 (61). – S. 112-121.
14. COMSOL Multiphysics ®. The Platform for Physics-Based Modeling and Simulation. [Electronic resource] – Access mode: http://www.comsol.com/comsol-multiphysics
15. D. Rojers, J. Adams. Matematicheskie osnovy mashinnoy grafiki. — M.: Mir, 2001.

Home