2. Home
  3. ARCHIVE
  4. 2018
  5. VOL 40, NO 2 (2018)
  6. Архив номеров
  7. 2017 год
  8. 39-3

Electronic Modeling

Vol 39, No 3 (2017)

https://doi.org/10.15407/emodel.39.03

CONTENTS

Mathematical Modeling and Computation Methods

  FEYZIYEV F.G., MEKHTIYEVA M.R., HUSEYNOVA A.J.
The Two-valued Analogue of Volterra Polynomial for Description of Full Reaction of Binary Multidimensional Nonlinear Modular Dynamic Systems
3-16
  LISTROVOY S.V., SIDORENKO A.V., LISTROVAYA E.S.
The Method of Determining the Largest Maximal Independent Sets of Vertices of Undirected Graph
17-36
  HUSEYNZADE S.O.
On a Method of Modeling of Gas-Water Drive Mode of Layers
37-46

Computational Processes and Systems

  SAPOZHNIKOV V.V., SAPOZHNIKOV Vl.V., EFANOV D.V.
Codes with Summation Detecting Any Symmetric Errors
47-60
  KALINOVSKY Ya.A., BOYARINOVA Yu.E.
The Metod for Research of Isomorphism of Indecomposable Hypercomplex Number Systems
61-76 

Application of Modeling Methods and Facilities

  KRAVTSOV H.A.
The Calculus over Classifications. Selection of Personnel as Interpretation of the Problem of Expert Selection
77-88
  DUNAYEVSKA N.I., ZASIADKO Ya.I., ZASIADKO P.Ya., SHCHUDLO T.S.
Mathematical Model of the Processes of Biomass and Coal Co-Firing in TPP Boilers
89-104
  OGIR A.S., OGIR E.A.
The Procedure of Filtering Diagnostic Images to Enhance their Informativeness
105-118

Chronicle and Information

Color figures to the articles are in the insets

THE TWO-VALUED ANALOGUE OF VOLTERRA POLYNOMIAL FOR DESCRIPTION OF FULL REACTION OF BINARY MULTIDIMENSIONAL NONLINEAR MODULAR DYNAMIC SYSTEMS

F.G. Feyziyev, M.R. Mekhtiyeva, A.J. Huseynova

Èlektron. model. 2017, 39(3):03-16
https://doi.org/10.15407/emodel.39.03.003

ABSTRACT

The construction of a two-valued analogue of Volterra polynomial for description of full reaction of binary multidimensional nonlinear modular dynamic systems is considered. The recurrence formulas are presented for determining coefficients of this polynomial at certain values of the input and output sequences of multidimensional nonlinear modular dynamic systems.

KEYWORDS

multidimensional nonlinear modular dynamic system, two-valued analogue of Volterra polynomial, the recurrence formulas.

REFERENCES

1. Faradjev, R.G. (1975), Lineynye posledovatelnoctnye mashiny [Linear sequential machines], Sovetskoe radio, Moscow, Russia.
2. Blyumin, S.L. and Faradjev, R.G. (1982), “Linear cellular machines: The approach of the state space (review)”, Avtomatika i telemekhanika, no 2, pp. 125-163.
3. Faradjev, R.G. and Feyziyev, F.G. (1996), Metody i algoritmy resheniya zadachi kvadratichnoy optimizatsii dlya dvoichnykh posledovatelnostnykh mashin [Methods and algorithms for solving quadratic optimization problem for binary sequential machines], Elm, Baku, Azerbaijan.
4. Feyziyev, F.G. and Faradjeva, M.R. (2006), Modulyarnye posledovatelnostnye mashiny: Osnovnye rezultaty po teorii i prilozheniyu [Modular sequential machines: The main results in the theory and application], Elm, Baku, Azerbaijan.
5. Feyziyev, F.G. and Samedova, Z.A. (2011), “Polynomial ratio to represent the full reaction 3Dnonlinear modular dynamical systems”, Elektronnoe modelirovanie, Vol. 33, no. 2, pp. 33-50.
6. Blyumin, S.L. and Korneyev, A.M. (2005), Diskretnoye modelirovaniye system avtomatizatsii i upravleniya: Monografiya [Discrete modeling of automation and control systems: Monograph], Lipetsk Ekologo-gumanitarny institut, Lipetsk, Russia.

