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

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

• С.А. Васильев. Искусственный Разум для автономной дискретной системы.
  
  На сегодня нет общепринятого определения понятия "Искусственный интеллект". Возможно, поэтому и отсутствует общее решение задачи его создания. Автор этой статьи попытался "сузить" задачу, а именно рассмотреть аспекты разумного поведения автономной дискретной системы (АДС)
  Ключевые слова: искусственный интеллект, интеллектуальная система
  
  Today there is no universally accepted definition of "Artificial Intelligence". Perhaps that is why there is no general solution to the problem of its creation. The author of this article tried to "narrow" the problem, namely to consider aspects of intelligent behavior of autonomous discrete system (ADS)
  Keywords: artificial intelligence, intelligent system
• А.В. Чечкин, А. Е. Евграфов, В.В. Рожков, М.В. Пирогов. Символьная модель проблемной области сложной системы – основа интеллектуализации такой системы на примере АКПУ.
  
  Успехи современных сложных систем, программно-технических средств (ПТС) и масштабы их распространения общеизвестны. Однако из разных источников постоянно появляется информация, свидетельствующая о многочисленных и разнообразных проблемах используемых сложных систем. Существует ли проблема современных сложных систем, которую можно определить как главную и фундаментальную? Если да, то в чем она заключается?
  Ключевые слова: Интеллектуальтая система, модель
  
  
  Keywords:

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

• В.А. Газарян, Ю.М. Нагорный, Ю.П. Пытьев, А.К. Шаховская. О теоретико-возможностных методах решения задач медицинской диагностики.
  
  Показано, что для решения многих задач медицинской диагностики естественно применение не вероятностной, а возможностной модели анализа и интерпретации данных [1, 2], полученных как с использованием современных медицинских технологий, так и отражающих самочувствие и состояние больного, профессиональный опыт и интуицию врача. Построена возможностная модель симптоматики заболевания, характеризующая нечёткую связь между симптоматийным описанием состояния больного и реальным его состоянием, в которой диагностические критерии определяются группами значений признаков (симптомов), ранжированных по значениям их возможностей при данном заболевании. В возможностной модели диагностики оптимальное решающее правило минимизирует возможность или (и) неизбежность потерь при постановке диагноза.
  Ключевые слова: медицина, диагностика, медицинская диагностика
  
  
  Keywords:
• А.В. Розанов. Моделирование плоского прямолинейного движения в однородной структуре.
  
  В работе рассматривается задача моделирования равномерного прямолинейного движения с отражением от препятствий с помощью однородных структур. Вводится понятие дискретной траектории, устанавливается взаимно однозначное соответствие дискретных и непрерывных траекторий. Строится однородная структура, универсальная для широкого класса препятствий, и показывается, что для остальных препятствий существует бесконечное множество начальных условий движения, не допускающих моделирования.
  Ключевые слова: однородная структура, моделирование, равномерное движение
  
  
  Keywords:
• А.П. Соколов. О нейросетевой реализации алгоритмов управления летательными аппаратами.
  
  Данная работа посвящена разработке метода синтеза нейронной сети, реализующей заданный наперед вычислительный алгоритм. Рассматриваются алгоритмы применямые в системах управления летательными аппаратами. Синтезируемая нейросеть должна быть в некотором смысле эквивалентной исходному алгоритму. Это означает, что поведение нейросети для всей системы управления вцелом не должно отличаться от поведения исходной вычислительной процедуры. Предполагается, что исходный алгоритм (вычислительная процедура) реализован на некотором языке программирования, например C++.
  Ключевые слова: нейросеть, нейронная сеть, летательный аппарат
  
  
  Keywords:
• Е.Е. Титова. Конструирование изображений клеточными автоматами.
  
  В работе рассматривается задача конструирования изображений клеточными автоматами на прямоугольном экране. Показано, что для любого изображения необходимо и достаточно, чтобы клеточный автомат имел 3 состояния. Получены оценки времени конструирования изображений в зависимости от числа состояний клеточного автомата.
  Ключевые слова: клеточный автомат, генератор, универсальный экран, конструирование изображений, оценка времени конструирования изображения
  
  The work deals with the problem of image construction with cellular automata on a rectangular screen. It is shown that for every image is necessary and sufficient that the cellular automaton has three states. Estimates are obtained for time of image construction depending on the number of states of a cellular automaton
  Keywords: cellular automaton, generator, universal screen, image construction, estimation for time of image construction

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

