Объединение граф-схем алгоритмов, страница 2

Алгоритм построения ОГСА состоит из следующих шагов.

1.  Для каждой ГСАq строится соответствующая МСА Mq ().

2.  Каждая МСА Mq кодируется вектором дополнительных переменных , где n определяется из неравенства , а «~» означает, что прямое значение переменной pi или инверсию.

3.  Каждой МСА Mq ставится в соответствии конъюнкция: Pq=, дополнительных переменных Pi (), т. е. код МСА Mq.

Код дополнительных переменных  назначают исходя их соображения, что наиболее связные между собой МСА  и  должны кодироваться соседними кодами Pp и Рq.

Для этого вначале подсчитывают значения коэффициентов связности  () по числу букв в одинаковых элементах  и .

4.  Строится объединенная МСА ОМСА, строки и столбцы которой отмечены всеми операторами, входящими в объединение множеств операторов МСА , …, .

После построения ОМСА, проводят ее минимизацию на основе учета распределения сдвигов. В результате получают минимизированную ОМСА`. Для перехода от ОМСА` к объединенной ОГСА ОМСА` разбивают на подматрицы, выписывают системы формул перехода, которые приводят к минимальной скобочной форме. Строят подграф ГСА для каждой минимальной скобочной формы (СКФ) и путем наложения операторных вершин друг на друга получают ОГСА.

26.2 Пример построения объединенной ОГСА по трем частным ГСА1, ГСА2, ГСА3

Частные ГСА1, ГСА2, ГСА3 приведены на рис. 26.1