Аннотации

Анализ гиперкубических коммуникационных структур параметрическими сетями Петри // Труды 24-й Британской конференции по инжинирингу производительности сетей (UKPEW 2008), 3-4 Июля 2008, кафедра вычислительных систем, Имперский колледж Лондона, с. 358-371 (соавтор Шмелёва Т.Р.).

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

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

Эффективность использования адресного пространства протокола Bluetooth // Труды 20-й Международной конференции Инжиниринг программного обеспечения и систем и его приложения (ICSSEA 2007), Париж 4-6 Декабря 2007. (соавторы Березнюк М.В., Гупта К.К.).

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

Ключевые слова: протокол Bluetooth, раскрашенная сеть Петри, имитационное моделирование, адресное пространство, эффект проскальзывания

Всемирная сеть Ethernet? // Зв'язок, № 5, 2007. - с. 14-19. (соавторы Ворибиенко П.П., Нечипорук О.Л.)

Предложены новые схемы адресации глобальных сетей (Е6/Е6-4/Е4Р), полностью построенных на основе технологии Ethernet с аннулированием протоколов сетевого-транспортного уровней стека протоколов TCP/IP и полным сохранением интерфейсов прикладного уровня. Выполнено эскизное проектирование стеков протоколов Е6/Е6-4/Е4Р и коммутирующих маршрутизаторов Е6, приведены примеры построения сетей. Преимуществом предложенного подхода является сокращение доли служебной информации, передаваемой, в сети, повышение производительности сети, в особенности, при передаче голосового трафика, расширение пространства сетевых адресов.

Ключевые слова: Ethernet, адрес Е6, стек протоколов, коммутирующий маршрутизатор

Оценка характеристик сетей Ethernet с помощью параметрических моделей Петри // Зв'язок, № 4, 2007. - с. 62-67. (соавтор Шмелёва Т.Р.)

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

Ключевые слова: Ethernet, коммутатор, параметрическая сеть Петри, время доставки фрейма, производительность

Оценка производительности сетей с коммутацией меток в моделирующей системе NS // Збiрник Наукових праць ОНАЗ iм. О.С. Попова, № 1, 2007. - с. 25-31. (соавтор Литвин Д.А.)

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

Ключевые слова: коммутация меток, MPLS, оценка производительности, имитационное моделирование

Моделирование телекоммуникационных сетей в системе NS // Збiрник Наукових праць ОНАЗ iм. О.С. Попова, № 2, 2006. - с. 35-43. (соавтор Шинкарчук Т.Н.)

Выполнено построение модели фрагмента Европейской магистрали Интернет в среде моделирующей системы NS. Для оценки пропускной способности магистрали, времени доставки пакета и процента доставленных пакетов разработаны соответствующие скрипты ОС Unix, выполняющие анализ полной трассы имитационного моделирования. Подтверждена адекватность ранее представленных моделей, построенных в форме раскрашенных сетей Петри.

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

Оценка времени отклика коммутируемой Ethernet с помощью раскрашенных сетей Петри // Труды международной средневосточной мультиконференции по моделированию, Август 28-30, 2006. - Александрия (Египет). - 2006. - С. 68-77 (соавтор Шмелёва Т.Р.).

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

Ключевые слова: Ethernet, коммутатор, время отклика, раскрашенная сеть Петри

Исследование эффективности технологии MPLS с помощью раскрашенных сетей Петри // Зв'язок. - 2006, №5. - C. 49-55 (соавтор Сакун А.Л.).

В настоящей работе построены модели Петри магистральных маршрутизаторов Интернет, реализующих классическую IP-маршрутизацию и технологию коммутации меток MPLS. На примере модели европейской магистрали Интернет выполнена сравнительная оценка эффективности IP-маршрутизации и MPLS. Для построения и исследования моделей использована промышленная моделирующая система CPN Tools. Применение технологии MPLS позволяет обеспечить увеличение трафика в среднем в 1,7 раз.

Ключевые слова: магистральная сеть, MPLS, раскрашенная сеть Петри, оценка еффективности

Верификация протокола TCP в процессе последовательной композиции модели Петри // Зв'язок. - 2006, Т. 64, №4. - С. 49-58.

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

Ключевые слова: TCP, Сеть Петри, Инвариант, Функциональная подсеть, Композиция.

О реализации композиционных алгоритмов решения систем линейных уравнений // Управляющие системы и машины. - 2006, №3. - С. 32-41.

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

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

Последовательная композиция кланов линейных систем // Системнi дослiдження та iнформацiйнi технологiї. - 2006, №2. - С. 121-137.

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

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

Верификация протоколов Ethernet с помощью параметрической композиции сетей Петри // INCOM'2006: 12-й IFAC/IFIP/IFORS/IEEE/IMS Симпозиум по проблемам информационного управления в производстве, Май 17-19 2006, Сант-Этьен (Франция), С. 261-267 (соавтор Зайцев И.Д.).

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

Ключевые слова: Ethernet, сеть Петри, инвариант, параметрическая композиция, функциональная подсеть

Исследование эффективности использования адресного пространства протокола Bluetooth // Радиоэлектроника. Информатика. Управление. - 2006, №1. - C. 57-63 (соавтор Березнюк М.В.).

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

Ключевые слова: раскрашенная сеть Петри, пикосеть Bluetooth, адресное пространство, оценка эффективности

Синтез модели Петри и верификация протокола электронной коммерции IOTP // Радиотехника: Всеукр. межведомств. науч.-техн. сб. 2006, Вып. 144. - С. 28-35 (соавтор Чорногала Е.Я.).

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

Ключевые слова: электронная коммерция, протокол, сеть Петри, верификация, синтез.

Передаточная функция сети Петри // Искусственный интеллект. - 2006, №1. - С. 23-30.

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

Ключевые слова: функциональная сеть Петри, уравнение состояний, передаточная функция, эквивалентность

Последовательная композиция моделей Петри телекоммуникационных протоколов // Зв'язок. - 2006, Т. 61, №1. - С. 45-50.

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

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

Композиционный анализ сетей Петри // Кибернетика и системный анализ. - 2006, № 1. - С. 143-154.

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

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

Синтез моделей Петри телекоммуникационных протоколов // Труды Одесской национальной академии связи им. А.С.Попова. - 2005, №2. - С. 36-42.

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

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

Основы построения параметрических моделей Петри коммутируемых сетей // Моделирование и компьютерная графика: Материалы 1-й международной научно-технической конференции, 4-7 октября 2005, Донецк, ДонНТУ, 2005, с.207-215 (соавтор Шмелёва Т.Р.).

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

Ключевые слова: раскрашенная сеть Петри; коммутируемая телекоммуникационная сеть; параметрическая модель

Измерение характеристик одноуровневой коммутируемой сети с помощью параметрической модели Петри // Радиотехника: Всеукр. межведомств. науч.-техн. сб. 2005, Вып. 142, c. 40-47 (соавтор Шмелёва Т.Р.).

Представлена параметрическая модель Петри одноуровневой коммутируемой локальной сети, позволяющая ограничивать размеры буферов и количество процессоров и реализующая дисциплину FIFO при работе с очередями. Обеспечено автоматическое измерение времени отклика локальной сети в процессе имитации динамики модели; для этих целей использованы специальные измерительные фрагменты сетей Петри. Исследованы вопросы существования стационарного режима работы локальной сети, а также зависимости времени отклика от характеристик применяемых программно-аппаратных средств. Результаты представлены в виде диаграмм, графиков, таблиц.

Ключевые слова: раскрашенная сеть Петри; коммутируемая сеть; параметрическая модель; измерение

Параметрическая модель Петри одноуровневой коммутируемой сети // Труды Одесской национальной академии связи им. А.С.Попова, № 1, 2005, с. 33-40 (соавтор Шмелёва Т.Р.).

Построена модель одноуровневой коммутируемой сети инвариантная по отношению к топологии. Модель представлена раскрашенной сетью Петри. Основными параметрами модели являются упакованная матрица топологии сети, таблица запросов рабочих станций к серверам, времена передачи фреймов и обработки запросов. Для отладки модели и сбора статистической информации использована система CPN Tools.

Ключевые слова: раскрашенная сеть Петри; коммутируемая сеть; параметрическая модель

