Contents of magazine "Intelligent systems"
Volume 14, issue 1-4, 2010
Part 1. General problens of Intelligent systems theory
- Баранович А.Е.. О систематизации аксиоматического аппарата предметной области «Искусственный интеллект» (in Russian).
With the positions of the information-evolutionary approach, questions of systematization of the axiomatic foundation of a object domain of the science, called now by "artificial intelligence" (AI), are considered. In contexts of scientific and ordinary consciousness it is a question what to eat ``naturally'', and that is ``unnaturally'' and is ``artificially'' in AI. Results of the lead analysis allow to make essential changes to phenomenology of its development.
Keywords: "Big history"; informatization; information-evolutionary approach; intelligence natural, artificial; intelligence computing, computer, technical; modelling; systems anthropogenous, anthropomorphous, intelligent, material
Part 2. Special questions of Intelligent systems theory
- Козлов В.Н.. Доказательность и эвристика при распознавании визуальных образов (in Russian).
In article are described in the short form the basic ideas as a principle of the is discrete-geometrical approach to recognition of visions, and at descriptive level the received results are described. Some reasons about the role of heuristics in recognition of visual images are discussed.
Keywords: recognition of images, visions, 3D-reconstruction of images
- Маслобоев А.В., Ломов П.А.. Использование общесистемного тезауруса как основы интеллектуального пользовательского интерфейса системы распределенного семантического поиска (in Russian).
This paper considers the application problem of expanded systems-wide thesaurus as the basis of intellectual interface of the distributed semantic retrieval information systems. The definition of shared thesaurus expansion by units of the top-level ontology and meta-properties is proposed. The inquiry formation technology based on identification procedures of its meshing possible variants that allows the thesaurus application as the basis for intellectual user interface design has been developed.
Keywords: information system, ontology, thesaurus, semantic information integration, query manipulation, intelligent user interface
- Адылова Л.Р.. О распознавании лиц (in Russian).
Methods of geometrical recognition of race of the person on a photo are studied. Geometrical invariants of face, allowing to refer it to one of three racial clusters: mongoloid, caucasian, negroid are found. Was found 11 such invariants in the form of points of the face at definitely set system of coordinates. On these points the code was constructed and then various methods of recognition of persons were applied to it.
Keywords: recognition, invariants, geometrical methods, race, training
- Боков Г.В.. Принцип максимума Понтрягина в задаче с временным запаздыванием (in Russian).
In this paper we consider a certain optimal control problem with time-delay. The state and the control variables contain various constant time-delays. It allows us to represent the necessary conditions in an explicit form. Solution of this problem with infinite terminal time is also given.
Keywords: Optimal control theory, time-delay differential equations, necessary conditions, maximum principle, finite and infinite terminal time
- Газарян В.А. Матвеева Т.В. Чехонина Ю.Г. Шаховская А.К.. О теоретико-возможностных методах анализа эффективности лечения (in Russian).
[1] shows that for solving many problems in medical diagnostics possibilistic model of data analysis and interpretation [2] is natural instead of probabilistic one. The possibilistic model of disease symptoms and possibilistic model of medical diagnosis were built. The aim of this work is developing of possibilistic methods for analyzing the effectiveness of treating of chronic pancreatitis patients. Particularly is developing of effect produced by one or another drug on the state and on biochemical indices of blood of such patients estimating method.
Keywords: theory of possibility, testing of statistical hypotheses, t-test, effectiveness of treating, chronic pancreatitis
- Галатенко А.В.. О восстановлении разбиения безопасности (in Russian).
We consider an automaton system; a subset of states of the automaton is considered to be secure. We investigate the complexity of reconstruction of such security partitions for secure and epsion-secure languages introduced in the article ``Automata models of secure computer systems''.
Keywords: Finite automaton, automata models, multiple conditional experiment
- Гасанов Э.Э., Колесниченко А.В.. Предикатная эквивалентность формул алгебры логики (in Russian).
Predicate equivalence of Boolean algebra formulas is investigated in the paper. Predicate equivalence is defined with help of a set of predicates P and a set of permutations M. The sets P and M are conformed if predicate equivalence coincides with common equivalence of Boolean formulas. Criterion of the sets conformity is proved. The algorithm of construction of conformed sets is suggested. Examples of conformed sets P and M are given.
Keywords: Boolean algebra, predicate logic, analytic description of geometric figures
- Докучаева Т.В.. Процесс самоочищения легких с очаговыми поражениями в чистой среде (in Russian).
In this paper we have constructed the model of functioning of lungs with pathologies. We have considered the function of lungs self-cleaning from the substance that gets into them from environment or is being produced in it during life. We have expanded the mechanism of substance transportation in healthy lungs to a case of pathologies of capacity and efficiency of ciliary mechanism. We have received the description of lungs self-cleaning process time complexity with pulmonary pathologies of ciliary capacity and(or) their efficiency in clean environment.
Keywords: bioinformatics, dendritic systems, lungs, ciliary mechanism, self-cleaning, transportation process
- Колесникова С.И.. Свойства корректной модификации метода парных сравнений (in Russian).
Properties of function of relative similarity as scalar measure of convolution of criteria used according to the method of paired comparisons are considered. Application of the function of relative similarity allows to correction of unwanted effects of known Т. Saaty’s method. Effects are related to using of linear convolution of criteria and of unit normalization of weight coefficient of alternatives. The illustrative example is given.
Keywords: method of analytical hierarchies, alternative weight coefficients, intelligence system, test pattern recognition, quality of decision-making
- Лёвин В.Ю.. О повышении криптостойкости однонаправленных хеш-функций (in Russian).
In this paper we introduce a solution of a data integrity ensuring using cryptographic one-way hash functions. The cryptographical security of such hash-functions was estimated by us in detail for different kinds of attacks. We propose a several new schemes of a one-way hash functions security strengthening without reformation of it’s internal algorithms. Also we outline schemes with the best speed and security level. We show that the Schneier’s method of suffix superposition has seriously drawback. In this article we also suggest the method of constructing collision resistant one-way hash-functions from standard well-known hash-functions. Therefore, the proposed schemas can be used for upgrade majority cryptographic one-way functions, such as MD4, MD5, RIPEMD, SHA, GOST 34 11-94.
Keywords: one-way hash-functions, Schneier’s method, message integrity, tunnel collisions, information security
- Пархоменко Д.В.. Моделирование вероятностными источниками (in Russian).
Hidden Markov Model (HMM) – this is Markov chain, which has user-visible "exit". In accordance with state-dependent distribution law, in the every state HMM provides an output character and moves to the next state. If output alphabet is finite, HMM is called probabilistic generator. The article describes usage of HMM-based devices and gives an account of the actual engineering problems, where they are used.
Keywords: hidden Markov models, image recognition, probabilistic generator
- Петюшко А.А.. О марковских случайных полях и их связи с цепями Маркова (in Russian).
This work is about markov random field and hidden markov random field. Some relationships are established between markov random fields and markov chains, and between hidden markov random fields and hidden markov models using the special introduced random variables.
Keywords: Markov random field, mrf, hidden Markov random field, hmrf, markov chain, hidden markov model, hmm
- Пивоваров А.П.. Моделирование вычислительных задач информационного поиска (in Russian).
This paper contains definitions and comparison of two models for computational information search problems algorithms description. First of them almost identical to the information graph model. The second uses automata functions for calculations. The answer cardinality search for one-dimensional interval search problem is used as a model problem for this study. The advantages of automata functions usage in computational information search problems are shown.
Keywords: computational information search problem, information graph, computational information graph, one-dimensional range searching, search modelling, search algorithms characteristics
- Рыков Д.О.. Об алгоритмах проверки правильности семейств функций (in Russian).
This paper considers the problem of propriety checking for families of functions. A new algorithm of propriety checking is introduced. The algorithm uses information about the graph of the family of functions and the complexity of the algorithm depends on the number of vertices in strong components of the graph. A new algorithm for families of monotonous functions is also introduced. The algorithm is based on two properties of proper families of monotonous functions: the presence of constant and functional closure of that class in $P_2$. It is demonstrated that the complexity of the algorithm is considerably less than complexity of the standard propriety checking algorithms.
Keywords: Proper family of functions, propriety checking algorithm for families of functions, graph of essential dependence of family of functions, family of monotonous functions, propriety criterion for family of functions.
Part 3. Mathematical models
- Блохина Г.Н., Кудрявцев В.В.. О спектрах классов Поста булевских функций (in Russian).
Keywords:
- Болонкин М.В.. О распознавании вирусов в регулярных текстах (in Russian).
In this paper we study properties of regular expressions and identical transformations of regular expressions on the issue of modelling of polymorphic viruses. Model of infection, weak and strong infection of program with virus is defined. The main contribution of this work is to find criteria of infection with virus and start modelling programs and virus properties in terms of regular expressions. As has been proved, there exists a criterion for infection (weak or strong) of *-free programs and criteria for some classes of regular expression with Kleene star.
Keywords: recognition, viruses, regular expression, subexpressions
- Кибкало М.А.. Об автоматной сложности некоторых классов булевых функций (in Russian).
We investigate the question of asymptotic behavior of maximal state complexity of a language represented by a DFA. We determine that closed sets of Boolean functions from Post's lattice divide into three groups in correspondence with their asymptotic complexity. Moreover, for certain sets exact values of maximal complexity are produced.
Keywords: complexity, DFA, finite automata, finite automaton, Boolean function, Shennon function, Post's lattice
- Кучеренко Н.С.. Задача поиска по ключу с определением позиции (in Russian).
Two ways of formalization of key search are studied in the article. They are the identical objects search (IOS) and expanded IOS. It is shown, that the search complexity for these ways of formalization are identical. The algorithm of transformation is described, which transforms solution for IOS to solution for expanded IOS without change of complexity.
Keywords: database, key search, search algorithm
- Лашева М.И.. О переключательных алгоритмах преобразования некоторых классов графов (in Russian).
In this paper we consider so called edge-switching algorithm created the transformation procedure for any pair of some class graphs keeping the same degree sequence and the particular class. The algorithm under consideration can be of use for the network optimization problem with the given set of providers and its communication capability. Due to its properties the algorithms of that kind don't require researching the global features of the network, only the local one.
Keywords: degree sequence, finite state automaton, edge-switching algorithm, trees, unicyclic graphs, connected graphs
- Летуновский А.А.. О выразимости суперпозициями автоматов c разрешимыми группами (in Russian).
The expressibility problem for finite automaton by system Phi U nu is considered. Phi consists of all k-valued functions and "delay" function. nu – a finite automata system. Previously author has shown the existence of algorithm for checking expressibility of automaton A by Phi U nu, where A is automaton with unconditional transitions. Author solve the problem of expressibility of automaton A by Phi U nu, where A is automaton with soluble group.
Keywords: expressibility, finite automaton, "delay" function, constant automaton, algorithm existence, soluble group
- Ли В.А.. Порядок сложности укладки деревьев на плоскость (in Russian).
This paper considers the problem of trees layout on the two-dimensional rectangular lattice. Such layout characteristics as area and edges length sum are minimized. For certain cases there are offered algorithms which are asymptotically optimal by order in both senses.
Keywords: tree layout, rectangular lattice layout, layout length, layout area, minimal layout, layout algorithm
- Муравьева А.А.. О кодировании дискретных фигур отрезками (in Russian).
The article deals with the coding of discrete figures by the ordered set of all pairwise distances between their points (spectrum). Some properties of the spectra are considered. An algorithm for constructing all the figures with a given spectrum in the space of any dimension is presented.
Keywords: pattern recognition, discrete geometry
- Осокин В.В.. О параллельной параметро-эффективной расшифровке псевдо-булевских функций (in Russian).
We consider the problem of parallel attribute-efficient learning pseudo-boolean functions in the context of exact learning model. We develop an algorithm of attribute-efficient learning the class of interval-constant functions that is optimal on the order. The class contains in particular the class of pseudo-boolean monotone functions and the class of splitting functions. For some subclasses of interval-constant functions we develop an algorithm of attribute-efficient learning that has both optimal parallel complexity and optimal standard complexity on this subclasses.
Keywords: learning complexity, attribute-efficient learning, learning juntas, parallel learning, pseudo-boolean functions, interval-constant functions, monotone functions, exact learning model
- Поцелуевская Е.А.. Криптосистема с открытым ключом на основе задачи об F-выполнимости булевых формул (in Russian).
In the modern world the considerable part of information is processed in electronic form. The necessity of protection of this information during its transmission over open communication channels has lead to a wide spread of public-key cryptographic systems based on different NP-complete problems. In this article the realization of an asymmetric cryptosystem based on the NP-complete S-satisfiability problem is concerned.
Keywords: cryptographic system, encryption, satisfiability, boolean functions
- Поцелуевская Е.А.. Алгоритмы решения задачи об F-выполнимости приближением к классам Шефера (in Russian).
In his work "The complexity of satisfiability problems" Thomas J. Schaefer defined 6 boolean functions classes for which the generalized satisfiability problem (so-called S-satisfiability) is decided in a polynomial time. The discovery of the other classes of functions for which the problem could also be solved fast has a significant practical value. In the current work two algorithms for S-satisfiability problem decision are described. These algorithms are based on the boolean functions approximation to the Schaefer classes and under specified constraints for initial functions have polynomial complexity.
Keywords: algorithm, S-satisfiability, Schaefer classes, complexity
- Родин С.Б.. Линейно реализуемые переходные системы (in Russian).
The main purpose of the article is the investigation of "`linear realized"' semiautomata, i.e. semiautomata, which has the state encoding such as the boolean operator inspired by this state encoding is linear. The necessary criterion of linear realizing property is formulated in the article. Also the lower and upper bound estimation of linear realized semiautomata number are formulated.
Keywords: automata theory, semiautomata, transition systems, assignment, state encoding, complexity
- Соколов А.П.. О сложности взаимной обучаемости почти всех нейронов (in Russian).
Problems of neurons learning complexity are considered in this paper. Threshold functions act as mathemetical model of neurons. Following problem is being studied: what is the complexity of mutual learning of pairs of threshold functions in most cases. Threshold functions are defined by means of linear forms with integer coefficients. Change of any coefficient of the linear form by one is the measure of complexity of mutual learning of threshold functions. It was shown that for quite all pairs of threshold functions the complexity of mutual learning one function into another grows exponentially with growth of number of variables.
Keywords: threshold functions, learning complexity of neural networks
- Соколов А.П.. Об одном многообразии пороговых функций (in Russian).
This paper is devoted to complexity of defining boolean threshold functions by means of linear forms with integer coefficients and absolute term. A very simple example of threshold function with exponential coefficients is presented. For an arbitrary number of variables the corresponding threshold function and integer linear form are explicitly constructed.
Keywords: threshold functions, learning complexity of neural networks
- Соколов А.П.. О конструктивной характеризации пороговых функций, инвариантных относительно групп перестановок (in Russian).
Classes of boolean threshold functions that are invariant by groups of permutations are considered in the paper. Complete description of these classes is obtained. This description is made in terms of groups of permutations which preserve partitions of varibles. It is shown that quite all threshold functions are nonsymmetric, i.e. they are invariant by only identical permutation. Complexity of defining threshold functions by means of linear forms with integer coefficients is also studied. Term <> is introduced. Lower and upper bounds of the amplitude were found for the threshold functions invariant by groups of permutations. The complexity of mutual learning one threshold function into another by means of changing the coefficients is also studied. Lower and upper bounds of complexity were obtained for the threshold functions invariant by groups of permutations.
Keywords: threshold functions, learning complexity of neural networks
- Цымжитов Д.. О мягком декодировании линейных кодов методом минимальных слов (in Russian).
In this paper we consider the modification of well-known minimal-codewords decoding algorithm, having an explicit limitation on the maximum number of iterations in the form of some constant t. If the allotted number of iterations is not enough to obtain optimal solution, the algorithm declares failure. We suggest a lower bound for the constant t, compliance with which ensures that the probability of decoding failure will be close to zero. If n is the length of the codeword, then this bound is O(ln(n)) when n -> inf. This new bound is an improvement of formerly known linear bound.
Keywords: soft-decision decoding, maximum-likelihood decoding, gradient-like decoding, linear block codes, minimal codewords, minimal vectors, decoding complexity
- Чернова Ю.Г.. О состояниях конденсации автоматной модели легких в чистой среде (in Russian).
In the article an automaton model of lungs selfcleaning 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 selfcleaning, state of condensation
- Членова Т.С.. О слоистости булевых функций и функций k-значной логики (in Russian).
The article introduces a lamination of complete systems in Pk, k >= 2. The upper estimate of the lamination of an arbitrary complete system in P2 is obtained. In the case of Pk, k >= 3, the problem of complete systems lamination finiteness is reduced to the problem of Slupecky systems lamination finiteness. A quite wide class of Slupecky systems with the finite lamination is also demonstrated.
Keywords: boolean function, function of k-valued logic, complete system, complexity, lamination
- Шуткин Ю.С.. Об одновременной минимизации объемной и временной сложности контактных и вентильных схем (in Russian).
Parallel optimization of contact circuits size and time complexity is investigated. With size of contact circuit or oriented contact circuit we mean the number of contact elements in the circuit. With time complexity of the circuit we mean the average time which model algorithm spend for calculation of the Boolean function value. The model of the circuit is defined directly by circuit structure and formalized in terms of information graphs. A method of contact and oriented contact circuits synthesis which is asymptotically optimal for both size and time complexity is proposed.
Keywords: Contact circuits, information graphs, contact circuits time complexity
- Соколов А.П.. Письмо в редакцию (in Russian).
Keywords:
|
