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

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

• С.А. Васильев. Искусственный Разум для автономной дискретной системы. На сегодня нет общепринятого определения понятия "Искусственный интеллект". Возможно, поэтому и отсутствует общее решение задачи его создания. Автор этой статьи попытался "сузить" задачу, а именно рассмотреть аспекты разумного поведения автономной дискретной системы (АДС)
  Ключевые слова: искусственный интеллект, интеллектуальная система
• А.В. Чечкин, А. Е. Евграфов, В.В. Рожков, М.В. Пирогов. Символьная модель проблемной области сложной системы – основа интеллектуализации такой системы на примере АКПУ. Успехи современных сложных систем, программно-технических средств (ПТС) и масштабы их распространения общеизвестны. Однако из разных источников постоянно появляется информация, свидетельствующая о многочисленных и разнообразных проблемах используемых сложных систем. Существует ли проблема современных сложных систем, которую можно определить как главную и фундаментальную? Если да, то в чем она заключается?
  Ключевые слова: Интеллектуальтая система, модель

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

• В.А. Газарян, Ю.М. Нагорный, Ю.П. Пытьев, А.К. Шаховская. О теоретико-возможностных методах решения задач медицинской диагностики. Показано, что для решения многих задач медицинской диагностики естественно применение не вероятностной, а возможностной модели анализа и интерпретации данных [1, 2], полученных как с использованием современных медицинских технологий, так и отражающих самочувствие и состояние больного, профессиональный опыт и интуицию врача. Построена возможностная модель симптоматики заболевания, характеризующая нечёткую связь между симптоматийным описанием состояния больного и реальным его состоянием, в которой диагностические критерии определяются группами значений признаков (симптомов), ранжированных по значениям их возможностей при данном заболевании. В возможностной модели диагностики оптимальное решающее правило минимизирует возможность или (и) неизбежность потерь при постановке диагноза.
  Ключевые слова: медицина, диагностика, медицинская диагностика
• А.В. Розанов. Моделирование плоского прямолинейного движения в однородной структуре. В работе рассматривается задача моделирования равномерного прямолинейного движения с отражением от препятствий с помощью однородных структур. Вводится понятие дискретной траектории, устанавливается взаимно однозначное соответствие дискретных и непрерывных траекторий. Строится однородная структура, универсальная для широкого класса препятствий, и показывается, что для остальных препятствий существует бесконечное множество начальных условий движения, не допускающих моделирования.
  Ключевые слова: однородная структура, моделирование, равномерное движение
• А.П. Соколов. О нейросетевой реализации алгоритмов управления летательными аппаратами. Данная работа посвящена разработке метода синтеза нейронной сети, реализующей заданный наперед вычислительный алгоритм. Рассматриваются алгоритмы применямые в системах управления летательными аппаратами. Синтезируемая нейросеть должна быть в некотором смысле эквивалентной исходному алгоритму. Это означает, что поведение нейросети для всей системы управления вцелом не должно отличаться от поведения исходной вычислительной процедуры. Предполагается, что исходный алгоритм (вычислительная процедура) реализован на некотором языке программирования, например C++.
  Ключевые слова: нейросеть, нейронная сеть, летательный аппарат
• Е.Е. Титова. Конструирование изображений клеточными автоматами. В работе рассматривается задача конструирования изображений клеточными автоматами на прямоугольном экране. Показано, что для любого изображения необходимо и достаточно, чтобы клеточный автомат имел 3 состояния. Получены оценки времени конструирования изображений в зависимости от числа состояний клеточного автомата.
  Ключевые слова: клеточный автомат, генератор, универсальный экран, конструирование изображений, оценка времени конструирования изображения

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

• Д.Н. Бабин, А.Б. Холоденко. Об автоматной аппроксимации естественных языков. В статье даётся краткий обзор математических моделей естественных языков, в том числе и работ авторов в этом направлении. Во второй части статьи определены автоматные языки, имеющие предельные частотные свойства и сформулирован ряд теорем про них.
  Ключевые слова: конечный автомат, регулярное выражение, n-грамма, биграмма, триграмма
• Н.Ю. Волков. Об автоматной модели преследования внутри квадрата. Изучается процесс преследования коллективом автоматов ("хищников") нескольких независимых друг от друга автоматов ("жертв"). Преследование происходит в квадрате со стороной l. Показано, что для произвольной конечной независимой системы жертв существует конечный коллектив хищников, который при любом натуральном l "ловит" данную систему жертв в квадрате со стороной l при любом начальном расположении в квадрате жертв и стартующих из одной точки хищников. В то же время показано, что для произвольного конечного коллектива хищников существует натуральное число l, такое, что для произольного начального расположения хищников в квадрате со стороной l существует независимая система жертв, таких, что их скорость меньше скорости хищников, и их обзор не больше обзора хищников, и их начальное расположение в квадрате со стороной l, при котором все жертвы "убегают" от хищников.
  Ключевые слова: задача преследования, лабиринт, периодическое поведение, независимая система автоматов, коллектив автоматов.
• Б.В. Воронин, В.В. Осокин. О сложности расшифровки существенных переменных функции, задающей разбиение булевого куба. В работе исследуется сложность определения существенных переменных функций из некоторого подкласса класса функций, задающих разбиение булевого куба на подкубы. Показано, что k*₂n запросов достаточно для определения всех существенных переменных любой функции из этого подкласса. Получены асимптотики сложностей определения существенных переменных при малых и больших значениях k: log₂n и n соответственно.
  Ключевые слова: расшифровка, существенная функция, алгебра логики, булев куб
• Ю. Г. Гераськина. Автоматная модель транспортировки вещества по легким в загрязненных средах. В работе предложена автоматная модель для описания функционирования механизма транспортировки вещества по легким (автоматная модель транспортировки – АМТ). Рассматриваются случаи функционирования АМТ как в загрязнённой стационарной среде, так и в нестационарной. Для каждого случая решены следующие задачи: для соответствующего автомата оценено число состояний в нём и диаметр его диаграммы Мура, описаны стартовые состояния и найдено их число, найдена средняя глубина диаграммы, указан критерий перехода одного состояния в другое и оценено время такого перехода, описаны финальные состояния и оценено их количество.
  Ключевые слова: Автомат, автоматная модель, диаграмма Мура, состояние автомата, транспортировка вещества, легкие, бронхи
• Д.Н. Жук. О неразрешимости проблемы полноты для дефинитных автоматов. В работе рассматриваются системы вида M = F U nu, где F – некоторый класс Поста, а nu – конечная система дефинитных автоматов. Выделены некоторые классы Поста, для которых проблемы полноты и A-полноты для систем вида F U nu алгоритмически неразрешимы.
  Ключевые слова: конечный автомат, дефинитный автомат, проблема полноты, разрешимость, неразрешимость
• Д.В. Зайцев. О сложности вложения матриц. В работе изучается сложность универсальных матриц, которые позволяют получать матрицы заданного класса в качестве подматриц. Под сложностью понимаем размер универсальной матрицы. Подобные объекты рассматривались в работах, посвященных последовательностям и торам де Брёйна
  Ключевые слова: матрица, вложение матриц, сложность
• В.Ю. Лёвин, В.А. Носов. Анализ повышения криптографической сложности систем при переходе на эллиптические кривые. Хорошо известно, что основную криптографическую сложность при взломе классических криптосистем над конечными полями дает сложность решения задачи дискретного логарифмирования. В случае классических криптосистем на основе эллиптических кривых такую сложность дает решение соответствующей задачи дискретного логарифмирования на эллиптической кривой. Стоить отметить, что большинство криптосистем позволяют перейти на эллиптические кривые. При этом происходит серьезное увеличение криптографической сложности. В данной работе проведен анализ изменения сложности при переходе на эллиптические кривые. В ходе анализа установлено, что возрастание сложности при подобном переходе не приводит к увеличению размеров ключей, а наблюдается эффект уменьшения их длин при сохранении общей криптосложности системы. В работе приведено теоретическое обоснование этого факта, построены зависимости длин ключей.
  Ключевые слова: эллиптическая кривая, криптографическая система
• И.В. Лялин. Решение автоматных уравнений с одной неизвестной. Пусть имеется автоматная схема S, полученная из автоматов с помощью операций суперпозиции и обратной связи. Пусть в S один автомат x разрешается заменять на любой подходящий по входам и выходам автомат x' так, чтобы полученная схема S' реализовывала автомат, эквивалентный наперед заданному автомату h. В статье приводится алгоритм, устанавливающий возможность такой замены, а также описывается множество всех подходящих x'. Данная работа является обобщением на случай схем с обратными связями.
  Ключевые слова: автоматное уравнение, конечный автомат, суперпозиция
• С.В. Моисеев. О реализации автоматов нейронными сетями. В работе исследуются функциональные возможности нейронных сетей. Изучается проблема реализуемости автомата нейронной сетью, моделируемости автомата при разрешённой перекодировке входных и выходных символов и проблема существования моделирующей кодировки. В каждом случае выявлены критериальные условия.
  Ключевые слова: нейронная сеть, нейросеть, автомат, конечный автомат
• В.А. Носов, А. Е. Панкратьев. О функциональном задании латинских квадратов. В работе исследуются функциональные способы задания латинских квадратов над множествами n-мерных булевых векторов, n-мерных векторов над произвольным простым конечным полем и произвольной конечной абелевой группой. Также приводится конструкция, задающая классы негрупповых латинских квадратов.
  Ключевые слова: латинский квадрат
• А.П. Пивоваров. Поиск представителя в задаче о метрической близости. Работа посвящена описанию алгоритма поиска представителя в задаче о метрической близости. Для поиска представителя в задаче о метрической близости разработан алгоритм, объем памяти которого линеен по числу записей в библиотеке, время поиска в среднем константа, а в худшем случае порядка log k.
  Ключевые слова: метрика, метрическая близость
• Е.А. Поцелуевкая. Полиномиальные случаи решения задачи об F-выполнимости булевых формул.. В данной статье приводится алгоритм решения задачи об F-выполнимости булевых формул, зависящих не более чем от трех переменных. Алгоритм относится к классу DPLL-алгоритмов и основан на переборе определенного подмножества S переменных x_i и решении для каждого фиксированного набора значений переменных из S полиномиальной подзадачи о 2-выполнимости. В статье также указаны условия, при которых сложность алгоритма является полиномиальной величиной.
  Ключевые слова: выполнимость, булева формула, F-выполнимость, алгоритм, минимальное множество
• А.П. Соколов. О конструктивной характеризации пороговых функций. В работе рассматриваются вопросы строения и сложности к классе пороговых функций алгебры логики. Вводится определение сигнатуры пороговой функции. Доказано, что если пороговая фукнция существенно зависит от всех своих переменных, то ее сигнатура определяется однозначным образом. Доказана теорема, характеризующая разбиение множества пороговых функций по классам сигнатур. Отмечается особая важность класса монотонных пороговых функций. Исследуется сложность преобразования одной пороговой функции, заданной некоторой целочисленной линейной формой, в другую. Показано, что в худшем случае данная задача имеет экспоненциальную сложность. Рассматривается строение множеств линейных форм, задающих одну пороговую функцию. Доказана теорема о бесконечной порожденности данных множеств относительно операции сложения линейных форм.
  Ключевые слова: пороговые функции, сложность обучения нейросетей