• Д.Н. Бабин, А.Б. Холоденко. Об автоматной аппроксимации естественных языков.
  
  В статье даётся краткий обзор математических моделей естественных языков, в том числе и работ авторов в этом направлении. Во второй части статьи определены автоматные языки, имеющие предельные частотные свойства и сформулирован ряд теорем про них.
  Ключевые слова: конечный автомат, регулярное выражение, n-грамма, биграмма, триграмма
  
  The paper consists of two parts. The first part presents a short review of the mathematical approaches to language models, including some works of the authors. In the second part a class of regular languages with limitary frequency properties is defined and some theorems concerning this class are stated
  Keywords: finite state machine, automaton, regular expression, n-gram, bigram, trigram
• Н.Ю. Волков. Об автоматной модели преследования внутри квадрата.
  
  Изучается процесс преследования коллективом автоматов ("хищников") нескольких независимых друг от друга автоматов ("жертв"). Преследование происходит в квадрате со стороной l. Показано, что для произвольной конечной независимой системы жертв существует конечный коллектив хищников, который при любом натуральном l "ловит" данную систему жертв в квадрате со стороной l при любом начальном расположении в квадрате жертв и стартующих из одной точки хищников. В то же время показано, что для произвольного конечного коллектива хищников существует натуральное число l, такое, что для произольного начального расположения хищников в квадрате со стороной l существует независимая система жертв, таких, что их скорость меньше скорости хищников, и их обзор не больше обзора хищников, и их начальное расположение в квадрате со стороной l, при котором все жертвы "убегают" от хищников.
  Ключевые слова: задача преследования, лабиринт, периодическое поведение, независимая система автоматов, коллектив автоматов.
  
  The process of pursuit of several independent "victim" automata by a collection of "predator" automata is studied. Pursuit is performed in a square with side l. We show that for an arbitrary finite set of independent "victims" there exists a finite collection of "predators" that "catches" all victims in the given set for arbitrary l, arbitrary initial positions of all "victims" and arbitrary starting point of "predators" (all "predators" start from the same position). We also show that for an arbitrary finite collection of "predators" there exists a natural number l such that for an arbitrary initial position of "predators" in a square with side l there exists a set of independent "victims" such that "victim" speed is less that "predator" speed, "victim" view is less than "predator" view, and an initial position of "victims" in the same square such that all victims "escape" from "predators".
  Keywords: pursuit, maze, periodical behavior, independent automata system, collection of automata
• Б.В. Воронин, В.В. Осокин. О сложности расшифровки существенных переменных функции, задающей разбиение булевого куба.
  
  В работе исследуется сложность определения существенных переменных функций из некоторого подкласса класса функций, задающих разбиение булевого куба на подкубы. Показано, что k*₂n запросов достаточно для определения всех существенных переменных любой функции из этого подкласса. Получены асимптотики сложностей определения существенных переменных при малых и больших значениях k: log₂n и n соответственно.
  Ключевые слова: расшифровка, существенная функция, алгебра логики, булев куб
  
  In the current paper we analyze the complexity of learning relevant variables of some subclass of functions splitting Boolean cube into cube faces. We show that k*log₂n membership queries is enough to learn all relevant variables of any function in this class. We obtain asymptotics of relevant variables learning complexity in the cases of small and big values of k: log₂n and n correspondingly
  Keywords: variable learning complexity, Boolean cube splitting, attribute-efficient learning, learning juntas, pseudo-boolean functions, exact learning model
• Ю. Г. Гераськина. Автоматная модель транспортировки вещества по легким в загрязненных средах.
  
  В работе предложена автоматная модель для описания функционирования механизма транспортировки вещества по легким (автоматная модель транспортировки – АМТ). Рассматриваются случаи функционирования АМТ как в загрязнённой стационарной среде, так и в нестационарной. Для каждого случая решены следующие задачи: для соответствующего автомата оценено число состояний в нём и диаметр его диаграммы Мура, описаны стартовые состояния и найдено их число, найдена средняя глубина диаграммы, указан критерий перехода одного состояния в другое и оценено время такого перехода, описаны финальные состояния и оценено их количество.
  Ключевые слова: Автомат, автоматная модель, диаграмма Мура, состояние автомата, транспортировка вещества, легкие, бронхи
  
  In the work an automaton model of mechanism of substance transportation in lungs is offered (the automaton model of transportation is АМТ). Cases of operation of АМТ in contaminated stationary medium, as well as in nonstationary are considered. For each case the following problems are settled: for a corresponding automaton the number of states in it and diameter of his Moore diagramm are estimated, start-up states are described and their number is found, the average depth of a diagramm is found, the criterion of a transition of some state into another is specified and time of such transition is appreciated, final states are described and their number is appreciated.
  Keywords: automaton, automaton model, Moore diagram, state of an automaton, transportation of substance, lungs, bronchi
