Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова


Последний номер	Содержание последнего номера журнала "Интеллектуальные системы"
Архив выпусков	Архив выпусков журнала: содержание всех выпусков, избранные материалы в формате PDF

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

Часть 1. Секция "Интеллектуальные системы"

Агниашвили П.Г. О восстановлении изображений по кодам в некоторых вырожденных случаях

Доказывается утверждение о свойствах кодов в рамках дискретно-геометрического подхода к распознаванию изображений. Рассматриваются изображения, все точки которых содержатся в двух параллельных гиперплоскостях. Исследуется возможность восстановления таких изображений по их кодам.
Ключевые слова: распознавание изображений, дискретно-геометрический подход, кодирование изображений.

Agniashvili P.G. About image recovery by its code in some degenerate cases

A statement is proved that concerns certain properties of codes under discrete-geomentrical approach to visual recognition. Images under consideration lie on the two parallel hyperplanes. The possibility of image recovery is investigated in this degenerate case.
Keywords: visual recognition, discrete-geometrical approach, image coding.
Алексеев Д.В. Использование метода В.Н. Козлова в образовательном процессе на кафедре МаТИС

Рассматривается использование мотода В.Н.Козлова восстановления трехмерных изображений в курсе "Дискретный анализ" и описывается система автоматического порождения задач по этой теме.
Ключевые слова: аналитическая геометрия, аффинные преобразования, распознавание образов, стереозрение

Alekseev D.V. Using V.N.Kozlov's method in education process on MaTIS chair

The article describes the usage of V.N.Kozlov's method in educational process in course "Discrete calculus" and the system of automatic problem generation for that theme.
Keywords: analytical geometry, affine transform, pattern recognition, stereo vision
Баранович А.Е., Боровиков Д.В., Лакуша Е.Л. Об алгебраизации модели k-гиперпространства СХ-гипертопографов: операции трансформации развития

Излагаются результаты синтеза алгебраических операций трансформации и развития семиотико-хроматических (CX-) гипертопографов (ητ-графов) в сигнатуре Ψ^Φ_{G^k_ητx}, где Φ есть вполне определенное множество (элементарных трансформаций). Предложена теоретико-множественная алгоритмическая реализация операции трансформации (ТСХ-процедура) для СХ-ητ-графов. Исследованы условия сходимости и глубина трансформации в ТСХ-процедуре на конечных СХ-ητ-графах. Приведена оценка (сверху) операционной сложности ТCХ-процедуры.
Ключевые слова: CX-гипертопографов трансформация, CX-гипертопографов развитие, k-гиперпространства CX-гипертопографов алгебраизация, трансформации элементарные, трансформации глубина, k-гиперпространство, СХ-гипертопограф

Baranovich A.E., Borovikov D.V., Lakusha E.L. Algebraization of model of k-hyperspace of SC-hypertopographs: transformations – evolutions operation's

Results of synthesis of algebraic operations of transformation and evolutions semiotic-chromatic (SС-) hypertopographs (ητ-graphs) in signature Ψ^Φ_{G^k_ητx} where Φ there is quite certain set (elementary transformations) are stated. Theoretic-multiple algorithmic realization of operation of transformation (TSС-procedure) for SС-ητ-graphs is offered. Conditions of convergence and depth of transformation in TSC-procedure on final SС-ητ-graphs are investigated. The estimation (from above) operational complexity TSC procedure is resulted.
Keywords: SC-hypertopographs transformation, SC-hypertopographs evolution, k-hyperspace SC-hypertopographs an algebraization, elementary transformations, transformations depth
Баранович А.Е., Иглицкая С.М. О некоторых результатах сравнительного анализа моделей музыкального и вербального текстов

Представлены результаты исследования музыкального текста (МТ) строгого стиля (СС), представленного моделью дискретных сообщений фон Неймана, в задаче оценки пропускной способности дискретного канала связи по Шеннону. Предложен расширенный алфавит представления МТ СС. Получены сравнительные оценки числа слов МТ длины, не превышающей l, и значения энтропии МТ в модели нулевого и первого приближений (одно- и двухголосие). Обоснована гипотеза о более высокой пропускной способности канала музыкальной коммуникации в отношении вербальной. В качестве модели объективной семантики МТ предложено использовать модель k-гиперпространства СХ-гипертопографов и СХ-гипертопосети – для динамического случая.
Ключевые слова: канал коммуникации, модель сообщения Дж. фон Неймана, семантика текста, текст вербальный, текст музыкальный, k-гиперпространство СХ-гипертопографов, СХ-гипертопосети

Baranovich A.E., Iglitskaya S.M. About some results of comparative analysis of models of musical and verbal texts

Results of research of the musical text (МТ) austere style (AS), presented by model of discrete messages von Neumann's, in a problem of an estimation of throughput of a discrete communication channel on Shannon are presented. The expanded alphabet of representation МТ AS is offered. Comparative estimations of number of words МТ of the length which are not exceeding l, and values of entropy МТ in model zero and the first approximation (one voice and double-voiced) are received. The hypothesis about higher throughput of the channel of musical communications concerning the verbal is proved. As model of objective semantics МТ is offered to use model of k-hyperspace of SC-hypertopographs and SC-hypertoponets – for a dynamic case.
Keywords: communications channel, model of message of J. von Neumann's, semantics of text, verbal text, musical text, k-hyperspace of SC-hypertopographs, SC-hypertoponets
Биштейнов Д.А. Математическая модель для оптимизации индивидуальной практической работы учащегося

Индивидуализация обучения — актуальная задача в нашей стране. В этой статье мы приводим модель представления теоретического материала учебника и практических заданий задачника с целью оптимизации управления индивидуальной практической работой ученика в классе за счет автоматизации выполнения некоторых задач учителя.
Ключевые слова: индивидуализация образовательного процесса, модель, математическое моделирование, графовая модель, система автоматизированного проектирования работы учителя (САПР учителя).

Bishteynov D.A. Mathematical model for the optimization of individual practical student work

In this article the author intriduces a mathematical model for the optimization of individual practical student work.
Keywords: model, mathematical modelling, graph model
Борченинов Я.В., Окуловский Ю.С. Эволюционные символьные вычисления: методика и инструментарий

В данной статье описывается проблема "раздувания" генов в процессе работы алгоримов генетического программирования. Приводятся возможные методы решения данной проблемы, а также, предлагается новый подход, основанный на комбинировании генетического программирования и символьных вычислений.
Ключевые слова: генетическое программирование, символьные вычисления, интеллектуальные системы

Borcheninov Ya.V., Okulovskiy Yu.S. Evolutionary symbolic computation: methods and tools

The current paper describes gene blowing problem during genetic programming computations. There were noted a number of possible methods to solve that problem. Also, there was proposed a new approach, which is based on combining genetic programming and symbolic computations.
Keywords: genetic programming, symbolic computations, intelligent systems
Гасанов Э.Э., Остроухова Е.Н. Приближенное решение задачи о близости в евклидовой метрике

В работе приводятся оценки для двух серий алгоритмов приближенного решения задачи о близости в евклидовой метрике. Эти алгоритмы отличаются объемами требуемой памяти, временем поиска и уровнем ошибок.
Ключевые слова: информационный граф, задача о близости, приближенные алгоритмы

Gasanov E.E., Ostroukhova E. N. Approximate solution of the problem of proximity in the Euclidean metric

The paper presents two types of approximate algorithms for the the proximity problem in the Euclidean metric. According to our approach these algorithms exploit a trade-off between required memory, search time and error rate.
Keywords: information graph, the problem of proximity, approximation algorithmsн
Дергунов А.В. База знаний повышения производительности MPI-приложений

Для анализа MPI программ наиболее часто используют программные системы, которые осуществляют сбор и визуализацию трассы выполнения программы. Но при использовании таких инструментов пользователь сталкивается с проблемой анализа больших объемов информации. Другой проблемой является то, что часто встречающиеся ситуации, приводящие к потерям производительности MPI программ, явно не визуализируются, т.е. отсутствует база знаний повышения производительности. Поэтому возникает потребность в средствах, которые бы автоматизировали анализ трассы и подсказали пользователю, как повысить производительность его программы. В данной работе описывается программная система, выполняющая эту задачу. Ключевым компонетом этой системы является база знаний причин недостаточных производительности MPI приложений, которая состоит из правил, описанных на специальном языке, разработанном в рамках этой системы.
Ключевые слова: MPI, анализ производительности, база знаний

Dergunov A.V. Knowledge base for performance improvement of MPI applications

To analyze MPI applications we usually use tools for tracing the execution of an application and then visualizing this trace and various statistics. But when using such kind of tools the user has to analyze a lot of data. Another problem with these tools is that frequent known situations leading to the loss of performance in MPI programs are not visualized. In other words, these tools lack a knowledge base for performance improvement. Thus there is a need to have tools for automating application trace analysis and recommending relevant solutions for improving performance of MPI applications. This article describes such system. The key component of this system is knowledge base encoding reasons of insufficient MPI application performance. The knowledge base contains rules described with a specialized language implemented for this system.
Keywords: parallel programming, knowledge representation, performance improvement, performance analysis
Козлов В.Н. Геометрический подход к распознаванию зрительных образов (краткий обзор)

Статья, как это следует из названия, представляет собой обзор по дискретно-геометрическому подходу к распознаванию изображений.
Ключевые слова: распознавание образов, изображения, компьютерное зрение

Kozlov V.N. Geometric approach to the recognition of visual images (an overview)

Article, as it name suggests, is a review on discrete geometric approach to images recognition.
Keywords: pattern recognition, image, computer vision
Конончук Д.О., Окуловский Ю.С. Универсальная модель алгоритмов коллективного разума и ее реализация

Рассмотрена модель алгоритмов коллективного разума, обобщающая известные алгоритмы искусственных иммунных систем, муравьиные алгоритмы, метод роя частиц и т.д. Данная модель является общей для многих видов алгоритмов коллективного разума, и позволяет создать единую формализацию этих методов. На базе данной модели создана программная реализация, позволяющая быстро разрабатывать алгоритмы коллективного разума, сравнивать различные методы, распараллеливать их выполнение, и т.д.
Ключевые слова: алгоритмы коллективного разума, муравьиные алгоритмы, искусственные иммунные системы

Kononchuk D.O., Okulovskiy Yu.S. Universal model of collective intelligence algorithms and its implementation

The work describes a universal model of collective intelligence algorithms generalizing the known algorithms of artificial immune systems, ant algorithms and other known methods.
Keywords: ant algorithms, artificial immune systems
Котельников С.В. Интеллектуальная система обучения программированию на REFAL

Актуальной задачей обучения в современных условиях является индивидуализация, которая обеспечивается использованием компьютера. Данная работа представляет собой интеллектуальную систему обучения языку логического программирования REFAL (в объеме REFAL-2).
Ключевые слова: Java EE, интеллектуальная система REFAL, интерпретатор, синтаксический семантический анализатор, система обучения

Kotelnikov S.V. Intelligent system training skills of REFAL langauge programming

Urgent task of education in modern conditions is individualization, which is ensured by using a computer. This work describes an intelligent language system for learning logic programming in REFAL language.
Keywords: interpreter, intelligent system, Java EE
Максимова А.Ю. Метод организации работы с данными в прикладных системах распознавания образов

Предложен метод организации работы с данными для программных системы распознавания образов, который позволяет автоматизировать процесс формирования выборок прецедентов на основе данных предметной области.
Ключевые слова: модели данных, распознавание образов, анализ данных

