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

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

• Редакционный коллектив журнала "Интеллектуальные системы". Валерий Борисович Кудрявцев. К 75-летию со дня рождения.
  
  
  Ключевые слова:
  
  
  Keywords:
• Баранович А.Е.. Информационно-эволюционный подход в теории интеллектуальных систем.
  
  Исследуется проекция информационно-эволюционного подхода к системному анализу и моделированию объективной реальности на предметную область теории интеллектуальных систем. Предлагаемая феноменология теории позволяет с конструктивных позиций оценить используемый аппарат моделирования сложных динамических систем и уточнить основные направления в исследовании универсальных механизмов интеллектуальной деятельности.
  Ключевые слова: интеллектуальных систем теория, интеллекта моделирование, моделирование сложных систем, мышления механизмы универсальные, системный генезис, эволюции объективной реальности модели
  
  The projection of the information-evolutionary approach to the system analysis and modeling of an objective reality on a problem domain of the theory of intelligent systems is investigated. The offered phenomenology of the theory allows to evaluate the used apparatus of modeling of complex dynamic systems from constructive positions and to specify the basic directions in research of universal mechanisms of intellectual activity.
  Keywords: intelligence modeling, models of evolution of an objective reality, modeling of complex systems, systems genesis, theory of intelligent systems, universal mechanisms of thinking
• Щербина О.А.. Удовлетворение ограничений и программирование в ограничениях.
  
  В статье представлен обзор основных направлений удовлетворения ограничений (УО) и программирования в ограничениях. Целью задачи УО является нахождение значений переменных, удовлетворяющих определенным ограничениям. В искусственном интеллекте парадигма УО признана в качестве удобного и эффективного способа моделирования и решения многих прикладных комбинаторных задач. Важная задача оценки конъюнктивных запросов в теории баз данных может рассматриваться как задача УО. Кроме того, задачи УО привлекают большое внимание в теории сложности, так как различные версии задач УО находятся в середине многих стандартных классов сложности, и поскольку у них имеется тенденция не иметь промежуточной сложности, то есть они бывают либо легко разрешимыми, либо полными для стандартных классов сложности. Программирование в ограничениях является парадигмой программирования для декларативного описания и эффективного решения комбинаторных задач, тесно связанной с теорией УО. Рассмотрены примеры использования моделей УО и конкретные приложения.
  Ключевые слова: удовлетворение ограничений; программирование в ограничениях; сложность; комбинаторные задачи
  
  A review of the main directions of constraint satisfaction (CS) and constraint programming is presented. The purpose of the CS problem (CSP) is finding the values of the variables satisfying certain restrictions. In artificial intelligence the CSP paradigm is recognized as a convenient and effective method of modeling and solving many applied combinatorial problems. The important task of answering the conjunctive queries in the database theory can be considered as a CSP. Moreover, CSPs attract great attention in the complexity theory as various versions of CSPs are in the middle of many standard complexity classes and they have a tendency not to have the intermediate complexity, that is they are either easily solvable or complete for the standard complexity classes. Constraint programming is a programming paradigm for the declarative description and effective solving of combinatorial problems, tightly connected to CSP theory. Examples of CS models usage and applications are considered.
  Keywords: constraint satisfaction; constraint programming; complexity; combinatorial problems

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

• Аширматов Б.Д.. Многомерный поиск в обучающих системах.
  
  В данной работе исследуется задача многомерной близости в базе данных на специфической модели данных. Вводится модель данных, исследуются ее свойства. Модель обобщается на непрерывный случай, исследуются также и ее свойства. На основе свойств моделей был предложен и реализован алгоритм поиска в базе данных.
  Ключевые слова: многомерный поиск, обучающие системы, модель данных, алгоритм поиска, задача ближайшего соседа, база данных, многомерная близость, свойства, моделирование, разбиение пространства
  
  In this paper we study the multidimensional nearest neighbor problem in database on specific data model. We introduce a data model, study its properties. The model is generalized to the continuous case, also its features are investigated. Based on models features a search algorithm in database was proposed and implemented.
  Keywords: multidimensional search, learning systems, teaching systems, data model, search algorithm, nearest neighbor problem, database, properties, modeling, space partition
