Русский
03.2015 - Volume 19 Issue 1 (PDF)
The paper describes the technology of complex process assessment and monitoring developed at the MATIS Department since the early 90s. A substantive statement of the information monitoring problem is given, and technological and mathematical aspects of information monitoring systems development are described. An overview of the main results is given.
Keywords: assessment and monitoring systems, fuzzy sets, fuzziness assessment, search in fuzzy databases.
The article generalizes the results of [1] to the case of k-valued logics. The concept of a predictive automaton is introduced, which for each super-word from a given set fed to its input, starting from a certain step at each moment t, produces the value of the input word at the moment t + 1, i.e. predicts the input super-word. A criterion for the predictability of sets of super-words is obtained. The best order method for constructing a predictive automaton for an arbitrary predicted set of super-words is given.
Keywords: finite automaton, predictive automaton, event prediction.
The class P L of piecewise linear functions together with superposition operations is considered [1]. In this paper, it is shown that in P L there are three precomplete classes containing the class L of all linear functions: the class of finite functions, the class of continuous functions, and the class of consistent functions. A criterion has been obtained that allows one to check the completeness of the set M ∪ L for a finite set M ∈ P L.
Keywords: class of piecewise linear functions, class of finite functions, class of continuous functions, class of consistent functions, Heaviside function, superposition operations, essential discontinuity.
The paper presents an algorithm for constructing a set based on given parameters, for which the actual number of steps reaches half the upper estimate of the number of steps for this set in Novikov's theorem. It is additionally proved that for a set consisting of two points, the actual number of steps is no more than \(({D^2}/{2*r^2})+2\).Keywords: neural networks, Novikov's theorem.
The paper considers two problems: classification of music files by genre and classification of images. In the first case, it is necessary to implement a web application that determines the genres of music files loaded into it (jazz, classical, disco, metal, blues). In the second case, it is necessary to implement a web application with the ability to load reference images. When subsequently loading images, the system must determine which of the reference images the loaded image is most similar to and assign it to the appropriate class.
Keywords: classification, music files, mfcc, hog, php.
The task is to build a web page search engine. The main task of the system is to return a sorted list of results that satisfy a given user search query. The system is divided into several parts: crawler, indexer, ranking, and search interface. The article contains a detailed description of each of these parts. In addition, an implementation is provided for each part.
Keywords: Internet, search engine, crawler, indexer, ranking, HITS, PageRank, TF-IDF.
The problem considered in the paper is as follows: let a set of words be given; for an arbitrary subword it is required to find all occurrences of this subword in words from this set. In this paper a lower bound for the running time of algorithms that allow such a search is given, and the order of the memory volume for algorithms that perform the search in the minimum time by order is obtained.
Keywords: search for occurrences of subwords, lower bound, upper bound.
This paper considers the solution of a dynamic problem of searching for an identical object for an arbitrary query flow. The complexity of parallel query processing over a common data structure lies in avoiding conflicts that arise when changing the same memory area. At the same time, we assume that reading from one memory area is acceptable for several processes. The solution is obtained using a dynamic information graph [1], [2], which in turn is a generalization of the information graph [3] for the cases of insertion and deletion of a record.
Keywords: dynamic databases, information graph, finite state machine, query flows, parallel data processing.
Earlier, the author proved that pushdown automata preserve many periodic sequences and gave an exponential estimate for the period extension in this case. For automata with a unary store, this estimate was reduced to quadratic.
Keywords: pushdown automaton with a single-letter store, deterministic function, periodic sequences.
The algorithmic solvability of the problem of expressibility of linear automata through an arbitrary finite system of automata with respect to extended superposition is proved.
Keywords: automaton, linear automaton, expressibility, superposition, algorithmic solvability.
This paper considers the solution of a dynamic problem of searching for identical objects for an arbitrary query flow with logarithmic complexity. The complexity of parallel query processing over a common data structure lies in avoiding conflicts that arise when changing the same memory area. In this case, we believe that reading from one memory area is acceptable for several processes. The solution is obtained using a multi-automaton dynamic information graph [1].
Keywords: dynamic databases, information graph, automaton, query flows, parallel data processing, balanced trees.
The paper considers the problem of deciphering polynomial ranking functions. In the case when the ranking function depends linearly on a known variable, an algorithm for decoding with an accuracy of up to a multiplicative factor with a known error is proposed, as well as an estimate of its complexity. A class of functions is presented for which there is an algorithm that determines for which of the variables the corresponding monomial has the lowest degree and the smallest major coefficient in absolute value. An estimate of the complexity of this algorithm is given.
Keywords: decoding functions, ranking functions, website promotion.