После того, как были рассмотрены возможные способы записи алгоритмов, вполне закономерным представляется вопрос о технологии их разработки. До середины 60-х годов теории разработки алгоритмов не существовало - процесс разработки целиком определялся опытом и искусством программиста. Однако по мере роста сложности программ возникла необходимость создания методологии их разработки, и она появилась в виде структурного программирования. Идеи структурного программирования были высказаны в 1965 г. Э. Дейкстрой, но сведены в некую законченную систему правил они не были. В том же году итальянские математики К. Бом и Д. Джакопини сформулировали теорему о структурности. Прежде, чем рассмотреть ее суть, необходимо ввести некоторые понятия.
Поскольку алгоритм определяет порядок обработки информации, он должен содержать, с одной стороны, действия по обработке, а с другой стороны, порядок их следования, называемым потоком управления.
Рассмотренные выше блоки, связанные с обработкой данных, делятся на простые и условные. Особенность простого действия в том, что оно имеет один вход и один выход, в отличии от условного, обладающим двумя выходами в зависимости от того, истинным ли окажется условие. Простое действие не означает, что оно единственное - это может быть некоторая последовательность действий.
Часть алгоритма, организованная как простое действие, т.е. имеющая один вход (выполнение начинается всегда с одного и того же действия) и один выход (т.е. после завершения данного блока всегда начинает выполняться одно и то же действие), называется функциональным блоком.
Из этого определения, в частности, следует, что каждое простое действие является функциональным блоком, а условное - нет.
Согласно положениям структурного программирования можно выделить всего три различных варианта организации потока управления действиями алгоритма. Поток управления может обладать следующими свойствами:
1) каждый блок выполняется не более одного раза;
2) выполняется каждый блок.
Поток управления, в котором выполняются оба эти свойства, называется линейным - в нем несколько функциональных блоков выполняются последовательно. Линейному потоку на языке блок-схем соответствует структура:
Очевидно несколько блоков, связанных линейным потоком управления, могут быть объединены в один функциональный блок:
Второй тип потока управления называется ветвлением - он организует выполнение одного из двух функциональных блоков в зависимости от значения проверяемого логического условия. Блок-схема структуры:
В этом типе выполняется свойство (1), свойство (2) - нет. Если структура содержит два функциональных блока (S1 и S2), ветвление называется полным; возможно существование неполного ветвления - при этом один из блоков пуст (обычно S2).
Третий тип потока управления называется циклическим - он организует многократное повторение функционального блока, пока логическое условие его выполнение является истинным. Для циклического потока выполняется свойство (2), но не выполняется (1). Его блок-схема показана на рисунке.
Поскольку ветвление и циклический типы управления имеют один вход и один выход, они в целом также подходят под определение функционального блока. Введем рекурсивным образом понятие стандартного функционального блока:
1) каждое простое действие есть стандартный функциональный блок;
2) каждая из описанных трех управляющих структур является стандартным функциональным блоком, если все входящие в них блоки являются стандартными функциональными;
3) других стандартных функциональных блоков не существует.
Определим еще одно понятие:
Алгоритм называется структурным,если он может быть представлен стандартным функциональным блоком.
Другими словами, структурный алгоритм представляет собой комбинацию трех рассмотренных выше структур (иногда они называются базовыми алгоритмическими структурами). Безусловно, не все алгоритмы являются структурными. Однако именно структурные алгоритмы обладают рядом замечательных преимуществ по сравнению с неструктурными:
· понятность и простота восприятия алгоритма (поскольку невелико число исходных структур, которыми он образован);
· проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
· модифицируемость (она состоит в простоте изменения структуры алгоритма, поскольку составляющие блоки относительно независимы).
После введенных определений можно сформулировать структурную теорему Бома-Джакопини: