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

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

• Абросимов В.К., Демидов Р.С.. Информационный ландшафт организации.
  
  Вводятся и анализируются новые понятия, необходимые для анализа эффективности выбора и внедрения информационных систем – информационный ландшафт, совместимость и согласованность, необходимость и достаточность информационного ресурса. Показано, что их совместное использование позволяет методически обоснованно из множества предлагаемых информационных систем с различными характеристиками выбрать наиболее эффективную и потенциально востребуемую бизнесом организации.
  Ключевые слова: информационная система, информационный ресурс, выбор, эффективность внедрения, ландшафт
  
  New concepts needed for the analysis of selection and implementation information systems effectiveness – the information landscape, the compatibility and the consistency, the necessity and sufficiency of information resource have introduced and discuss. It is shown that with its sharing it is easy and methodically reasonably to choose the most effective and potentially demanded for business information system from a group of such systems with different characteristics
  Keywords: information system, information resource, selection, implementation efficiency, landscape
• Лебедев А.А.. Синтез операторов агрегирования информации по экспертным описаниям.
  
  Задача выбора оператора агрегирования информации – определение функции, характеризующей зависимость некоторой величины от наблюдаемых параметров – возникает при разработке большинства систем сбора и обработки информации. В работе развивается подход к описанию функций k-значной логики на основе нечётких условий. Доказывается NP-полнота задачи выбора функции по нечётким описаниям в общем случае, а также приводятся полиномиальные алгоритмы решения этой задачи для некоторых частных случаев.
  Ключевые слова: выбор операторов агрегирования, нечеткие условия
  
  The problem of selecting an aggregation function, a function describing the behaviour of one element of a system relative to others, is omnipresent in developing information gathering and analysis systems. In this paper, we develop an approach to describe k-valued logic functions by fuzzy constraints. We prove that the general problem of defining a function by fuzzy constraints is NP-complete and also provide polynomial algorithms solving the problem in several special cases.
  Keywords: selecting aggregation functions, fuzzy constraints
• Топровер Г.Л., Киселев С.Л.. Имитационная модель компьютерного анализа фактов.
  
  В статье представлена формальная модель алгоритмического анализа фактов на базе имитационного подхода с применением методов теории распознавания образов.
  Ключевые слова: фактология, анализ фактов, фактография, управление знаниями
  
  The article presents a simulation-driven formal model for computer-aided facts analysis based on the pattern recognition theory methods.
  Keywords: knowledge management, factology, factography, facts analysis
• Чмырь И.А.. Естественный диалог: моделирование диалоговой транзакции в контексте представления знаний.
  
  Статья посвящена исследованию и моделированию диалога и диалоговых транзакций. Онтологическая модель диалогового взаимодействия, на которой базируются последующие рассуждения, получена на основе анализа диалогов между людьми и иллюстрируется одним из диалогов Платона, под наименованием Протагор. В дальнейшем внимание фокусируется на одном из типов диалога, названного эротетический диалог и на структуре эротетической диалоговой транзакции с точки зрения обмена знаниями в пределах транзакции. Предложен спектр формальных моделей, ориентированных на представление внутренней логической структуры эротетической транзакции. Отличительной особенностью всех моделей является их ориентация на лингво-независимые сущности представление декларативных знаний, ас-социированных с элементами транзакции.
  Ключевые слова: онтологическая модель диалога, эротетический диалог, диалоговая транзакция, декларативные знания, язык тернарного описания
  
  The paper deals with an investigation and modeling of dialogue and dialogue transactions. An ontological model of human dialogue interaction, underlying follow-up reasoning, is obtained on the basis of analysis of human-human dialogues and illustrated by one of Plato’s dialogue Protagoras. In the sequel, attention is focused on one type of human-human dialogues, called erotetic dialogue and on the structure of erotetic dialogue transaction from the viewpoint of knowledge interchange within the transaction. A spectrum of formal models, oriented towards discovering the inner logical structure of erotetic transaction is offered. The distinguishing feature of all models is their orientation on language-independent entities representing declarative knowledge associated with a transaction’s elements.
  Keywords: ontological dialogue model, erotetic dialogue, dialogue transaction, declarative knowledge, Language of Ternary Description

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

