Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 10

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

Например, простая программа (рис. 4) может быть представлена в виде программы (рис . 5).

 

                                                                            рис. 4

Рис. 5

В программе на (рис. 5) узел g является абстракцией простой программы см. рис. 6, а узел h абстрагирует простую программу (рис 7)

                                         

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

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

t

           3.1.4 Схемы и деревья выполнения

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

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

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

3. Формирование Е-схемы считать законченным, если  все пути  выполнения пройдены. При этом путь считается пройденным, если он заканчивается выходной линией или узлом слияния, номер которой  уже встречался на этом пути.

В результате выполнения данной процедуры будет построено конечное дерево, состоящее только из узлов блок - схемы. Например, для блок - схемы, показанной на рис. 8, Е - схема, построенная по этой процедуре приведена на рис. 9.

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

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

имеет Е – схему,

по которой можно построить   Е - дерева.(рис.10)

3.2 Программные функции

3.2.1 Функция

Функция - это такое отношение, при котором для каждого x ÎD(f) существует единственный элемент отношения (x, y)Îf. Традиционно, функцию записывают в виде y = f(x) и что бы  определить функцию f, достаточно  задать область определения функции D(f) и правило вычисления соответствующего значения функции для каждого значения аргумента из области D(f).  Таким правилом может быть программа для ЭВМ. Если правило не охватывает всей области определения функции, то рассматривается частичное правило. Правило играет вспомогательную роль по отношению к функции, так как каждой функции можно поставить в соответствие много правил.

Рассмотрим функцию

             f ={(x, y) | x Î{0, 1}, y = x² + 3x +2}

где (x Î{0, 1}) обозначает область определения функции, а правилом является выражение - (y = x² + 3x +2).Эта функция может быть задана перечислением элементов

                     f = {(0, 2), (1, 6)}

или описательным методом задания множества с правилом, сформулированным как два равенства, в виде

     f = {(x, y) | x(x -1) =0, y - x² - 3x -2 = 0}