Программное обеспечение для декомпозиции двудольных орграфов // Научные труды Донецкого государственного технического университета, серия "Информатика, кибернетика и вычислительная техника", Вып. 93, 2005, с. 60-70.

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

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

Функциональные сети Петри // Университет Париж-Дофин, Записки лаборатории LAMSADE, № 224, Апрель 2005, 62с (www.lamsade.dauphine.fr/cahiers.html).

Функциональные сети Петри и функциональные подсети введены и изучены в целях ускорения анализа сетей Петри алгебраическими методами. Показано, что произвольная функциональная подсеть может быть получена путём композиции минимальных функциональных подсетей. Предложено два способа декомпозиции сети Петри: посредством решения логических уравнений и с помощью специально построенного алгоритма полиномиальной сложности. Изучены свойства функциональных подсетей. Показано, что линейные инварианты сети Петри могут быть вычислены из инвариантов её функциональных подсетей; аналогичные результаты имеют место также для фундаментального уравнения сети Петри. Построены и изучены методы анализа сетей Петри с помощью композиции функциональных подсетей. Показано, что основанное на композиции вычисление инвариантов и решение фундаментального уравнения обеспечивает значительные ускорения вычислений. Для дополнительного ускорения вычислений предложена последовательная организация композиции функциональных подсетей. Задача последовательной композиции формализована в терминах теории графов и названа оптимальным коллапсом взвешенного графа. Построенные методы применены для композиционного анализа моделей Петри таких широко известных телекоммуникационных протоколов как ECMA, TCP, BGP.

Ключевые слова: сеть Петри; функциональная сеть; функциональная подсеть; композиция; коллапс графа

Решение линейных систем с помощью декомпозиции // Системнi дослiдження та iнформацiйнi технологiї, 2005, №2, с. 131-143.

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

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

Верификация протокола BGP с помощью декомпозиции модели Петри на функциональные подсети // Труды симпозиума по проектированию, анализу и моделированию распределённых систем, Апрель 2-8, 2005, Сан Диего, Калифорния, США, с. 72-78.

Построена модель Петри широко известного протокола BGP магистральной маршрутизации Интернет. Выполнена декомпозиция модели Петри протокола BGP на функциональные подсети. Инвариантность исходной модели доказана на основе установленной инвариантности её функциональных подсетей. Полученные ускорения вычислений оцениваются экспоненциальной функцией от размерности сети Петри.

Ключевые слова: сеть Петри; BGP; инвариантность; декомпозиция; функциональная подсеть

Измерительные фрагменты в моделях Петри телекоммуникационных сетей // Зв'язок №2(54), 2005, с. 65-71.

Представлена технология измерения характеристик моделей Петри коммутируемых сетей с помощью специальных измерительных фрагментов раскрашенных сетей Петри. Особенности применения измерительных фрагментов изучены на примере определения времени отклика в модели коммутируемой локальной сети. Для автоматизированного построения модели в форме иерархической раскрашенной сети Петри использована инструментальная система CPN Tools. Модель отражает такие особенности функционирования локальной сети Ethernet как процедуры доступа CDMA, полнодуплексный режим работы, а также обеспечивает лёгкую масштабируемость сетей Петри при отображении структуры конкретных ЛВС.

Ключевые слова: ЛВС; коммутатор; измерительный фрагмент; время отклика; раскрашенная сеть Петри

Верификация телекоммуникационных протоколов с помощью декомпозиции сетей Петри // Зв'язок №1(53), 2005, с. 41-47.

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

Ключевые слова: телекоммуникационный протокол; верификация; сеть Петри; инвариант; декомпозиция; функциональная подсеть

Решение фундаментального уравнения сетей Петри в процессе композиции функциональных подсетей // Искусственный интеллект, № 1, 2005, с. 59-68.

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

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

Последовательная композиция функциональных подсетей // Труды Одесской национальной академии связи им. А.С.Попова, № 3, 2004, с. 33-40.

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

Ключевые слова: сеть Петри; функциональная подсеть; последовательная композиция; коллапс графа

Декомпозиция сетей Петри // Кибернетика и системный анализ, №5, 2004, с. 131-140.

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

Ключевые слова: сеть Петри; функциональная подсеть; декомпозиция

Оценка времени отклика коммутируемой ЛВС с помощью раскрашенных сетей Петри // Труды 5-го семинара и школы по практическому использованию раскрашенных сетей Петри и CPN Tools, Октябрь 8-11, Орхус, Дания, с. 157-167.

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

Ключевые слова: ЛВС; коммутатор; время отклика; раскрашенная сеть Петри

Верификация протокола TCP с помощью декомпозиции модели Петри на функциональные подсети // Труды стендовой сессии 12-го ежегодного симпозиума IEEE / ACM по Моделированию и анализу компьютерных и телекоммуникационных систем, Октябрь 5-7, 2004, Фолендам, Нидерланды, с. 73-75.

Доказана инвариантность модели Петри для фаз установления соединения и разъединения протокола TCP. Выполнена декомпозиция модели Петри на функциональные подсети. Вычисление инвариантов осуществлено в процессе последовательной композиции, что обеспечило существенное ускорение вычислений.

Ключевые слова: TCP, сеть Петри, инвариант, функциональная подсеть

Решение фундаментального уравнения сетей Петри с помощью декомпозиции на функциональные подсети // Труды 11-го семинара "Алгоритмы и программы для сетей Петри", Сентябрь 30 - Октябрь 1, 2004, университет Падерборна, Германия, с. 75-81.

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

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

Ускорение решения линейных систем с помощью декомпозиции на кланы // Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004. Материалы международной научно-технической конференции. Т.1. Таганрог: Изд-во ТРТУ, 2004, с.259-264.

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

Ключевые слова: линейная система: клан; декомпозиция; ускорение вычислений

Верификация протокола ECMA с помощью декомпозиции модели Петри // Труды международной конференции по кибернетике и информационным технологиям, системам и приложениям, Орландо, Флорида, США, Июль 21-25, 2004.

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

Ключевые слова: протокол; сеть Петри; инвариант; функциональная подсеть; декомпозиция

Основанное на декомпозиции вычисление инвариантов сетей Петри // Труды семинара по вычислениям управляемым фишками 25-й международной конференции по приложениям и теории сетей Петри, Болонья, Италия, Июнь 21-25, 2004, с. 79-83.

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

Ключевые слова: сеть Петри; инвариант; декомпозиция; функциональная подсеть

Моделирование коммутируемых ЛВС раскрашенными сетями Петри // Математика и компьютеры в моделировании, том 65, № 3, 2004, с. 245-249.

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

Ключевые слова: локальная вычислительная сеть; коммутатор; сеть Петри; оценка параметров; время отклика

Инварианты временных сетей Петри // Кибернетика и системный анализ, № 2, 2004, с. 92-106.

Построено линейное фундаментальное уравнение временной сети Петри. Введены полные и частичные инварианты состояния и поведения временной сети Петри. Исследованы свойства инвариантных сетей. Показана взаимосвязь полных и частичных инвариантов. Рассмотрены примеры исследования сетевых моделей производственных систем и процессов.

Ключевые слова: временная сеть Петри; фундаментальное уравнение; частичный инвариант; полный инвариант

Моделирование коммутируемой локальной сети раскрашенными сетями Петри // Зв'язок, № 2(46), 2004, с. 56-60. (соавтор Шмелёва Т.Р.)

Изучены вопросы моделирования коммуникационных устройств раскрашенными сетями Петри. Построены модели коммутатора Ethernet, сервера и рабочей станции. Кроме того, раскрашенными сетями Петри представлены алгоритмы динамического ведения таблицы коммутации. Для имитации динамики и анализа свойств модели применена промышленная моделирующая система Design / CPN. Результаты проиллюстрированы на примере построения модели конкретной заданной локальной сети.

Ключевые слова: локальная вычислительная сеть; коммутатор; сеть Петри; оценка параметров; динамическая таблица коммутации

Инвариантность модели Петри протокола TCP // Труды Одесской национальной академии связи им. А.С.Попова, № 2, 2004, с. 19-27.

Доказана инвариантность модели Петри для фаз установления соединения и разъединения протокола TCP. Выполнена декомпозиция модели Петри на функциональные подсети. Вычисление инвариантов осуществлено в процессе последовательной композиции, что обеспечило существенное ускорение вычислений.

Ключевые слова: TCP, сеть Петри, инвариант, функциональная подсеть

К вопросу о вычислительной сложности метода Тудика // Искусственный интеллект, № 1, 2004, с. 29-37.

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

Ключевые слова: сеть Петри; инвариант; метод Тудика; двойная экспонента; эффект заливки

Теоретическое обоснование метода Тудика // Научные труды Донецкого государственного технического университета, серия "Информатика, кибернетика и вычислительная техника", Вып. 74, 2004, с. 286-293.

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

Ключевые слова: диофантово уравнение; линейная система; неотрицательное решение; сеть Петри; инвариант

Декомпозиция протокола ECMA // Радиотехника: Всеукр. межведомств. науч.-техн. сб. 2004, Вып. 138, c. 130-137.

Выполнена декомпозиция модели Петри протокола ECMA на минимальные функциональные подсети, левую и правую взаимодействующие системы, подсети установления соединения и разъединения. Инвариантность исходной модели доказана на основе установленной инвариантности функциональных подсетей. Изоморфность некоторых подсетей позволила вычислить инварианты в процессе последовательной композиции сети. Выполнена оценка ускорения вычислений при использовании композиционных методов нахождения инвариантов.

Ключевые слова: телекоммуникационный протокол; сеть Петри; инвариант; декомпозиция; функциональная подсеть

Верификация протоколов Ethernet // Труды Одесской национальной академии связи им. А.С.Попова, № 1, 2004.

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

Ключевые слова: телекоммуникационный протокол; сеть Петри; инвариант; композиция; функциональная подсеть

Инварианты функциональных подсетей // Труды Одесской национальной академии связи им. А.С.Попова, № 4, 2003, с. 57-63.

Представлен метод вычисления инвариантов сетей Петри, основанный на декомпозиции заданной сети на функциональные подсети. Метод состоит в вычислении инвариантов функциональных подсетей и последующем восстановлении инвариантов исходной сети. Получено экспоненциальное ускорение вычислений. Результаты проиллюстрированы на примере.

Ключевые слова: сеть Петри; инвариант; композиция; функциональная подсеть

Моделирование коммутируемых ЛВС раскрашенными сетями Петри // Труды Европейской конференции по моделированию, Неаполь, Италия, октябрь 27-29, 2003, с. 485-489.

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

Ключевые слова: локальная вычислительная сеть; коммутатор; сеть Петри; оценка параметров; время отклика

Формальное обоснование метода Тудика // Труды 10-го семинара "Алгоритмы и программы для сетей Петри".- Айхштадт, Германия, сентябрь 26-27, 2003, с. 184-190.

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

Ключевые слова: диофантово уравнение; линейная система; неотрицательное решение; сеть Петри; инвариант

Подсети с входными и выходными позициями // Бюллетень новостей по сетям Петри, Том 64, апрель 2003, с. 3-6. История картинки с обложки.

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

Ключевые слова: сеть Петри; функциональная подсеть; декомпозиция; алгоритм

Синтез функций непрерывной логики заданных таблично // Кибернетика и системный анализ, № 2, 1998, с. 47-56. (соавторы Сарбей В.Г., Слепцов А.И.)

Построен полиномиальный алгоритм, позволяющий выполнить синтез функции непрерывной (нечёткой) логики по заданной таблице выбора. Любая функция непрерывной логики может быть задана таблицей выбора. Определены условия, при выполнении которых таблица выбора задаёт некоторую функцию непрерывной логики.

Ключевые слова: непрерывная логика; нечёткая логика; таблица выбора; синтез функции; конституэнта максимума

Уравнение состояний и эквивалентные преобразования временных сетей Петри // Кибернетика и системный анализ, № 5, 1997, с. 59-76. (соавтор Слепцов А.И.)

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

Клычевые слова: временная сеть Петри; многоканальный переход; уравнение состояний; передаточная функция; функциональная эквивалентность

Визуализация производственных процессов в инструментальной системе диспетчера машиностроительного предприятия // Автометрия, 1990, № 4, с.90-93. (соавтор Слепцов А.И.)

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

Ключевые слова: оперативное планирование; сеть Петри; расписание; работы; ресурсы