Answer

27. Теоремы структурного программирования.

Структурная схема программы – это ориентированный граф, задающий порядок выполнения операторов; вершинам графа соответствуют операторы, а ребра определяют последовательность их выполнения.

Основная теорема:

Структурная схема любого алгоритма обработки данных может быть представлен в виде суперпозиции трех базовых управляющих структур: следования, выбора и повторения.

Простые и непростые структурные схемы. Структурная схема является простой, если она:

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

Теорема о декомпозиции:

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

Теорема о соотношениях элементов структурных схем:

Предположим, что в простой структурной схеме имеется:

f – операционных блоков;

p – блоков принятия решения;

g – узлов слияния;

t – линий передачи управления.

Тогда справедливо:

p = g
t = f + 3p + 1

Пусть n узлов слияний. Пусть для n узлов.

(1) Число начальных точек и конечных совпадает!

1 + f + g + 2p = 1 + f + 2q + p => 2p + g = 2g + p => p = q

(2) 1 + f + 2p + p = t = 1 + 3p + f

Содержание