8 Логическая структура алгоритма. (лса)

Логическая структура алгоритма определяет последовательность выполнения элементарных программных блоков в зависимости от условий, которые вычисляются внутри самих программных блоков.

ЛСА может быть задана графом либо матрицей переходов соответствующей SM. Существует несколько видов SM: SM общего вида; последовательностная SM; SM в виде БСА.

а) SM общего вида или просто SM= , где U – вычисляемые условия, выполнение условия (наступления события) определяются истинностью/ложью соответствующим предиката, П – множество элементарных программных блоков, S – состояния, абстрактные объекты (объекты не подлежащие программированию), которые служат для организации различных последовательностей вычисления по правилам Р вида , где На рис. 3 а, б показана ЛСА для задачи порождения L = aⁿb^n.

б) Последовательностная SM отличается от SM тем, что каждому состоянию соответствует элементарный программный блок.

с правилами вида

Существует двустороннее эквивалентное преобразование , эквивалентное в смысле алгоритма решения одной и той же задачи. На рис.3 в показана ЛСА в виде ПSM решающая задачу порождения L = aⁿbⁿ.

Можно видеть, что ПSM имеет пять состояний (соответствующая SM имеет три состояния). Эквивалентность обеспечивается эквивалентностью программных блоков.

ЛСА в виде ПSM обладает заметным удобством, которое превращает ПSM в программную строку. Для этой цели рассматриваются строки общего вида , они содержат более чем два перехода, которые совершаются по ключам (см. рис.3 г, д). Также как для строки Ляпунова, существуют эквивалентные SW, которые получаются перестановкой операторов и введением соответствующих безусловных переходов ().

Рис. 3. Порождение слов :

а) SM общего вида;

б) матрица переходов SM общего вида;

в

Программные бло- Эквивалентные

ки последователь- соотношения

ностной SM SM и ПSM

П_Ra – запись «а»; П₁  П_Ra П_RR

П_Rb – запись «b»; П₂  П_Rb П_RR

ПL_a – запись «а»; П₃  П_Lb П_RL

П_Lb – запись «b»; П₄  П_La П_LL

П_RR – сдвиг указателя

вправо

П_LL – сдвиг указателя

влево

)

е₀ – событие, соответствующее

тождественно истинному условию.

г)

д)

Рис. 3. Порождение слов :

в) последовательная SM (ПSM)

г) SW-строка (с переходами по ключам К₁ и К₂) программы;

д) SW-строка с перестановкой программных блоков П_RR и П_LL.

9 Структурное (структурированное) программирование.

В начале 70–х годов Дейкстра предложил принцип последовательного уточнения логической структуры алгоритмов. Внутреннее содержание каждого программного блока в БСА уточняется одним из четырёх способов, показанных на рисунке.

begin begin begin begin

begin begin begin begin

A₁ if R then A₁ while R do A₁ repeat A₁

end else A₂; end until R

begin end end end

A₂ end end end

еnd

end

Рис.4 Структуризация по Дейкстре.

Свойства структуризации по Дейкстре.

1. «один вход –один выход». Каждый программный блок имеет единственную точку входа (а) по управлению и единственную точку выхода (b). Например, выходы b₁ и b₂ (при структуризации типа «альтернатива») объединяются в один выход из блока А. В цикле с постусловием входная точка a₁ объединяет два входа;

2. запрет «GO TO» Запрещается употребление оператора «go to» при уточнении логики работы программных блоков.

Структурное программирование иногда называют программированием без «GO TO». На самом деле, оператор безусловного перехода необходим только для отображения графа ЛСА в строку Ляпунова для указания следующего программного блока. Структурированная по Дейкстре программа обладает свойством локализации логических переходов только в теле соответствующего программного блока, что даёт возможность эффективного поиска ошибок при построении автоматических отладчиков.

12