Maksimova A.Yu. The Method of Data Organization in the Applied Pattern Recognition System

We propose a method of organizing work with the data for software recognition system, which automates the process of samples prepearing based on data domain.
Keywords: models of data, pattern recognition, data mining
Перпер Е.М. Применение семантического графа для решения текстовых задач

В работе рассматривается метод автоматического решения текстовых задач с помощью преобразований над семантическими графами текста задачи. При этом каждое преобразование соответствует определённому шагу решения задачи человеком.
Ключевые слова: текстовая задача, автоматическое решение, семантический граф

Perper E.M. The semantic graph to solve textual problems

In the paper it is considered the method of automatic solution of textual problems. The solution is conducted by consecutive transformations on the semantic graph of the problem text. Each transformation corresponds to a certain step of human's solution of the textual problem.
Keywords: textual problem, automatic solution, semantic graph
Пивоваров А.П. Суммирование по полугрупповой операции для двумерной задачи интервального поиска с фиксированной стороной

В работе рассмотрена задача, в которой требуется найти полугрупповую сумму значений приписанных точкам на плоскости, попадающим в прямоугольник с одной заранее фиксированной стороной и тремя сторонами, определяемыми запросом. Получено семейство решений удовлетворяющих указанным ограничениям на время работы и количество используемой памяти.
Ключевые слова: интервальный поиск, вычислительный поиск, сложность поиска, частичное каскадирование, информационно-графовая модель поиска, вычислительная геометрия

Pivovarov A.P. Summation over the semigroup operation for two-dimensional interval search problem with a fixed side

This paper considers the problem of semigroup sum of values assigned to a set of points on a plane such that they are residing in a rectangle with one fixed side and three sides determined by a given query. A family of solutions is found which meets certain limitations on consumed space and time.
Keywords: range searching, computational search, search complexity, fractional cascading, information graph search theory, computational geometry
Плетнев А.А. Моделирование динамических баз данных

Функционирование базы данных – это обработка потока запросов типа поиск, вставка и удаление. При этом в результате запросов типа вставка и удаление база данных изменяется, а на запросы типа поиск выдается ответ. Если поток запросов на поиск существенно преобладает над запросами на изменение базы данных, то такие базы данных называются статическими. Для исследования таких баз данных предназначены информационные графы. Предлагаемая модель динамических баз данных построена на взаимодействии конечного детерминированного автомата и информационного графа. Задача автомата перестраивать информационный граф при изменении базы данных, тем самым обрабатывая динамические запросы пользователя.
Ключевые слова: динамические базы данных, математическое моделирование, информационный граф

Pletnev A.A. Dynamic databases modelling

The operation of database is a processing of requests stream types search, insert and removal. As a result of requests types search and removal the database changes, also there is a response for request type search. If the stream of search requests dominates on the requests for database changing, then this kind of databases are called static. For the investigation of this kind of databases we use the information graphs. An expected model of dynamic databases is built on interaction of finite deterministic automaton and information graph. The task of automaton is to rebuild an information graph with changing of databases by processing of dynamic requests of user.
Keywords: dynamic database, mathematical modelling, information graph.
Подколзин А.С. Компьютерное моделирование логических процессов

Предлагаемая работа посвящена развитию компьютерной системы, которая могла бы стать основой для универсальной экспертной системы ("решателя") указанного выше типа и одновременно "микроскопом" для изучения общих принципов организации логических процессов, включая самообучение. Система основана на применении нового языка программирования ГЕНОЛОГ, расположенного в точности на пограничном слое между теорией и алгоритмами. Прием на этом языке задается как теорема предметной области, снабженная некоторой алгоритмизирующей разметкой.
Ключевые слова: компьютерное моделирование, логика, семантика, искусственный интеллект

Podkilzin A.S. Computer modelling of logical processes

The work describes the development of computer system modelling the universal expert system ("Solver").
Keywords: computer modelling, logics, semantics, artificial intelligence
Половников В.С. О нелинейных характеристиках нейронных схем в произвольных базисах

В данной работе обобщены результаты, полученные для нейронных схем над фиксированным базисом на случай схем из элементов, представляющих собой полную (по операции суперпозиции) систему кусочно-параллельных функций, содержащую все линейные элементы и некоторую нелинейную часть
Ключевые слова: искусственные нейронные сети, нейронные схемы, нелинейная глубина, схемы из функциональных элементов, сложность

Polovnikov, V.S. On nonlinear characteristics of neural circuits over an arbitrary basis

The results obtained for the neural circuits over a fixed basis are generalized for the case of schemes over an arbitrary complete (by operation of superposition) basis of piecewise-parallel functions containing all linear functions and some non-linear part
Keywords: artificial neural networks, neural schemes, non-linear depth, schemes of functional elements, complexity
Давыдова (Романова) А.А. Моделирование электронного билингвального методического словаря открытого типа как составляющая процесса формирования интеллектуальной информационной системы

Одной из задач, решаемых интеллектуальными информационными системами, является обучение. Это подразумевает использование компьютера для обучения какой-то дисциплине или предмету. При построении интеллектуальных систем, основанных на знаниях, используются знания, накопленные экспертами в виде конкретных правил решения тех или иных задач, следовательно, билингвальный методический словарь-справочник, созданный по принципу Википедии, является типичным банком знаний, который впоследствии может быть включен в состав более сложной экспертной системы.
Ключевые слова: Интеллектуальная информационная система, билингвальный, словарь

Davydova (Romanova) A.A. Modeling of an electronic bilingual methodical dictionary of an open type as a part of intelligent information system formation process

One of the problems solved by intelligent information systems is the training. This involves the use of computers for studying some discipline or subject. When building intelligent systems based on knowledge, the knowledge accumulated by experts in the form of specific rules of solving various problems are used, therefore, bilingual methodical dictionary and reference book created on the principle of Wikipedia, is a typical knowledge bank, that can then be included in a more sophisticated expert system.
Keywords: Intelligent Information System, bilingual, dictionary
Рублев В.С., Смирнова Е.А. Объектная СУБД DIM и пути ее реализации

Рассматривается объектный подход к созданию СУБД, который предполагает не только изменение данных объектов, но и возможность изменения типов объектов, т. е. схемы базы данных, названный динамической информационной моделью (DIM). Язык объектно-динамических запросов ODQL для динамической информационной модели DIM обладает полнотой – любая группа объектов DIM (вместе с любыми их свойствами) может быть выделена ODQL-запросом. Рассматриваются пути реализации системы, при которой учитываются вопросы организации данных и их схемы, при которых учитывается динамичность данных и их типов, а также минимизируется (в эвристическом смысле) время выполнения запросов.
Ключевые слова: объектная СУБД, динамическая информационная модель, изменение объектов и типов, язык объектно-динамических запросов, минимизация времени выполнения запросов

Roublev V.S., Smirnova E.A. Object DIM DBMS and ways of its realization

Object approach to DBMS creation which assumes not only change of these objects, but also possibility of change of types of objects, i.e. the database schemes, called dynamic information model (DIM) is considered. Language of object and dynamic inquiries of ODQL for the dynamic information DIM model possesses completeness – any group of objects of DIM (together with any their properties) can be allocated with ODQL inquiry. Ways of realization of system at which questions of a data structure and their scheme at which dynamism of data and their types is considered are considered are considered, and also is minimized (in heuristic sense) time of performance of inquiries.
Keywords: object DBMS, dynamic information model, change of objects and types, language of object and dynamic inquiries, minimization of time of performance of inquiries
Руденко А.Д. О кодах конечных множеств точек в евклидовых пространствах

Рассматриваются коды конечных множеств точек n-мерного евклидова пространства, составленные из индексированных отношений мер n-мерных симплексов с вершинами в точках множества. Показывается, что изображение, не лежащее целиком в паре параллельных гиперплоскостей, восстанавливается по своему коду с точностью до аффинных преобразований.
Ключевые слова: кодирование изображений

Rudenko A.D. About codes of finite sets of points in an n-dimensional Euclidian space

A finite set of points in an n-dimensional Euclidian space is represented with indexed ratios of measures of n-dimensional simplices with vertices at set's points. It is shown that a set not contained in two parallel hyperplanes is restored from such representation uniquely up to affine transformations.
Keywords: image representation
Рыжов А.П. Системы оценки и мониторинга сложных процессов и их приложения

Описаны технологические и математические аспекты разработки систем информационного мониторинга и примеры приложений.
Ключевые слова: системы оценки и мониторинга, нечеткие множества, оценка нечеткости, поиск в нечетких базах данных, агрегация информации в нечетких иерархических динамических системах

Ryjov A.P. Intelligent systems for evaluation and monitoring of complex processes and theirs applications

The article presents technological and mathematical aspects of development an information monitoring systems and examples of theirs applications.
Keywords: systems for evaluation and monitoring, fuzzy sets, fuzziness, fuzzy data bases, aggregation in fuzzy hierarchical dynamic systems
Скатов Д.С. Эффективые реализации строковых словарей для решения задач компьютерной лингвистики

В контексте обработки текстов на естественном языке (морфологический анализ, исправление опечаток, подсказки для поисковой строки) рассматриваются ассоциативные множества со строковыми ключами. Их промышленное использование подразумевает высокую производительность, сериализауемость и компактность. В докладе предлагаются результаты детального сравнения существующих реализаций таких индексов (в т.ч. авторской). Обсуждаются особенности их применения для обработки и хранения естественно-языковых данных.
Ключевые слова: Структуры данных, ассоциативные множества, индексация строк, компьютерная лингвистика, префиксное дерево, trie, patricia, judy-array, hash, C и C++

Skatov D.S. Effective implementation of string dictionaries for solving computational linguistics problems

Associative sets with string keys are discussed in the context of natural language texts processing (tasks like morphological parsing, spell checking, query suggestions in search systems). Their industrial exploitation implies high performance, compactness and the ability of serialization. In this article, the results of detailed comparison between the existing implementations of such indices are proposed, including one that is author’s. The features of their application for processing and storing natural language data are discussed.
Keywords: Data structures, associative sets, indexing of strings, computational linguistics, prefix tree, trie, Patricia, Judy-array, hash, C and C++
Снегова Е.А. Критерий сводимости задачи о предотвращении столкновений к задаче о прокалывании

В работе исследуется задача о поиске движущихся объектов, которые могут столкнуться с движущимся объектом-запросом, где под столкновением понимается нахождение объектов в опасной близости.
Ключевые слова: поиск, информационный поиск, близость

Snegova E.A. Kriteriy svodimosti zadachi o predotvrashchenii stolknoveniy k zadache o prokalyvanii

Keywords: search, information search, closeness
Чуличков А.И., Демин Д.С., Копит Т.А., Цыбульская Н.Д. Анализ формы изображений, заданных с погрешностью

Рассматривается редукция измерений в линейной схеме, в которой измеряется выходной сигнал линейного измерительного прибора, на ход которого подан неизвестный входной сигнал. Измерения искажаются шумом. Результат редукции интерпретируется как измерение входного сигнала на приборе, близком к идеальному. Математическая модель измерительного прибора, связывающая результат измерения с его входным сигналом, неизвестна и извлекается из результатов тестовых измерений. Погрешность измерений описывается в терминах теории возможностей. Задача редукции измерений ставится как задача на максимум апостериорной возможности.
Ключевые слова: Принятие оптимальных решений, редукция измерений, возможность.

Chulichkov A.I., Demin D.S., Kopit T.A., Tsybulskaya N.D. The analysis of a form of the images which are known with an error

