2016 № 3 (32)

Сontents

Yunicheva N. R. SUFFICIENT CONDITIONS FOR STABILITY OF THE DYNAMIC SYSTEM WITH INACCURATE DATA
Achasova S. M. CELLULAR AUTOMATA SELF-REPLICATING MATRIX OF ARTIFICIAL BIOLOGICAL CELLS
Bredikhin S. V.,Lyapunov V. M., Shcherbakova N. G. THE STRUCTURE OF THE CITATION NETWORK OF SCIENTIFIC PUBLICATIONS
Zaripova G.I. ENSURING THE AUTHENTICITY OF DATA PROCESSING ON THE BASIS OF IDENTIFICATION OF NON-STATIONARY OBJECTS IN CONDITIONS OF UNCERTAINTY OF REGULAR ERROR
Kazancev G. Yu., Omarova G. A. SIMULATION OF TRAFFIC FLOWS USING CELLULAR AUTOMATA
Krutikov N. O., Podakov N. G., Zhilyakova V. A. DEVELOPMENT OF THE INFORMATION EXTRACTION SYSTEM FROM TEXTS IN RUSSIAN FOR SUBJECT DOMAIN CRIMINALISTICS
Matveev A. S., Nikitin* V.V. , Romanenko** A. A., . Duchkov A. A. EFFECTIVE IMPLEMENTATION OF USFFT ALGORITHM

Institute of Information and Computational Technologies, 125 Pushkin Street, 050010, Alma-Ata, Kazakhstan

SUFFICIENT CONDITIONS FOR STABILITY OF THE DYNAMIC SYSTEM WITH INACCURATE DATA

UDC 681.5

Mathematical description of the phenomena and processes of the nature is often carried out with this or that degree of error. Such errors lead to the fact that the mathematical model not rather fully reflects all qualities of studied processes. Desire to eliminate this deficiency contributed to development of a new scientific direction in the modern control theory, which acquires the increasing relevance and a demand in practice now. Within this direction of an error of modeling caused by the reasons of various type are considered directly in the most mathematical model by introduction of interval parameters with set lower and upper bounds. Such approach to a problem allows to judge existence of these or those qualities of the studied phenomenon or process in conditions, so-called, parametrical uncertainty. The most developed in sense of richness of ideas and methods of property research in conditions of parametrical uncertainty there was a class of linear mathematical models to which the most part of scientific works in this area is devoted. However, in practice there are cases when it is impossible to be limited to consideration only of linear mathematical models. On the other hand, today the arsenal of methods for studying dynamical qualities of processes described by nonlinear mathematical model with unknown parameters are presented extremely sparingly in current scientific work. In this regard special relevance is acquired by problems of development new and existing methods of quality research of nonlinear dynamic models of processes in the conditions of parametrical uncertainty.
Studying the properties of nonlinear dynamic systems with unknown parameters interval type is of great scientific interest. Many of the issues relating to the investigation of the stability of non-linear interval dynamic systems defined in the state space are still open. In this paper we consider the nonlinearity of sector type. Research problems of dynamic systems with nonlinearity of sector type, mathematical models are accurately known goes back to the works A. I. Lure, and Popov's and consists of two interrelated areas of the modern theory of absolute stability. The presence of interval uncertainty has given rise to a new round of the relevance of research tasks A. I. Lure nonlinear systems with unknown parameters. For example, obtained by modifying the frequency robust stability criteria absolute uncertainty in the linear part of the system. In contrast to this work, in which the linear part is given in the form of a family of polynomials, the greatest interest in this area is the study of nonlinear systems defined in the state space. In other work using the Lyapunov–Krasovskii functional, sufficient conditions for the absolute stability of interval nonlinear systems with delay in state and nonlinearity of sector type.

The development of Lyapunov's direct method, successfully proven in solving many problems of control theory, a class of interval-specified objects leads to the necessity of the study of solution sets of interval matrix Lyapunov equations, Sylvester. The complexity of the mathematical description of such sets leads to an exponential growth in computing costs in solving the problems of control theory. However, in most cases in practice it suffices to consider the outer or inner interval estimates of these sets.

In this paper, based on the direct method of Lyapunov, an algebraic criterion for absolute stability of zero equilibrium position interval dynamic system with vector nonlinearity of sector type is proposed.

Key words: inaccurate data, stability of a dynamic system, the tolerance solution set

References

1. Sokolova S. P., Ivlev R. S. E`ksponentcial`naia ustoi`chivost` interval`noi` nelinei`noi` sistemy` // Trudy` SPIIRAN, 2006. Vy`p. 3. Tom 2. P. 366–376.
2. Lure A. I. Nekotoryie nelineynyie zadachi teorii avtomaticheskogo regulirovaniya. M.: Gostehizdat, 1951.
3. Popov V. M. Giperustoychivost avtomaticheskih sistem. M.: Nauka, 1970.
4. Dzhuri E. I., Premaratne K., Ekanayake M. M. Robastnaya absolyutnaya ustoychivost diskretnyih sistem // Avtomatika i Telemehanika. 1999. N 3. P. 97–118.
5. Ivlev R. S. Absolyutnaya ustoychivost nelineynyih dinamicheskih sistem s parametricheskoy neopredelennostyu intervalnogo tipa i zapazdyivayuschim argumentom // Materialyi Mezhdunarodnoy konferentsii “Vyichislitelnyie tehnologii i matematicheskoe modelirovanie v nauke, tehnike i obrazovanie”. VTMM-2002. Novosibirsk-Alma-Ata, 2002. P. 27 – 34.
6. Kalmy`kov S. A., Shokin Iu. I., Iuldashev Z. KH. Metody` interval`nogo analiza. N.: Nauka SO, 1986. .
7. Zholen L., Kifer M., Didri O., Val`ter E`. Pricladnoi` interval`ny`i` analiz. M.: Institut komp`iuterny`kh issledovanii`. 2007.
8. Gelig A. KH., Leonov G. A., Iakubovich V. A. Ustoi`chivost` nelinei`ny`kh sistem s needinstvenny`m sostoianiem ravnovesiia. M.: Nauka. 1978.

