Название: Программирование - Методические указания(М.Г. Гриф)

Жанр: Информатика

Просмотров: 1165


Элементы теории структурного программирования

 

Блок-схемы программ. Блок-схема – это направленный граф, который указывает порядок выполнения операторов программы. Каждый оператор программы представляет собой вершину графа (узел), а каждое возможное направление передачи управления – линию. Если оператор управления при своем выполнении не воздействует на данные, то он является чистым оператором управления, в противном случае выполнение оператора сопровождается изменениями данных. Имеется три разновидности узлов блок-схемы. Если узел имеет один вход и один выход, его называют функциональным узлом. Такой узел обозначается прямоугольником, при этом функция f, указываемая в прямоугольнике, является типичным оператором присваивания:

Термин «функциональный узел» здесь особенно уместен, так как любой оператор присваивания по своему воздействию на данные полностью эквивалентен математической функции.

Если узел блок-схемы имеет один вход и два выхода и является чистым оператором управления, его называют предикатным узлом. Ромб, обозначающий такой узел, содержит имя предиката p:

Предикатный узел определяет порядок выполнения программы в соответствии с тем, какое значение принимает предикат – истина (1) или ложь (0), и никаких действий на данные не оказывает.

Естественно, кроме того, ввести узел с двумя входами и одним выходом. Такой узел изображается на блок-схеме кружком и называется узлом слияния. Узел слияния никаких действий на данные не оказывает:

Фактически  узел блок-схемы может содержать более двух входных линий. Узлы с произвольным количеством входов можно изобразить в виде последовательности узлов слияния:

Простые программы. Простая программа – это программа с управляющей структурой, обладающей следующими особенностями:

имеется только один вход и один выход;

через каждый узел проходит путь от входа к выходу структуры.

Второе свойство определяет недопустимые управляющие структуры, показанные на рис. 1, которые содержат либо недостижимые узлы, либо бесконечные циклы.

Простая программа может быть формально представлена (укрупнена, абстрагирована) в виде одного функционального узла. Функциональный узел обобщает суммарное действие операций и тестов простой программы, которую он представляет. Например, простая программа (рис. 2) может быть представлена в виде

(рис. 3), где узел g является абстракцией простой программы (рис. 4) и узел h абстрагирует простую программу (рис. 5). Полученная простая программа (рис. 3) может быть затем сведена к единственному узлу

 

Рис. 1

 

Рис. 2

 

Рис. 3

 

 

Рис. 4

 

Рис. 5

 

И, наоборот, любой функциональный узел программы может быть расширен без оказания влияния на другие части программы. Например, только что полученный функциональный узел может быть преобразован в следующую схему (рис. 6), которая после раскрытия узлов g и h принимает вид (рис. 7). Части программ, которые сами являются простыми программами, называют простыми подпрограммами. Примером таких подпрограмм являются подпрограммы g, h, a, b, c и d программы k. Предикаты p, q, s и t не относятся к простым подпрограммам, так как каждый из них имеет два выхода.

Рис. 6

 

Рис. 7

 

Схемы выполнения. Блок-схема программы определяет последовательность ее выполнения по путям и циклам. Последовательность выполнения программы удобно представить в виде конечного дерева или схемы выполнения (E-схемы). Если мы имеем блок-схему программы, то E-схему из узлов и линий управления можно построить по следующему алгоритму/

Начать создание E-схемы с входной линии и связанного с ней предикатного, функционального узла или узла слияния блок-схемы программы.

На каждом шаге построения рассматривать каждый путь выполнения (ориентированная цепь из линий и узлов, инцидентная (примыкающая) входной вершине) в E-схеме. Если рассматриваемый путь выполнения заканчивается непосредственно функциональным, предикатным узлом или узлом слияния, ранее не входившим в этот путь, то все выходные линии таких узлов (из блок-схемы) и узлы, с которыми эти линии соединены, если таковые имеются, включить в путь выполнения.

Формирование E-схемы считать законченным, если все пути выполнения заканчиваются выходными линиями или узлами.

Ясно, что такая процедура завершается построением конечного дерева, так как все пути в результате будут состоять только из узлов блок-схемы.

Выполнение блок-схемы соответствует выполнению путей ее E-схемы с учетом правила передачи управления повторяющегося пути из его конечного узла в начальный. Блок-схема не имеет циклов только тогда, когда ее E-схема не имеет повторяющихся путей выполнения. Кроме того, все узлы слияния, кроме находящихся на повторяющемся пути, могут быть из E-схемы удалены.

Дерево выполнения (Е-дерево) программы – это дерево, пути которого изображают все возможные последовательности реализации блок-схемы без возврата назад. Если блок-схема не имеет циклов, то соответствующая конечная E-схема является и

Е-деревом. Если же циклы входят в блок-схему, то Е-дерево

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

 

 

Рис. 8

 

Рис. 9

 

имеет E-схему (рис. 9), которую можно расширить до Е-дерева (рис. 10).

 

Рис. 10

 

Элементарные программы. Элементарной программой называется простая программа, которая не содержит простых подпрограмм более чем из одного узла. Например, программа

является элементарной, а программа

относится к простым, но не элементарным, так как имеет простые подпрограммы более чем из одного узла.

Типовые структуры. К типовым структурам структурного программирования относят следующие элементарные программы (рис. 11).

Известно, что любую простую программу можно за конечное число шагов преобразовать в составную программу, сгенерированную из элементарных программ базисного множества, например, «Последовательность», «Развилка», «WHILE DO». Генерация составных программ заключается в последовательной замене функциональных узлов на элементарные программы, начиная с единственного функционального узла.

 

Рис. 11

Структурные технологии проектирования программ. Суть структурных технологий разработки программ заключается в конструировании программы из конечного набора типовых структур (конструкций языка программирования) на основе применения процедур композиции (синтеза) и декомпозиции (анализа). Такой подход позволяет стандартизировать этапы разработки программного обеспечения, делает программу понятной не только разработчику и дает возможность выявить большую часть ошибок на этапе проектирования, а не отладки.

Нисходящее проектирование. Формальная схема нисходящего проектирования на языке блок-схем имеет следующий вид. На начальном этапе программист представляет программу в виде одного функционального узла. Затем, на основе анализа задачи производит его декомпозицию (замену) на простую программу, желательно на некоторую из типовых структур (рис. 11). После чего вновь анализирует полученную простую программу, декомпозирует новые функциональные узлы и т.д. Процесс прекращается, когда проводить декомпозицию уже нет смысла – задача решена.

Восходящее проектирование. При восходящем проектировании программист строит систему из уже готовых программных модулей (простых программ). Проверка правильности полученной программы осуществляется на самом последнем этапе, когда она уже написана. Очевидное преимущество нисходящего проектирования перед восходящим заключается в том, что оно протекает шаг за шагом, с постоянным контролем правильности программы в целом. На практике обычно применяется комбинированный метод проектирования, в котором внутри схемы нисходящего проектирования для не очень сложных подзадач используется схема восходящего проектирования.

Методы доказательства правильности программ. Программная функция программ. Для проверки (теоретической) правильности программы используют программную функцию программ, которая устанавливает связь между состояниями данных до и после выполнения программы. Например, программная функция для программы, состоящей из одного функционального узла f имеет вид [P] = {(x,y)| y = f(x)}, где x – вход, а y – выход узла f (программы). Программа, состоящая из последовательности двух функциональных узлов g и h

,

имеет программную функцию в виде композиции указанных частных функций

[P] = {(x,z)| z=h(g(x))}, где g={(x,y)}, а h={(y,z)}.

Приведем пример блок-схемы программы без циклов (рис. 12) и соответствующей ей Е- схемы (рис.13).

Тогда программная функция имеет вид:

[P] = {(x,y)|

p1(x) и p2°f1(x) и y=f2°f1(x), или                                                  (1)

p1(x) и ~p2°f1(x) и p3°f3°f1(x) и y=f2°f3°f1(x), или                   (2)

p1(x) и ~p2°f1(x) и ~p3°f3°f1(x) и y=f3°f1(x), или               (3)

~p1(x) и p3°f3(x) и y=f2°f3(x) , или                                               (4)

~p1(x) и ~p3°f3(x) и y=f3(x)}.                                                        (5)

Рис. 12

 

Методика составления программных функций для циклических программ в основном аналогична методике составления программных функций программ без циклов. Отличие состоит в том, что для каждого повторяющегося j-го узла слияния в Е-схеме программы вводится функция Fj, которая определяет функцию всех узлов, следующих за узлом j.

Рассмотрим пример (рис. 14). Соответствующая Е-схема приведена на рис. 15. Узлы слияния 1 и 2 заменены функциями F1 и F2 (рис. 16).

Тогда имеем [P] = F1, где

F1={(x,y)| y=F2°f1(x)},

F2={(x,y)|

p1°f2(x) и y=F1°f3°f2(x), или

~p1°f2(x) и p2°f2(x) и y=f2(x), или

~p1°f2(x) и ~p2°f2(x) и y=F2°f4°f2(x)}.

Существует два понятия эквивалентности программ. Если две программы имеют тождественные Е-деревья, то они эквивалентны по выполнению. Если две программы имеют две тождественные программные функции, то они функционально эквивалентны. Эквивалентность по выполнению предполагает функциональ-ную эквивалентность, но не наоборот.

Рис. 13

 

Рис. 14

Доказательство правильности программы достигается сравнением того, что должна делать программа (программной функции для одного функционального узла, описывающего постановку задачи) и построенной для нее программной функции программ. Построение программной функции облегчается тем, что программные функции для типовых структур известны, а исходная программа представима в виде суперпозиции (композиции) указанных структур.

Рис. 15

 

 

Рис. 16