Full text: PDF (in Russian)

THE METHOD OF DETERMINING THE LARGEST MAXIMAL INDEPENDENT SETS OF VERTICES OF UNDIRECTED GRAPH

S.V. Listrovoy, A.V. Sidorenko, E.S. Listrovaya

Èlektron. model. 2017, 39(3):17-36
https://doi.org/10.15407/emodel.39.03.017

ABSTRACT

A method of search for the largest maximal independent sets of an undirected connected graph is proposed that allows one to solve the problem of determining the largest maximal independent sets in polynomial time with the number of vertices in the graph not exceeding 120 and the density of edges in the range from 0.067 to 0.9. with a further increase in the number of vertices and a decrease in the density of edges in the graph, the algorithm has an exponential complexity that does not exceed at an average O (20,4n), which tends to the decrease with increasing the edge density in the graph, where n is the number of vertices in the graph.

KEYWORDS

maximal independent set, click, the top cover.

REFERENCES

1. Harary, F. and Ross, I.C. (1957), “A procedure for clique detection using the group matrix”, Sociometry, Vol. 20, pp. 205-215.
https://doi.org/10.2307/2785673
2. Butenko, S. and Wilhelm, W.E. (2006), “Clique-detection models in computational biochemistry and genomics”, European Journal of Operational Research, Vol. 173, pp. 1-17.
https://doi.org/10.1016/j.ejor.2005.05.026
3. Raymond, J.W. and Willett, P. (2002), “Maximum common subgraph isomorphism algorithmsmatching chemical structures”, Journal of Computer-Aided MolecularDesign,Vol. 16, pp. 521-533.
4. Varmuza, K., Penchev, P.N. and Scsibrany, H. (1998), “Maximum common substructures of
organic compounds exhibiting similar infrared spectra”, J. Chem. Inf. Comput. Sci., Vol. 38,
pp. 420-427.
5. Horaud, R. and Skordas, T. (1989), “Stereo correspondence through feature grouping and maximal cliques”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 11, no. 11.
6. Pelillo, M., Siddiqi, K. and Zucker, S.W. (1999), “Matching hierarchical structures using association graphs”, IEEE Trans. Pattern Anal. Mach. Intell., Vol. 21, no. 11.
7. Shearer, K., Bunke, H. and Venkatesh, S. (2000), Video indexing and similarity retrieval by largest common subgraph detection using decision trees, IDIAP-RR 00-15, Dalle Molle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland.
8. Shirinivas, S.G., Vetrivel, S. and Elango, N.M. (2010), “Application of graph theory in computer science an overview”, International Journal of Engineering Science and Technology, Vol. 2, no. 9, pp. 4610-4621.
9. Seliverstov, A.V. and Lyubetskiy, V.A. (2006), “Algorithm for the search for conservative segments of nucleotide sequences”, Informatsionnyie protsessy, Vol. 6, no. 1, pp. 33-36.
10. Bahadur, D.K.C., Akutsu, T., Tomita, E. and et al. (2002), “Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms”, Genome Inform., Vol. 13, pp. 143-152.
11. Carr, R.D., Lancia, G. and Istrail, S. (2000), Branch-and-cut algorithms for independent set problems: integrality gap and application to protein structure alignment. Technical report, Sandia National Laboratories, Albuquerque, NM (US); Sandia National Laboratories, Livermore, CA (US).
12. Harley, E., Bonner, A. and Goodman, N. (2001), “Uniform integration of genome mapping data using intersection graphs”, Bioinformatics, Vol. 17, pp. 487-494. 
13. Samudrala, R. and Moult, J. (1998), “A graph-theoretic algorithm for comparative modeling of protein structure”, J. Mol. Biol., Vol. 279, pp. 287-302.
https://doi.org/10.1006/jmbi.1998.1689
14. Tomita, E., Akutsu, T., Hayashida, M. and et al. (2003), “Algorithms for computing an optimal protein threading with profiles and distance restraints”, Genome Informatics, Vol. 14, pp. 480-481.
15. Bahadur, D.K.C., Tomita, E., Suzuki, J. and et al. (2005), “Protein sidechain packing problem: a maximum edge-weight clique algorithmic approach”, J. Bioinform Comput. Biol., Vol. 3, pp. 103-126.
https://doi.org/10.1142/S0219720005000904
16. Jianer, C., Iyad, K.A. and Ge, X. (2010), “Improved parameterized upper bounds for vertex cover”, Elsevier: Theoretical Computer Science, Vol. 411, pp. 3736-3756.
17. Bron, C. and Kerbosch, J. (1973), “Algorithm 457: Finding all cliques of an undirected graph”, Comm. of ACM, Vol. 16, pp. 575-577.
https://doi.org/10.1145/362342.362367
18. Fomin, F.V., Grandoni, F. and Kratsch, D. (2006), “Measure and conquer: a simple O(20.288n ) independent set algorithm”, Proceedings of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006.
19. Robson, J.M. (1986), “Algorithms for maximum independent set”, Journal of Algorithms, Vol. 7, no. 3, pp. 425-440.
https://doi.org/10.1016/0196-6774(86)90032-5
20. Tarjan, R.E. and Trojanowski, A.E. (1977), “Finding a maximum independent set”, SIAM Journal on Computing, Vol. 6, pp. 537-546.
https://doi.org/10.1137/0206038
21. Moon, J.W. and Moser, L. (1965), “On cliques in graphs”, Israel J. Math., Vol. 3, pp. 23-28.
https://doi.org/10.1007/BF02760024
22. Pardalos, P.M. and Xue, J. (1994), “The maximum clique problem”, Journal of Global Optimization, Vol. 4, pp. 301-328.
https://doi.org/10.1007/BF01098364
23. Olemskoy, I.V. and Firyulina, O.S. (2014), “The algorithm for finding the largest independent set”, Vestnik, S.Pb. Universiteta, Ser. 10: Prikladnaya matematika, informatika, protsessy upravleniya, Iss. 1, pp. 81-91.
24. Plotnikov, A.D. (2012), “Heuristic algorithm for searching for the largest independent set”, Kibernetika i sistemnyi analiz, no. 5, pp. 41-48.
25. Listrovoy, S.V. (2014), “The method of enumeration of maximal independent sets in arbitrary non-oriented graphs”, Elektronnoe modelirovanie, Vol. 36, no. 1, pp. 3-17.
26. Listrovoy, S.V. and Minukhin, S.V. (2010), “General approach to solving optimization problems in distributed computing systems and theory of intelligence systems construction”, Journal of Automation and Information Sciences, Vol. 42, no. 3, pp. 30-46.
https://doi.org/10.1615/JAutomatInfScien.v42.i3.30
27. Listrovoy, S.V. and Minukhin, S.V. (2010), “A general approach to solving optimization problems in distributed computing systems and the theory of constructing intelligent systems”, Problemy upravleniya i informatiki, no. 2, pp.65-82.