• Зубюк А.В.. Критерий отношения правдоподобия в случайной морфологии.
  
  Рассмотрены задачи классификации изображений, имеющих случайную форму, и поиска объекта, изображения которого имеют случайную форму, на неизвестном фоне. Предложен метод решения указанных задач, основанный на принципе отношения правдоподобия. Теоретико-возможностный вариант будет рассмотрен в следующей публикации.
  Ключевые слова: морфологический анализ изображений, случайная форма изображений, критерий отношения правдоподобия
  
  Classification of images with random forms and search for an object, which images have random form, on an undefined background are considered. Method of solving those problems based on the likelihood ratio principle is suggested. A variant based on the possibility theory will be considered in the further publication.
  Keywords: morphological image analysis, random form of images, likelihood ratio criteria
• Назаров А.Н.. Об оценках числа виртуальных соединений и качественной доставке трафика данных в сотовых сетях мобильной связи на технологии GPRS.
  
  На основе развития энтропийного подхода разработаны оптимизационная модель расчета числа виртуальных соединений и оптимизационная модель расчета числа виртуальных соединений с заданным качеством обслуживания трафика, позволяющие оценивать ресурсное обеспечение узлового оборудования и трактов передачи данных в сотовых сетях мобильной связи на технологии GPRS. Варьируемыми параметрами модели с заданным качеством обслуживания трафика являются значения полос пропускания битового трафика различных категорий. Расчеты по разработанным моделям сводятся к последовательному решению совместных систем линейных уравнений.
  Ключевые слова: GPRS, GGSN, SGSN, QoS, оптимизационная модель
  
  On the basis of development of Entropy approach the optimising model of calculation of number of virtual connections and optimising model of calculation of number of virtual connections with the set quality of service of the traffic are developed, allowing to estimate resource maintenance of the central equipment and data transmission paths in cellular networks of a mobile communication on technology GPRS. Varied parametres of model with the set quality of service of the traffic are values of pass-bands of the bit traffic of various categories. Calculations on the developed models are reduced to the consecutive decision of joint systems of the linear equations.
  Keywords: GPRS, GGSN, SGSN, QoS, optimising model
• Пивоваров А.П.. Функциональная сложность задачи подсчёта для двумерной задачи о доминировании.
  
  В работе рассматривается задача подсчёта для двумерной задачи о доминировании. В рамках информационно-графовой модели данных приводится три семейства алгоритмов, решающих данную задачу. Оцениваются объёмы требуемой памяти и время обработки запроса в худшем случае. В качестве одного из средств уменьшения времени обработки запросов за счёт увеличения объёма требуемой памяти используется техника частичного каскадирования.
  Ключевые слова: двумерная задача о доминировании, вычислительный информационный граф, информационный граф, функциональная сложность, частичное каскадирование
  
  This paper considers 2-dimensional dominance counting problem. Three types of algorithms that solve this problem are constructed in terms of information graph data model. Required space and worst case time are estimated for them. Fractional cascading technique is used as one of tools to reduce processing time at the cost of increased required space.
  Keywords: 2-dimensional dominance counting, computational information graph, information graph, functional complexity, fractional cascading
• Снегова Е.А.. Критерий сводимости задачи об опасной близости к одномерным задачам для полиномиальных законов движения.
  
  В статье рассматривается задача об опасной близости в случае, когда законы движения объектов и запросов принадлежат классу полиномов конечной степени. Для этого случая приводится критерий сводимости задачи об опасной близости к одномерным задачам – задаче о прокалывании и задаче одномерного интервального поиска.
  Ключевые слова: базы данных движущихся объектов, пространственно-временные базы данных, информационный граф, сложность
  
  In this paper we consider Moving objects closeness problem (MOC problem) for the case of polynomial laws of motion. For this case we present and prove criteria for reducibility of the MOC problem to one-dimensional problems range searching problem and one-dimensional stabbing problem.
  Keywords: databases of moving objects, spatio-temporal databases, information graph, complexity
• Тимирова А.Н.. Свойства модели Марковица при задании параметров средствами теории нечетких множеств.
  
  В работе представлена модель оценки доходности и риска в анализе формирования инвестиционных портфелей. Доходность ценных бумаг оценивается, как нечеткое число, а риск – как мера неопределенности доходности.
  Ключевые слова: нечеткие числа, степень нечеткости, модель Марковица, инвестиционный портфель
  
  This work presents the analysis of expected return and risk of assets based on portfolio selection model. Expected return is presented as a fuzzy number and risk – as fuzziness degree of expected return.
  Keywords: fuzzy number, fuzziness degree, Markowitz model, investment portfolio
