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

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

• К.Э. Плохотников. Математическое моделирование и вычислительный эксперимент: методология и практика.
  
  В статье приводится новый взгляд на методологию (математического) моделирования и вычислительного эксперимента. Предложено формальное определение метода (математического) моделирования, приводятся некоторые неформальные аспекты данной методологии. Наибольшее внимание сосредоточено на обсуждении феноменов многомоделия в одной и той же познавательной ситуации, а также интерактивный характер взаимодействия в связке “модели данной предметной области — субъект-модельер”. Приводится набор оригинальных примеров, иллюстрирующих использование данного взгляда на методологию.
  Ключевые слова: математическое моделирование, эксперимент, модель предметной области
  
  A new approach to the methodology of (mathematical) models and computational experiments is presented. We propose a formal description of the method of (mathematical) modeling and list a number of informal aspects of this methodology. The main attention is focused on the phenomenon of the existence of multiple models of the same cognitive situation, and on interactions between the subject and the object of the model. A number of examples illustrating our methodology is analyzed.
  Keywords: mathematical models, experiments, model subject

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

• Д.В. Алексеев. Кодирование изображений, инвариантное относительно проективных преобразований.
  
  В работе представлен метод кодирования плоских изображений, инвариантный относительно проективных преобразований расширенной плоскости. Показано, что при некоторых дополнительных условиях равенство кодов равносильно проективной эквивалентности изображений.
  Ключевые слова: проективное преобразование, кодирование изображений
  
  A method of image encoding invariant with respect to projective transformations is presented. It is shown that under some additional requirements code equivalence is equivalent to projective equivalence of images.
  Keywords: projective transformation, image encoding
• Д.Н. Жук. Континуальность множества предполных классов в классе дефинитных автоматов.
  
  В данной работе показано, что в классе дефинитных автоматов мощность множества всех предполных классов равна континууму.
  Ключевые слова: автомат, дефинитный автомат, предполный класс
  
  Definite automata are all finite automata that can be obtained from boolean functions and delay unit using operations of superposition. In this paper cardinality of the set of all precomplete classes for definite automata is proved to be continuum.
  Keywords: definite automata, continuum, precomplete class, cardinality
• С.Д. Махортов. Основанный на решетках подход к исследованию и оптимизации множества правил условной системы переписывания термов.
  
  В работе рассматривается подход к исследованию и оптимизации множества правил условной системы переписывания термов, основанный на решетках.
  Ключевые слова: предикат, терм
  
  The article is devoted to an approach studying and optimization of sets of rules for conditional term rewriting systems. The approach is based on lattices.
  Keywords: predicate, term
• И.Н. Молодцов. Математическое моделирование упругопластических процессов с траекториями средней кривизны.
  
  Построены и изучены определяющие четырехчленные уравнения дифференциального типа, связывающие напряжения и деформации в процессах сложного нагружения пластически деформируемого материала. Предложен вариант идентификации определяющих функционалов, произведено сравнение с теорией средних кривизн.
  Ключевые слова: математическое моделирование, дифференциальные уравнения
  
  We obtained and studied four-term differential equations for tension and deformation in plastically deformed materials under complex loading. We also proposed a variant of the determining functions identification and compared it with the mean curvature theory.
  Keywords: mathematical modelling, differential equations
• Т.А. Ракчеева. Квазилемнискаты в задаче приближения формы кривых.
  
  Предложен и разработан метод фокусной аппроксимации гладких замкнутых кривых. Базисом фокусного метода является семейство многофокусных лемнискат, параметрами которых являются конечное число фокусов внутри кривой и радиус. Анализ более общего класса квазилемнискат выделяет семейство лемнискат как удовлетворяющее наиболее общим требованиям к функции расстояния и описанию геометрических форм и их инвариантов.
  Ключевые слова: кривые, фокусы, лемниската, эллипс, форма, преобразования, инвариант, базис, метрика, аппроксимация, степени свободы, генерация форм, интерактивное управление.
  
  We proposed and developed a method of focal approximation of smooth closed curves. The method is based on the family of multifocal lemniscates parametrized by a radius and a finite set of focuses inside the curve. An analysis of a more general family of quasi-lemniscates singles out the family of lemniscates as fulfilling more general requirements to the distance function and the description of geometrical forms and their invariants.
  Keywords: curves, focuses, lemniscate, ellipse, form, transformations, invariant, basis, metrics, approximation, degree of freedom, form generation, interactive control