• Пархоменко Д.В.. Метод распознавания множества слов через синтез детерминированного автомата.
  
  В статье предложен метод распознавания с помощью построения распознающего автомата по множеству его выходных слов. Изучены свойства «множеств с кратностями», возникающих на выходе детерминированных автоматов. Даны оценки сложности алгоритма построения автомата по мультимножеству.
  Ключевые слова: автомат, детерминированный автомат, распознавание образов, выходное множество автомата, распознавание через синтез
  
  This paper proposes a recognition method by constructing a finite state automaton recognizing the set of its output words. Properties of multisets, emerging at the output of deterministic automata, are investigated. Estimations of the complexity of the algorithm for constructing an automaton from the multiset are given.
  Keywords: finite state automaton, finite state machine, image recognition, output set of the automaton, image recognition through the FSM synthesis
• Пивоваров А.П.. Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах.
  
  Итеративный поиск представляет собой поиск одного и того же ключа в нескольких линейно упорядоченных списках. Техника частичного каскадирования позволяет отказаться от отдельного бинарного поиска на каждой итерации. Количество требуемой памяти при этом может возрасти не более чем в константное число раз, однако каждая итерация, кроме первой, может быть произведена за меньшее время, ограниченное параметрами ветвления итеративного поиска. В данной статье описывается техника частичного каскадирования и производится оценка размеров получаемых структур данных.
  Ключевые слова: частичное каскадирование, итеративный поиск, компромисс между временем работы и требуемой памятью
  
  Iterative search is a search of one key in multiple linearly ordered lists. Fractional cascading technique can be used to avoid proceeding separate binary searches for all iterations. Amount of required space can be multiplied by at most constant factor. Time required for every iteration except first can be bounded depending on iterative search branching parameters. This paper describes fractional cascading technique and estimates size of obtained data structures.
  Keywords: fractional cascading, iterative search, space-time tradeoff
• Поцелуевская Е.А.. О некоторых свойствах классов Шефера.
  
  Вопрос о размерах и свойствах классов Шефера глубоко изучался начиная с момента описания этих классов самим Шефером. В частности, значительный вклад в изучение данного вопроса внесли работы авторов Алексеева В.Б.,Горшкова С.П, Гизунова С.А, Носова В.А и Тарасова А.В. В данной статье рассматриваются некоторые частные свойства классов Шефера, которые могли бы быть полезными для быстрого решения задачи об F-выполнимости или, напротив, для формирования задач, сложных для решения.
  Ключевые слова: классы Шефера, F-выполнимость, предполнота, алгоритм
  
  The issue of sizes and properties of Schaefer's classes has been being comprehensively examined since Schaefer had described these classes. In particular, a significant contribution to research of this question was introduced by works of the authors Alekseev V.B., Gorshkov S.P., Gizunov S.A., Nosov V.A. and Tarasov A.V. Some particular properties of Schaefer's classes, that could be useful to solve of the S-satisfiability problem fast or, alternatively, to form difficult for solution tasks, are considered in the article.
  Keywords: Schaefer's classes, S-satisfiability, precompleteness, algorithm
• Снегова Е.А.. Критерий сводимости задачи об опасной близости к задаче о прокалывании.
  
  В работе рассматривается задача о поиске движущихся объектов, которые могут столкнуться с движущимся объектом-запросом, где под столкновением понимается нахождение объектов в опасной близости. Приведен критерий сводимости данной задачи к одномерной задаче о прокалывании.
  Ключевые слова: базы данных движущихся объектов, пространственно-временные базы данных, информационный граф, сложность
  
  Consider two streams of moving objects inside the square [0, 1]². One of the streams moves from South to North and we call it a stream of queries, and another stream moves from West to East and we call it a stream of objects. Moving objects closeness problem (MOC problem) consists of enumeration for every new query those and only those objects that will be not far than . from the query in Manhattan metrics at some moment of time during the query's or the objects' movements inside the square. In this paper we present and prove criteria for reducibility of the MOC problem to one-dimensional stabbing problem.
  Keywords: databases of moving objects, spatio-temporal databases, information graph, complexity
