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

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

• Редакционный коллектив журнала "Интеллектуальные системы". Валерий Борисович Кудрявцев. К 75-летию со дня рождения.
• Баранович А.Е.. Информационно-эволюционный подход в теории интеллектуальных систем. Исследуется проекция информационно-эволюционного подхода к системному анализу и моделированию объективной реальности на предметную область теории интеллектуальных систем. Предлагаемая феноменология теории позволяет с конструктивных позиций оценить используемый аппарат моделирования сложных динамических систем и уточнить основные направления в исследовании универсальных механизмов интеллектуальной деятельности.
  Ключевые слова: интеллектуальных систем теория, интеллекта моделирование, моделирование сложных систем, мышления механизмы универсальные, системный генезис, эволюции объективной реальности модели
• Щербина О.А.. Удовлетворение ограничений и программирование в ограничениях. В статье представлен обзор основных направлений удовлетворения ограничений (УО) и программирования в ограничениях. Целью задачи УО является нахождение значений переменных, удовлетворяющих определенным ограничениям. В искусственном интеллекте парадигма УО признана в качестве удобного и эффективного способа моделирования и решения многих прикладных комбинаторных задач. Важная задача оценки конъюнктивных запросов в теории баз данных может рассматриваться как задача УО. Кроме того, задачи УО привлекают большое внимание в теории сложности, так как различные версии задач УО находятся в середине многих стандартных классов сложности, и поскольку у них имеется тенденция не иметь промежуточной сложности, то есть они бывают либо легко разрешимыми, либо полными для стандартных классов сложности. Программирование в ограничениях является парадигмой программирования для декларативного описания и эффективного решения комбинаторных задач, тесно связанной с теорией УО. Рассмотрены примеры использования моделей УО и конкретные приложения.
  Ключевые слова: удовлетворение ограничений; программирование в ограничениях; сложность; комбинаторные задачи

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

• Аширматов Б.Д.. Многомерный поиск в обучающих системах. В данной работе исследуется задача многомерной близости в базе данных на специфической модели данных. Вводится модель данных, исследуются ее свойства. Модель обобщается на непрерывный случай, исследуются также и ее свойства. На основе свойств моделей был предложен и реализован алгоритм поиска в базе данных.
  Ключевые слова: многомерный поиск, обучающие системы, модель данных, алгоритм поиска, задача ближайшего соседа, база данных, многомерная близость, свойства, моделирование, разбиение пространства
• Пархоменко Д.В.. Метод распознавания множества слов через синтез детерминированного автомата. В статье предложен метод распознавания с помощью построения распознающего автомата по множеству его выходных слов. Изучены свойства «множеств с кратностями», возникающих на выходе детерминированных автоматов. Даны оценки сложности алгоритма построения автомата по мультимножеству.
  Ключевые слова: автомат, детерминированный автомат, распознавание образов, выходное множество автомата, распознавание через синтез
• Пивоваров А.П.. Техника частичного каскадирования для итеративного поиска в линейно упорядоченных множествах. Итеративный поиск представляет собой поиск одного и того же ключа в нескольких линейно упорядоченных списках. Техника частичного каскадирования позволяет отказаться от отдельного бинарного поиска на каждой итерации. Количество требуемой памяти при этом может возрасти не более чем в константное число раз, однако каждая итерация, кроме первой, может быть произведена за меньшее время, ограниченное параметрами ветвления итеративного поиска. В данной статье описывается техника частичного каскадирования и производится оценка размеров получаемых структур данных.
  Ключевые слова: частичное каскадирование, итеративный поиск, компромисс между временем работы и требуемой памятью
• Поцелуевская Е.А.. О некоторых свойствах классов Шефера. Вопрос о размерах и свойствах классов Шефера глубоко изучался начиная с момента описания этих классов самим Шефером. В частности, значительный вклад в изучение данного вопроса внесли работы авторов Алексеева В.Б.,Горшкова С.П, Гизунова С.А, Носова В.А и Тарасова А.В. В данной статье рассматриваются некоторые частные свойства классов Шефера, которые могли бы быть полезными для быстрого решения задачи об F-выполнимости или, напротив, для формирования задач, сложных для решения.
  Ключевые слова: классы Шефера, F-выполнимость, предполнота, алгоритм
• Снегова Е.А.. Критерий сводимости задачи об опасной близости к задаче о прокалывании. В работе рассматривается задача о поиске движущихся объектов, которые могут столкнуться с движущимся объектом-запросом, где под столкновением понимается нахождение объектов в опасной близости. Приведен критерий сводимости данной задачи к одномерной задаче о прокалывании.
  Ключевые слова: базы данных движущихся объектов, пространственно-временные базы данных, информационный граф, сложность
