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

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

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

ЛСА может быть задана графом либо матрицей переходов соответствующей 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, которые получаются перестановкой операторов и введением соответствующих безусловных переходов (w).

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

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

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

Программные бло- Эквивалентные ки последователь- соотношения ностной SM SM и ПSM ПRa – запись «а»; П 1 º ПRa× ПRR ПRb – запись «b»; П 2 º ПRb× ПRR ПLa – запись «а»; П 3 º ПLb× ПRL ПLb – запись «b»; П 4 º ПLa× ПLL ПRR – сдвиг указателя вправо ПLL – сдвиг указателя влево

в)

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

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

г)

д)

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

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

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

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

В начале 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 Структуризация по Дейкстре.