Full text: PDF (in Russian)

ON A METHOD OF MODELING OF GAS-WATER DRIVE MODE OF LAYERS

S.O. Huseynzade

Èlektron. model. 2017, 39(3):37-46
https://doi.org/10.15407/emodel.39.03.037

ABSTRACT

The process of gas displacement by boundary water in the layer has been considered. The process is described by a nonlinear parabolic equation in a domain with a moving boundary. The problem of control of moving boundary is formulated as a boundary inverse problem, which consists in determining the mode of the operational gallery by a given law of motion of the moving boundary. Applying the method of straightening fronts based on transformation of independent variables, the domain of their determination is reduced to a rectangular form with fixed boundaries. A discrete analogue of the problem is proposed and computational algorithm is developed to solve the resulting system of linear algebraic equations.

KEYWORDS

as deposits, gas-water drive mode, the problem with moving boundary, the method of straightening of fronts, finite difference method.

REFERENCES

1. Charny, I.A. (1963), Podzemnaya gidrogazodinamika [Underground hydro-gas dynamics], Gostoptekhizdat, Moscow, USSR.
2. Basniev, K.S., Dmitriev, N.M. and Rosenberg, G.D. (2005), Neftegazovaya gidromekhanika [Oil and gas hydromechanics], Institut kompyuternykh issledovaniy, Moscow-Izhevsk, Russia.
3. Kanevskaya, R.D. (2002), Matematicheskoe modelirovanie gidrodinamicheskikh protsesov razrabotki mestorozhdeniy uglevodorodov [Mathematical modeling of hydrodynamic processes of development of hydrocarbon fields], Institut kosmicheskikh issledovaniy, Moscow-Izhesk, Russia.
4. Rubinshtein, L.I. (1967), Problema Stefana [Stefan problem], Zvaigzne, Riga, Latvian SSR.
5. Crank, J. (1984), Free and moving boundary problems, Clarendon Press, Oxford, UK.
6. Alexiades, V. and Solomon, A.D. (1993), Mathematical modeling of melting and freezing processes, Hemisphere Publ. Co, Washington DC, USA.
7. Meirmanov, A.M. (1986), Zadacha Stefana [Stefan problem], Nauka, Novosibirsk, USSR.
8. Samarskiy, A.A. and Vabishchevich, P.N. (2009), Chislennyie metody resheniya obratnykh zadach matematicheskoi fiziki [Numerical methods for solution of inverse problems of mathematical physics], LKI, Moscow, Russia.
9. Javierre-Perez, E. (2003), Literature study: Numerical methods for solving Stefan problems, Report 03-16, Delft University of Technology, Delft, USA.
10. Caldwell, J. and Kwan, Y.Y. (2004), Numerical methods for one-dimensional Stefan problems, Commun. Numer. Meth. Engng., no. 20, pð. 535-545.
https://doi.org/10.1002/cnm.691
11. Gamzaev, Kh.M. (2015), “Numerical solution of problem of unsaturated filtration with a moving boundary”, Elektronnoe modelirovanie, Vol. 37, no. 1, pp. 15-24.

