• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 30 публикаций
Сортировка:
по названию
по году
Статья
Begicheva A.K., Lomazova I.A. Моделирование и анализ информационных систем. 2017. Vol. 24. No. 2. P. 125-140.
Добавлено: 6 мая 2017
Статья
Begicheva A., Lomazova I. A. Моделирование и анализ информационных систем. 2015. Vol. 22. No. 3. P. 392-403.

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

Добавлено: 5 августа 2015
Статья
Remizov I. Моделирование и анализ информационных систем. 2015. Vol. 22. No. 3. P. 337-355.
Добавлено: 30 октября 2018
Статья
Shershakov S. A., Rubin V. A. Моделирование и анализ информационных систем. 2015. Vol. 22. No. 6. P. 818-833.
Добавлено: 22 декабря 2015
Статья
Захаров В. А., Коннов И. В. Моделирование и анализ информационных систем. 2010. Т. 17. № 4. С. 78-87.
Наиболее значительную трудность для всех инструментальных средств верификации моделей программ создает эффект комбинаторного взрыва. Один из способов сократить размер проверяемой модели $M$ --- выбрать подходящую группу автоморфизмов $G$ размеченной системы переходов $M$ и построить фактор-модель $M/G$. Состояниями фактор-модели $M/G$ служат орбиты состояний модели $M$ относительно группы $G$; также известно, что модели $M/G$ и $M$ находятся в отношении бисимуляции. К сожалению, поиск нетривиальной группы автоморфизмов $G$ произвольной конечной системы переходов $M$ является вычислительно трудной задачей. Для преодоления этой трудности был предложен метод адаптивного упрощения модели на основе симметрии. Этот метод позволяет воспользоваться преимуществами симметричного устройства модели $M$, не обращаясь явно к орбитам ее состояний. В самом начале решения задачи проверки достижимости состояний предполагается, что модель является абсолютно симметричной; далее это предположение корректируется по мере того, как обнаруживаются переходы, несовместные со сложившимся представлением о симметрии в модели. Пространство состояний модели оказывается разбитым на классы эквивалентности, которые называются мета-состояниями; на каждом шаге вычисления при рассмотрении очередного перехода мета-состояния могут подвергаться расщеплению. Мы обнаружили, что метод адаптивного упрощения модели на основе симметрии может быть с равным успехом применен для проверки выполнимости формул LTL. Основной результат работы --- новый теоретико-автоматный подход к верификации моделей программ, сочетающий метод адаптивного упрощения модели на основе симметрии и алгоритм двойного поиска в глубину для проверки пустоты автоматов Бюхи.
Добавлено: 30 сентября 2015
Статья
Губочкин И. В. Моделирование и анализ информационных систем. 2013. Т. 20. № 2. С. 23-33.

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

Добавлено: 2 декабря 2013
Статья
Бараш Л. Ю., Щур Л. Н. Моделирование и анализ информационных систем. 2012. Т. 19. С. 145-162.

Рассматриваются современные методы и пакеты программ генерации псев- дослучайных чисел высокого качества, а также генерации параллельных по- токов случайных чисел, для использования в расчетах Монте-Карло. Рассмот- рено свойство равнораспределения вероятности для генераторов вида Multiple Recursive Generators и параметры, при которых это свойство выполняется на длине до логарифма размера сетки.

Добавлено: 22 марта 2014
Статья
Синицын С., Давыдов А., Батаев А. и др. Моделирование и анализ информационных систем. 2010. № 17:4. С. 17-26.
Добавлено: 19 апреля 2012
Статья
Шершаков С. А. Моделирование и анализ информационных систем. 2014. Т. 21. № 5. С. 102-115.