The method of a reduction of linear measurements of an output signal of the measuring device is considered. It is regarded that on an entrance of the device the unknown measured signal is operated, measurements are distorted by noise. The reduction is interpreted as measurement on the device closest to the ideal. The model of measurements which connects result of measurement with its entrance signal, is unknown and is taken from results of test measurements. The error of measurements is described in terms of the theory of possibilities. Reductions of measurements is defined from conditions of a maximum of a posteriori possibility.
Keywords: Optimal decision making, measurement reduction, possibility
Ширяева И.А. Разработка модели реализации предметно-ориентированной интерактивной сети

Статья посвящена актуальной проблеме внедрения интерактивной обучающей сети в образовательное учреждение. В ней охарактеризована модель реализации дистанционного обучения на базе предметно-ориентированной интерактивной сети.
Ключевые слова: дистанционное обучение, интерактивность, интерактивная сеть, модель реализации

Shiryaeva I.A. Development of a model for implementing subject-oritnted interactive network

The article is devoted to the topical problem of the introduction of interactive learning network to educational institutions. It is characterized by the model of distance learning implementation based on object-oriented interactive network.
Keywords: distant learning, interactivity, interactive network, model of implementation

Часть 2. Секция "Теория автоматов"

Алёшин С.В. Полугруппы и группы автоматов

Рассмотрены задачи построения бесконечных групп и полугрупп автоматных отображений.
Ключевые слова: автомат, группа, проблема Бернсайда, свободная группа

Aleshin S.V. Semigroups and groups of automata

The article is devoted to the problem of construction of infinite groups and semi-groups , which elements are automata.
Keywords: automaton, group, Burnside's problem, free group
Бабин Д.Н. О суперпозициях автоматов

В работе приводится обзор основных задач и научных результатов, связанных с суперпозицией автоматов. Вводится функциональная система автоматов с фиксированной добавкой и понятие простого автомата.
Ключевые слова: конечный автомат, простая группа, суперпозиция

Babin D.N. On atomata superpositions

We introduce a concept of prime automata with respect a cascade concatenation.
Keywords: superposition, finite automaton, completeness, prime group
Бабин Д.Н. Простые автоматы в задаче полноты относительно суперпозиции

Для суперпозиции автоматов с добавкой из штриха Шеффера и задержки описаны простые автоматы.
Ключевые слова: конечный автомат, простая группа

Babin D.N. Prime automata in the problem of completeness with respect to superposition operation

The concept of prime automata was introduced.
Keywords: finite automata, prime automaton, prime group
Богомолов С.А. Автоматная модель взаимодействия организационных систем

В сообщении рассматривается конкуретно взаимодействие организационно-производственных систем. предлагается автоматная модель выбора варианта поведения в зависимости от сложившейся ситуации.
Ключевые слова: организационная система, автомат, ситуация, пространство, вариант поведения

Bogomolov S.A. Automata model for competed interaction of systems of organization

The article considers automat model of competed interaction of systems.
Keywords: systems of organization, automat, situation, space, variant of behaviour
Виноградов И.В. К вопросу о порядках элементов группы автоматных подстановок

В работе рассмотрен автомат 8-го порядка в группе автоматных подстановок AS₂, реализующий отрицание в одном состоянии и тождественную функцию в остальных. Пример автомата 4-го порядка, обладающего теми же свойствами, был дан в работе [2]. Изучение автоматов с одним отрицанием представляет особенный интерес, поскольку любой автомат из группы AS₂ разлагается в суперпозицию автоматов такого вида.
Ключевые слова: автоматы, группа автоматных подстановок, порядок элемента, диаграмма переходов, тождественная функция, отрицание

Vinogradov I.V. About an order of elements in the group of automata's permutations

The paper considers 8-th order automaton in the group of automata's permutations, which implements negation in one state and the identity function in others. An example of 4-th order automaton satisfying the same properties was given in Makarov's work. The study of automata with one negation is of special interest, as any automaton from the group of automata’s permutations is decomposed into a superposition of automata with this property.
Keywords: automata, group of automata’s permutations, order of element, diagram of transitions, identity function, negation
Епифанов А.С. Методы интерполяции частично заданных законов функционирования автоматов

Задачи управления, технического диагностирования, синтеза поведения систем и т.п. в случае сложных систем не обеспечены полной и точной информацией для их решения. Теория экспериментов по распознаванию поведения автоматов нашла эффективное применение в техническом диагностировании отдельных элементов, узлов, агрегатов и других технических объектов, допускающих задание явно представленными дискретными математическими структурами: таблицами, матрицами, графами, логическими уравнениями и т.п. В этих случаях модели объектов диагностирования задаются, как правило, явно и точно, средства диагностирования определены полностью, а решаемые вопросы сводятся к проверке работоспособности и локализации неисправности по местоположению или функциям. Принципиально отличается техническое диагностирование сложных систем. Неустранимая для сложных систем неполнота исходной и фактически получаемой контрольным и диагностическим экспериментами информации делает задачи доопределения информации актуальными. В работе исследуется доопределение частично заданных законов функционирования автоматов из классов (n, m, l) – автоматов, где n – число состояний автомата, m и l – числа входных и выходных сигналов автомата для классов (4,2,2)-автоматов, (8,2,2)-автоматов, (16,2,2)-автоматов и классов автоматов, законы функционирования которых представлены частично заданными последовательностями вторых координат точек геометрических образов.
Ключевые слова: дискретный детерминированный автомат, геометрический образ законов функционирования автомата, доопределение частично заданных автоматов, метод интерполяции Ньютона, метод интерполяции Лагранжа

Epifanov A.S. Methods of interpolation of partially set lows of functioning of automata.

Problems of management, technical diagnosing, synthesis of behaviour of systems, etc. in case of complex systems are not provided by the full and exact information for their decision. The theory of experiments on recognition of behaviour of automata has found effective application in technical diagnosing of elements, aggregates, units and other technical objects, supposing the task by obviously presented discrete mathematical structures: by tables, matrixes, graphs, by logic equations, etc. In these cases of model of objects of diagnosing are set, as a rule, obviously and precisely, diagnostics tools are defined completely, and solved questions are reduced to check of operability and malfunction localisation on a site or functions. Technical diagnosing of complex systems essentially differs. Ineradicable incompleteness for complex systems initial and actually received by control and diagnostic experiments information does actual problems of regularization of information . In paper it is investigated regularization of partially set laws of functioning of automata from classes (n, m, l) – automata, where n – number of statuses of the automaton, m and l – numbers of input and output signals of the automata for classes (4,2,2)-automata, (8,2,2)-automata, (16,2,2)-automata and classes of automata, which laws of functioning are presented by partially set sequences of the second co-ordinates of points of geometrical images.
Keywords: discrete determined automaton, geometrical image of laws of functioning of automata, regularization of partially set automata, method of interpolation of Newton, Lagrange method of interpolation
Кибкало М.А. Сложность полиномов Жегалкина и автоматная сложность булевых функций

Определение сложности представления языков различными структурами — одна из традиционных задач теории автоматов. В случае представимости конечными автоматами под сложностью языка понимается число состояний в представляющем его приведенном автомате. В работе рассматривается сложность представления булевых функций конечными автоматами и устанавливаются точные значения и асимптотические оценки функции Шеннона для замкнутых классов булевых функций, входящих в решетку Поста.
Ключевые слова: булевы функции, конечные автоматы, сложность, классы Поста.

Kibkalo M.A. Complexity of OBDD and automata complexity of Boolean functions

OBDD and polynomials for Boolean functions was explored.
Keywords: Boolean functions, finite automata, complexity
Курганский А.Н. Внутреннее и внешнее наблюдение коллектива автоматов с одним состоянием

В работе коллектив взаимодействующих в дискретной однородной среде автоматов с одним состоянием рассматривается как цельный автоматоподобный вычислительный динамический объект. Для таких распределённых в среде вычислительных объектов предлагается подход к определению понятия состояния.
Ключевые слова: коллектив атоматов, клеточные автоматы, конечные автоматы, специальная теория относительности

Kurganskiy A.N. Vnutrennee i vneshnee nablyudeniye kollektiva avtomatov s odnim sostoyaniyem

In this work a collective of interacting stateless automata in a discrete geometric environment is considered as an integral automata-like computational dynamic object. For such distributed on the environment object different approaches to definition of the measure of state transition are possible. We propose an approach for defining what a state is. The measure of state transition of collective we name the proper time of collective.
Keywords: сollective of automata, cellular automata, finite automata, special relativity theory, discrete models of physical processes
Кучеренко И.В. О минимизации монофункциональных классов бинарных клеточных автоматов с неразрешимым свойством обратимости

В работе продолжается исследование вопросов алгоритмического распознавания свойства обратимости для клеточных автоматов. Построен класс двухмерных бинарных клеточных автоматов с фиксированной локальной функцией переходов, в котором задача распознавания свойства обратимости является алгоритмически не разрешимой. Получена оценка для числа существенных переменных локальной функции переходов в данном классе.
Ключевые слова: Клеточные автоматы, обратимые клеточные автоматы

Kucherenko I.V. On the minimization of mono-functional binary cellular automaton classes with undecidable reversibility

The article is focused on study of algorithmic decidability of reversibility of cellular automaton. Class of two-dimensional binary cellular automaton with fixed transition function and with undecidable reversibility was constructed. Estimate of number of local transition function variables was obtained for this class.
Keywords: cellular automaton, reversible cellular automaton
Летуновский А.А. О выразимости суперпозициями групповых автоматов Медведева

Рассматривается задача выразимости конечного группового автомата Медведева M суперпозициями систем вида F∪R, где F состоит из всех булевых функций и задержки, а R – произвольная система автоматов
Ключевые слова: автомат, выразимость, алгоритм, разрешимость

Letunovskiy, A.A. On the problem of finite group Medvedev automaton expressiblity

The article is about problem of finite group Medvedev automaton expressiblity by systems of type F∪R. F is all boolean functions and R is arbitrary automata set.
Keywords: automaton, expressibility, algorithm, solvability
Мастихина А.А. Частичное угадывание сверхсобытий, образованных детерминированными контекстно-свободными языками

Рассматривается сверхитерация такого контекстно-свободного языка L, что L* является детерминированным контекстно-свободным языком. Сверхслово из этого множества подается на вход некоторой машины, реализующей детерминированную функцию. Машина угадывает t-ый символ входной последовательности, если этот символ совпадает с (t-1)-ым выходным символом. Множество частично угадывается, если при подаче любого его сверхслова на вход машины некоторая доля символов угадывается машиной. Получен критерий, для какого L его сверхитерация может быть частично угадана.
Ключевые слова: частичное угадывание, детерминированные контекстно-свободные языки, автоматы с магазинной памятью

Mastikhina A.A. Partial prediction of deterministic context-free languages’ infinite iteration

The article concerns infinite iteration of such context-free language L that L* is deterministic context-free language. Sequence of words of L is input of some deterministic machine. Machine predicts t-th symbol of the sequence if it is equal to its (t-1)-th output symbol. Set of sequences is partially predicted if in any sequence some percentage is predicted by that machine. A criterion is obtained defining what L can be partially predicted
Keywords: partial prediction, deterministic context-free languages, pushdown automata
Пархоменко Д.В. Вторая автоматная функция и с нею связанные классы регулярных языков.

В статье представлены некоторые свойства языков, появляющихся на выходе детерминированных автоматов. Изучены свойства множеств с кратностями, возникающих на выходе детерминированных автоматов. Также предложен метод построения детерминированного «аналога» вероятностного автомата.
Ключевые слова: мультимножество, конечный автомат, вероятностный источник, вторая автоматная функция