• Титова Е.Е.. Линейное по времени конструирование изображений клеточными автоматами.
  
  В работе рассматривается задача конструирования изображений клеточным автоматом на прямоугольном экране. Для случаев, когда элементарный автомат имеет 3, 4 и 5 состояний, и когда число состояний неограниченно растет, получены оценки времени конструирования изображений, линейно зависящие от размеров экрана. Найден алгоритм построения изображений для экрана, имеющего один свободный вход.
  Ключевые слова: клеточный автомат, генератор, универсальный экран, конструирование изображений, оценка времени конструирования изображения
  
  The work deals with the problem of image construction with a cellular automata on a rectangular screen. For cases where an elementary automaton has 3, 4 and 5 states were developed algorithms with time linear to the screen resolution. There were founded estimates of the image construction time with an increasing number of elementary automaton states. An algorithm of image construction for the screen with only one free input was developed.
  Keywords: cellular automaton, generator, universal screen, image construction, estimation for time of image construction
• Цымжитов Д.Н.. О новом подходе к решению задачи мягкого ML-декодирования линейных кодов.
  
  В работе представлен метод декодирования для двоичных линейных кодов, основанный на использовании векторов, которые мы называем неприводимыми. Неприводимый вектор представляет собой минимальную структуру определенного вида и является обобщением понятия минимального кодового слова. Нами предложены два алгоритма, реализующие этот подход применительно к двум классам кодов, характеризуемых некоторыми предположениями относительно структуры графа Таннера проверочной матрицы. В первом случае рассматриваются коды с ациклическим графом Таннера, а во втором случае – коды, у которых все символьные вершины в графе Таннера имеют степень не более 2. Если n – длина кода, то первый алгоритм выполняется за время O(n²) при n→∞, а второй – за время O(n⁴) при n→∞.
  Ключевые слова: мягкое декодирование, декодирование по максимуму правдоподобия, линейные коды, сложность декодирования, минимальные кодовые слова
  
  In this paper we present a method of decoding of binary linear codes based on the use of vectors, which we call irreducible. Irreducible vector represents the minimum structure of a certain type and is a generalization of the minimum codeword concept. We propose two algorithms that implement this approach for two classes of codes, which are defined by certain assumptions about the structure of their Tanner graph. In the first case, we consider codes with an acyclic Tanner graph, and in the second case, we consider codes with a Tanner graph in which all variable nodes have degree at most 2. If n is the length of the code, the first algorithm runs in O(n²) time, whereas the second one runs in O(n⁴) time.
  Keywords: soft-decision decoding, maximum-likelihood decoding, linear block codes, decoding complexity, minimal codewords

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

• Бокк Н.Г.. О порядке элемента в группе автоматных подстановок.
  
  Построена серия групповых автоматов конечных порядков вида 2n. Для автоматов с абелевой внутренней группой приведен критерий определения порядка по строению группы. Показана невозможность такого критерия для произвольной внутренней группы.
  Ключевые слова: автоматные подстановки, групповые автоматы, внутренняя полугруппа, порядок автомата
  
  We build a group automaton of 2n order for each natural n. We also introduce a criterion of order definition for automata with Abelian intrinsic groups by group generators. Finally we show that such criterion is impossible in general case.
  Keywords: automaton permutations, group automata, intrinsic semigroup, automaton order
• Ишматова Ю.А.. О некоторых свойствах групп алгебр с параметрами.
  
  Группы алгебр с параметрами являются основным объектом в ряде криптографических стандартов республики Узбекистан. В работе исследуется ряд свойств таких групп, существенных с точки зрения криптографии. Доказывается критерий обратимости элемента, вычисляется порядок группы, а также устанавливается связь возведения в степень с возведением в степень в мультипликативных группах колец вычетов.
  Ключевые слова: алгебры с параметром, криптографический стандарт, возведение в степень
  
  Groups of algebras with parameters are the main object of cryptographic standards of Uzbekistan. We investigate a number of cryptographically essential properties of such groups. We prove reversibility criterion, evaluate group order and show correspondence of exponentiation with parameter and exponentiation in residue rings.
  Keywords: algerbas with parameters, cryptographic standards, exponentiation