• Д.Н. Жук. О неразрешимости проблемы полноты для дефинитных автоматов.
  
  В работе рассматриваются системы вида M = F U nu, где F – некоторый класс Поста, а nu – конечная система дефинитных автоматов. Выделены некоторые классы Поста, для которых проблемы полноты и A-полноты для систем вида F U nu алгоритмически неразрешимы.
  Ключевые слова: конечный автомат, дефинитный автомат, проблема полноты, разрешимость, неразрешимость
  
  In this paper we consider the sets F U nu of definite automata, where F is a fixed closed class of Boolean functions and nu is a finite set of definite automata. Some closed classes of Boolean functions such that the completeness and A-completeness problem for these sets of definite automata is unsolvable were found.
  Keywords: definite automata, completeness problem, unsolvability
• Д.В. Зайцев. О сложности вложения матриц.
  
  В работе изучается сложность универсальных матриц, которые позволяют получать матрицы заданного класса в качестве подматриц. Под сложностью понимаем размер универсальной матрицы. Подобные объекты рассматривались в работах, посвященных последовательностям и торам де Брёйна
  Ключевые слова: матрица, вложение матриц, сложность
  
  In this paper we study the complexity of universal matrices, which provide the matrix of a given class as submatrices. The complexity refers to the size of the universal matrix. Such objects are considered in dealing with de Bruijn sequences and tori.
  Keywords: matrix, matrix embedding, complexity
• В.Ю. Лёвин, В.А. Носов. Анализ повышения криптографической сложности систем при переходе на эллиптические кривые.
  
  Хорошо известно, что основную криптографическую сложность при взломе классических криптосистем над конечными полями дает сложность решения задачи дискретного логарифмирования. В случае классических криптосистем на основе эллиптических кривых такую сложность дает решение соответствующей задачи дискретного логарифмирования на эллиптической кривой. Стоить отметить, что большинство криптосистем позволяют перейти на эллиптические кривые. При этом происходит серьезное увеличение криптографической сложности. В данной работе проведен анализ изменения сложности при переходе на эллиптические кривые. В ходе анализа установлено, что возрастание сложности при подобном переходе не приводит к увеличению размеров ключей, а наблюдается эффект уменьшения их длин при сохранении общей криптосложности системы. В работе приведено теоретическое обоснование этого факта, построены зависимости длин ключей.
  Ключевые слова: эллиптическая кривая, криптографическая система
  
  
  Keywords:
• И.В. Лялин. Решение автоматных уравнений с одной неизвестной.
  
  Пусть имеется автоматная схема S, полученная из автоматов с помощью операций суперпозиции и обратной связи. Пусть в S один автомат x разрешается заменять на любой подходящий по входам и выходам автомат x' так, чтобы полученная схема S' реализовывала автомат, эквивалентный наперед заданному автомату h. В статье приводится алгоритм, устанавливающий возможность такой замены, а также описывается множество всех подходящих x'. Данная работа является обобщением на случай схем с обратными связями.
  Ключевые слова: автоматное уравнение, конечный автомат, суперпозиция
  
  Let S be a digital circuit, which is consisted from finite-state machines. Let a finite-state machine x be possible to be changed to other finite-state machine x' with the same input and output alphabets. Does there exist such x' that after substitution x -> x', S will be equivalent to the finite-state machine h? The article describes the algorithm for solving this problema and describes the set of all appropriate x', depends on S and h.
  Keywords: finite-state machine, FSM, digital circuit, FSM equation
• С.В. Моисеев. О реализации автоматов нейронными сетями.
  
  В работе исследуются функциональные возможности нейронных сетей. Изучается проблема реализуемости автомата нейронной сетью, моделируемости автомата при разрешённой перекодировке входных и выходных символов и проблема существования моделирующей кодировки. В каждом случае выявлены критериальные условия.
  Ключевые слова: нейронная сеть, нейросеть, автомат, конечный автомат
  
  We consider discrete time neural networks as finite automata. Unlike the classical Kleene theorem, we demonstrate that it is not every finite automaton that can be represented by a neural network (without a time delay). We provide different criteria to test whether an automaton can be represented by a neural network (with or without time delay). We also provide a criterion to test if one can change the encoding of the input and output alphabets of an automaton in order that the automaton become representable by a neural network.
  Keywords: finite automata, discrete time neural networks