Parkhomenko D.V. Second automaton function and related classes of regular languages.

Some properties of languages, which are appeared on the state machine output are described here. Author studied properties of multisets appeared as an output of finite automata. Also author suggests "deterministic analogue" of probabilistic machine.
Keywords: superset, fsm, finite state machine, finite automaton, probabilistic machine, second automaton function
Твердохлебов В.А. Геометрические модели и методы распознавания автоматов

Впервые предложено и разработано представление символьных автоматных отображений числовыми структурами в форме выделенных точек на аналитически заданных геометрических кривых линиях. Найдены правила преобразования множества входных последовательностей в вполне линейно упорядоченное множество и варианты размещения такого множества на оси абсцисс. Показано, что при произвольных линейном порядке на множестве выходных сигналов и размещении этого множества на оси ординат различным автоматным отображениям соответствуют различные геометрические образы. Разработаны методы построения геометрических образов на геометрических кривых для автоматных отображений. Разработан метод распознавания автоматов на основе решения равенств и неравенств уравнений, определяющих геометрические кривые с точками, имеющими автоматную интерпретацию.
Ключевые слова: автомат, автоматное отображение, геометрическая кривая, отображение, распознавание автоматов, числовой график автоматного отображения.

Tverdokhlebov V.A. Geometrical models and methods of recognition of automata

For the first time it is offered and developed representation of symbolical automata mappings by numerical structures in the form of the allocated points on analytically set geometrical curves. Rules of transformation of set of inputr sequences in the quite linearly ordered set and variants of placing of such set on an axis of abscisses are found. It is shown, that at any a linear order on set of output signals and placing of this set on an axis of ordinates to various automata mappings correspond various geometrical images. On geometrical curves methods of construction of geometrical images are developed for automata mappings. The method of recognition of automata on the basis of the decision of equalities and inequalities of the equations, defining geometrical curves with points, having automata interpretation is developed.
Keywords: automaton, automaton mapping, geometrical curve, mapping, recognition of automata, numerical graph of automata mapping
Титова Е.Е. Сложность конструирования изображений клеточными автоматами

В работе рассматривается задача конструирования изображений клеточными автоматами на прямоугольном экране. Построена модель устройства, управляющего экраном, получены оценки сложности алгоритмов конструирования изображений.
Ключевые слова: клеточный автомат, генератор, универсальный экран, конструирование изображений, оценка времени конструирования изображения, оценка сложности алгоритма конструирования изображения, перестановка, задержка, разреживатель.

Titova E.E. Complexity of image construction with cellular automata

The work deals with the problem of image construction with the cellular automata on a rectangular screen. Model of the device which controls the screen was developed, evaluation of image construction algorithms were obtained.
Keywords: cellular automaton, generator, universal screen, image construction, time estimation of image construction, estimation of image construction algorithm, commutation, delay, rarefying device
Тяпаев Л.Б., Василенко Д.В. Дискретные динамические системы, определяемые геометрическими образами автоматов

Объектом исследования является дискретная динамическая система. Пространство состояний динамической системы – конечное множество геометрических образов конечных автоматов. Геометрические образы автоматов суть множества точек плоскости с рациональными координатами, прообразами которых являются множества входных слов автомата и его реакций. Фазовое пространство динамической системы формируется посредством ортогональных и аффинных преобразований пространства состояний. Определены коэффициенты аффинных преобразований для динамических систем, определяемых геометрическими образами автоматов; определены произведения динамических систем и их свойства: характеризация принадлежности состояния динамической системы циклу-аттрактору, характеризация точек ветвления, характризация принадлежности состояний динамической системы одной компоненте связности; описана геометрическая структура функционального пространства для динамических систем типа «аттрактор-притягиваемая цепь», определены количественные
Ключевые слова: Конечные автоматы, геометрические образы автоматов, аффинные классы, функциональные графы, динамические системы

Tyapaev L.B., Vasilenko D.V. Discrete dynamical systems over geometrical images of automata

We study the geometrical structure of space of dynamical systems over geometrical images of automata
Keywords: finite automata, geometrical images of automata, dynamical systems
Часовских А.А. О полноте в классе конечных автоматов, вычисляющих некоторые аффинные функции

Рассматривается класс конечных автоматов, вычисляющих линейные функции над кольцом дискретного нормирования, состоящего из рациональных чисел, знаменатели которых не делятся на 2. Для этого класса получен алгоритм проверки полноты конечных систем по операциям композиции.
Ключевые слова: конечный автомат, операции композиции, проблема полноты, линейные функции, предполные классы, алгоритмическая разрешимость

Chasovskikh A.A. On completeness of finite automata class computing some affine functions

The finite automata class of linear functions over discrete valuation ring consisting of rational numbers denominators of which are not divided into 2 is considered. Algorithm to test finite sets of this class to be complete over composition operations is obtained.
Keywords: finite automata, function composition, completeness problem, linear functions, precomplete classes, algorithmic solvability.
Чернова Ю.Г. О характеризации состояний автоматной модели лёгких в чистой среде

В тезисах предложена автоматная модель процесса самоочищения легких и продолжается изучение свойств её диаграммы Мура. Выделен особый класс состояний этой диаграммы, а именно те состояния, которые имеют наибольшее число предшественников в чистой среде. В работе представлено критериальное описание таких состояний, их количество, а также найдено число прямых предшественников каждого состояния конденсации
Ключевые слова: автомат, диаграмма Мура, лёгкие, процесс самоочищения, состояние конденсации

Chernova Ju. G. On states of a lung automaton model in a clean environment

In the theses an automaton model of lungs clearance process is offered and the exploration of properties of its Moore diagram continues. The special class of states of this diagram, namely the states which have the largest number of predecessors in clean environment are allocated. In the article there is criterion description of such states, their number are given, as well as the number of direct predecessors of each state of condensation is found
Keywords: automaton, Moore diagram, lungs, the process of clearance, state of condensation
Скобелев В.Г. О некоторых типах автоматов над конечными полями

Для автоматов над конечным кольцом решены задачи идентификации (параметрической и начального состояния) и анализа множеств неподвижных точек.
Ключевые слова: конечные кольца, автоматы, идентификация, неподвижные точки

Skobelev V.G. On some types of automata over finite ring

For automata over any finite ring there are resolved problems of identification (parametric and of initial state) and of fixed points’ analysis.
Keywords: finite rings, automata, identification, fixed points

Часть 3. Секция "Защита информации"

Александров Д.Е. Многопоточные сервера, использующие обработчики событий

В работе исследованы основные архитектуры TCP-серверов, реализуемых на SMP-системах. Были проанализированы основные параметры архитектурных решений, характеризующие производительность серверов. В результате разработана серверная архитектура, превосходящая по характеристикам существующие архитектуры.
Ключевые слова: информационная безопасность, параллельные вычисления, TCP-сервера, симметричные мультипроцессорные системы, SMP-системы

Aleksandrov D.E. Multithreaded servers using event handlers

This paper presents some results of TCP-servers research. Major server's features have been chosen to analyze and compare performance of different architectures for SMP-based systems. The result is the server with new server architecture, that unites benefits of the existing ones.
Keywords: information security, parallel computing, TCP-servers, symmetric multiprocessing systems, SMP-systems
Болотов А.А., Галатенко А.В., Гринчук М.И., Золотых А.А., Иванович Л. Методы оптимизации глубины реализации хэш-функций

В работе рассматриваются хэш-функции SHA-2, SHA-1 и MD5 и предлагается ряд методов, позволяющих построить схемные реализации с малой глубиной (и, следовательно, с высокой пропускной способностью). В результате глубина раунда функции SHA-2 понижена до 16 для 512-битных блоков и до 17 для 1024-битных блоков; глубина раунда SHA-1 понижена до 10; глубина раунда MD5 понижена до 20. Также предлагается ряд методов, позволяющих понизить сложность реализации.
Ключевые слова: оптимизация глубины схем, хэш-функции

Bolotov A.A., Galatenko A.V., Grinchuk M.I., Zolotykh A.A., Ivanovic L. Methods for optimization of hash function implementation depth

We consider hash functions SHA-2, SHA-1 and MD5 and propose a number of methods that allow to construct low-depth (and hence high throughput) circuits implementing these functions. As the result, SHA-2 round AND-OR depth is reduced to 16 for 512-bit block size and 17 for 1024-bit block size, SHA-1 round depth is reduced to 10, MD5 round depth is reduced to 20. We also propose a number of techniques that allow to reduce circuit area.
Keywords: circuit depth optimization, hash functions
Галатенко А.В. О восстановлении параметров ε-безопасности

В работе рассматривается автоматная система, часть состояний которой объявляется безопасной. Исследуется сложность восстановления разбиения множества состояний для безопасных и ε-безопасных языков, введенных в работе "Автоматные модели защищенных компьютерных систем".
Ключевые слова: конечные автоматы, безопасность системы, конечные эксперименты

Galatenko A.V. On reconstruction of parameters of ε-security

We consider an automata system; a subset of its states is considered secure. We investigate the possibility to reconstruct secure and ε-secure languages introduced in the atricle "Automata models of secure computer systems".
Keywords: finite automata, system security, finite experiments
Галатенко В.А., Костюхин К.А., Шмырев Н.В. К вопросу построения формальных моделей сбоеустойчивых приложений реального времени

В статье представлен формализм, позволяющий описать объекты реального времени и их взаимодействие в рамках системы реального времени.
Ключевые слова: системы реального времени, отладка, контролируемое выполнение

Galatenko V.A., Kostyukhin K.A., Shmyrev N.V. On construction of formal models for fault-tolerant real-time applications

The paper presents a formal description of real time objects and their interactions in real time system.
Keywords: real time systems, debugging, controlled execution
Годнева А.В. Исследование групповых свойств умножения с параметром

В работе исследуются групповые свойства операции умножения с параметром, используемой в стандарте электронной подписи республики Узбекистан.
Ключевые слова: мультипликативная группа, криптография, электронная подпись

Godneva A.V. Studying group properties of multipliction with a parameter

The paper is devoted to group properties of multipliction with a parameter, an operation used in digital signature standard of Uzbekistan.
Keywords: multiplicative group, cryptography, electronic signature
Кучеренко Н.С. Математическое ожидание средней длины кодов Хафмана

В работе изучается средняя длина кода Хафмана как случайная величина, зависящая от случайного набора вероятностей кодируемого алфавита. Получена асимптотика математического ожидания средней длины при увеличении мощности алфавита.
Ключевые слова: код Хафмана

Kucherenko N.S. Mathematical expectation of the average length of the Huffman codes

The average length of the Huffman code is studied as a random variable depending on the random set of encoded character probabilities. The asymptotic of the mathematical expectation of the average length in the case of increasing cardinality of the alphabet is obtained.
Keywords: Huffman code
Мазуренко И.Л. Об одном подходе к линейной адаптивной цифровой обработке сигналов

Адаптивная линейная система с обратной связью представляет собой адаптивный алгоритм, получающий на вход разность результата обработки входного сигнала x некоторым устройством обработки информации и требуемого выходного сигнала d. Автором данной работы была предложена модификация приближенного метода быстрых аффинных проекций, основанного на применении Теплицевого приближения автокорреляционной матрицы R. Данная модификация алгоритма, практически не проигрывая в скорости оригинальному методу FAP, дает на тестовых данных значительно более высокую скорость сходимости и надежность работы алгоритма адаптации.
Ключевые слова: фильтр, линейная система, FAP, NLMS, LMS, метод аффинных проекций, метод быстрых аффинных проекций

