Contents of magazine "Intelligent systems"
Volume 17, Issue 1-4, 2013
Part 1. Intelligent systems
- Agniashvili P.G. About image recovery by its code in some degenerate cases.
A statement is proved that concerns certain properties of codes under discrete-geomentrical approach to visual recognition. Images under consideration lie on the two parallel hyperplanes. The possibility of image recovery is investigated in this degenerate case.
Keywords: visual recognition, discrete-geometrical approach, image coding.
- Alekseev D.V. Using V.N.Kozlov's method in education process on MaTIS chair.
The article describes the usage of V.N.Kozlov's method in educational process in course "Discrete calculus" and the system of automatic problem generation for that theme.
Keywords: analytical geometry, affine transform, pattern recognition, stereo vision
- Baranovich A.E., Borovikov D.V., Lakusha E.L. Algebraization of model of k-hyperspace of SC-hypertopographs: transformations – evolutions operation's.
Results of synthesis of algebraic operations of transformation and evolutions semiotic-chromatic (SÑ-) hypertopographs (ητ-graphs) in signature ΨΦGkητx where Φ there is quite certain set (elementary transformations) are stated. Theoretic-multiple algorithmic realization of operation of transformation (TSÑ-procedure) for SÑ-ητ-graphs is offered. Conditions of convergence and depth of transformation in TSC-procedure on final SÑ-ητ-graphs are investigated. The estimation (from above) operational complexity TSC procedure is resulted.
Keywords: SC-hypertopographs transformation, SC-hypertopographs evolution, k-hyperspace SC-hypertopographs an algebraization, elementary transformations, transformations depth
- Baranovich A.E., Iglitskaya S.M. About some results of comparative analysis of models of musical and verbal texts.
Results of research of the musical text (ÌÒ) austere style (AS), presented by model of discrete messages von Neumann's, in a problem of an estimation of throughput of a discrete communication channel on Shannon are presented. The expanded alphabet of representation ÌÒ AS is offered. Comparative estimations of number of words ÌÒ of the length which are not exceeding l, and values of entropy ÌÒ in model zero and the first approximation (one voice and double-voiced) are received. The hypothesis about higher throughput of the channel of musical communications concerning the verbal is proved. As model of objective semantics ÌÒ is offered to use model of k-hyperspace of SC-hypertopographs and SC-hypertoponets – for a dynamic case.
Keywords: communications channel, model of message of J. von Neumann's, semantics of text, verbal text, musical text, k-hyperspace of SC-hypertopographs, SC-hypertoponets
- Bishteynov D.A. Mathematical model for the optimization of individual practical student work.
In this article the author intriduces a mathematical model for the optimization of individual practical student work.
Keywords: model, mathematical modelling, graph model
- Borcheninov Ya.V., Okulovskiy Yu.S. Evolutionary symbolic computation: methods and tools.
The current paper describes gene blowing problem during genetic programming computations. There were noted a number of possible methods to solve that problem. Also, there was proposed a new approach, which is based on combining genetic programming and symbolic computations.
Keywords: genetic programming, symbolic computations, intelligent systems
- Gasanov E.E., Ostroukhova E. N. Approximate solution of the problem of proximity in the Euclidean metric.
The paper presents two types of approximate algorithms for the the proximity problem in the Euclidean metric. According to our approach these algorithms exploit a trade-off between required memory, search time and error rate.
Keywords: information graph, the problem of proximity, approximation algorithmsí
- Dergunov A.V. Knowledge base for performance improvement of MPI applications.
To analyze MPI applications we usually use tools for tracing the execution of an application and then visualizing this trace and various statistics. But when using such kind of tools the user has to analyze a lot of data. Another problem with these tools is that frequent known situations leading to the loss of performance in MPI programs are not visualized. In other words, these tools lack a knowledge base for performance improvement. Thus there is a need to have tools for automating application trace analysis and recommending relevant solutions for improving performance of MPI applications. This article describes such system. The key component of this system is knowledge base encoding reasons of insufficient MPI application performance. The knowledge base contains rules described with a specialized language implemented for this system.
Keywords: parallel programming, knowledge representation, performance improvement, performance analysis
- Kozlov V.N. Geometric approach to the recognition of visual images (an overview).
Article, as it name suggests, is a review on discrete geometric approach to images recognition.
Keywords: pattern recognition, image, computer vision
- Kononchuk D.O., Okulovskiy Yu.S. Universal model of collective intelligence algorithms and its implementation.
The work describes a universal model of collective intelligence algorithms generalizing the known algorithms of artificial immune systems, ant algorithms and other known methods.
Keywords: ant algorithms, artificial immune systems
- Kotelnikov S.V. Intelligent system training skills of REFAL langauge programming.
Urgent task of education in modern conditions is individualization, which is ensured by using a computer. This work describes an intelligent language system for learning logic programming in REFAL language.
Keywords: interpreter, intelligent system, Java EE
- Maksimova A.Yu. The Method of Data Organization in the Applied Pattern Recognition System.
We propose a method of organizing work with the data for software recognition system, which automates the process of samples prepearing based on data domain.
Keywords: models of data, pattern recognition, data mining
- Perper E.M. The semantic graph to solve textual problems.
In the paper it is considered the method of automatic solution of textual problems. The solution is conducted by consecutive transformations on the semantic graph of the problem text. Each transformation corresponds to a certain step of human's solution of the textual problem.
Keywords: textual problem, automatic solution, semantic graph
- Pivovarov A.P. Summation over the semigroup operation for two-dimensional interval search problem with a fixed side.
This paper considers the problem of semigroup sum of values assigned to a set of points on a plane such that they are residing in a rectangle with one fixed side and three sides determined by a given query. A family of solutions is found which meets certain limitations on consumed space and time.
Keywords: range searching, computational search, search complexity, fractional cascading, information graph search theory, computational geometry
- Pletnev A.A. Dynamic databases modelling.
The operation of database is a processing of requests stream types search, insert and removal. As a result of requests types search and removal the database changes, also there is a response for request type search. If the stream of search requests dominates on the requests for database changing, then this kind of databases are called static. For the investigation of this kind of databases we use the information graphs. An expected model of dynamic databases is built on interaction of finite deterministic automaton and information graph. The task of automaton is to rebuild an information graph with changing of databases by processing of dynamic requests of user.
Keywords: dynamic database, mathematical modelling, information graph.
- Podkilzin A.S. Computer modelling of logical processes.
The work describes the development of computer system modelling the universal expert system ("Solver").
Keywords: computer modelling, logics, semantics, artificial intelligence
- Polovnikov, V.S. On nonlinear characteristics of neural circuits over an arbitrary basis.
The results obtained for the neural circuits over a fixed basis are generalized for the case of schemes over an arbitrary complete (by operation of superposition) basis of piecewise-parallel functions containing all linear functions and some non-linear part
Keywords: artificial neural networks, neural schemes, non-linear depth, schemes of functional elements, complexity
- Davydova (Romanova) A.A. Modeling of an electronic bilingual methodical dictionary of an open type as a part of intelligent information system formation process.
One of the problems solved by intelligent information systems is the training. This involves the use of computers for studying some discipline or subject. When building intelligent systems based on knowledge, the knowledge accumulated by experts in the form of specific rules of solving various problems are used, therefore, bilingual methodical dictionary and reference book created on the principle of Wikipedia, is a typical knowledge bank, that can then be included in a more sophisticated expert system.
Keywords: Intelligent Information System, bilingual, dictionary
- Roublev V.S., Smirnova E.A. Object DIM DBMS and ways of its realization.
Object approach to DBMS creation which assumes not only change of these objects, but also possibility of change of types of objects, i.e. the database schemes, called dynamic information model (DIM) is considered. Language of object and dynamic inquiries of ODQL for the dynamic information DIM model possesses completeness – any group of objects of DIM (together with any their properties) can be allocated with ODQL inquiry. Ways of realization of system at which questions of a data structure and their scheme at which dynamism of data and their types is considered are considered are considered, and also is minimized (in heuristic sense) time of performance of inquiries.
Keywords: object DBMS, dynamic information model, change of objects and types, language of object and dynamic inquiries, minimization of time of performance of inquiries
- Rudenko A.D. About codes of finite sets of points in an n-dimensional Euclidian space.
A finite set of points in an n-dimensional Euclidian space is represented with indexed ratios of measures of n-dimensional simplices with vertices at set's points. It is shown that a set not contained in two parallel hyperplanes is restored from such representation uniquely up to affine transformations.
Keywords: image representation
- Ryjov A.P. Intelligent systems for evaluation and monitoring of complex processes and theirs applications.
The article presents technological and mathematical aspects of development an information monitoring systems and examples of theirs applications.
Keywords: systems for evaluation and monitoring, fuzzy sets, fuzziness, fuzzy data bases, aggregation in fuzzy hierarchical dynamic systems
- Skatov D.S. Effective implementation of string dictionaries for solving computational linguistics problems.
Associative sets with string keys are discussed in the context of natural language texts processing (tasks like morphological parsing, spell checking, query suggestions in search systems). Their industrial exploitation implies high performance, compactness and the ability of serialization. In this article, the results of detailed comparison between the existing implementations of such indices are proposed, including one that is author’s. The features of their application for processing and storing natural language data are discussed.
Keywords: Data structures, associative sets, indexing of strings, computational linguistics, prefix tree, trie, Patricia, Judy-array, hash, C and C++
- Snegova E.A. Kriteriy svodimosti zadachi o predotvrashchenii stolknoveniy k zadache o prokalyvanii.
Keywords: search, information search, closeness
- Chulichkov A.I., Demin D.S., Kopit T.A., Tsybulskaya N.D. The analysis of a form of the images which are known with an error.
The method of a reduction of linear measurements of an output signal of the measuring device is considered. It is regarded that on an entrance of the device the unknown measured signal is operated, measurements are distorted by noise. The reduction is interpreted as measurement on the device closest to the ideal. The model of measurements which connects result of measurement with its entrance signal, is unknown and is taken from results of test measurements. The error of measurements is described in terms of the theory of possibilities. Reductions of measurements is defined from conditions of a maximum of a posteriori possibility.
Keywords: Optimal decision making, measurement reduction, possibility
- Shiryaeva I.A. Development of a model for implementing subject-oritnted interactive network.
The article is devoted to the topical problem of the introduction of interactive learning network to educational institutions. It is characterized by the model of distance learning implementation based on object-oriented interactive network.
Keywords: distant learning, interactivity, interactive network, model of implementation
Part 2. Automata theory
- Aleshin S.V. Semigroups and groups of automata.
The article is devoted to the problem of construction of infinite groups and semi-groups , which elements are automata.
Keywords: automaton, group, Burnside's problem, free group
- Babin D.N. On atomata superpositions.
We introduce a concept of prime automata with respect a cascade concatenation.
Keywords: superposition, finite automaton, completeness, prime group
- Babin D.N. Prime automata in the problem of completeness with respect to superposition operation.
The concept of prime automata was introduced.
Keywords: finite automata, prime automaton, prime group
- Bogomolov S.A. Automata model for competed interaction of systems of organization.
The article considers automat model of competed interaction of systems.
Keywords: systems of organization, automat, situation, space, variant of behaviour
- Vinogradov I.V. About an order of elements in the group of automata's permutations.
The paper considers 8-th order automaton in the group of automata's permutations, which implements negation in one state and the identity function in others. An example of 4-th order automaton satisfying the same properties was given in Makarov's work. The study of automata with one negation is of special interest, as any automaton from the group of automata’s permutations is decomposed into a superposition of automata with this property.
Keywords: automata, group of automata’s permutations, order of element, diagram of transitions, identity function, negation
- Epifanov A.S. Methods of interpolation of partially set lows of functioning of automata..
Problems of management, technical diagnosing, synthesis of behaviour of systems, etc. in case of complex systems are not provided by the full and exact information for their decision. The theory of experiments on recognition of behaviour of automata has found effective application in technical diagnosing of elements, aggregates, units and other technical objects, supposing the task by obviously presented discrete mathematical structures: by tables, matrixes, graphs, by logic equations, etc. In these cases of model of objects of diagnosing are set, as a rule, obviously and precisely, diagnostics tools are defined completely, and solved questions are reduced to check of operability and malfunction localisation on a site or functions. Technical diagnosing of complex systems essentially differs. Ineradicable incompleteness for complex systems initial and actually received by control and diagnostic experiments information does actual problems of regularization of information . In paper it is investigated regularization of partially set laws of functioning of automata from classes (n, m, l) – automata, where n – number of statuses of the automaton, m and l – numbers of input and output signals of the automata for classes (4,2,2)-automata, (8,2,2)-automata, (16,2,2)-automata and classes of automata, which laws of functioning are presented by partially set sequences of the second co-ordinates of points of geometrical images.
Keywords: discrete determined automaton, geometrical image of laws of functioning of automata, regularization of partially set automata, method of interpolation of Newton, Lagrange method of interpolation
- Kibkalo M.A. Complexity of OBDD and automata complexity of Boolean functions.
OBDD and polynomials for Boolean functions was explored.
Keywords: Boolean functions, finite automata, complexity
- Kurganskiy A.N. Vnutrennee i vneshnee nablyudeniye kollektiva avtomatov s odnim sostoyaniyem.
In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose an approach for defining what a state is. The measure of state transition of collective we name the proper time of collective.
Keywords: ñollective of automata, cellular automata, finite automata, special relativity theory, discrete models of physical processes
- Kucherenko I.V. On the minimization of mono-functional binary cellular automaton classes with undecidable reversibility.
The article is focused on study of algorithmic decidability of reversibility of cellular automaton. Class of two-dimensional binary cellular automaton with fixed transition function and with undecidable reversibility was constructed. Estimate of number of local transition function variables was obtained for this class.
Keywords: cellular automaton, reversible cellular automaton
- Letunovskiy, A.A. On the problem of finite group Medvedev automaton expressiblity.
The article is about problem of finite group Medvedev automaton expressiblity by systems of type F∪R. F is all boolean functions and R is arbitrary automata set.
Keywords: automaton, expressibility, algorithm, solvability
- Mastikhina A.A. Partial prediction of deterministic context-free languages’ infinite iteration.
The article concerns infinite iteration of such context-free language L that L* is deterministic context-free language. Sequence of words of L is input of some deterministic machine. Machine predicts t-th symbol of the sequence if it is equal to its (t-1)-th output symbol. Set of sequences is partially predicted if in any sequence some percentage is predicted by that machine. A criterion is obtained defining what L can be partially predicted
Keywords: partial prediction, deterministic context-free languages, pushdown automata
- Parkhomenko D.V. Second automaton function and related classes of regular languages..
Some properties of languages, which are appeared on the state machine output are described here. Author studied properties of multisets appeared as an output of finite automata. Also author suggests "deterministic analogue" of probabilistic machine.
Keywords: superset, fsm, finite state machine, finite automaton, probabilistic machine, second automaton function
- Tverdokhlebov V.A. Geometrical models and methods of recognition of automata.
For the first time it is offered and developed representation of symbolical automata mappings by numerical structures in the form of the allocated points on analytically set geometrical curves. Rules of transformation of set of inputr sequences in the quite linearly ordered set and variants of placing of such set on an axis of abscisses are found. It is shown, that at any a linear order on set of output signals and placing of this set on an axis of ordinates to various automata mappings correspond various geometrical images. On geometrical curves methods of construction of geometrical images are developed for automata mappings. The method of recognition of automata on the basis of the decision of equalities and inequalities of the equations, defining geometrical curves with points, having automata interpretation is developed.
Keywords: automaton, automaton mapping, geometrical curve, mapping, recognition of automata, numerical graph of automata mapping
- Titova E.E. Complexity of image construction with cellular automata.
The work deals with the problem of image construction with the cellular automata on a rectangular screen. Model of the device which controls the screen was developed, evaluation of image construction algorithms were obtained.
Keywords: cellular automaton, generator, universal screen, image construction, time estimation of image construction, estimation of image construction algorithm, commutation, delay, rarefying device
- Tyapaev L.B., Vasilenko D.V. Discrete dynamical systems over geometrical images of automata.
We study the geometrical structure of space of dynamical systems over geometrical images of automata
Keywords: finite automata, geometrical images of automata, dynamical systems
- Chasovskikh A.A. On completeness of finite automata class computing some affine functions.
The finite automata class of linear functions over discrete valuation ring consisting of rational numbers denominators of which are not divided into 2 is considered. Algorithm to test finite sets of this class to be complete over composition operations is obtained.
Keywords: finite automata, function composition, completeness problem, linear functions, precomplete classes, algorithmic solvability.
- Chernova Ju. G. On states of a lung automaton model in a clean environment.
In the theses an automaton model of lungs clearance process is offered and the exploration of properties of its Moore diagram continues. The special class of states of this diagram, namely the states which have the largest number of predecessors in clean environment are allocated. In the article there is criterion description of such states, their number are given, as well as the number of direct predecessors of each state of condensation is found
Keywords: automaton, Moore diagram, lungs, the process of clearance, state of condensation
- Skobelev V.G. On some types of automata over finite ring.
For automata over any finite ring there are resolved problems of identification (parametric and of initial state) and of fixed points’ analysis.
Keywords: finite rings, automata, identification, fixed points
Part 3. Cryptography
- Aleksandrov D.E. Multithreaded servers using event handlers.
This paper presents some results of TCP-servers research. Major server's features have been chosen to analyze and compare performance of different architectures for SMP-based systems. The result is the server with new server architecture, that unites benefits of the existing ones.
Keywords: information security, parallel computing, TCP-servers, symmetric multiprocessing systems, SMP-systems
- Bolotov A.A., Galatenko A.V., Grinchuk M.I., Zolotykh A.A., Ivanovic L. Methods for optimization of hash function implementation depth.
We consider hash functions SHA-2, SHA-1 and MD5 and propose a number of methods that allow to construct low-depth (and hence high throughput) circuits implementing these functions. As the result, SHA-2 round AND-OR depth is reduced to 16 for 512-bit block size and 17 for 1024-bit block size, SHA-1 round depth is reduced to 10, MD5 round depth is reduced to 20. We also propose a number of techniques that allow to reduce circuit area.
Keywords: circuit depth optimization, hash functions
- Galatenko A.V. On reconstruction of parameters of ε-security.
We consider an automata system; a subset of its states is considered secure. We investigate the possibility to reconstruct secure and ε-secure languages introduced in the atricle "Automata models of secure computer systems".
Keywords: finite automata, system security, finite experiments
- Galatenko V.A., Kostyukhin K.A., Shmyrev N.V. On construction of formal models for fault-tolerant real-time applications.
The paper presents a formal description of real time objects and their interactions in real time system.
Keywords: real time systems, debugging, controlled execution
- Godneva A.V. Studying group properties of multipliction with a parameter.
The paper is devoted to group properties of multipliction with a parameter, an operation used in digital signature standard of Uzbekistan.
Keywords: multiplicative group, cryptography, electronic signature
- Kucherenko N.S. Mathematical expectation of the average length of the Huffman codes.
The average length of the Huffman code is studied as a random variable depending on the random set of encoded character probabilities. The asymptotic of the mathematical expectation of the average length in the case of increasing cardinality of the alphabet is obtained.
Keywords: Huffman code
- Mazurenko, I.L. One approach to adaptive linear digital signals processing.
Author suggested a modified algorithm of fast affine projections that overperfoms the known analogs in terms of complexity / performance trade-off.
Keywords: filter, linear system, FAP, NLMS, LMS, affine projections, fast affine projections
- Markov A.S., Patrakov N.V., Fadin A.A. Resheniye zadachi optimizatsii bezopasnoy informatsionnoy sistemy.
In the paper there is a description of existing approaches to optimization of information systems with the preservation of the established integrity, avaliability and confidentiality level of the processed information.
Keywords: model optimization, information systems, component analysis, information systems security
- Mozgaleva O.A. Ataki na protokol Nidkhema-Shredera. Modifikatsiya protokola Nidkhema-Shredera i postroyeniya na ego osnove.
Keywords: n/a
- Panteleev, P. A. On polarization of Bernoulli sources by random linear transformations.
We study the recently discovered phenomenon of discrete random source polarization. It can be described as follows. There is a linear transformation over the field F2 such that after applying it to any i.i.d. Bernoulli sequence X1,...,Xn we obtain the binary random sequence Y1,...,Yn that can be divided into two parts: the random-like Yi1,...,Yim and the deterministic-like Yj1,...,Yjk. The entropy of the random-like component is close to the entropy of X1,...,Xn and the deterministic-like component can be obtained from the random-like one in an almost deterministic way. We show that for a random linear transformation over F2 the polarization phenomenon occurs asymptotically almost surely for any i.i.d. Bernoulli source.
Keywords: polar code, source polarization
- Chechulina K.A. Fast matrix multiplication over F2 field.
This manual is devoted to multithread algorithms of matrix multiplication over F2.
Keywords: matrix multiplication, block algorithm, multithread, MPI.
Part 4. Discrete mathematics and mathematical cybernetics
- Arkhipova A.N. About effectiveness of machine learning algorithms for some classes of Boolean functions.
The article is devoted to the studying machine learning algorithms within the PAC model for different classes of Boolean threshold functions. There is a direct proof of the fact that Hastad function does not belong to the class of nested functions. Also in the paper there is an example of the triple threshold functions, showing that the attempt to enter the distance in the class of threshold functions as the minimum value of the L1-norm over all integer linear forms representing two threshold functions is doomed to fail.
Keywords: Threshold functions, nested functions, PAC model
- Bokov G.V. O konechnoy porozhdennosti ischisleniya vyskazyvaniy s proizvolnymi operatsiyami vyvoda.
In this paper we obtain a criterion for finite complete axiomatization of propositional calculus
Keywords: propositional calculus, rule schemes, axioms
- Bokov G.V. Ob algoritmicheskoy nerazreshimosti problemy vyrazimosti propozitsionalnykh ischisleniy..
In this paper we proof a sufficient conditions for algorithmic undecidability of expressibility problem of propositional calculus with single rule scheme
Keywords: propositional calculus, rule schemes, expressibility problem.
- Gasanov E.E., Din A.A. Clock tree synthesis.
In the paper we study the problem of clock tree synthesis for integrated circuit design. It is shown that there are configurations of points with a minimum distance between the points of 3, which is impossible to build a synchronization tree. On the other hand, if the minimum distance between points of the configuration are not less than 4, then there exists a synchronization tree for this configuration.
Keywords: synchronization of signal; synchronizing tree
- Grunskiy I.S., Maksimenko I.I. Predstavleniya elementov chastichno-uporyadochennykh algebraicheskikh sistem fragmentami.
Keywords: n/a
- Zhuk D.N. Lattice of closed classes of self-dual functions in three-valued logic.
The lattice of all clones of self-dual functions in three-valued logic is described in the paper. Using this description different properties of the lattice and of the clones were derived. Pairwise inclusion of the clones into each other was described, and all finitely generated clones were found. Also, for each clone the relation degree, the cardinality of the set of all clones containing this clone, and the cardinality of the set of all clones that are contained in this clone were determined.
Keywords: Lattice of clones, closed class, self-dual function, precomplete class, maximal clone
- Ivanov I.O. On some aspects of Riemann-Roch theorem for finite graphs.
This paper is devoted to the search for an efficient algorithm finding a winning strategy in Chip-Firing Game, or claiming that it does not exist. As a result we get algorithms for complete and complete bipartite graphs.
Keywords: riemann-roch theorem, chip-firing game, dollar game
- Ikramov A.A. O slozhnosti testirovaniya logicheskikh ustroystv na nekotoryye tipy neispravnostey.
Author studied complexity of testing logic devices on errors such as clumping, inversion, scrambling and their union. In some cases, precise values are obtained, in other upper and lower bounds. Also author examined the complexity of testing logic devices of almost all boolean functions on inversion errors type 1.
Keywords: testing logic devices, complexity, inversion errors, scrambling errors, almost all boolean functions
- Magomedov A.M., Magomedov M.A. Dekompozitsiya grafa po sredney plotnosti.
Conditions for graph decomposition by average density have been studied.
Keywords: graph, average density, optimization, schedule
- Nosov M.V. About the formulae for the number of equivalence classes and threshold functions.
The number of threshold functions is represented as a combinatorial-arithmetic expression.
Keywords: equivalence classes, threshold function.
- Nosov M.V. Integralnaya formula chisla porogovykh funktsiy.
The number of threshold functions is presented in the form of the integral of an expression.
Keywords: equivalence classes, threshold function.
- Pavlov M.V. O slozhnosti raspoznavaniya diskretnykh obrazov ploskikh figur.
Keywords: n/a
- Papilin S.S., Pyt'ev Yu.P. Possibilistic models of two-player matrix games considering two variants of possibility theory.
The report describes models of normal-form games in terms of two variants of the possibility theory. The formulas for the equilibrium strategies and the value of game are given, and the existence of unfuzzy strategies is examined. The results are compared with those in terms of the probability theory.
Keywords: possibility theory, normal-form game, equilibrium strategies, value of game
- Petrova O.A. Weakly closed classes of linear Boolean functions.
Article contains description of all weakly closed classes of linear Boolean functions
Keywords: Boolean functions, linear Boolean functions, time delay, synchronous closing, first projection, weakly closed classes, relations of inclusion
- Petrova O.A. Weakly closed classes of self-dual Boolean functions.
Article contains description of all weakly closed classes of self-dual Boolean functions
Keywords: Boolean functions, self-dual Boolean functions, time delay, synchronous closing, first projection, weakly closed classes, relations of inclusion
- Petyushko A.A. About frequency languages over bigrams.
The paper deals with formal languages defined by the bigram matrix. The connection between different characteristics of the proposed languages and directed graphs and its euler circuits is established. The criteria of non-emptyness, finitness and infinity of the languages are presented. Conditions of regularity of the proposed languages are established.
Keywords: bigram matrix, bigram languages, frequency languages, regular languages, euler circuits, directed graphs.
- Podlovchenko R.I., Zakharov V.A. O dvukh metodakh raspoznavaniya ekvivalentnosti v algebraicheskikh modelyakh programm.
Keywords: n/a
- Podymov V.V. Equivalence-checking algorithms for recursive and sequentional programs on ordered semigroup scales.
We propose a technique which allows us to construct equivalence-checking algorithms for recursive programs, and, as a particular case, for sequential programs. Considered program semantics is defined by means of arbitrary finitely generated partially-ordered monoid, including semantics which approximate real program semantics.
Keywords: equivalence checking, recursive programs, sequential programs, semigroups
- Prianychnykova Olena Algebraic characterization of languages representable in labeled graphs.
In this work we consider languages representable in labeled graphs (graphs with labeled vertices, graphs with labeled edges, graphs where both vertices and edges are labeled). We propose algebraic characterization and methods of analysis and synthesis for these languages and study the family of algebras of languages representable in considered graphs and its properties.
Keywords: graphs, languages, finite automata, regular expressions
- Rodin A.A. Bazisy v P-mnozhestvakh.
Let D be a closed class in k-valued logic. Denote by P(D) the set of deterministic finite functions having boolean function from D in every state (P-sets). It is shown in the article, that there exists basis for some P-sets.
Keywords: automata mappings, bàsis, completness
- Selezneva S.N. A fast algorithm of construction polynomials modulo a composite k for k-valued logic functions.
We obtain an algorithm (in the model of circuits) that, by a given k-valued logic function truth-vector f (where k is an arbitrary prime number), checks whether f is represented by a polynomial modulo k, if so, constructs a polynomial representation for f, and has a O(N) bit time-complexity, where N is a length of truth-vector of f.
Keywords: k-valued logic function, polynomial modulo K, algorithm, complexity
- Starikov A.O. Order of growth for Shannon function of accumulated branching for logical circuits.
The paper describes the problem of reducing a certain complexity, which is called accumulated branching, in the synthesis of logical circuits. For the basis consisting of conjuction, disjunction, negation and identity operation, upper and lower estimates for Shannon function of such complexity were obtained. Combination of found estimates gives the order of growth for Shannon function of accumulated branching, which is O(n).
Keywords: circuits of functional elements, delay, accumulated branching, Shannon function
- Cheburakhin I.F. About minimization of difficulties of the presentation boolean functions from some classes.
The problem of optimal realization of Boolean functions from some classes is researched with formulas and schemes from functional elements (FE). The constructive method of the synthesis based on functional equations attended by ahead reception of analytical estimates of different factors of difficulties (on amount of subformulas and depth of superpositional formula; on amount of FE and depth of scheme) is offered.
Keywords: The Boolean functions, decomposition, optimization, measures of difficulties, factors of quality, synthesis formulas and schemes from functional elements, functional and differential equation.
- Emelichev V.A., Karelkina O.V., Kuzmin K.G. On five types of stability of multicriteria combinatorial minimin problem.
In this work, we address the issue of qualitative characteristics of stability of discrete multicriteria optimization problems. Analysis of the five most known stability types has been carried out for two multicriteria minimin combinatorial problems: with Pareto and lexicographic principles of optimality. As a result necessary and at the same time sufficient conditions for each stability type are obtained as well as interrelation between these types are revealed.
Keywords: combinatorial problem, multicriteriality, MINMIN-criteria, stability
- Skobelev V.V. On the 2D order curves over finite ring.
For 2-d order curves over a finite ring the structure of sets of points is investigated and canonical forms are presented.
Keywords: finite rings, 2-d order curves, canonical forms
Part 5. Computer science and research
- Aksenova E.A., Soklov A.V. The optimal method of redistributing shared memory for the two-priority queue represented in the form of two consecutive cyclic FIFO-queues.
This paper presents a mathematical model in the form of a random walk on the integer lattice in a rectangular area for representation of the two-priority queue in the form of two consecutive FIFO-queues. Based on this model, an algorithm, which allows for a given probability of the basic operations of a priority queue to find the optimal way of redistributing memory after a FIFO-queue overflow, was proposed. The criteria of optimality – maximization of the average work time until memory overflow.
Keywords: priority queue, FIFO-queue, random walks, Markov chains
- Andreev A.V., Pytyev Y.P. Deterministic methods of forecasting: construction and analysis.
Mathematical methods of forecasting are discussed on the example of asset prices forecasting. We compared the methods and made an attempt to restore probabilistic and possibilistic data models.
Keywords: forecasting methods, stichastic model
- Velichenko V.V. Konflikty mezhdu metodami matematiki i mekhaniki i tekhnogennyye katastrofy.
Mistakes of correct common use of mathematics and mechanics methods are considered.
Keywords: mathematics, mechanics, conflicts, mistakes, catastrophes
- Vyukova N.I., Galatenko V.A., Samborskiy S.V. Integer linear programming formulation of the joint problem of code selection and scheduling for code generation.
The paper presents a code generation method based on joint description of code selection and code scheduling tasks as an integer linear programming task.
Keywords: code optimization, instruction selection, instruction scheduling, integer linear programming
- Grigoreva A.M., Pytev Yu.P. Super resolution and robustness of dynamic sensors matrices.
An image registration system using the proposed model allows for obtaining significantly higher resolution compared to a system with fixed retina.
Keywords: image registration, mobile sensor matrix, mathematical modeling, resolution enhancement, superresolution, retina
- Grigoreva N.S. Scheduling precedence-constrained tasks to minimize the number of parallel processors.
We consider the NP-hard problem of scheduling precedence-constrained tasks for parallel processors. Makespan of schedule is fixed and we need to minimize the number of parallel processors. The goal of this article is to describe the branch and bound algorithm for the problem of scheduling a given length for the minimum number of processors. Branch and bound method allows to obtain an exact solution, or, when the time of the algorithm is restricted, a good approximation of the solution. New rules for vertex selection, branching and elimination are used in B&B algorithm. A computational experiment on randomly generated problems test the effectiveness of the proposed approaches.
Keywords: scheduling, precedence constrains, parallel processors, branch-and-bound method
- Zhiznevskiy A.N. Experimental research of the active contours method.
The authors conducted an experimental research of the active contours method in relation to image segmentation. The research revealed a correlation between segmentation results and the choice of the initial approximation and algorithm parameters.
Keywords: image segmentation, active contours
- Lemtyuzhnikova D.V., Shcherbina O.A. Local elimination algorithm and parallel computing.
The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). Usually, such DOPs from applications have a special structure, and the matrices of constraints for large-scale problems have a lot of zero elements (sparse matrices). One of the promising ways to exploit sparsity is local elimination algorithm (LEA), that is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEA heavily depends on elimination ordering which actually provides solving stages. This paper describes comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.
Keywords: discrete optimization, local algorithm, sparse problems, ordering, benchmarking
- Obukhov Yu.V., Korolev M.S. O chastotno-vremennykh priznakakh mnogokanalnykh elektroentsefalogramm mozga pri zabolevanii Parkinsona na ranney stadii.
Keywords: n/a
- Osokin V.V. Model of information retrieval site for branch of Moscow state University.
This paper considers the problem of constructing a universal search engine, based on which you can implement web-site of any division of MSU.
Keywords: information retrieval system, website
- Pereverten V.A. The model of hypertext organizing information in information systems for historical research.
The author's model of hypertext organizing information in information systems for historical research (HT-model) is proposed. The HT-model is based on a hypothetical conception about cognitive information work of a historian. Information object (IO), IO-image, hypertext object (HO), association and link are the basic concepts of the HT-model. The model is presented in the intensional and formalized form.
Keywords: information technology, information systems, historical research, information, hypertext, hypertext model
- Pyt'ev Yu. P. Modeling of subjective judgements made by a researcher/modeler about the model of the research object.
In scientific, engineering, technical and other creative activities it is not possible to avoid the use of unclear, incomplete and partially incorrect information associated with past experience, practice and knowledge. In the article we consider a method of mathematical modeling of such information expressed as subjective reasoning, possible a group one. The essence of the method is the concept of uncertain random element defined on the product of spaces: the probability space (Ω,A,Pr(.x)), known up to the value of parameter x∈X and modeling the research object, and the space (X,P(X),Pl,Bel) with measures of plausibility Pl and belief Bel, modeling the subjective judgements of the researcher/modeler about possible values of x∈X. It is shown that such model allows to estimate the plausibility and belief of any researcher's judgements about any properties of the research object caused by its model.
Keywords: incompleteness of knowledge, uncertainity, probability, plausibility, possibility
- Sadovnichiy V.A., Vetrov D.P., Vishnevskiy V.V., Galatenko A.V., Galatenko V.V., Zykova T.V., Korshunov A.A., Lebedev A.E., Lukashenko T.P., Podolskiy V.E., Politov A.V. Mathematical method for the problem of catalytic activity estimation of enzymes in biological solutions.
We present a mathematical formulation for the problem of catalytic activity estimation of enzymes in biological solutions. We propose a method for solving the problem consisting of three stages: integral transform, complex analytic extension and orthogonal expansion in the space of almost periodic functions.
Keywords: enzymes, catalytic activity, integral transform, complex analytic extension, almost periodic functions
- Sadovnichiy V.A., Sokolov M.E., Barmin V.V., Budanov V.M., Galatenko A.V., Galatenko V.V., Korshunov A.A., Kozorezov Yu.Yu., Podolskiy V.E. Retrieval, processing and reproduction of medical tactile information.
The paper is devoted to the medical tactile endoscopic complex. We discuss a number of applications of this complex including tactile data objectification, obtaining tactie data in endoscopic surgery, telemedicine, education and automated analysis of tactile images.
Keywords: medical tactile endoscopic complex, tactile mechanoreceptor, tactile display, tactile image
- Sadovnichiy V.A., Sokolov M.E., Vetrov D.P., Galatenko A.V., Galatenko V.V., Zykova T.V., Lebedev A.E., Lukashenko T.P., Podolskiy V.E., Politov A.V. Mathematical methods of tactile diagnostics automation.
The paper considers the problem of automated tactile diagnostics for the medical tactile endoscopic complex. We propose an approach to the solution of this problem consisting of dimension reduction, databank preprocessing and diagnosis prediction.
Keywords: medical tactile endoscopic complex, automated diagnostics, dimension reduction
- Sviridenko A.V., Shcherbina O.A. Variables ordering algorithms in local elimination algorithm.
The goal of this paper is impact analysis of variables ordering algorithms on the solving time of discrete optimization problem with help of non-serial dynamic programming algorithm
Keywords: discrete optimization, local elimination, non-serial dynamic programming, minimum degree algorithm, nested dissection heuristic, maximum cardinality search algorithm, minimum fill-in algorithm, lex-bfs algorithm
- Sevastyanov S.V., Chernykh I.D. Efficiently solvable case of the Open Shop problem in terms of total workload.
Open shop is a well-know classical scheduling model. Open shop problem is known to be NP-hard for the case of at least 3 machines. The three-machine case is thoroughly investigated. We obtained the tight function representing the relation between optumum and the total machine workload in terms of the standard lower bound. This improves previously known result on the optima localization for this problem. New polynomially-solvable cases are described.
Keywords: Open shop, total workload, standard lower bound, optima localization
- Starostin N.V., Safonova Ya.Yu. Parallel sparse Cholesky decomposition.
In this paper we discuss a problem of sparse Cholesky decomposition using parallel computational systems with shared memory. We propose an effective approach based on decomposition of matrix elimination tree. We show that parallel processing of non-intersecting subtrees provides speed-up compared with binary logarithm of p, where p is a number of independent processors of parallel system.
Keywords: parallel Cholesky decomposition, matrix elimination tree, solving sparse linear systems, nested dissection algorithm
- Fofanov V.B., Zhiznevskiy A.N. Formalizing the problem of searching for objects in a vector scene.
The work suggests ways of formalizing and solving the problem of searching for objects in a vector scene. The peculiarities of the problem statement are the type of objects (they are “spots”) and the initial scene details (a set of spatially superimposed images). The scene model is a locally homogeneous random vector field. The authors suggest a three-stage approach to object search. Initially, a square (a zone of interest) is defined for each object. Each square contains an object and its locality. On the second stage, each interest zone is segmented. The resulting object projection is used on the third stage for identifying geometric features and making the final decision about the presence of an object. The work proves the theorem on the existence of locally homogeneous fields, as well as the theorem on the convergence of solving rules to Bayesian on the interest zone location and segmentation stages.
Keywords: scene, image, object, object features, objects search, zone of interest, segmentation, classification
- Cheremnykh Yu.N. Matematicheskiye modeli ekonomicheskikh protsessov.
The article contains a historical review of application of mathematical methods to represent theories and analyze problems in economics
Keywords: mathematical economics, linear programming
- Chernykh I.D., Kuzevanov M.A. Efficiently solvable case of the two-machine Routing Open Shop with preemptions allowed.
Routing open shop problem with preemptions allowed if a generalization of the classical metric travelling salesman problem and one scheduling problem – preemptive open shop. This problem is polynomially solvable for the case of two machine on a link. The complexity status for the two-machine case on a triangle remains unknown yet. We investigate general two-machine case of the problem. We describe new polynomially solvable case in terms of unequal total loads of the nodes of the transportation network.
Keywords: Routing open shop, preemptions, overloaded node, polynomially solvable case.
|