• Чучалин А.Г., Кудрявцев В.Б., Алексеев Д.В., Анаев Э.Х., Анохина Т.Н., Носов М.В., Ревельский А.И., Ревельский И.А., Родионов А.А.. Математико-компьютерная обработка КВВ-экспериментов по распознаванию легочных заболеваний. Статья посвящена исследованию возможности диагностики хронической обструктивной болезни легких (ХОБЛ) и бронхиальной астмы, основанной на изучении состава среднелетучих органических соединений на ультранизком уровне в конденсате выдыхаемого воздуха (КВВ), с использованием методов выделения примесей и хромато-масс-спектрометрическом анализе всего концентрата аналитов КВВ-экспериментов. На основании обработки результатов анализа 70 образцов КВВ, собранных у здоровых, больных ХОБЛ и бронхиальной астмой людей, с использованием специально разработанного алгоритма, основанного на линейных методах теории распознавания образов, установлено, что можно различить здоровых и больных бронхиальной астмой с надежностью 75%, здоровых и больных ХОБЛ – с надежностью 85%, больных бронхиальной астмой и ХОБЛ – с надежностью 83%. Установлен ряд веществ, которые могут быть потенциальными маркерами рассматриваемых заболеваний.
  Ключевые слова: распознавание образов, хроническая обструктивная болезнь легких, бронхиальная астма, конденсат выдыхаемого воздуха, хромато-масс-спектрометрический анализ

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

• Агниашвили П.Г.. Однозначность восстановления изображения по его коду в n-мерном случае. В работе рассматривается дискретно-геометрический подход к распознаванию зрительных образов в случае произвольной конечной размерности. Найдены необходимые и достаточные условия, при которых возможно однозначное восстановление изображения по его коду. Получена геометрическая интерпретация результатов, описывающая класс допустимых изображений. Отдельно рассмотрен случай вырожденных изображений.
  Ключевые слова: распознавание образов, код изображения, модифицированный код, однозначность восстановления изображения
• Галатенко А.В.. Об аппроксимации регулярных языков безопасными языками. В работе исследуются аппроксимативные свойства безопасных языков, введенных в статье ``Автоматные модели защищенных компьютерных систем''. Рассматривается приближение произвольных регулярных языков сверху и снизу, а также возможные значения функции роста безопасных языков.
  Ключевые слова: безопасные языки, регулярные языки, приближение языков, функция роста
• Дергач П.С.. Об однозначности алфавитного декодирования регулярных текстов. А.А. Марковым было показано,что проблема однозначности алфавитного декодирования всех текстов над заданным конечным алфавитом A сводится к декодированию конечного числа слов над алфавитом A длины не большей некоторой вычислимой величины, зависящей от длины схемы кодирования, мощности алфавита A и др. параметров [1]. В этой статье исследован случай, когда кодируемое множество слов является любым регулярным множеством. Показывается, что результат Маркова A.А. может быть обобщен на случай алфавитного декодирования любого регулярного множества слов над алфавитом A.
  Ключевые слова: однозначное декодирование, регулярный язык, алфавитное кодирование
• Иванов И.Е.. Некоторые классы функций, вычислимые автоматами. В работе описаны замкнутые классы вычислимых функций, вычисляемых конечными автоматами, автоматами с магазинной памятью и автоматами с 2 магазинами.
  Ключевые слова: автомат, автомат с магазинной памятью, вычислимая функция
• Кибкало М.А.. Об автоматной сложности классов Поста булевых функций. Наборы, на которых функция f:{0,1}ⁿ → {0,1} принимает значение 1, можно рассматривать как слова конечного языка L_f. Минимальное число состояний автомата, представляющего язык L_f, называется автоматной сложностью функции f. Автоматной сложностью множества булевых функций называется максимальная автоматная сложность функции из этого множества. Значением функции Шеннона для класса булевых функций K называется автоматная сложность множества K ∩ Pⁿ₂ функций от n переменных из K. В статье рассматривается сложность автоматной реализации булевых функций и устанав-ливаются точные значения и асимптотические оценки функции Шеннона для замкну-тых классов булевых функций, входящих в решетку Поста.
  Ключевые слова: булева функция, детерминированный конечный автомат, автоматная сложность, замкнутый класс Поста, решетка Поста, функция Шеннона
• Летуновский А.А.. О задаче выразимости автоматов относительно суперпозиции для систем с фиксированной добавкой. Рассматривается задача выразимости конечного группового автомата Медведева M суперпозициями систем вида Ф U R, где Ф состоит из всех булевых функций и "задержки" , R – произвольная конечная система автоматов. Ранее автор показал, что для группового автомата Медведева M, группа которого является разрешимой, существует алгоритм проверки принадлежности M множеству [Ф U R]. В настоящей работе решается аналогичная задача выразимости произвольных групповых автоматов Медведева.
  Ключевые слова: автомат, суперпозиция, булева функция, выразимость
• Мастихина А.А.. Частичное угадывание сверхсобытий, порожденных простыми LL(1)-грамматиками. Автомат угадывает символ входной последовательности, если он выдает этот символ на выходе в предыдущий момент времени. В работе рассмотрен вопрос, можно ли с помощью детерминированного автомата частично предвосхитить некоторое сверхсобытие, то есть угадать некоторую ненулевую долю символов каждого сверхслова из этого сверхсобытия. Получены критерий и алгоритм, позволяющие это установить для сверхсобытий, образованных сверхитерацией языков, порожденных простыми LL(1)-грамматиками.
  Ключевые слова: угадывающие автоматы, автоматы с магазинной памятью, частичное угадывание, сверхсобытия, простые LL(1)-грамматики