Bibliographic reference: Yunicheva N. R. Sufficient conditions for stability of the dynamic system with inaccurate data //journal “Problems of informatics”. 2016. № 3. P. 4-12.

Article

Achasova S. M.

Institute of Computational Mathematics and Mathematical Geophysics of SB RAS. 630090, Novosibirsk. Russia

CELLULAR AUTOMATA SELF-REPLICATING MATRIX OF ARTIFICIAL BIOLOGICAL CELLS

UDC 681.32

John von Neumann used the concept of cellular automaton for presenting and studying the logical form of self-reproduction. His goal was to describe the fundamental principles and algorithms of information processing involved in the process of self-reproduction, in other words, to separate the logical form from the natural process of self-reproduction. It is interesting to note, a few years before J. Watson and F. Crick discovered the DNA double helix von Neumann formulated the need for a one-dimensional description (genome) of the self-replicating structure, which is fed on the input tape, and then generates the structure in the cellular automata space. In addition, von Neumann formulated the principle of the dual use of the genome that is fed on the input tape: it serves as a program for construction of the mother structure (translation of the genome), and is also copied to the mother structure (transcription of the genome) so that a daughter structure could then be produced.

Further study of self-reproduction was associated with Langton loop. This is a cellular automaton incapable of universal construction, but capable exclusively of self-replication. Originally Langton loop was a rectangular loop in a two-dimensional cellular automata space. The self-description (genome) of the mother loop circulates in Langton loop in the form of a sequence of cell states. Simultaneously with construction of the daughter loop the genome is rewritten into it, and then this loop creates its daughter. Langton loop was used as a model for verification hypotheses relating to the emergence of biological life. Langton loop was endowed with the ability to interact with the external observer. Attempts were made to create "useful replicator" on the basis of Langton loop; this is the cellular structure which executes a computational program together with constructing a copy. Subject to the successful development of such direction self-replicating structures can be considered as a new paradigm for designing fine-grain parallel algorithms and architectures.

In the paper the self-replicating cellular automaton structure in the form of a matrix of artificial biological cells "Star" is presented. The simple program for constructing this structure is based on the Parallel substitution algorithm (PSA) that is a spatial system for representing fine-grain parallel algorithms and architectures. An artificial biological cell is constructed from a genome that is fed on the input tape. The result is a model of an artificial biological cell, which contains the phenotype as a set of fixed data and the genotype as a set of mobile data. The structures of artificial biological cells can be the components of computer system that mimic the properties of living organisms – growth, self-replicating, self- repair.

The PSA is an expanded paradigm of the classical cellular automaton (CA) and has some new properties compared with CA, which enhances its functional and expressive abilities. These properties are as follows. An arbitrary substitution template is admitted. At each clock cycle, one substitution can change the states of several cells. New type of a substitution is introduced. This is the functional substitution, in which the new states of the cells are functions of the states of the adjacent cells. These properties of the PSA enable to create compact, easily foreseeable and structured description of the process of building fine-grain models of artificial biological cells. The devices possessing such properties can be used in space research, in radioactive environments, avionics, etc.

Key words: cellular automaton, self-replicating structure, parallel substitution algorithm, artificial biological cell, artificial multicellular organism.

References

1. Von Neumann J. Theory of self-replication automata / Burks A. W. (ed.) University of Illinois Press, 1966.
2. Watson J., Crick F. A structure for deoxyribose nucleic acid. // Nature. 1953. V. 171. P. 737–738.
3. Watson J. D. The Double Helix. New York: Atheneum, 1968.
4. Langton C. G. Self-replication in cellular automata // Physica D. 1984. V. 10. P. 135–144.
5. Langton C. G. Studying artificial life with cellular automata // Physica D. 1986. V. 22. P. 120–149.
6. Codd E. F. Cellular automata. New York: Academic Press, 1968.
7. Chou H.-H., Reggia J. A. Emergence of self-reproducing structures in a cellular automata space // Physica D. 1997. V. 110. P. 252–276.
8. Azpeitia I., Ibanez J. Spontaneous emergence of robust cellular replicators // Lect. Notes in Comput. Sci. 2002. V. 2493. P. 132–143.
9. Stauffer A., Sipper M. Externally controllable and destructible self-replicating loops // Lect. Notes in Artificial Intelligence. 2001. V. 2159. P. 282–291.
10. Chou H.-H., Reggia J.A. Problem solving during artificial selection of self-replicating loops // Physica D. 1998. V. 115. P. 293–312.
11. Petraglio E., Henry J.-M., Tempesti G. Arithmetic operations on self-replicating cellular automata // Lect. Notes in Artificial Intelligence. 1999. V. 1674. P. 447–456.
12. Mange D., Stauffer A., Petraglio E., and Tempesti G. Embryonic machines that divide and differentiate // Lect. Notes in Comput. Sci. 2004. V. 3141. P. 201–216.
13. Mange D., Stauffer A., Petraglio E., Tempesti G. Self-replicating loop with universal construction // Physica D. 2004. V. 191. P. 178–192.
14. Mange D., Stauffer A., Peparolo L., Tempesti G. A macroscopic view of self‐replication // Proc. IEEE. 2004. V. 92, Iss. 12. P. 1929–1945.
15. Stauffer A., Mange D., and Tempesti G. Bio-inspired computing machines with self-repair mechanisms // Lect. Notes in Comput. Sci. 2006. V. 3853. P. 128–140.
16. Stauffer A., Mange D., Rossier J. Self-organizing systems based on bio-inspired properties // Lect. Notes in Artificial Intelligence. 2007. V. 4648. P. 1171–1181.
17. Stauffer A., Mange D., Vannel F. Bio-inspired self-organizing cellular systems // Biosystems. 2008. V. 94, Iss. 1–2. P. 164–169.
18. Tempesti G., Mange D., Stauffer A. Self-replicating and cellular automata / In Encyclopedia of Complexity and Systems Science. Springer Science Business Media New York. 2013. P. 8066–8084.
19. Dighe S. G., Kanawate M. T. Field Programmable Gate Array Technique’s // International Journal of Computing and Technology. 2015. V. 2, Iss. 12. P. 521–527.
20. Achasova S. M. Modeling Artificial Biological Cell in Fine Grained Structure // Programming and Computer Software. 2014. V. 40, N 6. P. 354–361.
21. Achasova S. M. Self-replicating structure as an artificial multicellular organism // Cybernetics and Systems Analysis. 2014. V. 50, Iss. 2. P. 316–323.
22. Achasova S. M., Bandman O. L. Korrertnost parrallelnyh vychislitelnyh protsessov. [Validity of Parallel Computational Processes] Novosibirsk: Nauka. 1990.
23. Achasova S. M., Bandman O. L., Markova V. P., Piskunov S. V. Parallel substitution algorithm. Theory and application. Singapore: World Scientific. 1994.
24. Achasova S. M. Simple Self-Reproduction Programs in a Cellular Space Based on the Parallel substitution algorithm // Programming and Computer Software. 2004. V. 30. N 4. P. 181–188.
25. Achasova S. M. Program Constructor of Cellular Self-Reproducing Structures // Programming and Computer Software. 2009. V. 35. N 4. P. 190–197.