• В.А. Носов, А. Е. Панкратьев. О функциональном задании латинских квадратов.
  
  В работе исследуются функциональные способы задания латинских квадратов над множествами n-мерных булевых векторов, n-мерных векторов над произвольным простым конечным полем и произвольной конечной абелевой группой. Также приводится конструкция, задающая классы негрупповых латинских квадратов.
  Ключевые слова: латинский квадрат
  
  This paper studies functional methods for specification of Latin squares over the sets of n-dimensional Boolean vectors, n-dimensional vectors over an arbitrary finite prime field and over an arbitrary finite Abelian group. In conclusion, a method for constructing classes of non-group Latin squares is presented.
  Keywords: Latin square, Boolean vector, Abelian group
• А.П. Пивоваров. Поиск представителя в задаче о метрической близости.
  
  Работа посвящена описанию алгоритма поиска представителя в задаче о метрической близости. Для поиска представителя в задаче о метрической близости разработан алгоритм, объем памяти которого линеен по числу записей в библиотеке, время поиска в среднем константа, а в худшем случае порядка log k.
  Ключевые слова: метрика, метрическая близость
  
  This paper offers an algorithm to search representative record in two-dimensional metrical closeness problem. This algorithm requires O(k) memory, where k is the number of records in the library. Time-complexity of this algorithm is constant in average and O(log k) in the worst case.
  Keywords: metric, metrical closeness, но я бы добавил еще representative search
• Е.А. Поцелуевкая. Полиномиальные случаи решения задачи об F-выполнимости булевых формул..
  
  В данной статье приводится алгоритм решения задачи об F-выполнимости булевых формул, зависящих не более чем от трех переменных. Алгоритм относится к классу DPLL-алгоритмов и основан на переборе определенного подмножества S переменных x_i и решении для каждого фиксированного набора значений переменных из S полиномиальной подзадачи о 2-выполнимости. В статье также указаны условия, при которых сложность алгоритма является полиномиальной величиной.
  Ключевые слова: выполнимость, булева формула, F-выполнимость, алгоритм, минимальное множество
  
  In this article an algorithm for S-satisfiability problem decision for boolean functions depending at most on three variables is described. The algorithm belongs to the class of DPLL-algorithms and is based on exhaustive search of certain subset S of variables x_i and on solution of polynomial 2-SAT subproblem for any fixed set of variables values. In the article the conditions when the complexity of the algorithm is a polynomial value are also shown.
  Keywords: satisfiability, S-satisgiability, algorithm, minimal set
• А.П. Соколов. О конструктивной характеризации пороговых функций.
  
  В работе рассматриваются вопросы строения и сложности к классе пороговых функций алгебры логики. Вводится определение сигнатуры пороговой функции. Доказано, что если пороговая фукнция существенно зависит от всех своих переменных, то ее сигнатура определяется однозначным образом. Доказана теорема, характеризующая разбиение множества пороговых функций по классам сигнатур. Отмечается особая важность класса монотонных пороговых функций. Исследуется сложность преобразования одной пороговой функции, заданной некоторой целочисленной линейной формой, в другую. Показано, что в худшем случае данная задача имеет экспоненциальную сложность. Рассматривается строение множеств линейных форм, задающих одну пороговую функцию. Доказана теорема о бесконечной порожденности данных множеств относительно операции сложения линейных форм.
  Ключевые слова: пороговые функции, сложность обучения нейросетей
  
  Structure of the set of threshold functions and complexity problems are considered in the paper. The notion of a signature of threshold function is defined. It's shown that if threshold function essentially depends on all of its variables then signature of this function is unique. Set of threshold functions is partitioned onto classes with equal signatures. Theorem characterizing this partition is proved. Importance of the class of monotone threshold functions is emphasized. Complexity of transferring one threshold function specified by the linear form into another is examined. It's shown that in the worst case this transferring would take exponential time. Structure of the set of linear forms specifying the same threshold function is also examined. It's proved that for any threshold function this set of linear forms has unique basis in terms of the operation of addition of the linear forms. It's also shown that this basis is countable.
  Keywords: threshold functions, learning complexity of neural networks