Mazurenko, I.L. One approach to adaptive linear digital signals processing

Author suggested a modified algorithm of fast affine projections that overperfoms the known analogs in terms of complexity / performance trade-off.
Keywords: filter, linear system, FAP, NLMS, LMS, affine projections, fast affine projections
Марков А.С., Патраков Н.В., Фадин А.А. Решение задачи оптимизации безопасной информационной системы

В статье рассмотрены подходы к оптимизации информационных систем с сохранением заданного уровня целостности, доступности и конфиденциальности обрабатываемой в них информации.
Ключевые слова: оптимизация моделей, информационная система, компонентный анализ, безопасность информационных систем

Markov A.S., Patrakov N.V., Fadin A.A. Resheniye zadachi optimizatsii bezopasnoy informatsionnoy sistemy

In the paper there is a description of existing approaches to optimization of information systems with the preservation of the established integrity, avaliability and confidentiality level of the processed information.
Keywords: model optimization, information systems, component analysis, information systems security
Мозгалева О.А. Атаки на протокол Нидхема-Шредера. Модификация протокола Нидхема-Шредера и построения на его основе

Ключевые слова: нет

Mozgaleva O.A. Ataki na protokol Nidkhema-Shredera. Modifikatsiya protokola Nidkhema-Shredera i postroyeniya na ego osnove

Keywords: n/a
Пантелеев П.А. О поляризации источников Бернулли случайными линейными преобразованиями

Изучается недавно описанный феномен поляризации дискретных вероятностных источников, состоящий в том, что после применения некоторого специально подобранного преобразования к последовательности X₁,...,X_n двоичных случайных величин получается последовательность двоичных случайных величин Y₁,...,Y_n, которую можно условно разбить на две компоненты – Y_i₁,...,Y_{i_m} и Y_j₁,...,Y_{j_k}. Энтропия случайной компоненты близка к максимально возможной, а детерминированная компонента почти однозначно восстанавливается по случайной. В данной работе показывается, что эффект поляризации возникает для почти всех линейных преобразований.
Ключевые слова: полярный код, поляризация источника

Panteleev, P. A. On polarization of Bernoulli sources by random linear transformations

We study the recently discovered phenomenon of discrete random source polarization. It can be described as follows. There is a linear transformation over the field F₂ such that after applying it to any i.i.d. Bernoulli sequence X₁,...,X_n we obtain the binary random sequence Y₁,...,Y_n that can be divided into two parts: the random-like Y_i₁,...,Y_{i_m} and the deterministic-like Y_j₁,...,Y_{j_k}. The entropy of the random-like component is close to the entropy of X₁,...,X_n and the deterministic-like component can be obtained from the random-like one in an almost deterministic way. We show that for a random linear transformation over F₂ the polarization phenomenon occurs asymptotically almost surely for any i.i.d. Bernoulli source.
Keywords: polar code, source polarization
Чечулина К.А. Быстрое умножение матриц над полем из двух элементов.

Данная статья посвящена блочным алгоритмам умножения матриц над полем из двух элементов и параллельным вариантам алгоритма.
Ключевые слова: умножение матриц, блочный алгоритм, многопроцессорная система.

Chechulina K.A. Fast matrix multiplication over F2 field

This manual is devoted to multithread algorithms of matrix multiplication over F2.
Keywords: matrix multiplication, block algorithm, multithread, MPI.

Часть 4. Секция "Дискретная математика и математическая кибернетика"

Архипова А.Н. Об эффективности алгоритмов машинного обучения для некоторых классов булевых функций

Статья посвящена изучению алгоритмов машинного обучения в рамках РАС модели для различных классов булевых пороговых функций. В работе удалось получить прямое доказательство того факта, что функция Хастада не принадлежит классу вложенных функций. Также в работе приведен пример тройки пороговых функций, позволяющий показать, что попытка ввести расстояние в классе пороговых функций как минимальное значение L1 нормы по всем целочисленным линейным формам, представляющих две пороговые функции, обречена на неудачу.
Ключевые слова: Пороговые функции, вложенные функции, PAC модель

Arkhipova A.N. About effectiveness of machine learning algorithms for some classes of Boolean functions

The article is devoted to the studying machine learning algorithms within the PAC model for different classes of Boolean threshold functions. There is a direct proof of the fact that Hastad function does not belong to the class of nested functions. Also in the paper there is an example of the triple threshold functions, showing that the attempt to enter the distance in the class of threshold functions as the minimum value of the L1-norm over all integer linear forms representing two threshold functions is doomed to fail.
Keywords: Threshold functions, nested functions, PAC model
Боков Г.В. О конечной порожденности исчисления высказываний с произвольными операциями вывода

В работе получен критерий конечной порожденности пропозициональных исчислений
Ключевые слова: пропозициональные исчисления, схемные правила вывода, аксиомы.

Bokov G.V. O konechnoy porozhdennosti ischisleniya vyskazyvaniy s proizvolnymi operatsiyami vyvoda

In this paper we obtain a criterion for finite complete axiomatization of propositional calculus
Keywords: propositional calculus, rule schemes, axioms
Боков Г.В. Об алгоритмической неразрешимости проблемы выразимости пропозициональных исчислений.

В работе доказаны достаточные условия алгоритмической неразрешимости проблемы выразимости пропозициональных исчислений с одной схемной операцией вывода
Ключевые слова: пропозициональные исчисления, схемные правила вывода, проблема выразимости.

Bokov G.V. Ob algoritmicheskoy nerazreshimosti problemy vyrazimosti propozitsionalnykh ischisleniy.

In this paper we proof a sufficient conditions for algorithmic undecidability of expressibility problem of propositional calculus with single rule scheme
Keywords: propositional calculus, rule schemes, expressibility problem.
Гасанов Э.Э., Дин А.А. Построение синхронизирующих деревьев

В работе исследуется задача синхронизации сигнала в электронных схемах. Показано, что существуют конфигурации точек с минимальным расстоянием между точками, равным 3, для которых нельзя построить синхронизирующее дерево. С другой стороны, если минимальное расстояние между точками конфигурации не менее 4, то для этой конфигурации существует синхронизирующее дерево.
Ключевые слова: синхронизация сигнала, синхронизирующее дерево

Gasanov E.E., Din A.A. Clock tree synthesis

In the paper we study the problem of clock tree synthesis for integrated circuit design. It is shown that there are configurations of points with a minimum distance between the points of 3, which is impossible to build a synchronization tree. On the other hand, if the minimum distance between points of the configuration are not less than 4, then there exists a synchronization tree for this configuration.
Keywords: synchronization of signal; synchronizing tree
Грунский И.С., Максименко И.И. Представления элементов частично-упорядоченных алгебраических систем фрагментами

Ключевые слова: нет

Grunskiy I.S., Maksimenko I.I. Predstavleniya elementov chastichno-uporyadochennykh algebraicheskikh sistem fragmentami

Keywords: n/a
Жук Д.Н. Решетка замкнутых классов самодвойственных функций трехзначной логики

В работе описывается решетка замкнутых классов трех-значной логики, которые вкладываются в предполный класс самодвойственных функций. Также в работе описаны различные свойства этой решетки: выделены все конечно-порожденные и предикато-описуемые классы; найдены мощности надрешеток и подрешеток для всех классов.
Ключевые слова: решетка, замкнутый класс, клон операций, самодвойственная функция, предполный класс

Zhuk D.N. Lattice of closed classes of self-dual functions in three-valued logic

The lattice of all clones of self-dual functions in three-valued logic is described in the paper. Using this description different properties of the lattice and of the clones were derived. Pairwise inclusion of the clones into each other was described, and all finitely generated clones were found. Also, for each clone the relation degree, the cardinality of the set of all clones containing this clone, and the cardinality of the set of all clones that are contained in this clone were determined.
Keywords: Lattice of clones, closed class, self-dual function, precomplete class, maximal clone
Иванов И.О. О некоторых аспектах теоремы Римана-Роха на конечных графах

Данная работа посвящена поиску эффективного алгоритма, находящего выигрышную стратегию в Chip-Firing Game, либо утверждающего, что её не существует. В результате получены алгоритмы для полных и полных двудольных графов.
Ключевые слова: теорема Римана-Роха, chip-firing game, dollar game (нет русскоязычных аналогов терминам)

Ivanov I.O. On some aspects of Riemann-Roch theorem for finite graphs

This paper is devoted to the search for an efficient algorithm finding a winning strategy in Chip-Firing Game, or claiming that it does not exist. As a result we get algorithms for complete and complete bipartite graphs.
Keywords: riemann-roch theorem, chip-firing game, dollar game
Икрамов А.А. О сложности тестирования логических устройств на некоторые типы неисправностей

В работе изучены сложности тестирования логических устройств на неисправности типа слипания, перепутывания, инверсии и их объединения. В некоторых случаях получены точные оценки, в некоторых определены верхние и нижние оценки. Также изучен вопрос сложности тестирования почти всех булевых функций на неисправности типа инверсии (1).
Ключевые слова: Тестирование логических устройств, сложность, неисправности типа инверсии, неисправности типа перепутывания, почти все булевы функции

Ikramov A.A. O slozhnosti testirovaniya logicheskikh ustroystv na nekotoryye tipy neispravnostey

Author studied complexity of testing logic devices on errors such as clumping, inversion, scrambling and their union. In some cases, precise values are obtained, in other upper and lower bounds. Also author examined the complexity of testing logic devices of almost all boolean functions on inversion errors type 1.
Keywords: testing logic devices, complexity, inversion errors, scrambling errors, almost all boolean functions
Магомедов А.М., Магомедов М.А. Декомпозиция графа по средней плотности

Исследованы условия декомпозиции графа по средней плотности. Получены необходимые и достаточные условия существования декомпозиции графа по средней плотности.
Ключевые слова: Граф, средняя плотность, оптимизация, расписание

Magomedov A.M., Magomedov M.A. Dekompozitsiya grafa po sredney plotnosti

Conditions for graph decomposition by average density have been studied.
Keywords: graph, average density, optimization, schedule
Носов М.В. О формулах числа классов эквивалентности и числе пороговых функций

В работе представлены некоторые формулы числа классов эквивалентности, которые использованы для вывода комбинаторного арифметического выражения, задающего число пороговых функций.
Ключевые слова: классы эквивалентности, пороговая функция.

Nosov M.V. About the formulae for the number of equivalence classes and threshold functions

The number of threshold functions is represented as a combinatorial-arithmetic expression.
Keywords: equivalence classes, threshold function.
Носов М.В. Интегральная формула числа пороговых функций

Число пороговых функций представлено в виде интеграла от некоторого выражения.
Ключевые слова: классы эквивалентности, пороговая функция.

Nosov M.V. Integralnaya formula chisla porogovykh funktsiy

The number of threshold functions is presented in the form of the integral of an expression.
Keywords: equivalence classes, threshold function.
Павлов М.В. О сложности распознавания дискретных образов плоских фигур

Ключевые слова: нет

Pavlov M.V. O slozhnosti raspoznavaniya diskretnykh obrazov ploskikh figur

Keywords: n/a
Папилин С.С., Пытьев Ю.П. Теоретико-возможностные модели матричных игр двух субъектов в двух вариантах теории возможностей

