Сеть автоматов для моделирования асинхронного взаимодействия процессов

• Автор: Новик, Константин Валерьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Москва
• Количество страниц: 120 с. : ил.

ГЛАВА 1 ВВЕДЕНИЕ В СИСТЕМЫ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ

1.1 Сеть Петри для моделирования асинхронного взаимодействия процессов при использовании общих ресурсов

1.2 Сети с накоплениями событий

1.3 Сети с распознающими предикатами

1.4 Вычислительные сети (СІЧ)

1.5 Самосинхронизирующисся сети (вІЧ)

1.6 Асинхронные преобразующие сети

1.7 Высказывательная (пропозиционная) сеть для экспертных систем

1.8 Выводы по главе

ГЛАВА 2 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ТЕОРИИ и01ЫЕИ-СЕТЕЙ

2.1 Концептуальная интерпретация Лнпег-сетей и взаимосвязей их элементов

2.2 Формальная система, порождающая правильно построенные формулы ЛЧ
2.3 Матричная форма представления Ж
2.4 Проблемы анализа сетей и формы их представления, удобные для анализа
2.5 Лоіпег-алгебра (склеивающая алгебра)
2.6 Техника работы с Лошег-алгеброй
2.7 Теорема о ярусно-параллельной форме Лоіпег-сети
2.8 Многопроцессорное разложение сетей. Теорема о процессорной декомпозиции. Теорема о композиции локальных сетей
2.9 Формальная интерпретация ЛЧ сетью автоматов

2.10 Внутренняя структура элементарного автомата и правила его работы в сети
2.11 Теорема о «работающей» цепочке
2.12 Выводы по главе
ГЛАВА 3 ИЗВЕСТНЫЕ МОДЕЛИ АСИНХРОННЫХ СИСТЕМ УПРАВЛЕНИЯ ПРОЦЕССАМИ И ИХ ПРЕДСТАВЛЕНИЕ ЗОІИЕЛ-СЕТЬЮ
3.1 Сети Петри (РІЧ)
3.2 Асинхронные цифровые схемы (сети) Маллера (МІЧ)
3.3 Дискретные нейронные сети Мак Каллока-Питтса (УІЧ)
3.4 Семантическая сеть Ван-Хао (¥1Ч)
3.5 Алгебраические сети (АІЧ). Исчисление Эрбрана-Геделя. Вычислительные модели Э. Тыугу
3.6 Ринговые и роторные сети (ЯІЧ, ЛоІЧ)
3.7 Выводы по главе
ГЛАВА 4 МОДЕЛИ РЕАЛЬНЫХ АСИНХРОННЫХ СИСТЕМ, ИСПОЛЬЗУЮЩИХ ЗОтЕЛ-СЕТИ
4.1 Модель, описывающая процессы разрушения древнерусских фресок
4.1.1 Описание модели
4.1.2 Элементы модели
4.1.3 Сеть, описывающая состояние фрески
4.1.4 Пример работы сети
4.2 Модель удаленной Интернет-атаки
4.2.1 Описание модели
4.2.2 Элементы модели
4.2.3 Сеть для моделирования атаки
4.2.4 Пример работы сети
4.3 Модель системы связи канального процессора с двумя абонентами
4.3.1 Описание модели
4.3.2 Сеть, моделирующая систему связи канального процессора с двумя абонентами через адаптер
4.3.3 Пример работы сети
4.4 Модель информационной системы поля боя
4.4.1 Описание модели
4.4.2 Элементы модели
4.4.3 Сеть для четырех подразделений
4.4.4 Пример работы сети
4.5 Модель группового поведения стаи рыб
4.5.1 Описание модели
4.5.2 Элементы модели
4.5.3 Сеть для стаи из пяти рыб
4.5.4 Пример работы сети
4.6 Модель биржевой игры
4.6.1 Описание модели
4.6.2 Элементы модели
4.6.3 Сеть для двух игроков
4.6.4 Пример работы сети
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

Глава 3 Известные модели асинхронных систем управления процессами и их представление Лотег-сетью
В последнее время (90-е годы прошлого столетия и начало нынешнего) разразился настоящий бум исследований, посвященным сетевым моделям и их приложениям для решения различных прикладных задач. Только за последнее десятилетие было предложено более десятка различных математических конструкций сетей, а число публикаций по сетевой проблематике перевалило за тысячу. Разделы по данной тематике включаются в большинство международных конференций по дискретной математике, информатике, искусственному интеллекту, моделированию биологических и социальных систем. Современные учебные курсы по теоретической информатике также содержат разделы, посвященные сетям и, в обязательном порядке, сетям Петри.
Чем объяснить такой интерес математиков и практиков программирования к сетевой парадигме? Все исследователи, работающие по данной тематике, отмечают, что сети являются одним из самых мощных математических инструментов моделирования систем с ярко выраженными распределенными процессами, которые взаимодействуют между собой. В таких системах можно выделить специальные механизмы (асинхронное управление), позволяющие строить сценарии поведения систем во времени.
История развития сетевых моделей насчитывает более полувека. Отметим основные исторические вехи, связанные с сетевыми исследованиями (соответствующие ссылки на публикации будут приведены при дальнейшем изложении).
Первая сеть для исчисления Эрбрана-Геделя была построена Клини в . 1942 году. В том же 1942 году Мак-Коллаком и Питтсом было опубликовано исследование, посвященное дискретным нейронным сетям. Начиная с 1961 года, появляются публикации по самой известной сетевой модели - сетям Петри. В 1962 году американским математиком Маллером был разработан аппарат для проектирования асинхронных цифровых схем, а в 1967 году Котов и Нариньяни предложили сетевую модель асинхронных вычислений над памятью. В 1978 году эстонский математик Тыугу впервые представил . алгебраические сети, которые назвал вычислительными моделями над знаниями.
Глава 3 посвящена обобщению сетевой парадигмы, т.е. представлению самых различных сетей в виде Мпег-сети. В этой главе показано, что в каждой сети может быть выделено нечто общее — формальное (графовое) представление сети и интерпретация элементов сети автоматами. Оказалось,