• Перпер Е.М.. О функциональной сложности поиска подстроки.
  
  В работе рассматривается задача поиска подслова во множестве слов. Эта задача состоит в следующем: пусть дано множество слов; надо для произвольного подслова найти все слова из этого множества, содержащие это подслово. В данной работе разработаны 3 алгоритма поиска, с помощью которых получены оценки функциональной сложности поиска.
  Ключевые слова: слово, подслово, поиск, информационный граф, сложность, объём
  
  The paper deals with the problem of search subwords in set of words. This problem is as follows: suppose we are given a set of words; in this set for an arbitrary subword we must find words which contain this subword. In this paper, three algorithms of search are developed and, with them, estimates of the functional complexity of search are obtained.
  Keywords: word, subword, search, information graph, complexity, volume
• Пивоваров А.П.. Об одном способе получения нижних оценок сложности информационных графов.
  
  В работе приведен один способ получения нижних оценок сложности информационных графов различных видов (как в худшем случае, так и в среднем). Для этого вводится понятие информационного графа общего вида, под которое подпадают большинство модификаций информационных графов. Для информационных графов общего вида вводится понятие допустимости для выходной функции. Полученные нижние оценки сложности информационного графа общего вида зависят от количества различных значений, принимаемых выходной функцией.
  Ключевые слова: информационный граф общего вида, нижняя оценка сложности, моделирование поиска
  
  This paper contains one method for obtaining of lower bounds for complexity of information graphs of different types (in average and in the worst case). For this purpose the notion of general information graph is introduced. This notion covers the majority of information graph modifications. The notion of general information graph acceptability for a output function is introduced. The estimates obtained for some general information graph depend on the codomain cardinality of the output function.
  Keywords: general information graph, lower bound for complexity, search modelling
• Родин А.А.. О континуальности множества специальных предполных классов во множестве автоматных отображений.
  
  В работе рассматриваются предполные классы, содержащие все о.-д. функции, в каждом состоянии которых реализуется функция из некоторого замкнутого класса D k-значной логики. Показано, что мощность множества таких предполных классов равна континууму для любого замкнутого D.
  Ключевые слова: автоматные отбражения, предполный класс, К-значная логика
  
  Let D be a closed class in k-valued logic. Denote by P(D) the set of deterministic finite functions having k-valued function from D in every state. It is shown in the article, that there exists continuum of precomplete classes C such that C includes P(D).
  Keywords: automata mappings, precomplete class, K-valued logic
• Соколов А.П.. О сложности перестройки формальных нейронов.
  
  Работа посвящена вопросам сложности обучения нейронов. В качестве математической модели нейронов рассматриваются пороговые функции алгебры логики. Рассматривается вопрос сложности взаимной перестройки (обучаемости) пар пороговых функций в самом сложном случае, в большинстве случаев и внутри классов пороговых функций, инвариантных относительно групп перестановок. В качестве средства задания пороговых функций выстапают целочисленные линейные формы. В качестве меры сложности процесса перестройки рассматривается число элементарных операций над весовыми коэффициентами линейной формы. Получен ряд верхних и нижних оценок сложности взаимной перестройки формальных нейронов для различных случаев. Построен алгоритм, осуществляющий перестройку заданного формального нейрона в желаемый. Получены оценки временной сложности данного алгоритма.
  Ключевые слова: пороговые функции, сложность обучения нейросетей
  
  Problems of neurons learning complexity are considered in this paper. Threshold function act as mathemetical model of neuron. Following problem is being studied: what is the complexity of mutual reconstruction (learning) of pairs of threshold functions in the worst case, in most cases and inside sets of threshold functions that are invariant by groups of permutations. Threshold functions are defined by means of linear forms with integer coefficients. Number of elementary operations over weight coefficients of the linear form is the measure of complexity of mutual reconstruction of threshold functions. Set of upper and lower bounds for complexity of mutual reconstruction of formal neurons for various cases was found. It was developed an algorithm for reconstruction of given formal neuron to the desired one. Time complexity of this algorithm was estimated.
  Keywords: threshold functions, learning complexity of neural networks