В докладе с позиций двух вариантов теории возможностей рассмотрены матричные игры двух субъектов. Найдены оптимальные стратегии игроков и цены игр, исследовано существование четких стратегий. Результаты сравниваются с качественными результатами в теории матричных игр.
Ключевые слова: Теория возможностей, матричные игры двух субъектов, стратегии игроков, цена игры

Papilin S.S., Pyt'ev Yu.P. Possibilistic models of two-player matrix games considering two variants of possibility theory

The report describes models of normal-form games in terms of two variants of the possibility theory. The formulas for the equilibrium strategies and the value of game are given, and the existence of unfuzzy strategies is examined. The results are compared with those in terms of the probability theory.
Keywords: possibility theory, normal-form game, equilibrium strategies, value of game
Петрова О.А. Слабозамкнутые классы линейных булевых функций

В данной статье рассматриваются пары (f, t), где f — булева функция, t — натуральное число или 0, называемое временной задержкой. На множестве таких пар определяется операция синхронной суперпозиции по аналогии с операцией суперпозиции для булевых функций. Далее рассматриваются первые проекции множетсв пар (f, t) и для них определяется понятие слабой замкнутости по аналогии с замкнутостью для булевых функций. В даннной статье описываются слабозамкнутые классы множеств, состоящих из линейных функций. В статье получено описание всех слабозамкнутых классов таких функций.
Ключевые слова: булевы функции, линейные булевы функции, временные задержки, синхронное замыкание, первые проекции, слабозамкнутые классы, отношение по включению

Petrova O.A. Weakly closed classes of linear Boolean functions

Article contains description of all weakly closed classes of linear Boolean functions
Keywords: Boolean functions, linear Boolean functions, time delay, synchronous closing, first projection, weakly closed classes, relations of inclusion
Петрова О.А. Слабозамкнутые классы самодвойственных булевых функций

В статье получено описание всех слабозамкнутых классов самодвойственных булевых функций
Ключевые слова: булевы функции, слабозамкнутые булевы функции, временные задержки, синхронное замыкание, первые проекции, слабозамкнутые классы, отношение по включению

Petrova O.A. Weakly closed classes of self-dual Boolean functions

Article contains description of all weakly closed classes of self-dual Boolean functions
Keywords: Boolean functions, self-dual Boolean functions, time delay, synchronous closing, first projection, weakly closed classes, relations of inclusion
Петюшко А.А. О частотных языках на биграммах

В статье рассматриваются формальные языки, заданные матрицей биграмм. Устанавливается связь различных характеристик этих языков с ориентированными графами и эйлеровыми циклами в них. Приводятся критерии непустоты, конечности и бесконечности языков. Устанавливаются условия регулярности этих языков.
Ключевые слова: матрица биграмм, биграммные языки, частотные языки, регулярность языков, эйлеровы циклы, ориентированные графы.

Petyushko A.A. About frequency languages over bigrams

The paper deals with formal languages defined by the bigram matrix. The connection between different characteristics of the proposed languages and directed graphs and its euler circuits is established. The criteria of non-emptyness, finitness and infinity of the languages are presented. Conditions of regularity of the proposed languages are established.
Keywords: bigram matrix, bigram languages, frequency languages, regular languages, euler circuits, directed graphs.
Подловченко Р.И., Захаров В.А. О двух методах распознавания эквивалентности в алгебраических моделях программ

Назначение данной статьи – обратить внимание на один из последних результатов в теории моделей последовательных программ. В ней даётся представление об алгебраических моделях программ, об основных проблемах их теории, условиях, в которых они рассматриваются, и концепциях, лежащих в основе двух практикуемых методов распознавания эквивалентности. Формулируются результаты, полученные этими методами и применимые в программировании.
Ключевые слова: схема программ, эквивалентные преобразования, проблема эквивалентности, разрешающий алгоритм

Podlovchenko R.I., Zakharov V.A. O dvukh metodakh raspoznavaniya ekvivalentnosti v algebraicheskikh modelyakh programm

Keywords: n/a
Подымов В.В. О проверке эквивалентности последовательных и рекурсивных программ на упорядоченных полугрупповых шкалах

В данной работе предложен метод построения эффективных алгоритмов распознавания эквивалентности рекурсивных, а в качестве частного случая и последовательных программ. Рассматривается класс семантик, определяемых произвольными конечнопорожденными полугруппами с неразложимой единицей, включающий и семантики, аппроксимирующие семантику реальных программ.
Ключевые слова: проверка эквивалентности, рекурсивные программы, последовательные программы, полугруппы

Podymov V.V. Equivalence-checking algorithms for recursive and sequentional programs on ordered semigroup scales

We propose a technique which allows us to construct equivalence-checking algorithms for recursive programs, and, as a particular case, for sequential programs. Considered program semantics is defined by means of arbitrary finitely generated partially-ordered monoid, including semantics which approximate real program semantics.
Keywords: equivalence checking, recursive programs, sequential programs, semigroups
Пряничникова Е.А. Алгебраическая характеризация языков, допустимых в отмеченных графах

В работе рассматриваются языки, допустимые в отмеченных графах: графах с отмеченными дугами, графах с отмеченными вершинами, графах, в которых отмечены и дуги, и вершины. Найдена алгебраическая характеризация таких языков, разработаны методы их анализа и синтеза. Исследованы основные свойства семейства алгебр языков, допустимых в рассматриваемых графах.
Ключевые слова: графы, языки, конечные автоматы, регулярные выражения

Prianychnykova Olena Algebraic characterization of languages representable in labeled graphs

In this work we consider languages representable in labeled graphs (graphs with labeled vertices, graphs with labeled edges, graphs where both vertices and edges are labeled). We propose algebraic characterization and methods of analysis and synthesis for these languages and study the family of algebras of languages representable in considered graphs and its properties.
Keywords: graphs, languages, finite automata, regular expressions
Родин А.А. Базисы в P-множествах

В работе рассматриваются предполные классы, содержащие все о.-д. функции, в каждом состоянии которых реализуется функция из некоторого замкнутого класса D алгебры-логики (P-множества). Рассматривается задача о существовании базиса в различных P-множествах.
Ключевые слова: автоматные отбражения, базис, полнота

Rodin A.A. Bazisy v P-mnozhestvakh

Let D be a closed class in k-valued logic. Denote by P(D) the set of deterministic finite functions having boolean function from D in every state (P-sets). It is shown in the article, that there exists basis for some P-sets.
Keywords: automata mappings, bаsis, completness
Селезнева С.Н. Быстрый алгоритм построения для k-значных функций полиномов по составному модулю k

Предлагается алгоритм (СФЭ), который по вектору значений функции f(x₁,... , x_n) ∈ P_k, где k = p₁ ⋅ ... ⋅ p_m, p₁, ..., p_m – различные простые числа, определяет, задается ли эта функция полиномом по модулю k, в случае положительного ответа строит один из ее полиномов и имеет битовую сложность O(N), где N = k^{n – длина вектора значений функции f.

Ключевые слова: функция k-значной логики, полином по модулю k, алгоритм, сложность алгоритма

Selezneva S.N. A fast algorithm of construction polynomials modulo a composite k for k-valued logic functions

We obtain an algorithm (in the model of circuits) that, by a given k-valued logic function truth-vector f (where k is an arbitrary prime number), checks whether f is represented by a polynomial modulo k, if so, constructs a polynomial representation for f, and has a O(N) bit time-complexity, where N is a length of truth-vector of f.

Keywords: k-valued logic function, polynomial modulo K, algorithm, complexity}
Стариков А.О. Порядок функции Шеннона для накопленного ветвления схем из функциональных элементов

В работе рассматривается задача синтеза схем из функциональных элементов с точки зрения специально заданной сложности, называемой накопленным ветвлением. Получены верхние и нижние оценки функции Шеннона такой сложности для схем над базисом, состоящим из конъюнкции, дизъюнкции, отрицания и тождественного элемента. Совокупность полученных оценок дает порядок функции Шеннона для накопленного ветвления, равный O(n).
Ключевые слова: схемы из функциональных элементов, задержка схемы, накопленное ветвление, функция Шеннона

Starikov A.O. Order of growth for Shannon function of accumulated branching for logical circuits

The paper describes the problem of reducing a certain complexity, which is called accumulated branching, in the synthesis of logical circuits. For the basis consisting of conjuction, disjunction, negation and identity operation, upper and lower estimates for Shannon function of such complexity were obtained. Combination of found estimates gives the order of growth for Shannon function of accumulated branching, which is O(n).
Keywords: circuits of functional elements, delay, accumulated branching, Shannon function
Чебурахин И.Ф. О минимизации сложности представления булевых функций из некоторых классов

Исследуется задача оптимальной реализации булевых функций из некоторых классов формулами и схемами из функциональных элементов (ФЭ). Предлагается конструктивный метод синтеза на основе функциональных уравнений, сопровождаемый получением заранее аналитических оценок различных показателей сложности (по числу подформул и глубине суперпозиционной формулы; по числу ФЭ и глубине схемы).
Ключевые слова: Булевы функции, декомпозиция, оптимизация, меры сложности, показатели качества, синтез формул и схем из функциональных элементов, функциональные и разностные уравнения

Cheburakhin I.F. About minimization of difficulties of the presentation boolean functions from some classes

The problem of optimal realization of Boolean functions from some classes is researched with formulas and schemes from functional elements (FE). The constructive method of the synthesis based on functional equations attended by ahead reception of analytical estimates of different factors of difficulties (on amount of subformulas and depth of superpositional formula; on amount of FE and depth of scheme) is offered.
Keywords: The Boolean functions, decomposition, optimization, measures of difficulties, factors of quality, synthesis formulas and schemes from functional elements, functional and differential equation.
Емеличев В.А., Карелкина О.В., Кузьмин К.Г. О пяти типах устойчивости многокритериальной комбинаторной миниминной задачи

Данная работа относится к качественному направлению исследований устойчивости в задачах многокритериальной дискретной оптимизации. В ней для миниминных задач с паретовским и лексикографическим принципами оптимальности получены критерии пяти известных типов устойчивости.
Ключевые слова: Комбинаторная задача, многокритериальность, миниминные критерии, устойчивость

Emelichev V.A., Karelkina O.V., Kuzmin K.G. On five types of stability of multicriteria combinatorial minimin problem

In this work, we address the issue of qualitative characteristics of stability of discrete multicriteria optimization problems. Analysis of the five most known stability types has been carried out for two multicriteria minimin combinatorial problems: with Pareto and lexicographic principles of optimality. As a result necessary and at the same time sufficient conditions for each stability type are obtained as well as interrelation between these types are revealed.
Keywords: combinatorial problem, multicriteriality, MINMIN-criteria, stability
Скобелев В.В. О кривых второго порядка над конечными кольцами

Для кривых 2-го порядка над конечным кольцом исследована структура множества точек и построены канонические формы
Ключевые слова: конечные кольца, кривые 2-го порядка, канонические формы

Skobelev V.V. On the 2D order curves over finite ring

For 2-d order curves over a finite ring the structure of sets of points is investigated and canonical forms are presented.
Keywords: finite rings, 2-d order curves, canonical forms

Часть 5. Секция "Информатика и прикладные исследования"

Аксенова Е.А., Соколов А.В. Оптимальный метод перераспределения общей памяти для двухприоритетной очереди, представленной в виде двух последовательных циклических FIFO-очередей

В работе предложена математическая модель в виде случайного блуждания по целочисленной решетке в прямоугольной области на плоскости для представления двух-приоритетной очереди в виде 2 последовательных FIFO-очередей. На основе этой модели предложен алгоритм, который позволяет для заданных вероятностей выполнения основных операций с приоритетной очередью находить оптимальный способ перераспределения памяти после переполнения одной из FIFO-очередей. В качестве критерия оптимальности рассмотрено максимальное среднее время до переполнения памяти.
Ключевые слова: приоритетная очередь, FIFO-очередь, случайные блуждания, цепи Маркова

Aksenova E.A., Soklov A.V. The optimal method of redistributing shared memory for the two-priority queue represented in the form of two consecutive cyclic FIFO-queues

This paper presents a mathematical model in the form of a random walk on the integer lattice in a rectangular area for representation of the two-priority queue in the form of two consecutive FIFO-queues. Based on this model, an algorithm, which allows for a given probability of the basic operations of a priority queue to find the optimal way of redistributing memory after a FIFO-queue overflow, was proposed. The criteria of optimality – maximization of the average work time until memory overflow.
Keywords: priority queue, FIFO-queue, random walks, Markov chains
Андреев А.В., Пытьев Ю.П. Построение и анализ детерминированных методов прогнозирования

Рассматриваются математические методы прогнозирования на примере прогноза динамики курсов акций. Проводится сравнение использующихся методов. Делается попытка восстановить вероятностную и возможностную модель данных.
Ключевые слова: методы прогнозирования, анализ временных рядов, вероятностная модель, возможностная модель

Andreev A.V., Pytyev Y.P. Deterministic methods of forecasting: construction and analysis

Mathematical methods of forecasting are discussed on the example of asset prices forecasting. We compared the methods and made an attempt to restore probabilistic and possibilistic data models.
Keywords: forecasting methods, stichastic model
Величенко В.В. Конфликты между методами математики и механики и техногенные катастрофы

Рассматриваются технические и теоретические проблемы техногенных катастроф. Детально анализируются конфликты между методами математики и механики, приводящие при их формально правильном использовании к ошибочным выводам. Приводятся примеры катастрофических ошибок в технических расчетах в результате использования формально правильных методов математики и механики.
Ключевые слова: математика, механика, конфликты, ошибки, катастрофы

Velichenko V.V. Konflikty mezhdu metodami matematiki i mekhaniki i tekhnogennyye katastrofy

Mistakes of correct common use of mathematics and mechanics methods are considered.
Keywords: mathematics, mechanics, conflicts, mistakes, catastrophes
Вьюкова Н.И., Галатенко В.А., Самборский С.В. ЦЛП-формулировка для совмещенной задачи выбора и планирования инструкций в генераторе кода

В статье представлен метод генерации кода, основанный на совместном описании задач выбора и планирования команд в виде задачи целочисленного линейного программирования.
Ключевые слова: оптимизация кода, выбор команд, планирование команд, целочисленное линейное программирование

Vyukova N.I., Galatenko V.A., Samborskiy S.V. Integer linear programming formulation of the joint problem of code selection and scheduling for code generation

The paper presents a code generation method based on joint description of code selection and code scheduling tasks as an integer linear programming task.
Keywords: code optimization, instruction selection, instruction scheduling, integer linear programming
Григорьева А.М., Пытьев Ю.П. Сверхразрешение и робастность динамических матриц сенсоров

Такая система регистрации позволяет получать разрешение существенно выше, чем система регистрации, в которой сетчатка неподвижна.
Ключевые слова: математическое моделирование системы регистрации изображений, подвижная матрица сенсоров, сетчатка, сверхразрешение

Grigoreva A.M., Pytev Yu.P. Super resolution and robustness of dynamic sensors matrices

An image registration system using the proposed model allows for obtaining significantly higher resolution compared to a system with fixed retina.
Keywords: image registration, mobile sensor matrix, mathematical modeling, resolution enhancement, superresolution, retina
Григорьева Н.С. Задача минимизации числа параллельных процессоров для системы заданий с ограничениями предшествования

Рассматривается задача составления расписания выполнения множества частично упорядоченных заданий на параллельных идентичных процессорах. При заданном общем времени выполнения заданий требуется минимизировать количество процессоров. Прерывания выполнения заданий не допускаются. Для решения задачи предлагается алгоритм ветвей и границ в сочетании с бинарным поиском. Сформулированы и обоснованы правила сокращения перебора. Проведен вычислительный эксперимент.
Ключевые слова: многопроцессорное расписание, частично упорядоченные задания, метод ветвей и границ

Grigoreva N.S. Scheduling precedence-constrained tasks to minimize the number of parallel processors

We consider the NP-hard problem of scheduling precedence-constrained tasks for parallel processors. Makespan of schedule is fixed and we need to minimize the number of parallel processors. The goal of this article is to describe the branch and bound algorithm for the problem of scheduling a given length for the minimum number of processors. Branch and bound method allows to obtain an exact solution, or, when the time of the algorithm is restricted, a good approximation of the solution. New rules for vertex selection, branching and elimination are used in B&B algorithm. A computational experiment on randomly generated problems test the effectiveness of the proposed approaches.
Keywords: scheduling, precedence constrains, parallel processors, branch-and-bound method
Жизневский А.Н. Экспериментальное исследование метода активных контуров

Проведено экспериментальное исследование метода активных контуров применительно к сегментации изображний. Выявлены зависимость результата сегментации от выбора начального приближения и параметров алгоритма.
Ключевые слова: сегментация изображений, метод активных контуров

Zhiznevskiy A.N. Experimental research of the active contours method

The authors conducted an experimental research of the active contours method in relation to image segmentation. The research revealed a correlation between segmentation results and the choice of the initial approximation and algorithm parameters.
Keywords: image segmentation, active contours
Лемтюжникова Д.В., Щербина О.А. Локальный элиминационный алгоритм и параллельные вычисления

Алгоритмы декомпозиции являются методами решения NP-трудных задач дискретной оптимизации (ДО). Как правило, такие ДО, возникающие на практике, имеют специальную структуру, так как матрицы ограничений для крупномасштабных задач содержат много нулевых элементов (разреженные матрицы). Одним из перспективных методов, использующих разреженность, представляется локальной элиминационный алгоритм (ЛЭА) – алгоритм структурной декомпозиции на основе графа, который позволяет найти решение поэтапно таким образом, что каждый последующих этапов использует результаты предыдущих этапов. В то же время ЛЭА сильно зависит от порядка элиминации, который фактически является стадиями решения. В этой статье сравниваются нескольких эвристик для получения лучшего порядка элиминации и показывается, как связаны структура графа, порядок элиминации и время решения.
Ключевые слова: дискретная оптимизация, локальный алгоритм, разреженные задачи, упорядочивание, вычислительный эксперимент

Lemtyuzhnikova D.V., Shcherbina O.A. Local elimination algorithm and parallel computing

The decomposition algorithms provide approaches to deal with NP-hardness in solving discrete optimization problems (DOPs). Usually, such DOPs from applications have a special structure, and the matrices of constraints for large-scale problems have a lot of zero elements (sparse matrices). One of the promising ways to exploit sparsity is local elimination algorithm (LEA), that is a graph-based structural decomposition algorithm, which allows to compute a solution in stages such that each of them uses results from previous stages. At the same time LEA heavily depends on elimination ordering which actually provides solving stages. This paper describes comparison of a several heuristics for obtaining a better elimination order and shows how is related graph structure, elimination ordering and solving time.
Keywords: discrete optimization, local algorithm, sparse problems, ordering, benchmarking
Обухов Ю.В., Королев М.С. О частотно-временных признаках многоканальных электроэнцефалограмм мозга при заболевании Паркинсона на ранней стадии

Важной проблемой является диагностика болезни Паркинсона (БП) на ранней стадии. Одним из методов диагностики является электроэнцефалография (ЭЭГ). ЭЭГ пациентов с диагнозом БП было принято анализировать с помощью Фурье преобразования. Понижение частоты доминирующего ритма на поздних стадиях заболевания было исследовано. Описан новый метод анализа вейвлет – спектрограмм многоканальных ЭЭГ мозга, ориентированный на поиск признаков заболевания Паркинсона на ранней стадии.
Ключевые слова: электроэнцефалограмма, частотно-временной анализ, признаки заболевания Паркинсона

Obukhov Yu.V., Korolev M.S. O chastotno-vremennykh priznakakh mnogokanalnykh elektroentsefalogramm mozga pri zabolevanii Parkinsona na ranney stadii

Keywords: n/a
Осокин В.В. Модель информационно-поискового сайта филиала МГУ

Рассматривается задача построения универсального информационно-поискового сайта филиала МГУ. Приводится анализ требований к размещению информации на сайте филиала, анализ целевой аудитории сайта и использования сайта целевой аудиторией. Предлагается модель сайта филиала в рамках подхода MVC, описываются ключевые модули сайта, их взаимодействие и основы их реализации. Приводятся методы машинного обучения, которые можно использовать для анализа запросов пользователей сайта и выявления интересов посетителей сайта.
Ключевые слова: веб-сайт, MVC, информационно-поисковая система, машинное обучение, анализ поисковых запросов

Osokin V.V. Model of information retrieval site for branch of Moscow state University

This paper considers the problem of constructing a universal search engine, based on which you can implement web-site of any division of MSU.
Keywords: information retrieval system, website
Перевертень В.А. Модель гипертекстовой организации информации в информационных системах для исторических исследований

Предлагается авторская модель гипертекстовой организации информации в информационных системах для исторических исследований (HT-модель). HT-модель основывается на гипотетическом представлении о познавательно-информационной деятельности историка, которое заключается в том, что он накапливает самые разнородные фрагменты информации, а затем, исходя из некоторых своих соображений, объединяет их и связывает. В основе HT-модели лежат понятия информационный объект (ИО), образ ИО, объект гипертекста (ОГТ), ассоциация и связь. Особенностью HT-модели является понятие ассоциаций и связывание ОГТ относительно ассоциаций, в которые они входят. Модель представлена содержательно и в формализованном виде.
Ключевые слова: информационные технологии, информационные системы, исторические исследования, информация, историко-исследовательская информация, гипертекст, модель гипертекста

Pereverten V.A. The model of hypertext organizing information in information systems for historical research

The author's model of hypertext organizing information in information systems for historical research (HT-model) is proposed. The HT-model is based on a hypothetical conception about cognitive information work of a historian. Information object (IO), IO-image, hypertext object (HO), association and link are the basic concepts of the HT-model. The model is presented in the intensional and formalized form.
Keywords: information technology, information systems, historical research, information, hypertext, hypertext model
Пытьев Ю.П. Математическое моделирование субъективных суждений модельера-исследователя о модели объекта исследования.

В научной, инженерной, технической и прочей творческой деятельности невозможно исключить использование неясной, неполной и недостоверной информации, ассоциированной с опытом, практикой и с полученными ранее знаниями. В статье рассмотрен метод математического моделирования подобной информации, выраженной в форме субъективных суждений, возможно – коллективных. Основой метода является конструкция неопределенного случайного элемента, заданного на произведении пространств: вероятностного (Ω,A,Pr(.x)), известного с точностью до значения параметра x∈X и моделирующего объект исследования, и пространства (X,P(X),Pl,Bel) с мерами правдоподобия Pl и доверия Bel, моделирующего субъективные суждения модельера-исследователя о возможных значениях x∈X. Показано, что такая модель позволяет оценить правдоподобие и доверие его суждений о любых свойствах объекта, обусловленных его моделью.
Ключевые слова: неполнота знания, неопределенность, вероятность, правдоподобие, возможность

Pyt'ev Yu. P. Modeling of subjective judgements made by a researcher/modeler about the model of the research object