Извлечение процессов (process mining) — это новое направление в области моделирования и анализа процессов, в котором важную роль играет использование информации из журналов (логов) событий, хранящих историю поведения системы. Методы и подходы, используемые при извлечении процессов, часто опираются на различные эвристики, и эксперименты с большими логами событий важны для обоснования и сравнения разрабатываемых методов и алгоритмов. Такие эксперименты весьма трудоемки, поэтому их автоматизация является актуальной задачей в области извлечения процессов. В данной работе представлен язык DPMine, разработанный специально для описания и проведения экспериментов по извлечению и анализу моделей процессов. Дается описание основных концепций языка, а также принципов и механизмов его расширения. Рассматриваются вопросы интеграции языка в инструмент моделирования VTMine в виде динамически загружаемых компонентов. Приводится пример эксперимента по построению нечеткой модели процесса по логу данных, хранящемуся в виде нормализованной базы данных.   \end{abstract}

Добавлено: 20 октября 2014
Статья
Захаров В. А., Аббас М. М. Моделирование и анализ информационных систем. 2018. Т. 25. № 6. С. 589-606.

Математические модели распределенных вычислений, построенные на основе исчисления мобильных процессов ($\pi$-исчисления), широко используются для проверки свойств информационной безопасности криптографических протоколов. Поскольку $\pi$-исчисление является полной по Тьюрингу моделью вычислений, эта задача в общем случае алгоритмически неразрешима. Поэтому ее исследование проводится лишь для некоторых специальных классов процессов $\pi$-исчисления с ограниченными вычислительными возможностями, например, для нерекурсивных процессов, в которых все вычисления имеют ограниченную длину, для процессов с ограниченным числом параллельных компонентов и др. Однако и в этих случаях предложенные разрешающие алгоритмы оказываются весьма трудоемкими. Мы полагаем, что это обусловлено самой природой процессов $\pi$-исчисления. Цель данной работы --- показать, что даже для наиболее слабой модели пассивного противника и для сравнительно простых протоколов, в которых используются лишь базовые операции $\pi$-исчисления, задача проверки свойств информационной безопасности этих протоколов является co-NP-полной.  

Добавлено: 26 октября 2018
Статья
Дворянский Л.В., Ломазова И.А. Моделирование и анализ информационных систем. 2012. Т. 19. № 5. С. 115-130.

Вложенные сети Петри (NP-сети) — это расширение сетей Петри в рамках подхода “nets-within-nets”, когда фишки в разметке сети сами являются сетями Петри и обладают автономным поведением, при этом имеются средства синхронизации сетевых фишек и системной сети. Фомализм NP-сетей позволяет естественным образом моделировать многоуровневые мультиагентные системы с динамической структурой. В настоящее время не существует инструментальной поддержки имитационного моделирования и анализа вложенных сетей Петри. В работе предлагается проводить имитационное моделирование и построение графа достижимости для NP-сетей путем перевода NP-сетей в раскрашенные сети Петри и использования инструментария CPN Tools в качестве виртуальной машины для исполнения и средства автоматического анализа исходных NP-сетей.

Добавлено: 28 ноября 2012
Статья
Вербицкая Е. А., Григорьев С. В., Полубелова М. И. и др. Моделирование и анализ информационных систем. 2014. Т. 21. № 6. С. 131-143.

Часто при разработке сложных программных систем используется более чем один язык программирования. В таком случае принято говорить об основном (или исходном) языке и одном или нескольких встроенных языках. Из строковых выражений основного языка динамически формируются программы на отличном от него языке, которые потом интерпретируются специальными, работающими во время исполнения компонентами, такими как базы данных или веб-браузеры. Большинство языков программирования общего назначения могут играть роль как основного, так и встроенного языка. Самый яркий пример реализации такого подхода - динамический SQL, специфицированный в стандарте ISO SQL и поддерживаемый большинством СУБД. Автодополнение и подсветка синтаксиса - стандартная для интерактивных сред разработки функциональность - значительно упрощают процесс разработки с использованием встроенных языков. Существует несколько инструментов, предоставляющих функциональность интегрированных сред разработки для встроенных языков, но они в основном поддерживают только один конкретный встроенный язык, и поддержка другого языка требует нетривиального ручного вмешательства. Мы продемонстрируем разрабатываемую платформу, позволяющую создавать инструменты для статического анализа динамически формируемых выражений.