• Е.А. Снегова. Случай задачи об опасной близости, сводящийся к одномерному интервальному поиску.
  
  В работе рассматривается частный случай задачи об опасной близости. Доказано сведение этого случая к задаче одномерного интервального поиска.
  Ключевые слова: интервальный поиск, одномерный интервальный поиск
  
  This paper deals with a special case of dangerous nearness task. The reduction of this case to the one-dimensional interval search task is proved
  Keywords: interval search, one-dimensional interval search
• А.П. Соколов. Асимптотика логарифма сложности перестройки нейронов.
  
  В качестве средства задания пороговых функций в работе рассматриваются линейные формы вида x₁w₁ + ... + x_nw_n – s с целочисленными коэффициентами и свободным членом. Исследуется сложность преобразования одной пороговой функции, заданной линейной формой, к другой, путем пошагового изменения коэффициентов линейной формы. В качестве меры сложности данного процесса принимается изменение коэффициента или свободного члена линейной формы на единицу. Данный процесс может интерпретироваться как процесс обучения нейрона с пороговой функцией активации. Для характеризации сложности обучения в худшем случае вводится шенноновская функция r(n). Она говорит о том, сколько минимально достаточно выполнить единичных модификаций исходной линейной формы от n переменных для задания желаемой пороговой функции. Найдена асимптотика логарифма r(n).
  Ключевые слова: пороговые функции, сложность обучения нейронов, нейрон, нейросеть
  
  Threshold functions defined by linear forms x₁w₁ + ... + x_nw_n – s with integer coefficients are examined. Complexity of transferring one threshold function specified by the linear form into another is examined. Changing of a weight coefficient of threshold by one is a measure of complexity of learning. This process models learning of neuron with threshold activation functions. The asymptotics of a logarithm of a learning time is found when number of variables n grows to infinity.
  Keywords: threshold functions, learning complexity of neurons
• Б. Стаматович. Автоматное распознавание трехсвязных лабиринтов с конечным циклическим диаметром.
  
  Распознавание образов – актуальная тема в компьютерных науках. Распознавание букв является одним из ее частных случаев. Идея использования шахматных лабиринтов применима к растровому преставлению изображений. Определен класс лабиринтов C₈, который в геометрическом смысле представляет цифру восемь. В работе [1] показано, что не существует распознающего автомата для этого класса лабиринтов. В работе [2] показано, что существует распознающий коллектив автоматов типа (1,1) для класса лабиринтов C₈. Здесь поставлена задача для подкласса лабиринтов C₈^d с конечным диаметром дыры, и она положительно решена.
  Ключевые слова: лабиринт, трехсвязный лабиринт, автомат, конечный автомат, автоматное распознавание
  
  Pattern recognition is a popular area in computer science. Character recognition is the special case of pattern recognition. The idea of using chess labyrinthes is applicable to the raster images representation. The class of labyrinthes C8 is defined, which represents the digit '8' (in geometric sence). It is proved in the paper [1] that a recognizing automaton for this labyrinth class doesn't exist. It is shown in the paper [2] that a recognizing collective of automata of the type (1,1) for the labyrinth class C8 exists. Here the task for the labyrinth subclass C8d with a finite hole diamater is solved
  Keywords: labyrinth, triply connected labyrinth, automaton, finite automaton, automate recognition
• Д. Цымжитов. Об одном алгоритме ML-декодирования для низкоплотностных кодов.
  
  В работе представлен алгоритм мягкого декодирования для низкоплотностных двоичных кодов с графом Таннера без циклов. Показано, что этот алгоритм находит оптимальное решение задачи декодирования по максимальному правдоподобию и имеет асимптотическую сложность O(n), где n – длина кодового слова.
  Ключевые слова: код, низкоплотностный код, декодирование, двоичный код
  
  In the article a soft decoding algorithm for low density binary codes with Tanner graphs without cycles is proposed. It is shown that this algorithm provides an optimal solution of decoding problem using maximum likelihood and has asymptotic complexity of O(n) where n is codeword length
  Keywords: code, low density code, decoding, binary code

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

• Г.В. Боков. Проблема полноты в исчислении высказываний.
  
  В работе проблема полноты систем аксиом в исчислении высказываний рассматривается с позиции оператора замыкания, порожденного правилами вывода. Описываются некоторые свойства данного оператора, а также свойства замкнутых и предполных классов, задаваемых этим оператором. Доказывается алгоритмическая неразрешимость проблемы полноты конечных систем аксиом в исчислении высказываний.
  Ключевые слова: полнота, высказывание, исчисление высказываний, аксиома, правило вывода
  
  In this work the problem of axiomatic system completeness is regarded from the point of closure operator generated by the given inference rules. Some properties of the above-mentioned operator are described as well as some properties of closed and precompleted classes set by this operator. Algorithmically unsolvability of completeness problem for finite axiomatic system in propositional calculus is proved.
  Keywords: completeness, proposition, propositional calculus, axiom, inference rule
• Н.Ю. Волков. О возможности поимки жертв в квадранте.
  
  Изучается процесс преследования коллективом автоматов ("хищников") нескольких независимых друг от друга автоматов ("жертв"). Преследование происходит в лабиринте, представляющем собой квадрант. Показано, что существует конечный коллектив хищников, который "ловит" любую конечную независимую систему жертв с фиксированными скоростями и обзорами при любом начальном расположении жертв и стартующих из одной точки хищников.
  Ключевые слова: хищник, жертва, лабиринт, автомат, коллектив автоматов, конечный автомат, квадрант
  
  The process of pursuit of several independent "victim" automata by a collection of "predator" automata is studied. Pursuit is performed in a quadrant maze. We show that there exists a finite collection of "predators" that "catches" an arbitrary finite independent set of "victims" with fixed speed and view, for arbitrary starting points of "victims" and arbitrary starting point of "predators" (all predators start from the same position).
  Keywords: pursuit, maze, collection of automata, simulation, universal Turing machine, automata calculations
• Ю.И. Вторушин. О поиске вывода в системе натуральной дедукции логики предикатов.
  
  В статье описывается метод автоматического доказательства теорем, который используется в системах автоматизации дедукции Class и Int. Публикуемый алгоритм находит выводы в рамках многосортной системы натуральной дедукции, которая адэкватно моделирует реальные человеческие рассуждения. Алгоритм полон для минимальной, интуиционистской и классической систем натуральной дедукции логики предикатов.
  Ключевые слова: предикат, логика предикатов, дедукция, натуральная дедукция
  
  In the article the method of the automatic proof of theorems, which is used in systems of deduction automation named Class and Int, is described. The published algorithm finds derivations within the framework of multisortable system of natural deduction which sufficiently models real human reasoning. The algorithm is full for minimal, intuitionistic and classical systems of natural deduction of predicate logic.
  Keywords: predicate, predicate logic, deduction, natural deduction
• А.В. Галатенко, В.В. Галатенко. О расстоянии Хэмминга между почти всеми функциями алгебры логики.
  
  В работе оценивается расстояние Хэмминга между почти всеми функциями алгебры логики
  Ключевые слова: расстояние Хэмминга, алгебра логики, булева функция
  
  A precise estimation of Hamming distance between almost all Boolean functions is presented
  Keywords: Hamming distance, Boolean function
• Ю.Г. Гераськина. О переводимости состояний автоматной модели легких в чистой среде.
  
  В работе предлагается автоматная модель процесса транспортировки вещества в легочных структурах в чистой среде. Рассматривается процесс самоочищения легких от привнесенных веществ из среды, а также от веществ, образующихся в легких в процессе их жизнедеятельности. Для предложенной автоматной модели решаются следующие задачи – нахождение средней глубины диаграммы Мура, нахождение критерия перехода одного состояния в другое и оценки времени такого перехода.
  Ключевые слова: автомат, диаграмма Мура, легочные структуры, процесс транспортировки вещества, переводимость состояний автомата, бронхи
  
  In the work an automaton model of the process of substance transportation in lung structures in clean environment is offered. The process of lungs clearance during their vital activity is considered. For a proposed automaton model the following problems are being decided – determination of medium depth of a Moore diagram, determination of the criterion of a transition of some state into another state and evaluation of time of such a transition.
  Keywords: automaton, Moore diagram, lung structures, process of substance transportation, transition of automation states, bronchi
• Д.Н. Жук. Разрешимые случаи задачи об A-полноте для дефинитных автоматов.
  
  В работе рассматриваются системы вида M = F U nu, где F – некоторый класс Поста, а nu – конечная система дефинитных автоматов. Выделены некоторые классы Поста, для которых проблема A-полноты для систем вида F U nu алгоритмически разрешима.
  Ключевые слова: полнота, A-полнота, разрешимость, алгоритмическая разрешимость, класс Поста, решетка Поста, автомат, дефинитный автомат
  
  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 A-completeness problem for these sets of definite automata is solvable were found.
  Keywords: definite automata, completeness problem, solvability
• М.А. Кибкало. О сложности представления коллекции языков в конечных автоматах.
  
  Определение сложности представления языков – одна из традиционных задач теории автоматов. В статье рассматривается случай совместной представимости семейства языков в одном автомате. Существуют различные определения сложности регулярного языка основанные на характеристиках самого языка или представляющего его автомата. В данной работе под сложностью языка (семейства непересекающихся конечных языков) понимается число состояний в представляющем его (их) приведенном автомате. В работе решена задача о нахождении точного значения максимальной сложности семейства конечных языков в зависимости от максимальной длины слова в нем.
  Ключевые слова: автомат, конечный автомат, приведенный автомат, язык
  
  The problem of language complexity is one of traditional tasks of the finite automata theory. In this paper, we consider automata accepting collections of finite languages. There are different definitions of finite language complexity based on features of the language and the accepting automaton. We understand complexity of a finite language (a collection of finite languages) as the number of states in the reduced finite automaton accepting this language (collection). We found exact values of maximal complexity depending on the maximal word length in the language (collection)
  Keywords: maximal complexity, automaton, automata, finite automata, reduced automata, boolean language, boolean function, Shannon function
• Н.С. Кучеренко. О промежуточных функциях роста сложности поиска для случайных баз данных.
  
  В работе рассматриваются функции роста сложности оптимальных алгоритмов решения задачи поиска идентичных объектов в среднем по классу задач. Ранее автором были изучены случаи, когда функция роста является ограниченной функцией или имеет порядок логарифма от мощности базы данных. В данной статье описано семейство S возможных асимптотик и семейство S^* возможных порядков функций роста, которые являются неограниченно возрастающими, но по порядку меньшими, чем логарифм от мощности базы данных.
  Ключевые слова: поиск, сложность, база данных, алгоритм поиска
  
  In the work complexity of optimum algorithms for key search on the average on a classes of problems are considered. Growth functions of such complexity are studied. Earlier the author investigated cases when growth function was limited function or has the order of logarithm from database capacity. In given article the author investigated growth functions which are nonbounded functions, but under the order smaller, than the logarithm from database capacity. Family S of possible asymptotics and family S* of possible orders of such growth functions are described.
  Keywords: search, complexity, database, search algorithm
• А.А. Летуновский. О выразимости константных автоматов суперпозициями.
  
  Показано, что для конечных систем автоматных функций, содержащих все истинностные функции и задержку, существует алгоритм выразимости константных автоматных функций. Множество выразимых константных автоматных функций явно описывается по первоначально заданной конечной системе автоматов. Также показано существование алгоритма выразимости автономных автоматов.
  Ключевые слова: автомат, конечный автомат, константный автомат, суперпозиция, автоматная функция, выразимость, алгоритмическая разрешимость
  
  The expressibility problem for finite automaton by system Ф U nu is considered. Ф consists of all k-valued functions and "delay" function. nu is a finite automata system. Previously author has shown the existence of algorithm for checking expressibility of automaton A by {Ф U nu}, where A is automaton with unconditional transitions. Author solve the problem of expressibility of automaton A by {Ф U nu}, where A is automaton with soluble group.
  Keywords: expressibility, finite automaton, delay function, constant automaton, algorithm existence, soluble group
• И.В. Лялин. Решение автоматных уравнений с двумя неизвестными.
  
  Пусть имеется автоматная схема S, полученная из автоматов с помощью операции суперпозиции. Пусть в S несколько автоматов x₁, x₂, ..., x_n разрешается заменять на любые подходящие по входам и выходам автоматы x₁', x₂', ..., x_n'. Рассматривается следующая задача: существует ли такая замена, чтобы полученная схема S' реализовывала автомат, эквивалентный наперед заданному автомату h. В статье доказывается алгоритмическая неразрешимость этой задачи, если n >= 2.
  Ключевые слова: автомат, конечный автомат, автоматное уравнение
  
  Let S is a digital circuit, which is consisted from finite-state machines. Let some finite-state machines x₁, ..., x_N are possible to be changed to other finite-state machines x'₁, ..., x'_N with the same input and output alphabets. Are there exist such x'₁, ..., x'_N that after substitution x₁, ..., x_N -> x'₁, ..., x'_N, S will be equivalent to the finite-state machine h? The article proves that there are no algorithm for solving this problema if N >= 2.
  Keywords: finite-state machine, FSM, digital circuit, FSM equation, algorithmically unsolvable problem
• М.В. Носов. Комбинаторная формула числа пороговых функций.
  
  В работе представлен вывод комбинаторной формулы, задающей число пороговых функций. При выводе формулы использованы многочлены Лагранжа. Используется верхняя оценка на длину ребра куба, целочисленные точки которого задают все пороговые функции.
  Ключевые слова: пороговые функции, многочлен Лагранжа
  
  In this paper a conclusion of the combinatory formula setting number of threshold functions is presented. To derive the formula a conclusion Lagrange polynomial is used. The top estimation for length of an edge of the cube which integer points set all threshold functions is used
  Keywords: threshold functions, Lagrange polynomial
• В.В. Осокин. О параллельной расшифровке разбиений булевого куба.
  
  В работе рассматривается класс Ф^k,n дискретных функций, определенных на булевом кубе {0,1}ⁿ и существенно зависящих от не более чем k <= n переменных. Каждая функция f из Ф^k,n задает разбиение куба {0,1}ⁿ на непересекающиеся грани и сопоставляет уникальное число каждой грани результирующего разбиения. Мы доказываем нижнюю оценку сложности расшифровки функций из Ф^k,n и предлагаем алгоритм расшифровки функций из Фⁿ = Ф^n,n, оптимальный в том смысле, что число запросов на значение функции, требуемое алгоритму для расшифровки произвольной функции из Ф^k,n, по порядку совпадает с нижней оценкой. Построенный алгоритм может быть эффективно распараллелен и при максимальном распараллеливании его сложность по порядку равна k.
  Ключевые слова: булев куб, расшифровка булева куба, дискретная функция
  
  In the current paper we consider class Ф^k,n of discrete functions defined over Boolean cube {0,1}ⁿ with no more than k <= n relevant variables. Each function f in Ф^k,n defines a splitting of cube {0,1}ⁿ into nonoverlapping cube faces and assigns a unique number to each cube face of the resulting splitting. We prove the lower bound of learning functions in Ф^k,n complexity and develop an algorithm of learning functions in Фⁿ = Ф^n,n that is optimal in the sense that the number of membership queries that the algorithm needs to learn an arbitrary function in Ф^k,n on the order coincides with the lower bound. The algorithm can be effectively parallelized and when maximally parallelized its complexity equals k on the order.
  Keywords: learning complexity, Boolean cube splitting, attribute-efficient learning, learning juntas, parallel learning, pseudo-boolean functions, exact learning model
• Е.А. Поцелуевская. Теоретическая и практическая сложность задачи о выполнимости булевых формул.
  
  В работе описываются различные варианты постановки задачи о выполнимости, а также приводится обзор наиболее известных алгоритмов её решения, их классификация и некоторые теоретические оценки сложности. В заключительной части статьи рассматриваются наиболее примечательные результаты, полученные в данном направлении за последние 10 лет, а также некоторые практические оценки сложности.
  Ключевые слова: выполнимость, SAT, обзор, алгоритм, сложность
  
  In the current work different variants of satisfiability problem statement are described, moreover a review of the most well-known algorithms for its decision, algorithms classification and some theoretical estimations for complexity are shown. At the final part of the article the most notable results obtained in this field during the last 10 years and several practical complexity estimations are regarded.
  Keywords: satisfiability, SAT, review, algorithm, complexity
• А.П. Соколов. Об одном семействе нейронов с ограниченной сложностью взаимной перестройки.
  
  Исследуется сложность преобразования одной пороговой функции, заданной линейной формой, к другой, путем пошагового изменения коэффициентов линейной формы. В качестве меры сложности данного процесса принимается изменение коэффициента или свободного члена линейной формы на единицу. Данный процесс может интерпретироваться как процесс обучения нейрона с пороговой функцией активации. Приводится конструктивное построение такого класса пороговых фукнций, что сложность взаимной перестройки функций из данного класса ограничено заранее заданной величиной, лежащей в диапазоне от 3..n до 3..2ⁿ, где n – число переменных. При этом, мощность данного класса экспоненциально зависит от n.
  Ключевые слова: пороговые функции, сложность обучения нейронов
  
  Complexity of transferring one threshold function specified by the linear form into another is examined. Changing of a weight coefficient of threshold by one is a measure of complexity of learning. This process models learning of neuron with threshold activation functions. It's described such class of neurons that the complexity of learning one neuron into another within this class is limited by an arbitrary value between 3..n and 3...2ⁿ, where n is a number of variables. At the same time the size of this class grows exponentially with n.
  Keywords: threshold functions, learning complexity of neurons
• Ю.С. Шуткин. Реализация монотонных булевых функций монотонными информационными графами.
  
  Рассматривается задача реализации булевых функций с помощью монотонных информационных графов, т. е. графов, базовое множество которых состоит из переменных без отрицаний. Получены оценки сложности для различных подклассов этой задачи.
  Ключевые слова: булева функция, монотонная булева функция, информационный граф
  
  A problem of monotone Boolean function representation using monotone information graphs is considered. Monotone information graphs have monotone base set, i. e. base set consisting of variables without negations. Complexity estimations for different subclasses of this problem were obtained
  Keywords: boolean function, monotone boolean function, information graphs, boolean functions representation