Содержание журнала "Интеллектуальные системы"
Том 14, выпуск 1-4, 2010 г.

Часть 1. Общие проблемы теории интеллектуальных систем

• Баранович А.Е.. О систематизации аксиоматического аппарата предметной области «Искусственный интеллект».
  
  C позиций информационно-эволюционного подхода рассматриваются вопросы систематизации аксиоматического аппарата предметной области науки, именуемой в настоящее время, <<искусственным интеллектом>> (ИИ). В контекстах научного и обыденного сознания речь идет о том, что есть <<естественно>>, а что <<неестественно>> и <<искусственно>> в ИИ. Результаты проведенного анализа позволяют внести существенные изменения в феноменологию его развития.
  Ключевые слова: "Большая история"; информатизация; информационно-эволюционный подход; интеллект естественный, искусственный; интеллект вычислительный, компьютерный, технический; моделирование; системы антропогенные, антропоморфные, интеллектуальные, материальные
  
  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

Часть 2. Специальные вопросы теории интеллектуальных систем

• Козлов В.Н.. Доказательность и эвристика при распознавании визуальных образов.
  
  В статье в краткой форме излагаются основные идеи, положенные в основу дискретно-геометрического подхода к распознаванию зрительных образов, и на содержательном уровне описываются полученные результаты. Приводятся некоторые соображения о роли эвристики в распознавании визуальных образов.
  Ключевые слова: распознавание образов, зрительные образы, 3D-реконструкция изображений
  
  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
• Маслобоев А.В., Ломов П.А.. Использование общесистемного тезауруса как основы интеллектуального пользовательского интерфейса системы распределенного семантического поиска.
  
  В статье рассмотрена проблема использования общесистемного расширяемого тезауруса как основы интеллектуального интерфейса информационной системы распределенного семантического поиска. Предложено расширенное элементами онтологии DOLCE и метасвойствами определение разделяемого тезауруса. Разработана технология формирования запроса на основе правил определения возможных вариантов его усложнения, что позволяет использовать тезаурус в качестве основы для разработки интеллектуального пользовательского интерфейса.
  Ключевые слова: информационная система, онтология, тезаурус, семантическая интеграция информации, формирование запроса, интеллектуальный пользовательский интерфейс
  
  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
• Адылова Л.Р.. О распознавании лиц.
  
  Изучаются методы геометрического распознавания расовой принадлежности лица человека по фотографии. Находятся геометрические инварианты лица, позволяющие отнести его к одному из трех расовых кластеров: монголоидному, европеоидному, негроидному. Таких инвариантов в виде точек лица при определенным образом заданной системе координат оказалось 11. По этим точкам строился код, к которому затем применялись различные методы для распознавания лиц.
  Ключевые слова: распознавание, инварианты, геометрические методы, раса, обучение
  
  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 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
• Газарян В.А. Матвеева Т.В. Чехонина Ю.Г. Шаховская А.К.. О теоретико-возможностных методах анализа эффективности лечения.
  
  В [1] показано, что для решения многих задач медицинской диагностики естественно применение не вероятностной, а возможностной модели анализа и интерпретации данных [2]. Построена возможностная модель симптомов заболевания, возможностная модель постановки медицинского диагноза. Целью данной работы является разработка возможностных методов анализа эффективности лечения пациентов, страдающих хроническим панкреатитом, в частности, – метода оценивания эффекта, производимого тем или иным препаратом на состояние и на биохимические показатели крови таких пациентов.
  Ключевые слова: теория возможностей, проверка статистических гипотез, t-критерий, эффективность лечения, хронический панкреатит
  
  [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
• Галатенко А.В.. О восстановлении разбиения безопасности.
  
  В работе рассматривается автоматная система, часть состояний которой объявляется безопасной. Исследуется сложность восстановления разбиения множества состояний для безопасных и эпсилон-безопасных языков, введенных в работе ``Автоматные модели защищенных компьютерных систем''.
  Ключевые слова: Конечный автомат, автоматная модель, кратный условный эксперимент
  
  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
• Гасанов Э.Э., Колесниченко А.В.. Предикатная эквивалентность формул алгебры логики.
  
  В работе исследуется предикатная эквивалентность формул, вводимая с помощью множества предикатов P и множества перестановок M. Множества P и M согласованы, если соответствующая им предикатная эквивалентность совпадает с обычной эквивалентностью формул. Доказывается критерий согласованности множеств. Предложен алгоритм построения согласованных множеств предикатов. Приводятся серии примеров взаимно согласованных множеств P и M с разными соотношениями сложностных характеристик.
  Ключевые слова: алгебра логики, логика предикатов, аналитическое описание геометрических фигур
  
  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 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
• Колесникова С.И.. Свойства корректной модификации метода парных сравнений.
  
  Рассматриваются свойства функции относительного сходства как функции скаляризации критериев, применение которой разрешает нежелательные особенности известного метода парных сравнений Т. Саати (МАИ), связанные с применением линейной свертки и единичной нормализации при получении весовых коэффициентов альтернатив. Рассмотрен пример применения модификации МАИ.
  Ключевые слова: метод анализа иерархий, весовые коэффициенты альтернатив, интеллектуальная система, тестовое распознавание образов, качество принятия решения
  
  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
• Лёвин В.Ю.. О повышении криптостойкости однонаправленных хеш-функций.
  
  В статье приводится конструктивные предложения решения задачи обеспечения подлинности и достоверности цифровых документов с использованием однонаправленных хеш-функций. Численно оценена стойкость однонаправленных хеш-функций при различных видах их взлома. Предложен ряд алгоритмов позволяющих серьезно повысить криптостойкость хеш-функций без переделки их внутренных алгоритмов. Среди предложенных методов по повышению криптостойкости выбран лучший по скорости и качеству. Показано, что метод суффиксной суперпозиции, предложенный Б. Шнаером, не годится для использования в этих целях. Предложенные в статье методы могут быть использованы для улучшения большинства однонаправленных хеш-функций, таких как, MD4, MD5, RIPEMD, SHA, ГОСТ 34 11-94.
  Ключевые слова: однонаправленные хеш-функции, метод Шнайера, целостность, информационная безопасность
  
  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
• Пархоменко Д.В.. Моделирование вероятностными источниками.
  
  Скрытая Марковская Модель (СММ) – это марковская цепь, обладающая видимым пользователю «выходом». В каждом состоянии, в соответствие с зависящим от состояния законом распределения, СММ выдает выходной символ и переходит в другое состояние как марковская цепь. В случае конечного выходного алфавита СММ называют вероятностным источником. В статье описано применение аппарата скрытых марковских моделей и рассказано об актуальных инженерных задачах, где они используются.
  Ключевые слова: скрытые марковские модели, распознавание образов, вероятностный источник
  
  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
• Петюшко А.А.. О марковских случайных полях и их связи с цепями Маркова.
  
  В данной работе рассматриваются марковские и скрытые марковские случайные поля. Устанавливаются взаимосвязи между марковскими случайными полями и цепями Маркова, а также между скрытыми марковскими полями и скрытыми марковскими моделями посредством введенных порожденных случайных величин.
  Ключевые слова: Марковское случайное поле, скрытое марковское случайное поле, марковская цепь, скрытая марковская модель
  
  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
• Пивоваров А.П.. Моделирование вычислительных задач информационного поиска.
  
  Работа посвящена определению и сравнению двух моделей для описания алгоритмов решения вычислительных задач информационного поиска. Первая модель почти совпадает с понятием информационного графа, вторая получается использованием для вычислений автоматных функций. Исследование производится на примере модельной задачи –- вычислении размера ответа задачи одномерного интервального поиска. Обосновано преимущество использования автоматных функций для вычислительных задач информационного поиска.
  Ключевые слова: вычислительная задача информационного поиска, информационный граф, вычислительный информационный граф, одномерный интервальный поиск, моделирование поиска, характеристики алгоритмов поиска
  
  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
• Рыков Д.О.. Об алгоритмах проверки правильности семейств функций.
  
  В работе изучается вопрос проверки правильности семейств функций. Построен алгоритм проверки правильности, учитывающий информацию о графе семейства. Сложность приведенного алгоритма зависит от порядков сильных компонент графа. Построен алгоритм проверки правильности семейств монотонных функций. В основе алгоритма лежат два свойства правильных семейств монотонных функций: наличие константы и функциональная замкнутость класса монотонных функций в $P_2$. Сложность алгоритма значительно меньше сложности стандартных алгоритмов проверки правильности.
  Ключевые слова: Правильное семейство функций, алгоритм проверки правильности семейств функций, граф существенной зависимости семейства функций, семейство монотонных функций, критерий правильности семейства функций
  
  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.

Часть 3. Математические модели

• Блохина Г.Н., Кудрявцев В.В.. О спектрах классов Поста булевских функций.
  
  В работе изучаются длины базисов классов Поста булевских функций. Множество всех длин базисов такого класса называется его спектром. Основным результатом работы является нахождение всех спектров классов Поста.
  Ключевые слова: булевская функция, спектр, базис, классы Поста
  
  
  Keywords:
• Болонкин М.В.. О распознавании вирусов в регулярных текстах.
  
  Исследуются свойства регулярных выражений и их тождественных преобразований для распознавания полиморфных вирусов. Определена модель зараженности, сильной и слабой зараженности программы вирусом, исследованы некоторые классы выражений. Доказаны критерии зараженности программы вирусом как для множества программ, не содержащих оператор Клини, так и подмножества программ, содержащих его, но глубины вложенности не более 1.
  Ключевые слова: распознавание, вирусы, регулярное выражение, подформулы
  
  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
• Кибкало М.А.. Об автоматной сложности некоторых классов булевых функций.
  
  Под сложностью языка (его функцией Шеннона) будем понимать число состояний в представляющем его приведенном автомате. В данной работе устанавливается, что булевы языки, соответствующие замкнутым классам Поста, разбиваются на три пояса в соответствие с асимптотикой функции Шеннона, причем для некоторых классов устанавливается точное значение функции Шеннона.
  Ключевые слова: сложность, конечные автоматы, конечный автомат, булевы функции, булева функция, решетка Поста, функция Шеннона
  
  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
• Кучеренко Н.С.. Задача поиска по ключу с определением позиции.
  
  В работе изучаются два способа формализации задачи поиска по ключу – задача поиска идентичных объектов (ЗПИО) и расширенная ЗПИО. Показано, что сложность поиска для этих способов формализации одинакова. Описан алгоритм преобразования, который алгоритм поиска для ЗПИО преобразует в алгоритм поиска для расширенной ЗПИО без изменения сложности поиска.
  Ключевые слова: базы данных, поиск по ключу, алгоритм поиска
  
  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 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 разрешимыми группами.
  
  Рассматривается задача выразимости конечного автомата A суперпозициями системы Phi U nu, где Phi состоит из всех функций k-значной логики и "задержки", nu – произвольная конечная система автоматов. Ранее автор показал, что для автомата A с безусловными переходами существует алгоритм проверки выразимости A через Phi U nu. В настоящей работе решается задача алгоритмической разрешимости задачи выразимости автомата с разрешимой группой через систему Phi U nu.
  Ключевые слова: выразимость, конечный автомат, задержка, константный автомат, алгоритмическая разрешимость, разрешимая группа
  
  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
• Ли В.А.. Порядок сложности укладки деревьев на плоскость.
  
  В работе рассматривается задача укладки деревьев на 2-х мерную прямоугольную решетку. Предложено несколько алгоритмов укладки, оптимальных по порядку, как для суммарной длины ребер, так и для площади укладки.
  Ключевые слова: укладка дерева, укладка в прямоугольную решетку, длина укладки, площадь укладки, минимальная укладка, алгоритм укладки
  
  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
• Муравьева А.А.. О кодировании дискретных фигур отрезками.
  
  В работе изучается кодировка дискретных фигур упорядоченным по величине набором всех попарных расстояний между их точками (спектром). Приводится условный алгоритм построения всех фигур с заданным спектром в пространстве любой размерности. Изучаются свойства спектров и способы продолжения подспектра, являющегося невозрастающей конечной последовательностью чисел, до спектра путем добавления новых элементов.
  Ключевые слова: распознавание образов, дискретная геометрия
  
  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
• Осокин В.В.. О параллельной параметро-эффективной расшифровке псевдо-булевских функций.
  
  В работе рассмотрена задача параллельной параметро-эффективной расшифровки псевдо-булевских функций в рамках модели точной расшифровки. Для интервально-постоянных функций, примерами которых являются псевдо-булевские монотонные функции и разбивающие функции, предложен оптимальный по порядку алгоритм параметро-эффективной расшифровки. Предложен параметро-эффективный алгоритм расшифровки некоторых подклассов интервально-постоянных функций с оптимальной по порядку параллельной сложностью и оптимальной по порядку обычной сложностью.
  Ключевые слова: сложность расшифровки функций, параметро-эффективная расшифровка, параллельная расшифровка, псевдо-булевские функции, интервально-постоянные функции, монотонные функции, модель точной расшифровки
  
  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-выполнимости булевых формул.
  
  В современном мире значительная часть информации обрабатывается в электронном виде. В связи с необходимостью обеспечить защиту такой информации при передаче по открытым каналам связи, широкое распространение получили криптографические системы с открытым ключом, основанные на различных NP-полных задачах. В настоящей работе рассматривается реализация асимметричной криптографической системы на основе NP-полной задачи об F-выполнимости булевых формул.
  Ключевые слова: криптосистема, шифрование, выполнимость, булевы функции
  
  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-выполнимости приближением к классам Шефера.
  
  В своей работе "The complexity of satisfiability problems" Шефер выделил 6 классов булевых функций, для которых обобщенная проблема выполнимости (т.н. F-выполнимость) решается за полиномиальное время. Нахождение других классов функций, для которых задача также решалась бы быстро, имеет значительную практическую ценность. В настоящей работе представлены два алгоритма решения задачи об F-выполнимости, которые основаны на приближении булевых функций к классам Шефера, и при определенных ограничениях на исходные функции, имеют полиномиальную сложность.
  Ключевые слова: алгоритм, F-выполнимость, классы Шефера, сложность
  
  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
• Родин С.Б.. Линейно реализуемые переходные системы.
  
  Данная работа посвящена изучению "линейно реализуемых" переходных систем, т.е. переходных систем, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевкий оператор является линейным. В работе приведено необходимое условие линейной реализуемости переходной системы. Также приведены нижняя и верхняя оценка числа линейно реализуемых переходных систем.
  Ключевые слова: теория автоматов, переходные системы, кодирование, сложность
  
  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
• Соколов А.П.. О сложности взаимной обучаемости почти всех нейронов.
  
  Работа посвящена вопросам сложности обучения нейронов. В качестве математической модели нейронов рассматриваются пороговые функции алгебры логики. Рассматривается вопрос сложности взаимной обучаемости пар пороговых функций в большинстве случаев. В качестве средства задания пороговых функций выстапают целочисленные линейные формы. В качестве меры сложности процесса обучения принято единичное изменение весового коэффициента линейной формы. Показано, что для почти всех пар пороговых функций от n переменных сложность перестройки одной пороговой функции, заданной линейной формой, в другую с ростом n растет экспоненциально.
  Ключевые слова: пороговые функции, сложность обучения нейросетей
  
  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
• Соколов А.П.. Об одном многообразии пороговых функций.
  
  В работе исследуется сложность задания пороговых функций алгебры логики линейными формами с целочисленными коэффициентами и свободным членом. Приводится очень простой пример пороговой функции, при задании которой целочисленными линейными формами необходимы экспоненциальные весовые коэффициенты. При этом, для произвольного числа переменных данная линейная форма явно предъявляется.
  Ключевые слова: пороговые функции, сложность обучения нейросетей
  
  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
• Соколов А.П.. О конструктивной характеризации пороговых функций, инвариантных относительно групп перестановок.
  
  В работе рассматриваются классы пороговых функций, инвариантных относительно групп перестановок. Получено полное описание данных классов в терминах групп перестановок, сохраняющих разбиения. Показано, что <<почти все>> пороговые функции являются несимметрическими, то есть инвариантными относительно лишь тождественной перестановки. Рассматриваются вопросы сложности задания пороговых функций целочисленными линейными формами. Введено понятие размаха пороговой функции. Получены верхняя и нижняя оценки на величину размаха для пороговых функций, инвариантных относительно групп перестановок. Исследуется сложность взаимной перестройки пороговых функций, инвариантных относительно групп перестановок, путем пошагового изменения коэффициентов линейных форм. Получены верхняя и нижняя оценки сложности перестройки в худшем случае.
  Ключевые слова: пороговые функции, сложность обучения нейросетей
  
  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
• Цымжитов Д.. О мягком декодировании линейных кодов методом минимальных слов.
  
  В работе рассмотрена модификация известного алгоритма ML-декодирования методом минимальных слов, имеющая явное ограничение на максимальное количество итераций в виде некоторого числа t. В случае, если отведенного числа итераций недостаточно для получения оптимального решения, алгоритм объявляет об отказе. Предложена нижняя граница для константы t, соблюдение которой гарантирует, что вероятность отказа декодера будет близка к нулю. Если n – длина кодового слова, то данная граница лежит в классе O(ln(n)) при n->inf. Полученная оценка является улучшением известной ранее линейной оценки.
  Ключевые слова: мягкое декодирование, декодирование по максимуму правдоподобия, линейные коды, сложность декодирования, минимальные кодовые слова
  
  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 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-значной логики.
  
  В статье вводится понятие слоистости полных систем в P_k, k>=2. Получена оценка сверху слоистости произвольной полной системы в P₂. В случае P_k, k >= 3, произведено сведение проблемы конечности слоистости полных систем к проблеме конечности слоистости систем Слупецкого. Также приведен довольно широкий класс систем Слупецкого, слоистость которых конечна.
  Ключевые слова: булева функция, функция k-значной логики, полная система, сложность, слоистость
  
  The article introduces a lamination of complete systems in P_k, k >= 2. The upper estimate of the lamination of an arbitrary complete system in P₂ is obtained. In the case of P_k, 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
• Шуткин Ю.С.. Об одновременной минимизации объемной и временной сложности контактных и вентильных схем.
  
  Рассматривается задача одновременной минимизации объемной и временной сложности контактных и вентильных схем. Под объемной сложностью контактной или вентильной схемы понимается ее стандартная сложность, определяемая числом ребер в схеме. Под временной сложностью понимается среднее время работы алгоритма, моделирующего контактную или вентильную схему. Модель схемы строится в виде информационного графа, для которого алгоритм функционирования определяется уже формально. Получено асимптотически наилучшее решение задачи одновременной минимизации временной и объемной сложности контактных и вентильных схем.
  Ключевые слова: Контактные схемы, информационные графы, временная сложность контактных схем
  
  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
• Соколов А.П.. Письмо в редакцию.
  
  Глубокоуважаемая редакция, прошу принять к рассмотрению замечания по следующим моим работам, опубликованным в журнале "Интеллектуальные системы"...
  Ключевые слова:
  
  
  Keywords: