DRAKON.SU

Текущее время: Четверг, 28 Март, 2024 13:43

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ 1 сообщение ] 
Автор Сообщение
 Заголовок сообщения: Граф-схема алгоритма
СообщениеДобавлено: Четверг, 08 Август, 2019 19:38 

Зарегистрирован: Воскресенье, 24 Февраль, 2008 15:32
Сообщения: 5846
Откуда: Москва
Цитата:
Граф-схема алгоритма
Материал из Википедии — свободной энциклопедии

Ждущая вершина алгоритма
Граф-схема алгоритма (ГСА) — конечный связный ориентированный граф {\displaystyle G=\left\langle A,V\right\rangle } G=\left\langle A,V\right\rangle , вершины которого {\displaystyle a_{i}\in A,i={\overline {1,N}}} a_{i}\in A,i=\overline {1,N} соответствуют операторам, а дуги {\displaystyle v_{k}=\left(a_{i},a_{j}\right)\in V,k={\overline {1,M}},i,j={\overline {1,N}}} v_{k}=\left(a_{i},a_{j}\right)\in V,k=\overline {1,M},i,j=\overline {1,N} задают порядок следования вершин (операторов) алгоритма, где {\displaystyle N=\left|A\right|} N=\left|A\right| — число вершин графа, {\displaystyle M=\left|V\right|} M=\left|V\right| — число дуг. В более широком смысле вершинам графа соответствуют не только операторные вершины, но и условные, начальная и конечная вершины и т. д. При рассмотрении параллельных алгоритмов вводится понятие параллельной граф-схемы алгоритма (ПарГСА), в состав которой входят вершины распараллеливания/синхронизации, функциональность которых обычно совмещается. Иногда[1][2][3] в состав ГСА вводятся вершины дополнительных типов: объединения альтернативных дуг (парная вершина для условной вершины), фиктивные операторные вершины, вершины маркировки (с целью обеспечения возможности моделирования выполнения алгоритма сетью Петри), ждущие вершины.

Однако не любой ориентированный граф, составленный из вершин указанных выше типов, может быть отождествлен с корректным алгоритмом. Например, из операторной вершины не может выходить более одной дуги. Поэтому на практике обычно ограничиваются рассмотрением подкласса граф-схем алгоритмов, удовлетворяющих свойствам безопасности, живости и устойчивости.[4] Алгоритмы преобразования ГСА, являющиеся подмножеством алгоритмов обработки графов общего вида, зачастую имеют существенные отличия ввиду использования особых свойств ГСА, что позволяет их упрощение, снижение временной или ёмкостной сложности.[1][3][5]

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

См. также

Граф потока управления

Примечания

Ватутин Э. И., Зотов И. В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов. Известия курского государственного технического университета. Курск. № 2. С. 85–89. (2004). Архивировано 28 апреля 2012 года.
Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
Закревский А. Д. О корректности параллельных алгоритмов логического управления // Известия АН СССР. Техническая кибернетика. — 1987. — № 4. — С. 106—112.
Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления. Информационно-измерительные и управляющие системы. № 11, Т. 7. М.: «Радиотехника». С. 49–56. (2009). Архивировано 28 апреля 2012 года.

Ссылки
Баранов С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Л.: Энергия, 1979. 232 с.
Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989. 328 с.
Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. Под ред. В. И. Варшавского. М.: Наука, 1986. 400 с.
Гост


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2008-2024, участники конференции «DRAKON.SU», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB