12.2016 - том 20 выпуск 4 (PDF)
Работа посвящена вопросу сложности восстановления частичного порядка на конечном множестве, если известно, что частичный порядок обладает какими-то наперед заданными свойствами. Рассматривается модель вычислений в которой под сложностью понимается количество сравнений, необходимое для восстановления частичного порядка. Исследуются классы частично упорядоченных множеств, для которых задача восстановления порядка решается меньше чем за квадратичное число сравнений относительно количества элементов в множестве.
Ключевые слова: частичный порядок, конечное множество, восстановление порядка, сортировка, сравнение.
В статье описывается применение фильтра Калмана для уменьшения погрешности оценки позиции объекта при детектировании и для экстраполяции позиции объекта на следующем кадре.
Ключевые слова: фильтр Калмана, обработка изображений, трекинг объектов.
Предложены методы решения задачи безусловной минимизации, в которых итерационный процесс перезапускается по определенному правилу через наперед заданное число шагов (рестарт). Приводятся результаты численного эксперимента по сравнению эффективности предложенных методов с методами без рестарта.
Ключевые слова: безусловная минимизация, рестарт, релаксация, модифицированный метод сопряженных градиентов, градиентный метод, метод Флетчера-Ривса.
В работе исследуется возможность вычисления малыми коллективами автоматов арифметических функций на целочисленной прямой. Будем говорить, что коллектив автоматов \[(W_1, W_2)\] находится в \[a\]-расстановке (\[a\geqslant 0\]), если автомат \[W_2\] находится на \[a\] делений правее автомата \[W_1\]. Будем говорить, что коллектив автоматов \[(W_1, W_2)\] вычисляет целочисленную функцию \[f(x)\], если для любого целого неотрицательного \[x\], стартуя из \[x\]-расстановки, коллектив останавливается в \[f(x)\]-расстановке. В зависимости от ограничений на подвижность автоматов коллектива определяются сильная вычислимость функций коллективом автоматов, слабая вычислимость и просто вычислимость. В работе полностью описан класс целочисленных функций, вычислимых коллективами из двух автоматов. Этот класс представляет собой композиции «периодических» функций и функций вида \[f(x)=x+c\]. Показано, что классы всех функций, вычислимых коллективами из двух автоматов, слабо вычислимых коллективами из двух автоматов и сильно вычислимых коллективами из двух автоматов - совпадают. Также показано, что класс функций, вычислимых коллективами из трех автоматов - значительно шире.
Ключевые слова: коллектив автоматов, лабиринт, вычислимость, целочисленные функции.
Предложены новые обобщенные варианты «\[r\]-быстрой» сходимости В. Штрассена для последовательности случайных величин. Установлены необходимые и достаточные условия «\[\Phi\]-быстрой» сходимости последовательности сумм случайных величин с отброшенными экстремальными членами.
Ключевые слова: случайные величины, сходимость, случайное блуждание, хвостовые вероятности, закон больших чисел, «\[r\]-быстро», «\[\Phi\]-быстро», порядковые статистики, скорость сходимости.
Построены отображения между автоматными моделями информационных систем, описанными в работах Московитца-Костича и Грушо-Шумицкой, сохраняющие свойства безопасности.
Ключевые слова: автоматные модели, скрытые каналы, модель невлияния, вероятностное невлияние.
Описывается методология построения моделей структур данных, цели, задачи и результаты разработки программного комплекса управления медицинскими данными исследования методов лечения \[\beta\]-талассемии. Цель разработки и внедрения оригинального программного комплекса управления медицинскими данными исследования методов лечения \[\beta\]-талассемии является накопление, хранение и аналитическая обработка клинических и лабораторно-диагностических данных пациентов с возможностью последующего применения к ним инструментов фармакоэкономического анализа. Основным результатом разработки и внедрения программного комплекса является формализация и автоматизация процессов проведения исследований в области методов лечения данного гематологического заболевания в научно-клинических учреждениях системы здравоохранения Российской Федерации.
Ключевые слова: медицинская информатика, информационные системы и технологии в здравоохранении, научно-клинические исследования, гематологические заболевания, методы лечения \[\beta\]-талассемии.
Данная работа посвящена семантическому анализу текста, составленному на естественном языке, и распознаванию именованных сущностей. Основной целью исследования было сравнение латентного размещения Дирихле и латентно-семантического анализа для выявления элементов внешности человека в тексте. В качестве сравнительной характеристики методов была выбрана полнота поиска информации.
Ключевые слова: распознавание именованных сущностей, ЛСА, ЛДА, разрешение кореференции, распознавание внешности человека.
В статье рассматривается задача управления доступом к объектам информационных систем управления наукометрической информацией. Представлена реляционная модель логического разграничения доступа к объектам таких систем, обладающая рядом важных в контексте поставленной задачи свойств, которыми не обладают другие модели логического разграничения доступа.
Ключевые слова: информационная безопасность, наукометрия, разграничение доступа, реляционная модель.
В работе предложен алгоритм локализации и распознавания объектов на изображениях, основанный на нейронных сетях с глубокими архитектурами. Предложенная в настоящей работе архитектура нейронной сети решает обе задачи локализации и распознавания за один проход вычислений. Это позволяет вывести все вычисления на графических процессорах и существенно ускорить локализацию и распознавание.
Ключевые слова: распознавание образов, локализация объектов, нейронные сети, глубокое обучение.
Сформулирована и экспериментально подтверждена гипотеза о характере зависимости суммарной длины контуров на полутоновом изображении от порога методы выделения контуров. На основе этой модели предложен оригинальный эвристический метод выбора порога, обеспечивающий высокое качество выделения контуров согласно множественным экспертным оценкам.
Ключевые слова: полутоновые изображения, выделение контуров, метод Кэнни, метод Собеля, L-кривая, оценка кривизны, адаптивный порог, устойчивость к шумам.
В работе рассматриваются матрицы самосравнения одномерного сигнала (в частности, речевого). Предлагается метод нелинейного растяжения этих симметричных матриц для нахождения оптимального расстояния между ними в смысле похожести сигналов.
Ключевые слова: одномерный сигнал, матрица самосравнения, нелинейное растяжение.
Соответствия Галуа для классов дискретных функций, порожденные отношением сохранения между функциями \[f\] на множестве \[A\] и множествами \[H\] функций \[f:Q\to A\] для произвольного множества \[Q\], есть удобный инструмент для изучения ряда абстрактных и прикладных задач. В работе на языке функциональных соответствий Галуа сформулирована одна из основных задач теории коллективного выбора и предложена удобная характеризация симметричных классов решающих правил без свойства Эрроу.
Ключевые слова: соответствие Галуа, замкнутый класс, клон, свойство Эрроу.
В статье описывается формализованное представление структуры медицинских данных в соответствии с задачами научно-клинического исследования в области трансплантации гемопоэтических стволовых клеток. На основе представления структуры медицинских данных разработан программный комплекс накопления и хранения клинических и лабораторно-диагностических данных пациентов с целью последующего проведения вычислительных экспериментов и анализа результатов применения данного метода лечения.
Ключевые слова: трансплантация гемопоэтических стволовых клеток, научно-клинические исследования, медицинские и лабораторные информационные системы, медицинская информатика.
В статье описывается атака на шифр ГОСТ 34.12-2015 с длиной блока 128 бит, реализуемая путем внесения ошибок в процесс зашифрования. Показано, что с помощью анализа внесенных ошибок при известных блоках замены можно вычислить значение ключа в среднем за \[2^{13}\] инъекций неисправностей, используя около 128 Кб открытого текста.
Ключевые слова: криптоанализ, ГОСТ 34.12-2015, атака внесением ошибки, атака на блочный шифр.
В статье описан разработанный научным коллективом программный комплекс, предназначенный для построения и анализа терминосистемы. Проект представляет собой экспертную систему, содержащую словарь-тезаурус (TSReader), систему идентификации и классификации терминов (TSBuilder), терминологическую базу данных. Автоматизированное создание терминосистемы достигается благодаря использованию эвристического алгоритма идентификации терминов и видоизмененного персептрона Розенблатта для классификации терминов.
Ключевые слова: интеллектуальный анализ текста, нейросетевое моделирование, моделирование терминосистемы, автоматизированная идентификация терминов, автоматизированная категоризация терминов.
Рассматривается задача о реализации булевых функций инициальными булевыми автоматами с константными состояниями и \[n\] входами, \[n \geqslant 1\]. Найдены все множества максимальной мощности, состоящие из булевых функций, которые могут быть реализованы одним автоматом такого типа с двумя или тремя состояниями при условии возможности произвольного порядка подачи наборов значений входных переменных на входы автомата.
Ключевые слова: булева функция, инициальный автомат, реализация булевых функций.
В данной статье рассматривается вопрос о построении математической модели шума светодиодных маркеров для повышения точности задачи захвата движений, которая базируется на принципах распознавания образов. Алгоритм создания математической модели основан на синтезировании искусственнного светодиодного маркера с добавлением гауссового шума. Для оценки прототипа математической модели был выбран метод минимизации функционала стандартного отклонения. Визуально результаты представлены в гистограммах.
Ключевые слова: распознавание образов, захват движений, математическая модель шума, синтезирование искусственного светодиода.
Представлены новые возможности использования построенной ранее в [6] обеспечивающей рост устойчивости рекурсивной конструкции платовидных булевых функций с шагом числа переменных 3 с пересекающимися носителями спектра порождающих функций, приведён новый пример начальных функций.
Ключевые слова: булевы функции, корреляционная иммунность, устойчивость, платовидность, рекурсивные конструкции.
В настоящей работе предложен протокол генерации общего ключа, использующий группу матриц над конечным полем. В качестве одного из этапов протокола используется атака линейным разложением, недавно предложенная В. А. Романьковым для компрометации протоколов, в которых платформа является линейной группой. Анализируется стойкость предложенной криптосистемы против различных известных атак.
Ключевые слова: группа матриц над конечным полем, некоммутативная криптография, криптография с открытым ключом, протокол генерации общего ключа, атака линейным разложением.
На основе системного подхода описаны математические методы исследования различных электрогидродинамических явлений. Обсуждаются три модели с минимальным набором «эффективных» переменных и задаваемых параметров и некоторые результаты, полученные в рамках каждой из них.
Ключевые слова: электрогидродинамика, электрическое поле, слабопроводящие среды, математические модели, объемный электрический заряд, электрохимические реакции, электризация.
В работе представлена математическая дискретная модель процесса самоочищения лёгких от различных веществ, как превнесённых туда извне, так и получающихся за счёт жизни и деятельности организма. Представлены функции Шеннона времени самоочищения лёгких как в здоровом случае, так и случае патологий двух типов.
Ключевые слова: лёгкие, процесс самоочищения, автоматы, функция Шеннона.
Для суперпозиции строится пример, не расширяющегося до предполного класса, множества автоматов.
Ключевые слова: автомат, суперпозиция, предполный класс.
Ранее автором было доказано, что автоматы с магазинной памятью сохраняют периодические последовательности, и была приведена экспоненциальная от характеристик автомата оценка сверху на максимальную длину периода. Для случая, когда алфавит магазина состоит из одного символа, автору удалось понизить общую оценку до квадратичной. В случае алфавита, состоящего хотя бы из двух символов, автором было доказано, что существенно понизить верхнюю оценку нельзя. В данной работе приводится улучшение предложенной ранее нижней оценки. Новое доказательство заметно проще предыдущей конструкции.
Ключевые слова: автомат с магазинной памятью, детерминированная функция, периодические последовательности.
В работе рассматриваются основные результаты, связанные с разложением графов в виде объединения деревьев, псевдодеревьев и деревьев-звезд. Приводятся собственные результаты о хроматическом числе этих графов.
Ключевые слова: древесность, хроматическое число.
Работа по теории абстрактных клонов. Исследуются бинарные предикаты на \[k\]-элементном множестве и операции над этими предикатами. Приведён список операций над бинарными предикатами, замыкание относительно которых для \[k \in \{2, 3\}\] эквивалентно замыканию относительно всех примитивных позитивных формул. При \[k \geqslant 4\] показано, что замыкание относительно указанных операций строго слабее замыкания относительно всех примитивных позитивных формул.
Ключевые слова: теория клонов, бинарные предикаты, бинарные отношения, операции на предикатах, примитивные позитивные формулы, оператор замыкания, \[k\]-значная логика.
Рассмотрен класс линейных 2-адических автоматов с операциями композиции. Получен алгоритм проверки полноты конечных подмножеств таких автоматов. Найдены все максимальные подклассы, число которых оказалось счетным.
Ключевые слова: конечный автомат, p-адическое число, линейный 2-адический автомат, операции композиции, обратная связь, проблема полноты, алгоритм проверки полноты, последовательный двоичный сумматор, задержка.
Актуальный выпуск от 09.2016 - том 20 выпуск 3 к юбилею академика В.Б. Кудрявцева (PDF)
Коды с малой плотностью проверок на четность (LDPC) были впервые предложены Р. Галлагером в [1], позднее они были переоткрыты Д. МакКеем и Р. Нилом ([2]). Они демонстрируют возможности по исправлению ошибок, близкие к пределу Шеннона. Кроме того они позволяют реализацию кодека с высокой степенью параллелизма, что означает возможность эффективной программной и аппаратной реализации. Поэтому LDPC коды используются во многих областях: жестких дисках, беспроводных коммуникациях и т. д. В данной работе предлагается эффективный алгоритм кодирования для случая проверочной матрицы определенного вида, обладающей неполным рангом. В работе [3] предложен другой эффективный алгоритм, основанный на китайской теореме об остатках.
Ключевые слова: кодирование, коды НППЧ, квазициклические коды, нормальная форма Смита.
В настоящей статье доказано, что не существует алгоритма, с помощью которого из конечной полной системы полиномиальных функций с целыми коэффициентами можно было бы выделить базис.
Ключевые слова: полином, алгоритм, неразрешимость, проблема полноты, базис, операции суперпозиций, функциональная система, 10-я проблема Гильберта.
Доклад посвящен заданию логических процессов средствами пропозициональных исчислений. Будет рассказано о том, как логические системы задаются исчислениями, условия существования такого задания, свойства решетки логических систем, порожденных исчислениями, условия разрешимости проблемы вывода для пропозициональных исчислений и сложность этого вывода.
Ключевые слова: пропозициональные исчисления, логические системы, проблемы вывода, сложность вывода.
Данная статья посвящена условному тестированию схемы Кардо для трех и четырех переменных. Установлено, что для схемы Кардо четырех переменных минимальный полный диагностический условный тест имеет длину 14, а для схемы Кардо трех переменных - 8.
Ключевые слова: схема Кардо, тест, тестирование, длина теста, условный диагностичеcкий тест.
В работе исследуются относительные влияния переменных булевой функции. Множество булевых функций разбивается на классы \[\tau-Inf\]-эквивалентности в зависимости от максимального относительного влияния переменных. Приводятся нижняя и верхняя оценки количества классов \[\tau-Inf\]-эквивалентности для пороговых функций. Они равны \[2^{n/2}\] и \[n2^{2n}\].
Ключевые слова: пороговые функции, влияние переменных булевой функции, относительное влияние переменных булевой функции, классы \[\tau-Inf\]-эквивалентности.
В работе рассматривается задача о накрытии семейства \[A\] натуральных чисел минимальным количеством арифметических прогрессий с запретом на накрытие элементов другого конечного семейства \[B\]. Более точно, нас интересует нахождение минимального количества \[f(A)\] элементов в семействе \[B\], которых достаточно, чтобы сделать накрытие семейства \[A\] наиболее сложным, то есть имеющим максимально возможное количество арифметических прогрессий. Приводятся соответствующие верхние и нижние оценки на \[f(A)\] в зависимости от мощности семейства \[A\].
Ключевые слова: арифметическая прогрессия, натуральный ряд, сложность накрытия.
Статья посвящена мощностной сложности плоских схем, реализующих функции из замкнутых классов. Плоскую схему можно представлять, как укладку схемы из функциональных элементов на целочисленную решётку на плоскости таким образом, что провода заменяются на клеточные элементы, реализующие тождественные функции. В качестве меры мощности схемы рассматривается средний и максимальный потенциал, равный среднему и, соответственно, максимальному количеству единиц на выходах элементов схемы. Будет сформулирована теорема о порядке функции Шеннона потенциала для класса монотонных функций и показано, как с учётом этого результата получаются оценки функции Шеннона для остальных замкнутых классов.
Ключевые слова:плоские схемы, клеточные схемы, активность схем, мощность схем, функция Шеннона, классы Поста, монотонные булевы функции.
Рассматривается система линейных полиномов с целыми коэффициентами. Предлагается схема эффективного вычисления этой системы. Схема вычислений позволяет устранить избыточность представления исходных данных, а также упростить вычисления устранением многократности вычислений одних и тех же значений при той же функциональности, что и без использования схемы. Приводится пример применения предлагаемой схемы вычислений.
Ключевые слова:линейный полином, сложность вычислений, классификация.
Пусть \[k > 2\], \[E_k = \{0, 1, \ldots, k-1\}\]. Обозначим через \[P_k\] множество всех конечноместных функций на \[E_k\]. Вследствие теоремы А. В. Кузнецова при любом \[k\] в \[P_k\] имеется конечное число предполных классов. Все они были описаны в 1965 г. И. Розенбергом в терминах сохранения некоторых предикатов.В данной работе доказан ряд утверждений о вложении некоторых пересечений предполных классов в некоторый (другой) предполный класс. Такие утверждения помогают построить для предполных классов так называемую решетку пересечений, являющуюся, в определенном смысле, \[«остовом»\] континуальной (при \[k > 2\]) решетки замкнутых классов в \[P_k\], в целях получения конечной классификации замкнутых классов. При \[k = 3\] решетка пересечений предполных в \[P_k\] классов построена автором ранее, тогда как при всех \[k > 3\] проблема пока остается открытой.
Ключевые слова: многозначная логика, предполные классы, замкнутые классы, решетка, решетка пересечений.
В статье представлены исследования задачи представления числа булевских решений линейного уравнения многих переменных с целыми коэффициентами, как функции от двоичного разложения этих коэффициентов.
Ключевые слова:уравнение в целых числах, двоичное разложение.
В работе предлагается метод синтеза неизбыточных схем из функциональных элементов в базисе Жегалкина, реализующих произвольные булевы функции без дополнительных входов и выходов и допускающих относительно произвольных константных неисправностей на входах и выходах элементов единичные проверяющие тесты, длина которых ограничена сверху константой 16.
Ключевые слова: схема из функциональных элементов, проверяющий тест, константная неисправность, функция Шеннона, легкотестируемая схема.
Одним из направлений исследования дискретных функций является исследование функциональных систем: множеств функций и множеств операторов, заданных над этими функциями. В частности, активно изучаются функциональные системы, в которых в отличие от классических над множеством \[k\]-значных функций, рассматриваются обобщения функций \[k\]-значной логики: частичные функции, мультифункции и гиперфункции. Гиперфункции представляют собой функции, заданные на конечном множестве \[A\] и принимающие в качестве своих значений все непустые подмножества множества \[A\] относительно оператора суперпозиции. Кроме оператора суперпозиции интерес представляют более сильные операторы замыкания, дающие нетривиальную классификацию функций. Например, для гиперфункций ранее получен критерий полноты для оператора разветвления по предикату равенства. Также известными сильными операторами являются оператор параметрического и позитивного замыкания. Для них известны все замкнутые классы на множестве булевых функций.
Ключевые слова: замыкание, параметрическое замыкание, гиперфункция, критерий полноты, суперпозиция.
В данной работе рассматривается проблема стабилизации булевых сетей, а именно, вопрос наличия точечных аттракторов в асинхронной булевой сети. Найден критерий стабилизации в зависимости от выбора компонент булевой сети: граф, булевы функции, начальное состояние, порядок обновления.
Ключевые слова: булевы сети, стабилизация.
Рассматриваются алгебраические системы, элементами которых являются отображения, реализуемые конечными автоматами. По богатству примеров и выразительности средств автоматы порой не уступают классическим алгебраическим системам. Полугруппы, группы, кольца, а также функциональные системы автоматов позволили решить ряд трудных математических проблем. Эти конструкции приводятся в книге наряду с примерами конкретных автоматов. Книга предназначена студентам, аспирантам, преподавателям и научным сотрудникам.
Ключевые слова: конечный автомат, алгебраическая система, группа, функциональная система.
Авторы вводят понятие расширенной суперпозиции, как суперпозиции с обязательным наличием в системе \[«задержки»\] и функции Шеффера. Для расширенной суперпозиции авторам удалось доказать алгоритмическую разрешимость задачи выразимости для широкого класса автоматных функций: константных автоматных функций, групповых автоматных функций Медведева, а также линейных автоматных функций, что в случае обычной суперпозиции было алгоритмически неразрешимо.
Ключевые слова: автомат, детерминированная функция, суперпозиция.
Автоматная функция (при подаче всех входных слов), вообще говоря, некоторые выходные слова не выдает, а некоторые из них выдает неоднократно. Если сопоставить слову число его появлений на выходе автомата, то возникает новая функция, названная авторами гистограммной функцией автомата, а само множество выходных слов становится мультимножеством. Изучаются свойства таких мультимножеств.
Ключевые слова: автомат, детерминированная функция.
В данной работе показано, что оптимальная функция выхода может быть получена алгоритмом, который используется в доказательстве критерия прогнозируемости для общерегулярных сверхсобытий в многозначном алфавите, а также, что степень прогнозирования сверхсобытия автоматом, полученным путем использования этого алгоритма, может отличаться от оптимальной в любое количество раз.
Ключевые слова: прогнозирующий автомат, прогнозирование сверхсобытий, автоматный цикл.
Изучается свойство автомата содержать во множестве своих выходных слов заданное регулярное множество. Устанавливается, что данное свойство может быть проверено путем изучения строения множества выходных слов автомата ограниченной длины.
Ключевые слова: абстрактный конечный автомат, регулярное событие, регулярное выражение, генератор, алгоритмическая разрешимость.
Данная работа посвящена изучению \[«линейно реализуемых»\] автоматов, то есть автоматов, обладающих тем свойством, что существует кодирование, при котором порождаемый кодированием, булевкий оператор является линейным. В работе приведен критерий линейной реализуемости автомата. Также приведены нижняя и верхняя оценка числа линейно реализуемых автоматов.
Ключевые слова: теория автоматов, автомат, переходные системы, перестановка, подстановка, кодирование, сложность.
Изучены особенности операторов K, S и A-замыкания в классе линейно-автоматных функций над полем из двух элементов.
Ключевые слова: конечный автомат, линейно-автоматная функция, операции композиции, операции суперпозиции, замкнутые классы, максимальные подклассы.
Данная работа является результатом анализа опыта создания дистанционных обучающих систем сотрудниками кафедры \[\mbox{МаТИС}\] МГУ имени М. В. Ломоносова. Работы по созданию интеллектуальных обучающих систем ведутся на кафедре с 1991 года. За это время были разработаны обучающие системы в различных предметных областях, а также инструмент (авторская система) для обеспечения процесса создания обучающих систем, см., например, [2].
Ключевые слова: дистанционное обучение, программирование, практикум на ЭВМ.
В данной работе предлагается формализация идей М.М. Ботвинника, которые отражают особенности логического мышления человека. В основе подхода лежит понятие цепочки, как последовательности действий, направленных на достижение цели. Существование логических связей между цепочками приводит к представлению шахматной позиции в виде набора цепочек. Предлагается формальная модель описания позиции и алгоритм эвристического нахождения оптимального представления.
Ключевые слова: шахматная позиция, цепочка, оптимизация, математическое моделирование, когнитивные процессы.
Предлагается классификационная структура гипотетической эволюции интеллектуальных систем, основанная на постнеклассических информационно-эволюционном подходе к системному анализу и моделированию объективной реальности, атрибутивно-ингредиентной концепции информации и концепции управляемой эволюции естественного языка. Вводятся новые подклассы расширенного класса интеллектуальных систем: аутоанагенные, коншентиальные и психоэйнические системы.
Ключевые слова: знания, информация, моделирование, системы аутоанагенные, системы интеллектуальные, системы коншентиальные, системы психоэйнические, феноменология, эволюция.
В статье рассматривается математическая модель динамических баз данных, которая обрабатывает три типа запросов: поиск, вставка и удаление. Она построена на взаимодействие информационного графа и конечного детерминированного автомата. Модель позволяет решать динамические задачи поиска и оценивать сложность их решения. Кроме этого, модель позволяет строить бесконечно распараллеливаемые алгоритмы решения.
Ключевые слова: динамические базы данных, информационный граф, автомат, потоки запросов, параллельная обработка данных.
Рассматривается алгоритм синтеза дискретных управляющих систем в виде программируемых логических матриц. Программируемые логические матрицы строятся на основе полиномиальных нормальных форм булевых функций. Для дискретных управляющих систем важен результат на определенном подмножестве всех входных значений. Такие системы можно моделировать с помощью частично заданных булевых функций. Предлагается использовать генетические алгоритмы для нахождения близких к минимальным полиномиальных представлений таких функций.
Ключевые слова: логический синтез, полиномиальная нормальная форма, генетические алгоритмы, булевы функции.
В работе рассмотрен подход к распознаванию визуальных образов, основывающийся на построении кодов изображений, инвариантных относительно геометрических преобразований.
Ключевые слова: распознавание визуальных образов, кодирование изображений.
Изучается взаимосвязь между обобщениями формальных понятий на случай нечётких контекстов. Рассматриваются чётко-порождённые нечёткие формальные понятия (Р. Белохлавек с соавторами), протонечёткие понятия (О. Кридло и С. Крайчи), узорные структуры (C. Кузнецов и Б. Гантер). Устанавливаемые соответствия между протонечёткими и чётко-порождёнными формальными понятиями позволяют переформулировать задачи и использовать полученные ранее критерии и свойства.
Ключевые слова: нечёткие формальные понятия, протонечёткие формальные понятия, чётко-порождённые формальные понятия, интервальные формальные понятия.
Работа посвящена изложению результатов компьютерного моделирования логических процессов в логической системе \[«Искра»\]. Исследовались вопросы, связанные с обучением компьютерных решателей задач и автоматическим синтезом приемов.
Ключевые слова: интеллектуальная система, самообучение, логическая система, компьютерный решатель задач, автоматический синтез приемов.
Известно, что нейронные схемы реализуют кусочно-постоянные функции. Для соответствия нейронным сетям модели Мак-Каллока-Питтса следует разрешить использование только \[«цельных нейронов»\] В этом случае выход нейронной схемы будет принимать значение из множества \[\{0,1\}\], а функция реализуемая схемой – индикаторной. В работе доказана представимость произвольной индикаторной функции нейронными сетями с не более чем тремя слоями. Сформулирован критерий представимости функций индикаторов двуслойными нейронными сетями.
Ключевые слова: нейронная сеть, нейронная схема, нелинейная глубина, модель Мак-Каллока-Питтса.
Актуальными для медицины являются задачи автоматического анализа тактильных образов, регистрируемых инструментально при проведении эндоскопических операций. Важным элементом этого анализа является автоматическое обнаружение неоднородностей. В 2016 году Р. Ф. Солодовой с соавторами были предложены три метода автоматического обнаружения неоднородностей по инструментально зарегистрированным результатам одного нажатия тактильным механорецептором на исследуемый участок. Цель настоящего исследования - теоретическое сравнение согласованности срабатывания этих методов. Более конкретно, изучается вопрос, следует ли из того, что один из методов определил участок как неоднородный, утверждение, что тогда и другие методы определят этот участок как неоднородный.
Ключевые слова: тактильные образы, автоматический анализ, обнаружение неоднородностей, медицинский тактильный эндохирургический комплекс, тактильный механорецептор.
Рассмотрены основные проблемы развития компьютерных обучающих систем. Показано, что ключевой задачей и точкой роста для таких систем является персонификация процесса обучения. Формулируются необходимые условия персонификации обучения. Приводятся результаты экспериментов с данными, накапливаемыми в процессе обучения. Основные положения иллюстрируются на примере платформы Учи.ру.
Ключевые слова: компьютерные обучающие системы, персонификация, кластеризация, ранжирование.
В работе исследуется сложность решения следующей задачи. Дана система, разграничение доступа в которой основано на RelBAC-модели, введенной в статьях В. А. Васенина с соавторами, и пара (субъект, объект). Требуется определить, существуют ли условия, при которых субъект может получить заданный доступ к объекту. Мы показываем, что в общем случае эта задача NP-полна. Если же максимальная длина путей ограничена константой, то задача становится полиномиальной.
Ключевые слова: информационно-аналитические системы, NP-полнота, графы, информационная безопасность.
В работе формулируется критерий полиномиальной полноты квазигруппы простого порядка, а также показывается, что проверка полиномиальной полноты может быть проведена за время, полиномиальное от порядка.
Ключевые слова: квазигруппа, полиномиальная полнота, алгоритмическая сложность.
В работе исследуется модель долгосрочных профилей систем активного аудита, предложенная А. В. Галатенко, А. Е. Лебедевым и И. Н. Емельяновым в 2009 году. Доказывается, что предложенное авторами модели достаточное условие сходимости профилей является критерием.
Ключевые слова: выявление вторжений, состоятельность долгосрочных профилей.
В предлагаемой работе исследуется проблема синтеза пространственно распределенных систем управления в контексте существующего уровня развития систем связи и вычислительных устройств, обосновывается преимущество агентного подхода к систезу пространственно распределенных систем управления. Отдельное внимание уделяется некоторым аспектам онтологического обеспечения и проектирования распределенных многоагентнных систем управления.
Ключевые слова: система управления, агентный подход, интернет вещей.
Безопасный язык программирования C\[_s\] и операционная система, созданная компилятором этого языка, обеспечивают полную защиту от вредоносных программ и кибер-атак. Система, состоящая из C\[_s\] и его операционной системы, открыта только для программ, созданных компилятором C\[_s\] или удовлетворяющих стандартам C\[_s\]. Имеется робот, преобразующий все существующие программы к этим стандартам.
Ключевые слова: информационная безопасность, языки программирования, вредоносные программы, кибер-атаки.
В работе излагается модель криптографических протоколов, основанная на теории процессов с передачей сообщений. Показано, как можно использовать данную модель для решения задач верификации криптографических протоколов (то есть построения математических доказательств утверждений о том, что криптографические протоколы обладают заданными свойствами). В качестве примера таких свойств рассматриваются свойства целостности и секретности. Данные свойства определяются формально, как некоторые соотношения, выражаемые в терминах наблюдаемой эквивалентности процессов с передачей сообщений. Показаны примеры верификации данных свойств для некоторых криптографических протоколов.
Ключевые слова: криптографические протоколы, верификация, наблюдаемая эквивалентность.
Описывается параллельная реализация алгоритма поиска в ширину на графе, разработанная в компании Т-Платформы. Ключевой особенностью является оптимизированное внутреннее представление графа, позволяющее упорядочить коммуникации между вычислительными процессами и разделить выполнение на потоки внутри каждого из процессов. Приводится описание оптимизации по направлению и ее многопоточной имплементации. Также приведены результаты исследования производительности разработанной реализации.
Ключевые слова: распределенные вычисления, параллельные вычисления, графы, поиск в ширину.
При математическом моделировании электрогидродинамических явлений основная трудность связана с включением в модель физических параметров, сведения о которых весьма неопределенны. Возникает потребность в разработке математических моделей с минимальным набором \[«эффективных»\] искомых переменных и задаваемых параметров. В работе описаны три модели возрастающей сложности и приведены результаты, полученные в рамках каждой из них.
Ключевые слова: электрогидродинамика, электрическое поле, слабопроводящие среды, математические модели, объемный электрический заряд, электрохимические реакции, электризация.
В работе исследуется задача объединения двух систем, в каждой из которых реализована политика безопасности take-grant. Объединение называется безопасным, если внутри каждой из объединяемых систем не появляется новых доступов. Предлагается критерий безопасности объединения, а также легко проверяемое достаточное условие безопасности.
Ключевые слова: формальные модели безопасности, модель take-grant, безопасное объединение.
В работе говорится о глубине аппаратной (схемной) реализации потокового шифра ZUC и способах ее минимизации. Сначала приводится простая реализация алгоритма. После этого показываются способы оптимизации данной реализации.
Ключевые слова: потоковые шифры, оптимизация глубины схем.
06.2016 - том 20 выпуск 2 (PDF)
4 июля 2016 г. исполнилось 80 лет основателю и бессменному главному редактору журнала «Интеллектуальные системы», доктору физико-математических наук, профессору механикоматематического факультета МГУ имени М.В.Ломоносова Валерию Борисовичу Кудрявцеву.
Решение задачи распознавания движений, производимых над объектом, имеет обширное количество приложений в робототехнике, производстве мобильных устройств и мобильных приложений. Она является примером типовой задачи классификации и во многих случаях может быть решена сравнительно простым анализом показаний приборов: акселерометра, гироскопа, магнитометра и других. Однако в случаях, когда графики показаний приборов для различных жестов визуально неотличимы и поверхностный анализ не даёт содержательных результатов, приходится пользоваться методами машинного обучения. В статье рассматривается одна из таких задач и освещается тема общей методологии решения задач классификации.
Ключевые слова: машинное обучение, анализ данных, распознавание жестов, Скрытые Марковские Модели, акселерометр
В работе рассматривается задача создания компьютерной программы, осуществляющей синтаксический анализ юридических текстов на русском языке. На вход эта программа должна принимать текст одного предложения, а на выход должна выдавать построенное по этому предложению синтаксическое дерево, в вершинах которого находятся слова предложения, а рёбрам приписаны синтаксические отношения между словами предложения. В работе приведены правила, позволяющие проводить синтаксический анализ при наличии морфологической информации о словах предложения.
Ключевые слова: синтаксический анализ, синтаксическое дерево, морфологические характеристики, правила.
В статье предлагается архитектура реконфигурируемого на лету аппаратного БЧХ декодера.
Ключевые слова: аппаратная реализация, структурные автоматы, помехоустойчивые коды, коды БЧХ.
В статье приводится результат о нахождении минимального количества f(n) арифметических прогрессий, необходимых для того, чтобы получить в объединении все натуральные числа, не сравнимые по модулю n с 0 и −1. Здесь n произвольное натуральное число. При этом прогрессии могут пересекаться. Приводится точное значение для функции f(n), а также конструктивное разбиение этого подмножества натурального ряда на f(n) арифметических прогрессий.
Ключевые слова: натуральный ряд, арифметическая прогрессия, декомпозиция.
В данной статье рассматривается решение двух задач: одномерная упаковка в одинаковые контейнеры и двумерное замощение прямоугольной области с программной реализацией на языке PHP. Для первой задачи будет получено приближенное решение с помощью эвристического BFD-алгоритма и метода ветвей и границ. Для второй задачи, в силу специфики ограничений на входные данные и способы замощения, будет использован метод ветвей и границ, позволяющий получить точное решение за премлемое время работы.
Ключевые слова: PHP, одномерная упаковка в контейнеры, двумерное замощение.
В статье представлен новый алгоритм верификации отпечатков пальцев на основе поиска максимального пути в графе. Центральной идеей данного подхода является поиск максимального пути в специальным образом сконструированном ациклическом графе. Средняя скорость работы алгоритма верификации составляет 100 сравнений в секунду (Intel Core i5-2500 CPU @3.30 GHz 3.30GHz, 4 Гб ОЗУ, ОС Windows 7).
Ключевые слова: отпечатки пальцев, верификация, минуции, граф, максимальный путь в графе.
В работе рассматривается задача параметроэффективной расшифровки линейных функций k-значной логики в рамках модели точной расшифровки. Получены точные значения сложности расшифровки для малого количества существенных переменных. Получены верхние и нижние оценки для общего случая для двух типов запросов: на значение и на сравнение. При стремлении числа переменных к бесконечности получен порядок сложности расшифровки для обоих типов запросов.
Ключевые слова: точная расшифровка функций, линейные функции k-значной логики, запросы на значение, запросы на сравнение.
Статья состоит из двух частей. В первой части рассматривается проблема проверки однозначности алфавитного декодирования в классе регулярных языков. Приводится ряд из нескольких ограничений на эти языки, выполнение которых позволяет построить новый решающий алгоритм и значительно улучшить его сложность в сравнении со сложностью аналогичного алгоритма из [4]. Вторая часть статьи посвящена проблеме проверки однозначности алфавитного декодирования для класса регулярных языков с полиномиальной функцией роста. Полученные в первой части статьи результаты ложатся в основу алгоритма, решающего рассматриваемую проблему. Разработана техника, позволяющая реализовать для языков с полиномиальной функцией роста те допущения, которые приведены в первой части статьи.
Ключевые слова: регулярные языки, функция полиномиального роста, алфавитное декодирование.
В работе рассматривается задача одновременной минимизации площади, мощности и глубины плоских схем, реализующих частичные булевы операторы. В качестве меры мощности рассматривается максимальный потенциал, он равен максимальному количеству выходов элементов, выдающих единицу на заданном входном наборе схемы, где максимум берётся по всем входным наборам. Показано, что при незначительных ограничениях на область определения оператора существует схема, имеющая оптимальный порядок мощности, площади и глубины. В частности, для всюду определённых операторов с n входами и m выходами порядок мощности равен \[({m\sqrt{2^n}})/({\sqrt{min(m,n)}})\], порядок глубины равен \[max(n,log_2m)\].
Ключевые слова: схемы из функциональных элементов, плоские схемы, клеточные схемы, мощность, глубина, функция Шеннона, верхние оценки, булевы операторы.
В работе предложены новые аналитические формулы для констант фазового равновесия, учитывающие влияние состава флюида и точнее передающее фазовое поведение многокомпонентных растворов. Подход позволяет построить термодинамически согласованную модель удобную для численного моделирования многокомпонентную фильтрации: сокращаются требуемые вычислительные ресурсы, повышается надежность расчетов.
Ключевые слова: константы фазового равновесия, УРС, фазовый переход.
Настоящая работа является продолжением статьи [1] и использует понятия и обозначения, введённые в [1]. В работе излагаются основные понятия теории вероятностных автоматов Мура с числовым выходом и теории вероятностных языков. Приводятся новые доказательства классических результатов теории вероятностных автоматов, связанных с эквивалентностью и редукцией вероятностных автоматов Мура с числовым выходом, а также с регулярностью вероятностных языков.
Ключевые слова: вероятностные автоматы, вероятностные языки.
Множество слов, у которых частоты встречаемости пар соседних букв образуют одну и ту же матрицу это формальный (биграммный) язык. В статье описывается матрицы, соответствующие регулярным и контекстно-свободным биграммным языкам.
Ключевые слова: биграммный язык, матрица частот, соседние буквы, эйлеровы циклы.
В работе изучается как связаны класс автоматов, являющихся «просто» реализуемыми, с классом автоматом, обладающим свойством, что все операторы, задаваемые всевозможными кодированиями, являются различными. Показывается, что указанные классы автоматов имеют не пустое пересечение, и ни один из классов не лежит в другом.
Ключевые слова: автомат, кодирование, свойство максимальности.
03.2016 - том 20 выпуск 1 (PDF)
Статья посвящена оптимальной стратегии управления кредитно-депозитными ставками с целью максимизации банковского капитала. Для описании работы Банка используется динамическая система с дискретным временем и рядом нормативных ограничений. В модели присутствуют гипотезы экспертов о поведении рынка, что позволяет использовать её в условиях отсутствия достаточной статистики, в т.ч. когда происходят серьезные изменения в экономики страны. Представлены основные этапы построения модели, исследованы поведения банковских ставок в двух периодах: в обычное время и в кризис.
Ключевые слова: банк, банковские ставки, управление, моделирование.
И.А. Рачковская К вопросу об обеспечении прослеживаемости в условиях неиндустриализации
В статье показано воздействие неоиндустриализации или новой промышленной революции на обеспечение прослеживаемости в цепи поставок. Рассмотрены основные тенденции в развитии Индустрии 4.0 и их влияние на участников рынка. Процедура прослеживаемости рассмотрена на примере предприятий пищевой промышленности.
Ключевые слова: неоиндустриализация, Индустрия 4.0, интернет вещей, прослеживаемость, управление цепями поставок.
Задачи энтропийно-линейного программирования часто возникают в различных приложениях (транспортные задачи, исследования химических реакций и др.). Такие задачи формулируются обычно как задачи максимизации энтропии (или минимизации минус энтропии) с аффинными ограничениями и линейными ограниченияминеравенствами. В работе исследуется метод решения такой задачи, в основе которого лежит решение двойственной задачи с восстановлением решения прямой задачи: каждой точке в двойственном пространстве, вычисляемой методом, ставится в соответствие определенная точка в прямом. Для указанного метода получена верхняя оценка числа итераций, необходимого для достижения решения с заданной точностью. Изложенный метод применим также к более широкому классу сильно выпуклых функционалов с аналогичным допустимым множеством.
Ключевые слова: энтропийно-линейное программирование, быстрый градиентный метод, двойственная задача, прямо-двойственный метод.
В работе исследуется глубина аппаратной (схемной) реализации блочного шифра Кузнечик. Также проводится сравнение глубины реализации алгоритма Кузнечик с другими распространенными алгоритмами блочного шифрования.
Ключевые слова: оптимизация глубины схем, блочные шифры.
В статье рассматривается математическая модель и методы верификации функциональных программ. Основное внимание уделено теории функций, вычисляемых функциональными программами (эти функции называются наименьшими неподвижными точками функциональных программ). Также излагаются основные методы верификации функциональных программ: метод вычислительной индукции и метод структурной индукции.
Ключевые слова: верификации функциональных программ, метод вычислительной индукци,метод структурной индукции.
В данной статье рассматривается применение алгоритма двумерной упаковки при вырезании прямоугольных панелей произвольных размеров из стандартных прямоугольных панелей фиксированных размеров (сэндвич-панелей). Требуется определить минимальное количество сэндвичпанелей, необходимое для производства всех требуемых панелей. Будет рассмотрено решение этой задачи при помощи HBF-алгоритма с реализацией на языке программирования PHP.
Ключевые слова: PHP, двумерная упаковка, HBFалгоритм
В работе исследуются относительные влияния переменных булевой функции. Найдены значения нижней и верхней границы максимума относительного влияния для пороговых функций от n переменных в зависимости от n. Они равны \[1/n\] и \[({2^{n-1}})/({2^{n-1}+n-2})\]. Приводится разбиение всех пороговых функций четырёхмерного пространства на классы в зависимости от максимального относительного влияния переменных.
Ключевые слова: пороговые функции, влияние переменных булевой функции, относительное влияние переменных булевой функции, τ -регулярные булевы функции.
Рассматривается оценка одного из параметров конечных автоматов — степень различимости состояний. В работе рассматриваются множества конечных автоматов с произвольными функциями выхода и переходов. Состояния конечного автомата называются r эквивалентными, если соответствующие им автоматные функции одинаковы на словах длины r. Состояния называются r–различимыми, если они (r–1)-эквивалентны и соответствующие им автоматные функции различаются на словах длины r. Максимальная степень различимости состояний автомата называется его степенью различимости. При отсутствии ограничений известна достижимая верхняя оценка степени различимости равная s−1, где s — число состояний автомата. В каждом своем состоянии конечный автомат реализует функцию, аргументы которой (значения которой) суть элементы входного (выходного) алфавита. Число различных таких функций будем называть статической функциональностью автомата. Рассматриваются автоматы с заданной статической функциональностью. Получена достижимая верхняя оценка степени различимости, равная s + 1 − F, где F — статическая функциональность автомата. Множество \[\{s_1, s_2, . . . , s_F\}\], где \[s_i\], \[1\leq {i}\leq{F}\], — мощность i-го класса 1-эквивалентности будем называть спектром конечного автомата. Показана зависимость максимальной степени различимости состояний конечного автомата от его спектра.
Ключевые слова: конечный автомат, автоматная функция, различимость состояний.
Рассматривается динамическая задача поиска идентичных объектов (ДЗПИО). В данной работе представлен конечный МДИГ с радиусом видимости один и степени ветвления два, обрабатывающий произвольный поток запросов. Это минимально возможный по степени ветвления МДИГ с радиусом видимости один, решающий поставленную задачу.
Ключевые слова: динамические базы данных, информационный граф, автомат, потоки запросов.
В данной работе доказана нижняя оценка числа вершин (t,s)-бирегулярных графов обхвата 6 при 2 < t < s. Придуман алгоритм построения (t,s)-бирегулярных графов. Доказано, что при определенных значениях t и заданных значениях s алгоритм «(t,s)-построения» строит граф обхвата 6.
Ключевые слова: бирегулярный граф, двудольный граф, обхват, LDPC-код.