Preview

Моделирование и анализ информационных систем

Расширенный поиск
Том 24, № 2 (2017)
Скачать выпуск PDF

Оригинальные статьи 

125-140 6241
Аннотация

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

141-154 7385
Аннотация

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

155-167 9022
Аннотация

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

168-185 5897
Аннотация

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

186-204 621
Аннотация

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

205-214 6443
Аннотация

В работе изучаются взаимоотношения между гипотезой Тэйта для дивизоров на расслоенном многообразии над конечным полем и гипотезой Тэйта для дивизоров на общем схемном слое при условии, что общий схемный слой имеет иррегулярность нуль. Пусть \(\pi:X\to C\) -- сюръективный морфизм гладких проективных многообразий над конечным полем \(F_q\) характеристики \(p\), \(C\) -- кривая, общий схемный слой морфизма \(\pi\) является гладким многообразием \(V\) над полем \(k=\kappa(C)\) рациональных функций кривой \(C\), \(\overline k\) -- алгебраическое замыкание поля \(k\), \(k^s\) -- его сепарабельное замыкание, \(NS(V)\) -- группа Нерона -- Севери классов дивизоров на многообразии \(V\) по модулю алгебраической эквивалентности, причем выполнены следующие условия: \(H^1(V\otimes\overline k,\mathcal O_{V\otimes\,\overline k})=0,\) \; \(NS(V)=NS(V\otimes\overline k).\) Если для простого числа \(l\), не делящего \({Card}([NS(V)]_{tors})\) и отличного от характеристики поля \(F_q\), верно соотношение \(NS(V)\otimes\Bbb Q_l\,\,\widetilde{\rightarrow}\,\,[H^2(V\otimes k^{sep},Q_l(1))]^{Gal( k^{sep}/k)} \)\; \((\)другими словами, если верна гипотеза Тэйта для дивизоров на \(V )\), то для любого простого числа \(l\neq charr(F_q)\) гипотеза Тэйта верна для дивизоров на \(X\): \(NS(X)\otimes Q_l\,\,\widetilde{\rightarrow} \,\,[H^2(X\otimes\overline F_q,Q_l(1))]^{Gal(\overline F_q/ F_q)}.\) В частности, из этого результата следует гипотеза Тэйта для дивизоров на арифметической модели K3 -- поверхности над достаточно большим глобальным полем конечной характеристики, отличной от 2.

215-226 690
Аннотация

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

227-238 516
Аннотация

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

239-252 725
Аннотация

Для практического применения кодовой криптосистемы типа Мак-Элиса необходимо, чтобы используемый в основе криптосистемы код имел быстрый алгоритм декодирования. С другой стороны, используемый код должен быть таким, чтобы нахождение секретного ключа по известному открытому ключу было практически неосуществимо при относительно небольшом размере ключа. В связи с этим в настоящей работе  предлагается в криптосистеме типа Мак-Элиса использовать тензорное произведение \(C_1\otimes C_2\) групповых \(\textrm{MLD}\)-кодов \(C_1\) и \(C_2\). Алгебраическая структура кода \(C_1\otimes C_2\) в общем случае отличается от структуры кодов \(C_1\) и \(C_2\), поэтому представляется возможным построение стойких криптосистем типа Мак-Элиса даже на основе кодов \(C_i\), для которых известны успешные атаки на ключ. Однако на этом пути возникает проблема декодирования кода \(C_1\otimes C_2\). Основной результат настоящей работы -- построение и обоснование набора необходимых для декодирования этого кода быстрых алгоритмов. Процесс построения декодера существенно опирается на групповые свойства кода \(C_1\otimes C_2\). В качестве приложения в работе построена криптосистема типа Мак-Элиса на коде \(C_1\otimes C_2\) и приводится оценка ее стойкости к атаке на ключ в предположении, что для кодовых криптосистем на кодах \(C_i\) возможна эффективная атака на ключ. Полученные результаты численно проиллюстрированы в случае, когда \(C_1\), \(C_2\)  -- коды Рида--Маллера--Бермана, для которых соответствующая кодовая криптосистема взломана Л. Миндером и А. Шокроллахи (2007 г.).



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)