Понятие базисного множества базовых структур. Понятие структурированной блок-схемы

В базисное множество базовых структур вошли: следование, ветвление, цикл-пока. Цикл-до в базисное множество не вошел, так как его можно представить через базовую структуру «цикл-пока».

В 1966 году Бом и Якопини доказали следующую теорему:

Любую блок-схему с одним входом и одним выходом можно построить, используя только базисное множество базовых структур { следование, ветвление, цикл-пока }.

Структурированные блок-схемы

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

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

Пример. 1 шаг.

2-й шаг.

3-й шаг.

Процесс можно продолжать до тех пор, пока не останутся только простые блоки.