Непоименованный блок. Структурирование и анализ непоименованного блока

Министерство Образования и Науки Российской Федерации

Новосибирский Государственный Технический Университет

Рассчётно Графическая Работа

по предмету «Информатика»

Факультет: Прикладной Математики и Информатики

Группа:  ПМИ-52

Студенты: Коваленко И. А.

Преподаватель: Шапошникова Т. А.

Новосибирск 2006 г.

Условие

Для данной схемы:

I. Получить непоименованный блок;

II. Структурировать этот непоименованный блок:

1) Построить помеченную структурированную схему;

2) Построить рекурсивную структурированную схему;

3) Построить E-схему и описать функцию непоименованного блока;

III. Провести анализ непоименованного блока:

1) где в блоке нарушен принцип структурированности?

2) как эта проблема решается формальным образом?

3) можно ли найти другое решение этой проблемы – неформальное?

Решение

I. Выделим в схеме все элементарные подпрограммы и заменим каждую новым функциональным узлом.

Элементарная подпрограмма “While do”:

Последовательность:

Элементарная подпрограмма “If then else”:

Элементарная подпрограмма “While do”:

Элементарная подпрограмма “Do while”:

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

Элементарная подпрограмма “Do while”:

Элементарная подпрограмма “Do while”:

Последовательность:

Последовательность:

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

Последовательность:

Элементарная подпрограмма “While do”:

Элементарная подпрограмма “If then else”:

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

Последовательность:

Не осталось ни одной не замещённой элементарной программы. Получили упрощённую схему, функционально эквивалентную исходной – непоименованный блок.

II. Проименуем блоки и дуги:

1) Начнём составление помеченной структурированной схемы. Для этого представим каждый блок в виде блока с ссылками.

Получили помеченную структурированную схему:

2) Любой помеченной структурированной схеме можно построить эквивалентную рекурсивную схему.

Начнём с подпрограммы №3:

Далее подставим подпрограмму №4:

Далее подставим подпрограмму №7:

Далее подставим подпрограмму №6:

Далее подставим подпрограмму №5:

Далее подставим подпрограмму №2:

Завершим построение рекурсивной схемы подстановкой подпрограммы №1:

3) Построим E-схему:

Переименуем блоки для удобства описания функции:

Опишем функцию непоименованного блока:

F(X) = { P₁(F₁(X)) ^ P₂(F₂(F₁(X))) ^ Y=F₃(F₂(F₁(X))) |

             P₁(F₁(X)) ^ ¬P₂(F₂(F₁(X))) ^ Y=F₄(F₂(F₁(X))) |

             ¬P₁(F₁(X)) ^ Y=F₆(F₅(F₁(X))) }

III. Проведём анализ непоименованного блока:

После замены всех элементарных подпрограмм мы получили непоименованный блок. В нём нарушен принцип структурированности: цикл if p4 then f5 else f4 имеет два входа. Неформально проблема может быть решена путём дублирования блока (F4,5; P4). В результате мы получим структурированную программу. Полученная схема эквивалентна исходной. Для доказательства этого достаточно показать, что они эквивалентны по выполнению. E-схема исходного непоименованного блока приведена выше. E-схема программы выглядит следующим образом:

E-схемы эквивалентны -> эквивалентны E-деревья -> эквивалентны программы. При формальном решении мы получили тот же результат: блок (F4,5; P4) продублирован в те же ветки программы.