• Чучалин А.Г., Кудрявцев В.Б., Алексеев Д.В., Анаев Э.Х., Анохина Т.Н., Носов М.В., Ревельский А.И., Ревельский И.А., Родионов А.А.. Математико-компьютерная обработка КВВ-экспериментов по распознаванию легочных заболеваний.
  
  Статья посвящена исследованию возможности диагностики хронической обструктивной болезни легких (ХОБЛ) и бронхиальной астмы, основанной на изучении состава среднелетучих органических соединений на ультранизком уровне в конденсате выдыхаемого воздуха (КВВ), с использованием методов выделения примесей и хромато-масс-спектрометрическом анализе всего концентрата аналитов КВВ-экспериментов. На основании обработки результатов анализа 70 образцов КВВ, собранных у здоровых, больных ХОБЛ и бронхиальной астмой людей, с использованием специально разработанного алгоритма, основанного на линейных методах теории распознавания образов, установлено, что можно различить здоровых и больных бронхиальной астмой с надежностью 75%, здоровых и больных ХОБЛ – с надежностью 85%, больных бронхиальной астмой и ХОБЛ – с надежностью 83%. Установлен ряд веществ, которые могут быть потенциальными маркерами рассматриваемых заболеваний.
  Ключевые слова: распознавание образов, хроническая обструктивная болезнь легких, бронхиальная астма, конденсат выдыхаемого воздуха, хромато-масс-спектрометрический анализ
  
  The article is devoted to research of methods diagnosis of COPD and asthma based on study of semi-volatile organic compounds (SvOC) on ultra-low level in exhaled breath condensate (EBC) with use of methods of admixture detection and chromatography-mass spectrometry of EBC. There were collected 70 EBC samples from patients with acute exacerbations of obstructive lung diseases (20 – with asthma, 20 – with COPD) and 30 healthy nonsmokers using an ECoScreen condenser. Testing for SvOC with different polarity in EBC was conducted by gas chromatography/mass-spectrometry (GC/MS) method. The collected data were analyzed using an algorithm based on linear methods of pattern recognition theory. The methods showed that it is possible to distinguish asthma patients from healthy with reliabilty equal to 75%, COPD patients from healthy with reliability 85% and COPD patients from asthma patients with reliabilty 83%. Some substances were detected that may can potentially be the markers for those diseases.
  Keywords: pattern recognition, chronic obstructive pulmonary disease, asthma, exhaled breath condensate, chromatography-mass spectrometry

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

• Агниашвили П.Г.. Однозначность восстановления изображения по его коду в n-мерном случае.
  
  В работе рассматривается дискретно-геометрический подход к распознаванию зрительных образов в случае произвольной конечной размерности. Найдены необходимые и достаточные условия, при которых возможно однозначное восстановление изображения по его коду. Получена геометрическая интерпретация результатов, описывающая класс допустимых изображений. Отдельно рассмотрен случай вырожденных изображений.
  Ключевые слова: распознавание образов, код изображения, модифицированный код, однозначность восстановления изображения
  
  The paper considers discrete-geometrical approach to visual recognition in case of arbitrary finite dimension. Necessary and sufficient conditions are obtained that give a criterion of unique image recovery by its code. A geometrical interpretation is given that describes the class of allowable images. The case of degenerate images is particularly considered.
  Keywords: visual recognition, image code, modified code, image recovery uniqueness
• Галатенко А.В.. Об аппроксимации регулярных языков безопасными языками.
  
  В работе исследуются аппроксимативные свойства безопасных языков, введенных в статье ``Автоматные модели защищенных компьютерных систем''. Рассматривается приближение произвольных регулярных языков сверху и снизу, а также возможные значения функции роста безопасных языков.
  Ключевые слова: безопасные языки, регулярные языки, приближение языков, функция роста
  
  We investigate approximation properties of secure languages introduced in the atricle ``Automata models of secure computer systems''. We consider lower and upper approximations of regular languages and estimate possible values of secure languages growth.
  Keywords: secure languages, regular languages, language approximation, growth functions
• Дергач П.С.. Об однозначности алфавитного декодирования регулярных текстов.
  
  А.А. Марковым было показано,что проблема однозначности алфавитного декодирования всех текстов над заданным конечным алфавитом A сводится к декодированию конечного числа слов над алфавитом A длины не большей некоторой вычислимой величины, зависящей от длины схемы кодирования, мощности алфавита A и др. параметров [1]. В этой статье исследован случай, когда кодируемое множество слов является любым регулярным множеством. Показывается, что результат Маркова A.А. может быть обобщен на случай алфавитного декодирования любого регулярного множества слов над алфавитом A.
  Ключевые слова: однозначное декодирование, регулярный язык, алфавитное кодирование
  
  А.А. Markov reduced the one-to-one problem of the alphabetic decryption of all messages in the fixed alphabet A to the decryption of the finite set of words in this alphabet with length less than some fixed constant. This constant is determined by the encryption scheme, power of the alphabet A and some other quantities [1]. This paper considers the case when encrypted set is regular. It is shown that Markov's result may be generalized to the case of alphabetic decryption of the arbitrary regular set.
  Keywords: one-to-one property of the alphabetic decryption, regular text