Добавлено: 29 января 2019
Статья
Мицюк А. А., Ломазова И. А., ван дер Аалст В. Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 459-480.

В ходе жизненного цикла информационной системы (ИС) ее реальное поведение может перестать соответствовать исходной модели системы. Между тем для поддержки системы очень важно иметь актуальную модель, отражающую текущее поведение системы. Для корректировки модели можно использовать информацию из журнала событий системы. Журналы событий процессно-ориентированных информационных систем содержат запись истории исполнения поддерживаемых процессов в виде более или менее детальных списков событий. Такие журналы, как правило, записываются всеми современным ИС. Эта информация может использоваться для анализа реального поведения ИС и ее усовершенствования. В работе рассматривается задача корректировки (исправления) модели процесса на основе информации из журнала событий. Исходными данными для этой задачи являются первоначальная модель процесса в виде сети Петри и журнал событий. Результатом корректировки должна быть новая модель процесса, лучше отображающая реальное поведение ИС, чем исходная модель. Актуальная модель может быть построена и полностью заново, например, с помощью одного из известных алгоритмов автоматического синтеза модели процесса по журналу событий. Однако структура исходной модели при этом может полностью измениться. Полученную модель будет трудно сопоставить с прежней моделью процесса, что затруднит ее понимание и анализ. Поэтому при корректировке модели важно по возможности сохранить ее прежнюю структуру. Предлагаемый в настоящей работе алгоритм корректировки модели основан на принципе «разделяй и властвуй». Исходная модель процесса декомпозируется на фрагменты. Для каждого из фрагментов проверяется, соответствует ли он актуальному журналу событий. Фрагменты, для которых выявлены несоответствия, заменяются на заново синтезированные. Новая модель собирается из фрагментов путем слияния переходов. Проведенные эксперименты показывают, что наш алгоритм корректировки дает хорошие результаты, если применяется для исправления локальных несоответствий. Работа содержит описание алгоритма, формальное обоснование его корректности, а также результаты экспериментального тестирования на искусственных примерах.

Добавлено: 28 августа 2017
Статья
Биктимиров М. Р., Глебский В., Долгов Б. и др. Моделирование и анализ информационных систем. 2015. Т. 22. № 1. С. 114-126.

В работе анализируется опыт создания и использования информационных технологий и инфраструктур для агрегации научной информации в трех странах-лидерах мирового ИТ-рейтинга «Индекс сетевой готовности», а также опыт Европейского Союза в целом. Изучались как руководящие и аналитические документы, так и конкретные действующие проекты в рассматриваемой предметной области. Проведенное исследование позволяет выделить как характерные общие черты в подходах, в понимании актуальности и необходимости решения задачи создания национальных инфраструктур хранения и обработки данных научных исследований и их объединения, так и заметные организационные различия, основанные на принятых в каждой конкретной стране механизмах (традициях) и органах управления, а также оценить уровень продвижения в решении поставленных задач. Были также указаны общие основные элементы построения всех инфраструктур хранения и обработки данных научных исследований.

Добавлено: 10 октября 2015
Статья
Волканов Д., Захаров В. А., Зорин Д. и др. Моделирование и анализ информационных систем. 2012. Т. 19. № 6. С. 45-56.

Исследуется задача верификации систем реального времени (СРВ). Для описания СРВ удобно использовать диаграммы состояний UML с семантикой, определяемой иерархическими автоматами. Для верификации СРВ часто применяется средство UPPAAL, разработанное для проверки формул логики TCTL на сети временных автоматов. Основным результатом данной статьи является алгоритм трансляции иерархических автоматов в сеть временных автоматов и обоснование его корректности.

Добавлено: 29 сентября 2015
Статья
Кушик Н. Г., Евтушенко Н. В., Бурдонов И. Б. и др. Моделирование и анализ информационных систем. 2017. Т. 24. № 6. С. 730-742.

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