Full text: PDF (in Russian)

CODES WITH SUMMATION DETECTING ANY SYMMETRIC ERRORS

V.V. Sapozhnikov, Vl.V. Sapozhnikov, D.V. Efanov

Èlektron. model. 2017, 39(3):47-60
https://doi.org/10.15407/emodel.39.03.047

ABSTRACT

Features of errors arising in separable codes data vectors have been considered. The classification of codes oriented to the 100% detection of specific type errors has been formed. Separable codes detecting any symmetric fault in data vector have been analyzed in detail. Conditions of formation of codes detecting all symmetric errors have been stated; some examples are given.

KEYWORDS

technical diagnostics of discrete systems, separable codes, Berger code, data vectors errors classification.

REFERENCES

1. Nicolaidis, M. and Zorian, Y. (1998), “On-line testing for VLSI – a compendium of approaches”, Journal of Electronic Testing: Theory and Applications, no. 12, pp. 7-20.
https://doi.org/10.1023/A:1008244815697
2. Mitra, S. and McCluskey, E.J. (2000), “Which concurrent error detection scheme to choose?”, Proceedings of International Test Conference, USA, Atlantic City, NJ, October 03-05, 2000, pp. 985-994.
3. Drozd, A.V. (2008), “Untraditional view of operational diagnostics of computing devices”, Problemy upravleniya, no. 2, pp. 48-56.
4. McCluskey, E.J. (1986), Logic Design Principles: With Emphasis on Testable Semicustom Circuits, Prentice Hall PTR, New Jersey, USA.
5. Sogomonyan, E.S. and Slabakov, E.V. (1989), Samoproveryaemyye ustroystva i otkazoustoychivye sistemy [Self-checking devices and fault-tolerant systems], Radio i svyaz, Moscow, Russia.
6. Pradhan, D.K. (1996), Fault-tolerant computer system design, Prentice Hall, New York, USA.
7. Fujiwara, E. (2006), Code design for dependable systems: Theory and practical applications, John Wiley & Sons, New Jersey, USA.
8. Lala, P.K. (2007), Principles of Modern Digital Design, John Wiley & Sons, New Jersey, USA.
9. Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1992), Samoproveryaemye diskretnye ustroystva [Self-checking discrete devices], St. Petersburg, Energoatomizdat, Russia.
10. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Cherepanova, M.R. (2016), “Modulo codes with summation in concurrent error detection systems. I. Ability of modulo codes to detect error in data vectors”, Elektronnoe modelirovanie, Vol. 38, no. 2, pp. 27-48.
11. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Cherepanova, M.R. (2016), “Modulo codes with summation in concurrent error detection systems. II. Decrease of hardware redundancy of concurrent error detection systems”, Elektronnoe modelirovanie, Vol. 38, no. 3, pp. 47-61.
12. Morosow, A, Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Goessel, M. (1998), “Self-checking combinational circuits with unidirectionally independent outputs”, VLSI Design, Vol. 5, Iss. 4, pp. 333-345.
https://doi.org/10.1155/1998/20389
13. Busaba, F.Y. and Lala, P.K. (1994), “Self-checking combinational circuit design for single and unidirectional multibit errors”, Journal of Electronic Testing: Theory and Applications, Vol. 5, Iss. 5, pp. 19-28.
https://doi.org/10.1007/BF00971960
14. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2015), “Errors classification in information vectors of systematic codes”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Priborostroenie, Vol. 58, no. 5, pp. 333-343. DOI 10.17586/0021-3454-2015-58-5-333-343.
15. Berger, J.M. (1961), “A note on error detecting codes for asymmetric channels”, Information and Control, Vol. 4, no. 1, pp. 68-73. DOI: 10.1016/S0019-9958(61)80037-5.
https://doi.org/10.1016/S0019-9958(61)80037-5
16. Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2010), “On sum code properties in functional control systems”, Avtomatika i telemekhanika, no. 6, pp. 155-162.
17. Bose, B. and Lin, D.J. (1985), “Systematic unidirectional error-detection codes”, IEEE Transactions on Computers, Vol. C-34, pp. 1026-1032.
18. Piestrak, S.J. (1995), Design of self-testing checkers for unidirectional error detecting codes, Oficyna Wydawnicza Politechniki Wroclavskiej, Wroclaw, Poland.
19. Sapozhnikov, V., Sapozhnikov, Vl. and Efanov, D. (2015), “Modular sum code in building testable discrete systems”, Proceedings of 13th IEEE East-West Design & Test Symposium (EWDTS`2015), Batumi, Georgia, September 26-29, 2015, pp. 181-187. DOI 10.1109/EWDTS.2015.7493133.
20. Dong, H. (1984), “Modified Berger codes for detection of unidirectional errors”, IEEE Transaction on Computers, Vol. C-33, June 1984, pp. 572-575.
21. Jha, N.K. and Vora, M.B. (1988), “A t-unidirectional errors-detecting systematic code”, Computers & Mathematics with Applications, Vol. 16, no. 9, pp. 705-714.
https://doi.org/10.1016/0898-1221(88)90006-5
22. Parhami, B. (1991), “New class of unidirectional error-detection codes”, Proc. of IEEE International Conference on Computer Design: VLSI in Computers and Processors. Oct. 14-16, 1991 (ICCD ‘9), Cambridge, MA, pp. 574-577.
23. Das, D. and Touba, N.A. (1999), “Weight-based codes and their application to concurrent error detection of multilevel circuits”, Proceedings of the 17th IEEE Test Symposium, USA, California, pp. 370-376.
https://doi.org/10.1109/VTEST.1999.766691
24. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Nikitin, D.A. (2015), “Research of sum codes with one weighted data bit properties in concurrent error detection systems”, Elektronnoe modelirovanie, Vol. 37, no. 1, pp. 25-48.
25. Sapozhnikov, V.V., Sapozhnikov, Vl.V. and Efanov, D.V. (2016), “Checking of combinational circuits, based on sum codes with one weighted data bit”, Avtomatika na transporte, Vol. 2, no. 4, pp. 564-597.
26. Sapozhnikov, V.V., Sapozhnikov, Vl.V., Efanov, D.V. and Dmitriev, V.V. (2017), “New structures of the concurrent error detection systems for logic circuits”, Avtomatika i telemekhanika, no. 2, pp. 127-143.
https://doi.org/10.1134/S0005117917020096
27. Blyudov, A.A., Efanov, D.V., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (2012), “Formation of the Berger modified code with minimum number of undetectable errors of data bits”, Elektronnoe modelirovanie, Vol. 34, no. 6, pp. 17-29.
28. Hamming, R.W. (1950) “Error Detecting and Correcting Codes”, Bell System Technical Journal, Vol. 29, no. 2, pp. 147-160.
https://doi.org/10.1002/j.1538-7305.1950.tb00463.x
29. Goessel, M., Morozov, A.A., Sapozhnikov, V.V. and Sapozhnikov, Vl.V. (1997), “Investigation of Combination Self-testing Devices Having Independent and Monotone Independent Outputs”, Automation and Remote Control, Vol. 58, no. 2, pp. 180-193.

Full text: PDF (in Russian)