Bibliographic reference: Achasova S. M. Cellular automata self-replicating matrix of artificial biological cells //journal “Problems of informatics”. 2016. № 3. P. 13-25.

Article

Bredikhin S. V., Lyapunov V. M., Shcherbakova N. G.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

THE STRUCTURE OF THE CITATION NETWORK OF SCIENTIFIC PUBLICATIONS

UDC 001.12—303.2

Methods of measurement of the parameters characterizing a structure of the citation network of scientific publications are presented: average distance, density and transitivity. Values of these parameters are calculated based on the citation data extracted from the bibliographic DB RePEc. Clustering analysis of co-citation, bibliographic coupling and summary graphs corresponding to the main network component is made using two algorithms of community detection. The comparison of results was done by computing NMI. Analysing allowed to detect groups of articles, joint by common subject and to characterize them.

Key words: average distance, density, transitivity, clustering coefficient, communities, clustering algorithm, modularity, NMI measure.

References

1. Bredikhin S. V., Lyapunov V. M., Shcherbakova N. G., Yurgenson A. N. Parametry “tsentral’nosti uzlov seti tsetirovaniya naucnnykh statey // Probl. inform. 2016. № 1. S. 30–57.
2. Bredikhin S. V., Lyapunov V. M., Shcherbakova N. G. Parametry par uzlov seti tsetirovaniya naucnnykh statey // Probl. inform. 2016. № 2. S. 30-49.
3. General principles. Available at: http://repec.org.
4. Milgram S. The small world problem // Psychol. Today/ 1967. V. 2. P. 60–67.
5. Fortunato S. Community detection in graphs // Phys. Reports. 2010. V. 486. P. 75–174.
6. Watts D. J. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton: Princeton University Press, 1999.
7. Wasserman S., Faust K. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
8. Broder A., Kumar R., et al. Graph structure in the web // 9th International World Wide Web conference, Amsterdam (Netherlands), 2000. V. 33. P. 309–320.
9. Faloutsos M., Faloutsos P., Faloutsos C. On power-law relationships of the internet topology // Proc. ACM conference on applications, technologies, architectures and protocols for computer communications. Cambridge (USA), August 30-September 03, 1999. P. 251–262. Available at: http://www.cs.cmu.edu/~christos/publications/sigcomm99.pdf
10. Watts D. J., Strogatz S. H. Collective dynamics of ‘‘small-world’’ networks // Nature. 1998. V. 393. P. 440–442.
11. Newman M. E. J. The structure and function of complex networks // SIAM Review. 2003. V. 45. P. 167–256.
12. Ebel H., Mielsch L. I., Bornholdt S. Scale-free topology of e-mail networks // Phys. Rev. E. 2002. V. 66, 035103.
13. Albert R., Barabasi A. L. Statistical mechanics of complex networks // Reviews of Modern Physics. 2002. V. 74. P. 47–97.
14. Burt R. S. The Social structure of competition. Cambridge, MA: Harvard University Press, 1992.
15. Csárdi G., Nepusz T. The igraph software package for complex network research // InterJournal Complex Systems. 2006. 1695 P. Available at: http://igraph.org/r/doc/.
16. Network analysis. Methodological Foundations. 2005. Springer, LNCS 3418.
17. Meilă M., Pentney W. Clustering by weighted cuts in directed graphs // Proc. of the 2007 SIAM International Conference on Data Mining, Minneapolis (USA), Apr. 26-28, 2007. P. 135–144.
18. Marshakova I. V. Sistema svyazey mezhdu dokumentami, postroennaya na osnove ssylok: po dannym Science Citation Index // Nauch-Techn.Inform, ser.2. 1973. № 6. S. 3–8.
19. Small H. Co-citation in the scientific literature: A new measure of the relationship between two documents // J. Amer. Soc. Inform. Sci. 1973. V. 24, iss. 4. P. 265–269.
20. Kessler M. M. Bibliographic coupling between scientific papers // Amer. Documentation. 1963. V.14, iss.1. P. 10–25.
21. Satuluri V., Parthasarathy S. Symmetrizations for clustering directed graphs // Proc. 14th Internat. Conference on extending database technology. Uppsala (Sweden), March 21-25, 2011. P. 343–354. Available at: http://dblp.uni-trier.de/db/conf/edbt/edbt2011.html.
22. Kleinberg J. M. Authoritative sources in a hyperlinked environment // J. of the ACM. 1999. V. 46, iss. 5. P. 604–632.
23. Zhou D., Schulkopf B., Hofmann T. Semi-supervised learning on directed graphs // Advances in Neural Information Processing Systems Conference, 2005. 5–8 December, Vancouver (Canada). P. 1633–1640.
24. Guimerа R., Pardo M. S., Amaral L. A. N. Module identification in bipartite and directed networks // Phys. Rev. E 76 (3) 036102+. 2007.
25. Newman M. E. J., Girvan M. Finding and evaluating community structure in networks // Phys. Rev. 2004. E 69 (2) 026113.
26. Newman M. E. J. Fast algorithm for detecting community structure in networks // Phys. Rev. 2003. E 69 066133.
27. Arenas A., Duch J., Fernández A., Gómez S. Size reduction of complex networks preserving modularity // New J. Phys. 2007. V. 9, N. 6. P. 176–190.
28. Leskovec J., Lang K.J., Dasgupta A., Mahoney M.W. Statistical properties of community structure in large social and information networks // Proc. of the 17th International Conference on World Wide Web, Beijing (China), April 21–25, 2008. P. 695–704.
29. Yang Y., Leskovec J. Overlapping community detection at scale: A nonnegative matrix factorization approach // Proc. of the Sixth ACM International Conference on Web Search and Data Mining, Rome (Italy), Feb. 6–8, 2013. P. 587–596.
30. Meila M. Comparing clustering by the variation of information // Proc. of 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Washington, (USA), August 24–27, 2003. P. 173–187.
31. Fred A. L. N., Jain A. K. Robust data clustering // Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Minneapolis (USA), June 16–22, 2003. P. 128–136.
32. Girvan M., Newman M. E. J. Community structure in social and biological networks // Proc. Nat. Acad. Sci. USA. 2002. V. 99. P. 7821–7826.
33. Pons P., Latapy M. Computing communities in large networks using random walks // J. Graph Algorithms and Applications. 2006. V. 10, N 2. P. 191–218.
34. Chen J., Yuan B. Detecting functional modules in the yeast protein-protein interaction network // Bioinformatics. 2006. V. 22, iss. 18. P. 2283–2290.
35. Raghavan U. N., Albert R., Kumara S. Near linear time algorithm to detect community structures in large-scale networks // Phys. Rev. E 76, 036106. 2007.
36. Blondel V. D., Guillaume J. L., Lambiotte R., Lefebvre E. Fast unfolding of community hierarchies in large networks // J. Stat. Mech. 2008. P10008.

