Моделирование параллельных процессов, Сети Петри, Мараховский В.Б., Розенблюм Л.Я., Яковлев А.В., 2014

Моделирование параллельных процессов, Сети Петри, Мараховский В.Б., Розенблюм Л.Я., Яковлев А.В., 2014.

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




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

В качестве примера рассмотрим асинхронный процесс, граф которого представлен на рис. 1.4а. На рис. 1.46 показано отношение F для классов эквивалентности множества ситуаций этого асинхронного процесса.

ОГЛАВЛЕНИЕ.
ОТ АВТОРОВ.
ВВЕДЕНИЕ.
СОКРАЩЕНИЯ, ПРИНЯТЫЕ В ТЕКСТЕ.
ГЛАВА 1. АСИНХРОННЫЙ ПРОЦЕСС.
1.1. ОПРЕДЕЛЕНИЕ АСИНХРОННОГО ПРОЦЕССА.
Понятие асинхронности.
Концепция асинхронного процесса.
Спецификация асинхронного процесса.
Протокол асинхронного процесса.
1.2. КЛАССИФИКАЦИЯ.
Автономный асинхронный процесс.
Эффективный асинхронный процесс.
Управляемый асинхронный процесс.
Простой асинхронный процесс.
1.3. РЕПОЗИЦИЯ.
Композиция асинхронного процесса и его репозиции.
Приведенный асинхронный процесс.
Конвейерный асинхронный процесс.
1.4. СТРУКТУРИРОВАНИЕ.
1.5. РЕДУКЦИЯ.
Редукция по инициатору.
Редукция по результанту.
Редукция по входной компоненте ситуации.
Редукция по выходной или внутренней компоненте.
1.6. КОМПОЗИЦИЯ.
Параллельная композиция.
Последовательная композиция.
Замыкание.
1.7. КОММЕНТАРИЙ. НЕДОСТАТКИ МОДЕЛИ АСИНХРОННОГО ПРОЦЕССА.
1.8. УПРАЖНЕНИЯ.
ГЛАВА 2. СЕТИ ПЕТРИ.
2.1. РЕТРОСПЕКТИВА СЕТЕЙ ПЕТРИ.
2.2. ОПИСАНИЕ МОДЕЛИ.
2.3. ДИАГРАММА МАРКИРОВОК.
Отношения между событиями.
Сети Петри как модельная интерпретация асинхронных процессов.
Два начала сетей Петри: статическое и динамическое.
2.4. КЛАССИФИКАЦИЯ СЕТЕЙ ПЕТРИ.
Зачем нужна классификация сетей Петри.
Классификация по динамическим ограничениям.
Классификация по статическим ограничениям.
2.5. ЗАДАЧИ И АЛГОРИТМЫ АНАЛИЗА.
2.5.1. Первая группа методов анализа.
Задача достижимости.
Модификации задачи достижимости.
Алгоритм порождения диаграммы маркировок.
Свойства диаграмм маркировок.
Сводимость задач достижимости.
Задача живости Сети Петри.
2.5.2. Вторая группа методов анализа.
2.5.3. Третья группа методов анализа.
Дедлоки.
Ловушки.
2.5.4. Оценки вычислительной сложности проблем анализа сетей Петри.
2.6. АНАЛИЗ: МАТРИЧНЫЙ ПОДХОД.
Анализ на свойства структурной ограниченности и живости.
Инвариантные и согласованные сети Петри.
Решение задачи достижимости.
2.7. ФУНКЦИОНАЛЬНЫЕ ВОЗМОЖНОСТИ.
Сведения из теории формальных грамматик и языков.
Генерирование формальных языков сетями Петри.
2.8. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ СЕТЕЙ ПЕТРИ. ИНТЕРПРЕТАЦИЯ СЕТЕЙ ПЕТРИ.
Пример спецификации конечного автомата сетью Петри.
Использование сетей Петри в параллельном программировании.
Пример моделирования аппаратных средств.
Моделирование конвейерных процессов.
2.9. УПРАЖНЕНИЯ.
ГЛАВА 3. ДРУГИЕ СЕТЕВЫЕ МОДЕЛИ, РОДСТВЕННЫЕ СЕТЯМ ПЕТРИ.
3.1. СЕТИ СО ВЗВЕШЕННЫМИ ДУГАМИ.
Преобразование сети с взвешенными дугами в ординарную сеть Петри.
Пример спецификации химической реакции сетью с взвешенными дугами.
Проверка отсутствия маркера в некоторой позиции.
3.2. РАСКРАШЕННЫЕ СЕТИ.
3.3. СЕТИ С ТОРМОЗЯЩИМИ ДУГАМИ (ИНГИБИТОРНЫЕ СЕТИ ПЕТРИ).
3.4. ПРИОРИТЕТНЫЕ И ВРЕМЕННЫЕ СЕТИ.
3.5. СИНХРОННЫЕ И САМОМОДИФИЦИРУЕМЫЕ СЕТИ.
3.6. СТОХАСТИЧЕСКИЕ СЕТИ ПЕТРИ.
3.7. ОЦЕНОЧНЫЕ СЕТИ.
Примитивы оценочных сетей.
Мотивы появления оценочных сетей.
3.8. СЕТИ ПОТОКОВ ДАННЫХ.
3.9. РАЗРЕШИМОСТЬ ЗАДАЧ АНАЛИЗА.
3.10. УПРАЖНЕНИЯ.
ГЛАВА 4. ДИНАМИЧЕСКАЯ ЛОГИКА.
4.1. ДИАГРАММЫ ПЕРЕХОДОВ И ИХ КЛАССИФИКАЦИЯ.
Состояния бинарной диаграммы переходов.
Бифуркантное состояние.
Классы диаграмм переходов.
4.2. СХЕМЫ МАЛЛЕРА.
Гипотезы о задержках в логических элементах и проводах.
Самосинхронные схемы.
Диаграммы Маллера.
Понятие динамической логики.
Задача построения рабочего цикла.
4.3. МАРКИРОВАННЫЕ ГРАФЫ.
4.4. СИГНАЛЬНЫЕ ГРАФЫ.
Построение кумулятивной диаграммы по маркированному графу.
Свойства кумулятивных диаграмм.
Связь сигнальных графов с диаграммами переходов.
Нормальность сигнального графа.
Понятия одновременности и предшествования сигналов.
Анализ сигнального графа на свойства регулярности и нормальности.
4.5. УПРАЖНЕНИЯ.
ГЛАВА 5. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ. ЗАДАЧИ КООРДИНАЦИИ И СИНХРОНИЗАЦИИ ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ.
5.1. АНОМАЛИИ ДИНАМИКИ.
Поведенческий и структурный дедлоки.
Эффект “каннибализма”.
Эффект “голодной смерти”.
Свойства “справедливости” и “голодания".
5.2. ЗАДАЧА ОБ ОБЕДАЮЩИХ ФИЛОСОФАХ.
5.3. ЗАДАЧИ ВЗАИМНОГО ИСКЛЮЧЕНИЯ И СЕМАФОРЫ.
Семафоры Дейкстры.
Семафоры Цикритзиса и Бринч-Хансена.
Семафоры Агервапы и Вентилборга.
5.4. ЗАДАЧА “ПРОИЗВОДИТЕЛИ - ПОТРЕБИТЕЛИ”.
Фрагмент спецификации Г. Дейтела.
Программа Д. Цикритзиса и Ф. Бернстайна.
5.5. ЗАДАЧА “ЧИТАТЕЛИ - ПИСАТЕЛИ”.
5.6. ЗАДАЧА О КУРИЛЬЩИКАХ.
5.7. МЕХАНИЗМ РАНДЕВУ.
5.8. СЕМАНТИКА ВЗАИМОДЕЙСТВУЮЩИХ ПРОЦЕССОВ.
Пошаговая детализация действий программ.
Взаимные переходы между двумя формами семантик.
Проверка условий справедливого решения конфликта.
Выводы.
5.9. ЗАКЛЮЧЕНИЕ.
5.10. УПРАЖНЕНИЯ.
ГЛАВА 6. ПРИНЦИПЫ АППАРАТНОЙ РЕАЛИЗАЦИИ.
6.1. ОСОБЕННОСТИ САМОСИНХРОННОЙ СХЕМОТЕХНИКИ.
6.2. СИНТЕЗ ПО МОДЕЛИ МАЛЛЕРА.
Редукция диаграммы переходов.
Кратные состояния.
Проверка спецификации на полумодулярность.
Проекции диаграмм переходов.
Устранение противоречивости диаграмм переходов.
Свойства логических переменных полумодулярных диаграмм переходов.
Стандартные реализации самозависимых переменных.
Метод совершенной реализации схемы Маллера.
6.3. СТАНДАРТНЫЕ РЕАЛИЗАЦИИ ФРАГМЕНТОВ СЕТЕЙ ПЕТРИ.
Реализация многовходовых С-элементов Маллера.
Моделирование продвижения маркера в сети Петри элементом Давида.
Прямая трансляция сетей Петри в логические схемы.
Минимальный базис реализации сетей Петри методом прямой трансляции.
6.4. ПРИНЦИПЫ КОМПОЗИЦИИ.
6.4.1. Дополнительные модули.
Модуль преобразования фазовой дисциплины.
Модуль многократного вхождения оператора.
Модуль управления циклом.
6.4.2. Реализация неустойчивых сетей Петри.
Реализация сетей Петри с вершинами свободного выбора.
Явление электронного арбитража.
Электронные арбитры.
Ограниченные арбитры.
Неограниченные арбитры.
Реализация неустойчивых ограниченных сетей Петри.
6.5. УПРАЖНЕНИЯ.
ГЛАВА 7. ПРОТОКОЛЫ ИНФОРМАЦИОННОГО ОБМЕНА.
7.1. КЛАССИФИКАЦИЯ ИНТЕРФЕЙСОВ.
7.1.1. Классификация по топологии.
Интерфейсы с кольцевой структурой.
Интерфейсы с радиальной структурой.
Интерфейсы с магистральной структурой.
Интерфейсы со смешанной структурой.
7.1.2. Классификация по способу передачи данных.
7.1.3. Классификация по принципу реализации.
Синхронные интерфейсы.
Асинхронные интерфейсы.
Самосинхронные интерфейсы.
7.1.4. Классификация интерфейсов по назначению.
7.2. ЗАДАНИЕ ПРОТОКОЛОВ.
7.2.1. Протокол чтения данных в интерфейсе «Общая шина».
7.2.2. Примерная процедура проектирования протокола.
7.2.3. Разработка описания протокола, его анализа и реализации. Оценка сложности аппаратной и программной поддержки протокола.
Сервисный уровень протокола.
Построение структурной модели интерфейсного протокола.
Формализация описания интерфейсного протокола.
Синтез средств сопряжения.
Реализация протоколов.
7.2.4. Формальная модель протокола информационного обмена физического уровня.
7.2.5. Пример использования сети Петри для задания протокола обмена.
7.3. ВЕРИФИКАЦИЯ ПРОТОКОЛОВ.
7.3.1. Верификация эффектов взаимодействия.
Выбор способа анализа протокола.
Выбор совокупности желаемых эффектов.
7.3.2. Выявление свойств протоколов.
Анализ асинхронного протокола «чередующегося бита».
Модель с идеальным каналом.
Модель с искажением сообщения в канале.
Модель с потерей сообщений.
Модель с ложным срабатыванием механизма таймаута.
Модель без ограничений на емкость канала и число срабатываний таймаута.
Модель с буферированным каналом.
7.3.3. Описание протоколов сигнальными графами и диаграммами переходов.
7.4. УПРАЖНЕНИЯ.
ГЛАВА 8. ПРИМЕРЫ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ.
8.1. ЛОГИЧЕСКОЕ УПРАВЛЕНИЕ.
Первый пример — "Управление манипулятором".
Второй пример — "Управление движением вагонеток".
8.2. ПРОТОКОЛЫ АСИНХРОННЫХ СХЕМ.
8.3 ИНФОРМАЦИОННЫЙ ОБМЕН.
8.4. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ.
Пример 1.
Пример 2.
8.5. УПРАЖНЕНИЯ.
ПОСЛЕСЛОВИЕ АВТОРОВ (О В.И. ВАРШАВСКОМ И СТАНОВЛЕНИИ СОВЕТСКОЙ/РОССИЙСКОЙ НАУЧНОЙ ШКОЛЫ).
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ.
СПИСОК ЛИТЕРАТУРЫ.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Моделирование параллельных процессов, Сети Петри, Мараховский В.Б., Розенблюм Л.Я., Яковлев А.В., 2014 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - pdf - Яндекс.Диск




Теги: учебник по математике :: математика :: Мараховский :: Розенблюм :: Яковлев :: сети Петр