In scientific, engineering, technical and other creative activities it is not possible to avoid the use of unclear, incomplete and partially incorrect information associated with past experience, practice and knowledge. In the article we consider a method of mathematical modeling of such information expressed as subjective reasoning, possible a group one. The essence of the method is the concept of uncertain random element defined on the product of spaces: the probability space (Ω,A,Pr(.x)), known up to the value of parameter x∈X and modeling the research object, and the space (X,P(X),Pl,Bel) with measures of plausibility Pl and belief Bel, modeling the subjective judgements of the researcher/modeler about possible values of x∈X. It is shown that such model allows to estimate the plausibility and belief of any researcher's judgements about any properties of the research object caused by its model.
Keywords: incompleteness of knowledge, uncertainity, probability, plausibility, possibility
Садовничий В.А., Ветров Д.П., Вишневский В.В., Галатенко А.В., Галатенко В.В., Зыкова Т.В., Коршунов А.А., Лебедев А.Е., Лукашенко Т.П., Подольский В.Е., Политов А.В. Математический метод определения каталитической активности ферментов в сложных биологических растворах

В работе приводится математическая постановка задачи об определении каталитической активности ферментов в растворе. Предлагается метод решения этой задачи, состоящий из трех этапов: интегральное преобразование, комплексно-аналитическое продолжение и разложение по ортогональной системе в пространстве почти периодических функций.
Ключевые слова: ферменты, каталитическая активность, интегральное преобразование, комплексно-аналитическое продолжение, почти периодические функции

Sadovnichiy V.A., Vetrov D.P., Vishnevskiy V.V., Galatenko A.V., Galatenko V.V., Zykova T.V., Korshunov A.A., Lebedev A.E., Lukashenko T.P., Podolskiy V.E., Politov A.V. Mathematical method for the problem of catalytic activity estimation of enzymes in biological solutions

We present a mathematical formulation for the problem of catalytic activity estimation of enzymes in biological solutions. We propose a method for solving the problem consisting of three stages: integral transform, complex analytic extension and orthogonal expansion in the space of almost periodic functions.
Keywords: enzymes, catalytic activity, integral transform, complex analytic extension, almost periodic functions
Садовничий В.А., Соколов М.Э., Бармин В.В., Буданов В.М., Галатенко А.В., Галатенко В.В., Коршунов А.А., Козорезов Ю.Ю., Подольский В.Е. Получение, обработка и воспроизведение медицинской тактильной информации

В работе описывается медицинский тактильный эндоскопический комплекс. Обсуждаются приложения этого комплекса, включая объективизацию тактильных данных, получение тактильной информации при проведении эндоскопических операций, телемедицину, обучение и автоматизированный анализ тактильных образов.
Ключевые слова: медицинский тактильный эндоскопический комплекс, тактильный механорецептор, тактильный дисплей, тактильный образ

Sadovnichiy V.A., Sokolov M.E., Barmin V.V., Budanov V.M., Galatenko A.V., Galatenko V.V., Korshunov A.A., Kozorezov Yu.Yu., Podolskiy V.E. Retrieval, processing and reproduction of medical tactile information

The paper is devoted to the medical tactile endoscopic complex. We discuss a number of applications of this complex including tactile data objectification, obtaining tactie data in endoscopic surgery, telemedicine, education and automated analysis of tactile images.
Keywords: medical tactile endoscopic complex, tactile mechanoreceptor, tactile display, tactile image
Садовничий В.А., Соколов М.Э., Ветров Д.П., Галатенко А.В., Галатенко В.В., Зыкова Т.В., Лебедев А.Е., Лукашенко Т.П., Подольский В.Е., Политов А.В. Математические методы автоматизации тактильной диагностики

В работе рассматривается задача автоматизации тактильной диагностики при использовании медицинского тактильного эндоскопического комплекса. Предлагается подход к решению этой задачи, включающий понижение размерности, предобработку банка данных и предсказание диагноза.
Ключевые слова: медицинский тактильный эндоскопический комплекс, автоматизированная диагностика, понижение размерности

Sadovnichiy V.A., Sokolov M.E., Vetrov D.P., Galatenko A.V., Galatenko V.V., Zykova T.V., Lebedev A.E., Lukashenko T.P., Podolskiy V.E., Politov A.V. Mathematical methods of tactile diagnostics automation

The paper considers the problem of automated tactile diagnostics for the medical tactile endoscopic complex. We propose an approach to the solution of this problem consisting of dimension reduction, databank preprocessing and diagnosis prediction.
Keywords: medical tactile endoscopic complex, automated diagnostics, dimension reduction
Свириденко А.В., Щербина О.А. Алгоритмы упорядочивания переменных в локальном элиминационном алгоритме

Целью данной статьи является анализ влияния алгоритмов упорядочивания переменных, оказываемое ими на время решения разреженной задачи дискретной оптимизации с помощью несериального динамического алгоритма.
Ключевые слова: дискретная оптимизация, локальный элиминационный алгоритм, несериальное динамическоe программирование, алгоритм минимальной степени, алгоритм рекурсивного разбиения, алгоритм поиска по максимальной степени, алгоритм минимального пополнения, алгоритм лексикографического поиска в вершину

Sviridenko A.V., Shcherbina O.A. Variables ordering algorithms in local elimination algorithm

The goal of this paper is impact analysis of variables ordering algorithms on the solving time of discrete optimization problem with help of non-serial dynamic programming algorithm
Keywords: discrete optimization, local elimination, non-serial dynamic programming, minimum degree algorithm, nested dissection heuristic, maximum cardinality search algorithm, minimum fill-in algorithm, lex-bfs algorithm
Севастьянов С.В., Черных И.Д. Достаточное условие эффективной разрешимости задачи Open shop в терминах суммарной нагрузки

Классическая в теории расписаний задача Open Shop является NP-трудной, когда число машин превышает 2. В работе подробно исследуется случай трех машин. Построена точная функция зависимости длины расписания от суммарной нагрузки в терминах стандартной нижней оценки, что уточняет раннее известный результат о локализации оптимумов этой задачи. Выявлены новые полиномиально разрешимые подслучаи в терминах суммарной нагрузки.
Ключевые слова: Open shop, суммарная нагрузка, стандартная нижняя оценка, локализация оптимумов

Sevastyanov S.V., Chernykh I.D. Efficiently solvable case of the Open Shop problem in terms of total workload

Open shop is a well-know classical scheduling model. Open shop problem is known to be NP-hard for the case of at least 3 machines. The three-machine case is thoroughly investigated. We obtained the tight function representing the relation between optumum and the total machine workload in terms of the standard lower bound. This improves previously known result on the optima localization for this problem. New polynomially-solvable cases are described.
Keywords: Open shop, total workload, standard lower bound, optima localization
Старостин Н.В., Сафонова Я.Ю. Параллельное разложение Холецкого разреженной матрицы

В статье рассматривается вопрос распараллеливания разложения Холецкого разреженной матрицы на системах с общей памятью. Предлагается подход, основанный на разбиении дерева исключения исходной матрицы. Ускорение достигается за счет параллельной обработки независимых поддеревьев. Рассматривается эффективная реализация, позволяющая достичь ускорения, чье значение равно двоичному логарифму от p, где p – количество независимых вычислителей.
Ключевые слова: параллельное разложение Холецкого, дерево исключения матрицы, решение разреженных симметричных систем, метод вложенных сечений

Starostin N.V., Safonova Ya.Yu. Parallel sparse Cholesky decomposition

In this paper we discuss a problem of sparse Cholesky decomposition using parallel computational systems with shared memory. We propose an effective approach based on decomposition of matrix elimination tree. We show that parallel processing of non-intersecting subtrees provides speed-up compared with binary logarithm of p, where p is a number of independent processors of parallel system.
Keywords: parallel Cholesky decomposition, matrix elimination tree, solving sparse linear systems, nested dissection algorithm
Фофанов В.Б., Жизневский А.Н. Формализация задачи поиска объектов на векторной сцене

Предлагается формализация и решение задачи поиска объектов на векторной сцене. Особенностью постановки задачи являются вид объектов (они являются "пятнами") и исходная информация о сцене (набор пространственно совмещенных изображений). В качестве модели сцены используется локально однородное векторное случайное поле. Поиск объектов предлагается организовать в три этапа. Вначале для каждого объекта определяется квадрат (зона интереса), содержащая объект и его окрестность. На втором этапе проводится сегментация каждой зоны интереса. Полученная в результате сегментации проекция объекта используется на третьем этапе для вычисления геометрических признаков и принятия окончательного решения о присутствии объекта. Доказаны теорема существования локально однородных полей, а также теоремы о сходимости решающих правил к байесовским на этапах поиска зон интереса и сегментации.
Ключевые слова: сцена, изображение, объект, признаки объектов, поиск объектов, зона интереса, сегментация, классификация

Fofanov V.B., Zhiznevskiy A.N. Formalizing the problem of searching for objects in a vector scene

The work suggests ways of formalizing and solving the problem of searching for objects in a vector scene. The peculiarities of the problem statement are the type of objects (they are “spots”) and the initial scene details (a set of spatially superimposed images). The scene model is a locally homogeneous random vector field. The authors suggest a three-stage approach to object search. Initially, a square (a zone of interest) is defined for each object. Each square contains an object and its locality. On the second stage, each interest zone is segmented. The resulting object projection is used on the third stage for identifying geometric features and making the final decision about the presence of an object. The work proves the theorem on the existence of locally homogeneous fields, as well as the theorem on the convergence of solving rules to Bayesian on the interest zone location and segmentation stages.
Keywords: scene, image, object, object features, objects search, zone of interest, segmentation, classification
Черемных Ю.Н. Математические модели экономических процессов

В работе приводится исторический обзор математических методов моделирования экономических процессов
Ключевые слова: математическая экономика, метод множителей Лагранжа, линейное программирование

Cheremnykh Yu.N. Matematicheskiye modeli ekonomicheskikh protsessov

The article contains a historical review of application of mathematical methods to represent theories and analyze problems in economics
Keywords: mathematical economics, linear programming
Черных И.Д., Кузеванов М.А. Достаточное условие разрешимости двухмашинной задачи open shop с маршрутизацией и разрешением прерываний

Задача open shop с маршрутизацией и разрешением прерываний обобщает классическую метрическую задачу комивояжера и задачу теории расписаний open shop с разрешением прерываний. Известно, что двухмашинная задача является полиномиально разрешимой для случая двухвершинной маршрутизации. Сложностной статус двухмашинной задачи с тремя вершинами на данный момент неизвестен. В работе рассматривается двухмашинная задача на произвольной транспортной сети. Описывается полиномиально разрешимый подкласс этой задачи в терминах неравномерного распределения нагрузки по вершинам.
Ключевые слова: Routing open shop, прерывания, перегруженная вершина, полиномиально разрешимый подслучай

Chernykh I.D., Kuzevanov M.A. Efficiently solvable case of the two-machine Routing Open Shop with preemptions allowed

Routing open shop problem with preemptions allowed if a generalization of the classical metric travelling salesman problem and one scheduling problem – preemptive open shop. This problem is polynomially solvable for the case of two machine on a link. The complexity status for the two-machine case on a triangle remains unknown yet. We investigate general two-machine case of the problem. We describe new polynomially solvable case in terms of unequal total loads of the nodes of the transportation network.
Keywords: Routing open shop, preemptions, overloaded node, polynomially solvable case.

Написать вебмастеру

Последние новости - в телеграм-канале кафедры МаТИС:

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

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