Bibliographic reference: Bredikhin S. V.,Lyapunov V. M., Shcherbakova N. G. The structure of the citation network of scientific publications //journal “Problems of informatics”. 2016. № 3. P. 26-43.

Article

Zaripova G.I.

Samarkand State University, 140104, Samarkand, Uzbekistan

ENSURING THE AUTHENTICITY OF DATA PROCESSING ON THE BASIS OF IDENTIFICATION OF NON-STATIONARY OBJECTS IN CONDITIONS OF UNCERTAINTY OF REGULAR ERROR FACTORS

UDC 658.512.011

Probability structure of information authenticity is the main reason for complexity of solving the problems of identification of non-stationary objects; improve the performance of automated control systems to technological processes, and also ensuring of efficiency of data processing. Thus, significant factors that reduce authenticity of data transfer and processing become non-stationarity of processes, insufficiency of priory knowledge and large parametrical uncertainty in models to describing objects [1, 2].

In this context, development of methodical bases to constructing methods and software-algorithmic complexes for improve the authenticity of data processing, taking into account kind, properties, distribution laws, regular error represent actual scientific and technical problem [2, 3].

In traditional approaches to development of methods to improve the authenticity of information the solutions of tasks are gotten on the basis of statistical and dynamic modeling, algorithmic implementation and experimental studies with extensive a priory data. Thus the most typical statistical characteristics of factors used for estimation of the regular error are mathematical expectation, mean-squared deviation, distribution laws, auto correlation functions, coefficients of pair and mutual correlation connections, other dynamic characteristics of random time series (RTS), describing non-stationary objects [3].

Feature of the present issue is the development of methodical bases for multivariate analysis of regular error function in methods of RTS’ identification and approximation on the basis of mechanisms to revealing and use statistical, dynamic characteristics of information and probabilities of errors’ distribution with limited retrospective data of information process.

The offered approach to ensure the authenticity of data assumes search of extremum of influences function, creating in future an opportunity to evaluate the minimal regular error of RTS identification. Thus the regular error of identification on model of non-stationary objects is represented by the sum of additional factor errors caused at each stage of information transformation [4, 5].

The technique of multivariate analysis is developed on the basis of identification of non-stationary objects in view of estimates of influence degree on a regular error on all stages of information processes. The structural components of the influencing factors are considered. The models and algorithms of RTS identification are developed on the basis of account of a regular error according to given technique.

Functions in the form of regression dependences are used as model of identification and approximations of non-stationary object and in them estimates of error are defined by parameters of mathematical expectation and mean-squared deviation with the normalized level of influencing factor coefficient’s sign.

The perspective and effective approach is offered to improve the authenticity of data processing by overlapping opportunities of statistical and dynamic models of identification with methods to estimate influence factors on a regular error. Questions of synthesis of statistical and dynamic models for non-stationary objects identification are investigated as the basic fundamentals of methods to improve the authenticity of non-stationary objects’ data.