• Иванов И.Е.. Некоторые классы функций, вычислимые автоматами.
  
  В работе описаны замкнутые классы вычислимых функций, вычисляемых конечными автоматами, автоматами с магазинной памятью и автоматами с 2 магазинами.
  Ключевые слова: автомат, автомат с магазинной памятью, вычислимая функция
  
  In the current paper we consider some classes of functions computable by finite automata, pushdown automata and 2-way pushdown automata.
  Keywords: automata, pushdown automata, computable function
• Кибкало М.А.. Об автоматной сложности классов Поста булевых функций.
  
  Наборы, на которых функция f:{0,1}ⁿ → {0,1} принимает значение 1, можно рассматривать как слова конечного языка L_f. Минимальное число состояний автомата, представляющего язык L_f, называется автоматной сложностью функции f. Автоматной сложностью множества булевых функций называется максимальная автоматная сложность функции из этого множества. Значением функции Шеннона для класса булевых функций K называется автоматная сложность множества K ∩ Pⁿ₂ функций от n переменных из K. В статье рассматривается сложность автоматной реализации булевых функций и устанав-ливаются точные значения и асимптотические оценки функции Шеннона для замкну-тых классов булевых функций, входящих в решетку Поста.
  Ключевые слова: булева функция, детерминированный конечный автомат, автоматная сложность, замкнутый класс Поста, решетка Поста, функция Шеннона
  
  Boolean vectors for which a Boolean function f:{0,1}ⁿ → {0,1} is equal to 1 could be treated as words of the finite language L_f. Let automata complexity of f be the minimal state number of the deterministic finite automaton accepting L_f. The automata complexity of a Boolean function set is the maximal complexity of a function from this set. For a Boolean function class K we define the Shannon function as the automata complexity of the n-variable function set from K. Here we consider the automata complexity of Boolean functions and determine precise values or asymptotic estimations of Shannon functions for all closed Post classes of Boolean functions.
  Keywords: boolean function, deterministic finite automaton, automata complexity, closed Post class, Shannon function
• Летуновский А.А.. О задаче выразимости автоматов относительно суперпозиции для систем с фиксированной добавкой.
  
  Рассматривается задача выразимости конечного группового автомата Медведева M суперпозициями систем вида Ф U R, где Ф состоит из всех булевых функций и "задержки" , R – произвольная конечная система автоматов. Ранее автор показал, что для группового автомата Медведева M, группа которого является разрешимой, существует алгоритм проверки принадлежности M множеству [Ф U R]. В настоящей работе решается аналогичная задача выразимости произвольных групповых автоматов Медведева.
  Ключевые слова: автомат, суперпозиция, булева функция, выразимость
  
  We consider the problem of expressibility finite group Medvedev-automaton M using superpositions F U R, where F consists of all Boolean functions and the "delay", R – arbitrary finite system of automata. Earlier, the author showed that for Medvedev-automaton solvable group M, there exists an algorithm to test membership M in [F U R]. In this paper we solve a similar problem of expressibility arbitrary group Medvedev-automata.
  Keywords: automaton, superpositions, Boolean functions, expressibility
• Мастихина А.А.. Частичное угадывание сверхсобытий, порожденных простыми LL(1)-грамматиками.
  
  Автомат угадывает символ входной последовательности, если он выдает этот символ на выходе в предыдущий момент времени. В работе рассмотрен вопрос, можно ли с помощью детерминированного автомата частично предвосхитить некоторое сверхсобытие, то есть угадать некоторую ненулевую долю символов каждого сверхслова из этого сверхсобытия. Получены критерий и алгоритм, позволяющие это установить для сверхсобытий, образованных сверхитерацией языков, порожденных простыми LL(1)-грамматиками.
  Ключевые слова: угадывающие автоматы, автоматы с магазинной памятью, частичное угадывание, сверхсобытия, простые LL(1)-грамматики
  
  A machine predicts an input symbol if this symbol is equal to its output symbol in previous moment. A machine partially predicts a set of w-words if it predicts some substantial part of symbols in any w-word. An algorithm determining wether the set of w-words generated by LL(1) grammar is partially predictable is described.
  Keywords: predicting automata, pushdown automata, partial prediction, w-languages, LL(1) grammars