Категория:Сводимые и регуляризуемые графы

Материал из WEGA
Версия от 11:48, 4 сентября 2019; KVN (обсуждение | вклад) (Новая страница: «Регуляризуемые графы представляют собой наиболее общий тип граф-моделей структурирова…»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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