With the purpose of a regular error reduction during RTS identification the technique is offered to use the method checking observance the balance ratio entered into structure of dynamic model of non-stationary object. To optimize the analysis and processing of data in structure of dynamic model for non-stationary object identification the additional balance ratio are entered, and they are set based on normative requirements revealed on a long enough time interval. The mathematical model is formalized for identification of non-stationary object with procedures of check of observance of balance ratio. The check of observance of balance ratio in dynamic models of identification of non-stationary object is carried out by method of target shift of RTS sequence values inside a range of probability distribution with account iteratively, conditions of non-stationarity and parametrical uncertainty.

The general solution of task is gotten in the form of continuous and differentiable by all variable equations. The algorithm is developed for identification of non-stationary objects by correcting balance ratio with linear dynamic equations.
The method to dynamic identification is investigated under various distribution laws for a regular error and properties of RTS non-stationarity. The composition of specific characteristics of input variable, models and algorithms to control of a regular error, adjustment and correction of parameters of model are determined and also obtained estimates of minimization of RTS dispersion and target parameters are investigated. It is proved, that realization of methods to synthesis models of multivariate influences of a regular error with dynamic model of non-stationary object, methods to improve information authenticity by check and correction of balance ratio contribute to achieving improve the stability of identification, and also efficiency of data analysis and processing.

References

1. Zaripova G.I. Adaptivniy kontrol dostovernosti texnologicheskix parametrov na osnove modeley nechetkogo vivoda [The adaptive control of technological parameters authenticity on the basis of fuzzy conclusion models] // Materiali VIII mejdunarodnoy nauchno-prakticheskoy konferenciyi «Nauchnaya diskussiya: voprosi texnicheskix nauk», Moskva: «Mejdunarodniy centr nauki i obrazovaniya», 2013. – pp. 31-37.
2. Miroshnik I.V., Nikiforov V.O., Fradkov A.L. Nelineynoe i adaptivnoe upravleniye slojnimi dinamicheskimi sistemami [Nonlinear and adaptive management of complex dynamic systems] - S-Pb.: Nauka, 2000. -314 p.
3. Mif N.P. Modeli i osenki pogreshnosti texnixheskix izmereniy. [Models and estimations of error of technical measurements] – M.: Standarti, 1976. – 144p.
4. Igamberdiyev X.Z., Sevinov J.U., Zaripov O.O. Regulyarniye metodi i algoritmi sinteza adaptivnix system upravleniya s nastraivayemimi modelyami. [Regular methods and algorithms to synthesis adaptive control systems with adjusted models]. - T.: TashGTU, 2014. - 160 p.
5. Karabutov N.N. Adaptivnaya identifikasiya system. Informasionniy sintez. [Adaptive identification of systems. Information synthesis].-M.: Kom Kniga, 2006. - 384p.
6. Zaripova G.I., Akhatov A.R. Methods and Algorithms to Control Information Authenticity during Transfer and Handling of Data of Continuous Objects on the basis of a Neuro-Fuzzy Network // 2013 International Conference in Central asia on Internet (ICI), Tashkent, 8-10 october 2013, Section 7, IEEE. – Tashkent, 2013. – p.12-18.
7. Jumanov I.I., Abdullayev A.N. Kontrol tochnosti peredachi informasii v sistemax avtomatizasii izmereniya I obrabotki dannix nestasionarnoy prirodi [Control of accuracy of information transfer in systems for automation measurement and processing of non-stationary nature data] // «Intellektualniye sistemi dlya industrialnoy avtamatizasii» WCIS – 2006, TGTU, Tashkent. – pp. 213-218.
8. Yarushkina N.G. Osnovi nechotkix i gibridnix sistem. [Bases of fuzzy and hybrid systems]. – Uchebnoye posobiye. – M.: Finansi i statistika. 2004. - 320 p.

Bibliographic reference: Zaripova G.I. Ensuring the authenticity of data processing on the basis of identification of non-stationary objects in conditions of uncertainty of regular error //journal “Problems of informatics”. 2016. № 3. P. 44-58.

Article

Kazancev G. Yu., Omarova G. A.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, 630090, Novosibirsk, Russia

SIMULATION OF TRAFFIC FLOWS USING CELLULAR AUTOMATA

UDC 519.179.2—512.23

Simulation of transport systems is the demanded task in control of road networks helping to make decisions on further development and extension of transport system. In particular, simulation allows defining need for extension of a road network or adding of means of regulation. In this paper, traffic is simulated according to the cellular automaton of the Nagel-Scheckenberg model. It was the first model to take into account the imperfect behavior of human drivers and was thus the first model to explain the spontaneous formation of traffic jams. Now application of cellular automaton is also actual for simulation and research of different road situations and behavior of pedestrians. This model satisfies to traffic regulations in ideal conditions, when all machines move with the fixed speed and all drivers follow rules.

The Nagel-Scheckenberg model is a one-dimensional stochastic machine designed to simulate traffic. The model dimensional grid used in each cell is placed exactly one machine, the cell is either empty or contains a car. Time is discrete, the machine moves to forward an integral number of cells for each step of iteration. At each step of the iteration for each car in turn all the rules are applied. The first rule is responsible for aspiration of drivers to go as soon as possible, without violating the rule, the second rule doesn't allow collisions, and the third rule introduces an element of randomness in the motion of each driver. This rule set is the minimum set necessary for reproduction of basic properties of a transport flow. The main advantage of this model is its simplicity compared with other approaches; it is important in the transition to more complex structures, such as multi-row model or models including intersections. Both of these generalizations require a transition to a two-dimensional grid and seriously complicate the process of updating the machine state, as multiband movement also requires at each step to assess the need and possibility to change the band, and also requires a method of resolving the conflict when you attempt to move in one cell from two different neighboring bands. Creation of the intersection, results in need to process movement in the non-parallel directions through the same cells that can be realized through the cells containing only part of the machine. Besides creation of the intersection it is necessary to consider a priority of roads that can seriously complicate rules of transition or procedure of their application. For implementation of the intersection the following cellular automaton was defined.

Cellular automaton CA=<A,C,M,X,T>, A – set of statuses of a cell, C – set of cells, M – transition function that changes the state of the automaton, X – neighborhood relation, T – set of clock periods of time. Each object is characterized by two parameters – the direction of movement and the identifier. Cells belonging to the set C, are determined by two different sizes of the full and half. One object occupies one cell of the complete size or two cells of the half size. The neighborhood ratio X is not the same in different cells and strongly depends on the position of the cells relative to intersections. For determination of M we introduce rules for all cells, after that we define application of M on some configuration of the automatic machine as, application of rules of cells in a certain order.

Functions for operation with the cellular automaton: Rules(ci) – set of rules of a cell ci, Name(rij) – rule name rij in Rules(ci). Imp(rij) and Next(rij) – set of important and following cells for the rule. The basic rules have the general structure. The structure of additional rules for the second part of object is available only for cells of the half size. As for these cell it is necessary to distinguish objects from each other, for this purpose we enter the Id function returning an object identifier. The rule for an empty cell is trivial - the cell doesn't influence adjacent cells and doesn't change the statuses without influence of other cells. Each cell has rule set for movement through it in any the allowed direction, according to traffic regulations.

A cellular automaton for traffic simulation on a group of intersections was designed. The program of generation of the cellular automaton for different intersections was realized.
The models can be used to understand, predict and optimize different traffic situations and as examples for the various possible extensions and fields of applications.

Key words: Model, cellular automata, distance, speed, acceleration, regular grid.

References

1. Kravchenko P. S., Omarova G. A. Mikroskopicheskie matematicheskie modeli transportnyh potokov. Analiticheskij obzor [ZHurnal Problemy informatiki] N 1. 2014, s.71–78.
2. Gasnikov A.V. i dr., Vvedenie v matematicheskoe modelirovanie transportnyh potokov [ MFTI Moskva ] 2010.
3. SHvecov V. I. Matematicheskoe modelirovanie transportnyh potokov. [Avtomatika i Telemekhanika] 2003, N 11, s. 3–46.
4. Dzh. fon Nejman. Teoriya samovosproizvodyashchihsya avtomatov. [M.: <Mir>], 1971.
5. Cremer M., Ludwig J. A fast simulation model for traffic flow on the basis of Boolean operations [Math. Comp Simul.] 1986. V. 28. P. 297–303.
6. Nagel K., Schreckenberg M. A cellular automation model for freeway traffic [Phys. I France.] 1992. V. 2. P. 2221–2229.
7. Simon P. M., Gutowitz H. A. A Cellular Automaton Model for Bi-Directional
8. Traffic. [Phys. Rev.] E 57, 2441, 1998.
9. Nowak S., Schadschneider A. A Cellular Automaton Approach for Lane Formation in Pedestrian Counterflow [Traffic and Granular Flow] '11, pp 149–160.
10. Torsten Held, Stefan Bittihn: Cellular automata for traffic simulation - Nagel-Schreckenberg model. [Computational Physics], Bonn, 2011.
11. Hafstein S. F., Chrobok R., Pottmeier A., Wahle J., Schreckenberg M. A High Resolution Cellular Automata Traffic Simulation Model with Application in a Freeway Traffic Information System [Computer-Aided Civil and Infrastructure Engineering], Volume 19, Issue 5, pages 338–350, 2004.
12. Zamith M., R. C'elia P. Leal - Toledo, M. Kischinhevsky, E. Clua, D. Brand'ao, A. Montenegro, Edgar B. Lima: A Probabilistic Cellular Automata Model for Highway Traffic Simulation [Procedia Computer Science] 1, 2012, pp. 337–345.
13. Omarova G. A., Kazantsev G. YU. Primeneniye kletochnykh avtomatov dlya odelirovaniya transportnykh potokov . [Zhurnal Problemy informatiki] N 3. 2015 , s.15–21 .

Bibliographic reference: Kazancev G. Yu., Omarova G. A. Simulation of traffic flows using cellular automata //journal “Problems of informatics”. 2016. № 3. P. 59-69.

Article

Krutikov N. O., Podakov N. G., Zhilyakova V. A.

Novosibirsk national research state university, 630090, Novosibirsk, Russian Federation

DEVELOPMENT OF THE INFORMATION EXTRACTION SYSTEM FROM TEXTS IN RUSSIAN FOR SUBJECT DOMAIN CRIMINALISTICS

UDC 004.852

This article describes an approach to Russian language information extraction systems development presented for subject domain Criminalistics.At first; we should describe the task in details. The developed system should extract named entities from the text, such as people and organizations, and events. Also, attributes of the extracted entities, such as name, gender and date of birth for individuals and name and type of organization, time and place for the event should be filled. Relationships between named entities and events should be extracted; semantic role should be defined for each dependent entity (for example “subject” and “object” of event). Different semantic entities that describe single real object (person, organization or event) must be glued together by resolving coreference, their attributes should be united.

For text analysis RCO FX Ru library is used in system. This library used rule-based approach and provides the following results: list of the extracted from the text semantic entities, their morphological and syntactic attributes and semantic graph of each proposal.To resolve the problem corpus of texts has been builded, domain ontology has been developed and a system of rules and patterns based on the RCO FX has been realized. After processing texts are translated to RDF structure and saved in RDF store.Also, the system has visualization module that allows the user to view text analysis results, search among the extracted information, and use a variety of filters that discard the most important information.The approach allows extract information from texts with level precision 70–80 % with recall 30–35 %.

Key words: information extraction, rule-based approach, CAPE, named entity, event extraction, relation extraction, ontology.

References

1. RCO Fact Extractor SDK.[Electron. resource]. http://www.rco.ru/?page_id=3554 (Accessed 11.05.2016).
2. Tomita-parser/ Yandex. Website of the Tomita-parser technology. [Electron. resource]. https://tech.yandex.ru/tomita/ (Accessed 11.05.2016).
3. GitHub - yandex/tomita-parser / GitHub, Inc. Open source code of the Tomita-parser project. 2016. [Electron. resource].https://github.com/yandex/tomita-parser/ (Accessed 11.05.2016).
4. About ABBYY Compreno technology / ABBYY.Describing ABBYY Intelligent Search SDK technology. 2016. [Electron. resource].http://www.abbyy.ru/isearch/compreno/ (Accessed 11.05.2016).
5. PolyAnalyst – data analysis. Text analysis / Megaputer Intelligence, Inc.Website of thePolyAnalyst product 2015.[Electron. resource].http://megaputer.ru/polyanalyst.php (Accessed 11.05.2016).
6. ApacheJena / TheApacheSoftwareFoundation. Website of theApacheJena project. 2015. [Electron. resource].https://jena.apache.org/ (Accessed 11.05.2016).
7. OpenRdfSesame. [Electron. resource].http://www.openrdf.org/ (Accessed 01.03.2016).
8. dotNetRdf – SemanticWeb, RDFandSPARQLLibraryforC#/.NET / RobVesse. Website of thedotNetRdf project.2015. [Electron. resource].http://dotnetrdf.org/ (Accessed 11.05.2016).
9. Kormalev D. A. Obobshenie i specializatsiya pri postroenii pravil izvlecheniya informatsii// Conference. KII–2006.Т.2. M.: Phismatlit, 2006. P. 572–579.
10. Kurshev E. P., Kormalev D. A., Suleymanova E. A., Trofimov I. V. Issledovanie metodov izvlecheniya informatsii iz tekstov s ispolzovaniem avtomaticheskogo obucheniya i realizatsiya issledovatelskogo prototipa sistemi izvlecheniya informatsii // Matematicheskie metodi raspoznovaniya obrazov: 13All-RussianConference. Leningrad region, Zelenogorsk, 30th of September – 6th of October 2007: Reports collection. M.: MAKS Press, 2007. P. 602–605.
11. Ermakov A. E. Izvlechenie znaniy iz texta i ih obrabotka: sostoyanie i perspektivi // Information technologies. 2009. N 7.
12. Simakov K. V. Modeli i metodi izvlecheniya znaniy iz tekstov na estesstvennom yazike. Candidate of Technical Sciences dissertation: 05.13.17. M. 2008.
13. AndreevA. M., Berezkin D. V., Simakov K.V. Metod obucheniya modeli izvlecheniya znaniy iz estesstvennoyazikovih tekstov //Vestnik MGTU. Instrumentation. 2007. N 3. P. 75–94.
14. Tolpegin P. V. Novie metodi I algoritmi avtomaticheskogo razresheniya referentsii mestoimeniy tretiyego litsa russkoyazichnih tekstov. M.: KomKniga, 2006. P. 88.
15. The results of the competition Dialogue 2016 on the extraction of named entities [Electron. resource].

http://pullenti.ru/DownloadFile.aspx?file=FactRuEval.pdf // (Accessed 29.05.2016).
16. Brat rapid annotation tool [Electron. resource].http://brat.nlplab.org/ (Accessed29.03.2016).
17. Conference materials DIALOGUE 2014 [Electron. resource].http://www.dialog-21.ru/dialogue2014/results // (Accessed 29.05.2016).
18. RU-EVAL-2014: Evaluating Anaphora and Coreference Resolution for Russian [Electron. resource]. http://www.dialog-21.ru/digests/dialog2014/materials/pdf/ToldovaSJu.pdf // (Accessed29.05.2016).

Bibliographic reference: Krutikov N. O., Podakov N. G., Zhilyakova V. A. Development of the information extraction system from texts in russian for subject domain criminalistics //journal “Problems of informatics”. 2016. № 3. P. 70-84.

Article

Matveev A. S., Nikitin * V.V. , Romanenko** A. A., Duchkov A. A.
IPGG SB RAS, 630090, Novosibirsk, Russia
*NSU, 630090, Novosibirsk, Russia
** Center for Mathematical Sciences, Lund University, 22100, Lund, Sweden

EFFECTIVE IMPLEMENTATION OF USFFT ALGORITHM

UDC 621

