Cтраница 2
Применяют для разделения исходной общей задачи на локальные подзадачи. При этом возможны два варианта: 1) последовательная декомпозиция и преобразование исходной задачи в цепочку подзадач; 2) параллельная декомпозиция. [16]
В ряде случаев порядок выделенного подграфа ( пустого или полного), являющегося некоторым промежуточным результатом решения любой из названных задач, может служить оценкой сложности ожидаемого результата. По величине оценки можно судить о целесообразности получения окончательного решения соответствующей оптимизационной задачи, что важно при диалоговом режиме выполнения алгоритма. Например, в случае параллельной декомпозиции автомата, которая применяется с целью сокращения размерности задач синтеза, порядок наибольшего пустого подграфа есть оценка числа состояний наиболее сложной компоненты в получаемой сети автоматов. Если эта величина незначительно отличается от числа состояний заданного автомата, то нет смысла решать задачу параллельной декомпозиции, так как указанная цель не будет достигнута. [17]
Некоторые методы, рассмотренные в настоящей главе, удалось разработать благодаря существованию аналогичных классических результатов. Галуа рассматривал примерно в 1830 г. Основная конструкция параграфа 5 в матричной форме известна с 1900 г. как фробениусовское мономиальное представление. Аналогом параллельного соединения для линейных динамических систем является приведение к нормальной форме. Соответствующая теория была развита К. Жорданом примерно в 1880 г. Для нас, однако, эти нормальные координаты - причина некоторой неудовлетворенности. Казалось бы, они должны появляться в линейном аналоге теории каскадной декомпозиции, но пока еще не ясно, как их можно получить с помощью методов, рассмотренных ранее. Трудность состоит в том, что в случае параллельной декомпозиции приходится прибегать к более мощному аппарату. [18]