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

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

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

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

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

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

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

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

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

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

Частные ГСА₁, ГСА₂, ГСА₃ приведены на рис. 26.1