This article is devoted to the Unequispaeed Fast Fourier Transform (USFFT), which is a popular analytical tool for solving physics and engineering problems. The most common applications of the transform include seismology, optics, computed tomography, crystallography, etc. Despite the favorable computational complexity of the USFFT algorithm (0(N logN)), the execution time remains rather high due to the algorithm structure and large input data sizes. There are two main types of USFFT: Fourier transform from equispaeed grid to unequispaeed grid and Fourier transform from unequispaeed grid to equispaeed grid. Corresponding computational algorithms consist of three main steps: convolution, Fast Fourier Transform (FFT) and deconvolution. Profiling shows that up to 95% of execution time is spent on the convolution step. In this paper, we propose a parallel USFFT algorithm and its effective cache-optimized implementation on CPU for one-, two- and three-dimensional cases. Cache performance optimization is based on the sorting of unequispaeed grid points. The constructed sorting procedure sufficiently reduces the number of cache misses. For instance, for the two-dimensional ease the number of cache misses is reduced by 36 times, which results in 2x speed-up of the transform evaluation. Next, we propose a parallel block algorithm for the convolution step and implement it by making use of OpenMP, a popular extension for the С programming language supporting multiplatform shared memory parallel programming. The obtained parallel implementation was optimized in terms of optimal block sizes and type of scheduling for the convolution step. Numerical tests show high parallel efficiency: speed-up on 16 processors compared to the sequential implementation is approximately equal to 13. The tests also show that the performance is several times higher than the performance of the commonly-used library for the fast Fourier transform at nonequispaeed nodes (NFFT 3.0). USFFT is commonly used for fast evaluation of the Radon transform operator which is one of the main mathematical tools in computed tomography. In this paper, we consider a standard reconstruction of tomography data by inversion of the Radon transform, and an iterative reconstruction by using the Expectation-maximization algorithm. The iterative reconstruction is well-suited for processing data with [21] or irregularly-structured data. Since iterative schemes assume applying the forward and adjoint Radon operators several times, computational times for preprocessing procedures such as sorting of grid points and allocation memory can be diminished. The obtained program for evaluating iterative schemes was tested for synthetic Radon data containing Poisson noise. The program outperforms the implementation via NFFT by 4.4 times for the same accuracy level.

Key words: fast Fourier transform, unequispaeed grids, parallel algorithm, optimization, high performance computing.

References

1. Cooley J. W., Tukev J. W. An algorithm for the machine calculation of complex Fourier series // Mathematics of computation. 1965. T. 19. N 90. P. 297-301.
2. Intel Math Kernel Library (Intel MKL) (El. res.] // https://software.intel.com/en-us/ intel-mkl
3. cuFFT | NVIDIA Developer (El. res.] // https://developer.nvidia.com/cufft
4. FFTW Home page (El. res.] // http://www.fftw.org
5. Bracewell R. N. Strip integration in radio astronomy // Australian Journal of Physics. 1956. T. 9. N 2. P. 198-217.
6. Duchkov A. A., Andersson F., De Hoop М. V. Discrete almost-symmetric wave packets and multiscale geometrical representation of ((8]) waves // Geoscience and Remote Sensing, IEEE Transactions on. 2010. T. 48. N 9. P. 3408-3423.
7. Bevlkin G., Burridge R. Linearized inverse scattering problems in acoustics and elasticity // Wave motion. 1990. T. 12. N 1. P. 15-52.
8. Zwartjes P. М., Sacchi M. D. Fourier reconstruction of nonuniformlv sampled, aliased seismic data // Geophysics. 2006. T. 72. N 1. P. V21-V32.
9. Dutt A., Rokhlin V. Fast Fourier transforms for nonequispaced data // SIAM Journal on Scientific computing. 1993. T. 14. N 6. P. 1368-1393.
10. Bevlkin G. On the fast Fourier transform of functions with singularities // Applied and Computational Harmonic Analysis. 1995. T. 2. N 4. P. 363-381.
11. Greengard L., Lee J. Y. Accelerating the nonuniform fast Fourier transform // SIAM review. 2004. T. 46. N 3. P. 443-454.
12. Fessler J. A., Sutton B. P. Nonuniform fast Fourier transforms using min-max interpolation // Signal Processing, IEEE Transactions on. 2003. T. 51. N 2. P. 560-574.
13. NUFFT page (El. res.] // http://www.cims.nyu.edu/cmcl/Clll/nufft.html
14. NFFT — TU Chemnitz (El. res.] // https://www-user.tu-chemnitz.de/$\sim$potts/nfft/
15. Andersson F. Algorithms for unequally spaced fast Laplace transforms // Applied and Computational Harmonic Analysis. 2013. T. 35. N 3. P. 419-432.
16. Herman G. Т., Louis A. K., Natterer F. (ed.). Mathematical methods in tomography: proceedings of a conference held in Oberwolfach, Germany, 5-11 June, 1990. Springer, 2006.
17. Yilmaz O. Seismic data analysis. Tulsa : Society of exploration geophysicists, 2001. T. 1. P. 74170-2740.
18. Tretiak O., Metz C. The exponential Radon transform // SIAM Journal on Applied Mathematics. 1980. T. 39. N 2. P. 341-354.
19. Natterer F. Inversion of the attenuated Radon transform // Inverse problems. 2001. T. 17. N 1. P. 113.
20. Shepp L. A., Logan B. F. The Fourier reconstruction of a head section // Nuclear Science, IEEE Transactions on. 1974. T. 21. N 3. P. 21-43.
21. Barrett H. H., Wilson D. W., Tsui В. M. W. Noise properties of the EM algorithm. I. Theory // Physics in medicine and biology. 1994. T. 39. N 5. P. 833.
22. Yan М., Vese L. A. Expectation maximization and total variation-based model for computed tomography reconstruction from undersampled data // SPIE Medical Imaging. International Society for Optics and Photonics, 2011. P. 79612X-79612X-8.
23. Champlev K. SPECT reconstruction using the expectation maximization algorithm and an exact inversion formula: дис. MS Thesis, Oregon State University, 2004.
24. Dempster А. P., Laird N. N4., Rubin D. В. Maximum likelihood from incomplete data via the EM algorithm // Journal of the royal statistical society. Series В (methodological). 1977. P. 1-38.
25. Miqueles E. X., Helou E. S., De Pierro A. R. Generalized Backprojection Operator: Fast Calculation // Journal of Physics: Conference Series. IOP Publishing, 2014. T. 490. N 1. P. 012148.

Bibliographic reference: Matveev A. S., Nikitin V.V. , Romanenko A. A., . Duchkov A. A Effective implementation of usfft algorithm //journal “Problems of informatics”. 2016. № 3. P. 85-102.

Article

Main menu

You are here

2016 № 3 (32)

Сontents