Ответ на
»сообщение 5522« (Сергей Перовский)
___________________________
Мы опять упираемся в терминологию...
Я не зря прошу пояснить что с чем синхронно в конечных автоматах.
В электронике используют синхронные и асинхронные схемы.
Различаются тем, что в асинхронных командой на выполнение операции является изменение входных сигналов, а в синхронных - отдельный тактовый импульс.
Примерно в этом смысле мы различали синхронные и асинхронные имитационные модели - является ли событием наступление очередного такта времени или не является.
Хорошо. Давайте попробуем разобраться. Как исполняется (интерпретируется) классическая сеть Петри? По
тактам. Сначала выделяется множество переходов, удовлетворяющих правилу запуска (наличие достаточного числа фишек во входных позициях). Затем из этих переходов (произвольным образом) выбирается один, который и запускается. Он (в соответствии с топологией сети) меняет вектор разметки. После чего процесс повторяется.
Казалось бы и причём тут асинхронность, если переходы запускаются синхронно?
Мы привыкли понимать синхронность (в отношении управления) как одновременность, а асинхронность -- как свободу (в привязке ко времени, включая и такую примитивную как сначала-потом: "делай раз", "делай два"). Сети Петри нас будут интересовать применительно к изучению (моделированию, реализации и т.п.) параллельных активностей (процессов). В этом плане есть две известных схемы:
1. Последовательный поток управления, в котором выделяются точки параллельного ветвления (распараллеливания). Параллельные ветви должны в итоге синхронизироваться, чтобы вернуться в последовательное русло. Это и называют
последовательно-параллельным программированием.
2. Задаётся асинхронный поток (произвольный, "линеаризация" которого суть специфика интерпретации/отображения). Все действия (операторы) программы
изначально считаются независимыми, параллельно исполняемыми, а на них уже накладываются ограничения в отношении порядка исполнения. Это называют
асинхронным программированием.
Терминология не моя. Это позиция новосибирской школы программирования. Такой взгляд развивался с середины 1960-х годов. Довольно подробно всё это разобрано в теперь уже классической книге "Элементы параллельного программирования" (В.А.Вальковский, В.Е.Котов, А.Г.Марчук, Н.Н.Миренков, 1983).
В последовательно-параллельном программировании
первична (априорна) синхронность действий. В асинхронном программировании первична асинхронность. Первое является синхронно-асинхронным. Второе -- асинхронно-синхронным. Асинхронный принцип является в определённом смысле
дополнительным по отношению к последовательно-параллельному. Оба они
эквивалентны в том понимании, что могут моделировать друг друга.
В этом контексте конечные автоматы (в рамках конкретного автомата) хорошо описывают синхронность (последовательность) исполнения, тогда как сети Петри -- асинхронность. Это не означает, что тот и другой аппарат (а конечные автоматы являются
частным случаем сетей Петри: им эквивалентны автоматные сети) не может применяться для противоположных задач (асинхрона для КА и синхрона для СП).
В КА нет разделения на атомарное и составное состояние (оно одно). В сети Петри составное состояние (вектор разметки) состоит из атомарных (значений фишек в каждой позиции). Это даёт возможность гибче работать на этапе моделирования. Если неверно выбрано проектное решение (забыли какие-то состояния), то КА придётся полностью переделывать. В случае же сети Петри достаточно слегка поменять топологию сети (добавить позиции/переходы и дуги, пересмотрев распределение фишек в позициях). Сеть Петри -- это народная тропа. КА -- заасфальтированная трасса. Нет смысла в отлаженной сети Петри (если она сводится к КА) сохранять такую гибкость, если всё устраивает, и проектные ошибки не предвидятся. Т.е. начинать лучше с сетей Петри, а потом смотреть, что из них кристаллизуется в КА, а что лучше оставить в гибкой форме. Сети Петри более "фотогеничны" (более наглядно представляются в графической форме, динамика исполнения видна как на ладони). Но за всё надо платить. КА более компактны. И как любой специализированный инструмент свои задачи решают лучше более универсального. Кроме того, чем меньшей свободой (выразительной мощностью) обладает формализм, тем легче его анализировать (больше возможностей для анализа).
Разумеется, для описания/реализации сложных систем используются конструкты -- ансамбли конечных автоматов, иерархические сети Петри (переход может из себя представлять новую сеть и так далее в глубину). Но это никак не отрицает вышеизложенного. Специфика в первичности, что определяет в итоге и
аспект мышления.
Ответ на
»сообщение 5530« (info21)
___________________________
А вот есть мнение, что богатая, это закольцованная.
Лента или дерево имеют связей на 1 меньше, чем узлов.
Это самые простые по богатству :) системы.
Отсюда богатая структурированность равна числу связей минус число узлов. Если с нуля, то ещё отнять единицу.