Добавлено: 11 августа 2018
Статья
Магазинов А. Н. Моделирование и анализ информационных систем. 2013. Т. 20. № 4. С. 71-80.

В 1929 году Б. Н. Делоне привел полную классификацию комбинаторных типов схождений параллелоэдров в гранях коразмерности 3. Оказалось, что любое схождение дуально одному из следующих пяти трехмерных многогранников: тетраэдру, четырехугольной пирамиде, октаэдру, треугольной призме или параллелепипеду. В статье приводится новое доказательство этого результата, основанное на формуле Эйлера. С использованием этой классификации получены некоторые дальнейшие свойства граней коразмерности 3 разбиений пространства на параллелоэдры. Показано, что для граней коразмерности 3 выполнена гипотеза о размерности, т.е. аффинная оболочка центров параллелоэдров, сходящихся в грани коразмерности 3, трехмерна. Наконец, установлено, что центры параллелоэдров, сходящихся в грани коразмерности 3, порождают трехмерную подрешетку индекса 1. 

Добавлено: 4 октября 2018
Статья
Захаров В. А., Гнатенко А. Р. Моделирование и анализ информационных систем. 2018. Т. 25. № 5. С. 506-524.

О выразительных возможностях некоторых расширений линейной темпоральной логики // Моделирование и анализ информационных систем. — 2018. — Т. 25, № 5. — С. 506–524. Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Мы полагаем, что для формального описания поведения реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционная темпоральная логика линейного времени LTL. В этой работе рассматривается новый язык формальных спецификаций LP-LTL, представляющий собой расширение темпоральной логики LTL, специально разработанное для описания свойств вычислений автоматов-преобразователей. Темпоральные операторы в формулах LP-LTL снабжены параметрами, в качестве которых используются множества слов (языки), описывающие потоки сигналов управления, поступающих на вход реагирующей системы. Базовые предикаты в формулах LP-LTL также определяются языками в алфавите элементарных действий; эти языки описывают ожидаемую реакцию системы в ответ на воздействия окружающей среды. В более ранних работах авторов этой статьи изучалась задача верификации конечных автоматов-преобразователей относительно спецификаций, представленных формулами логик LP-LTL и LP-CTL. Было показано, что для обеих логик эта задача алгоритмически разрешима. Цель данной работы — оценить выразительные возможности логики LP-LTL и сравнить ее с широко известными логиками, применяющимися в информатике для спецификации реагирующих систем. В логике LP-LTL были выделены два фрагмента LP-1-LTL и LP-n-LTL. Нам удалось установить, что язык спецификаций LP-1-LTL более выразителен, чем LTL, в то время как фрагмент LP-n-LTL обладает точно такими же выразительными возможностями, что и монадическая логика второго порядка S1S.

Добавлено: 26 октября 2018
Статья
Захаров В. А., Жайлауова Ш. Р. Моделирование и анализ информационных систем. 2017. Т. 24. № 4. С. 415-433.

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

Добавлено: 12 октября 2017
Статья
Захаров В. А., Темербекова Г. Г. Моделирование и анализ информационных систем. 2016. Т. 23. № 6. С. 741-753.

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

Добавлено: 13 октября 2016
Статья
Захаров В. А., Чемерицкий Е. В. Моделирование и анализ информационных систем. 2014. Т. 21. № 6. С. 57-69.
Разработка алгоритмов реконфигурирования сетей является важным направлением развития программного обеспечения для телекоммуникационных сетей нового поколения --- программно конфигурируемых сетей. Частный случай проблемы реконфигурирования сетей --- это задача плавного восстановления заданной сетевой конфигурации, после того как некоторые правила коммутации пакетов были удалены из таблиц коммутаторов (например, по истечении срока их активности). В данной статье проведено исследование этой задачи в рамках формальной модели программно конфигурируемых сетей, предложены корректные и безопасные алгоритмы восстановления сетевых конфигураций, и показано, что в общем случае задачу плавного восстановления конфигураций нельзя решить без обращения к правилам коммутации с приоритетами.
Добавлено: 30 сентября 2015
1 2