Методология преобразования произвольной программы в структурированную

Методология преобразования произвольной программы в структурированную

Цель работы: освоить методологию преобразования произвольной программы в структурированную.

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

Метод дублирования кодов. Рассмотрим программу, блок-схема которой приведена на рисунке 1. В настоящем виде программа не является структурированной; каждый блок не удовлетворяет требованию «один вход - один выход».

Чтобы получить структурированную программу, мы воспользуемся дублированием тех модулей, в которые можно войти из нескольких мест. Рассмотрим исходную программу как простую конструкцию типа IF-THEN-ELSE, показанную на рисунке 2.

Рисунок 2 -Упрощенное представление схемы по рисунку 1.

Она может быть расширена до структуры, изображенной на рисунке 3. Окончательно вся программа может быть представлена в виде, показанном на рисунке 4.

Метод применим к любой программе, имеющей структуру решетки

Рисунок 3 - Более подробное представление схемы.

или сети, но не может быть применен к циклическим программам.

Метод дублирования кодов имеет недостаток: он требует больше памяти, чем исходный неструктурированный подход. Однако часто оказывается, что дублируемые модули содержат по 2-3 оператора. В таком случае дублирование кодов - приемлемая плата за возможность получить распадающуюся на уровни структуру. Если же модули состоят из значительного объема кодов, то вводятся подпрограммы. При этом важно, чтобы они были организованы как подпрограммы с формальными параметрами, что дает возможность установить их правильность вне зависимости от контекста, в котором они используются.

Метод введения переменной состояния. Метод применим к любым программам и допускает автоматическое применение. Процесс преобразования состоит из пяти шагов.

Рисунок 5 - Неструктурированная программа

Каждому блоку неструктурированной схемы приписывается номер.

В программу вводится новая переменная i целого типа.

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

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

Теперь перестраиваем блок-схему, придав ей форму, показанную на

Рисунок 6 - Структурированная форма программы

Начальное значение i=1.

Затем последовательно выполняется опрос значений переменной i и т.д.

Рисунок 7 - Схема выполнения программы.

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

На рисунке 8 приведен пример построения программной функции циклической программы. В данном случае [P] рекурсивно зависит от f1 и f2.

а) циклическая программа

б) дерево выполнения

в) вывод системы рекурсивных функций

Рисунок 8 - Пример построения программной функции

Недостатки метода:

разрушается форма и топология исходной блок-схемы;

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

Достоинства метода:

преобразованная введением переменной состояния форма может быть неограниченно продолжена, не усложняя при этомобщего подхода;

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

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

Метод булевого признака. Существует еще один метод структурирования программ, содержащих циклы. Данный метод требует введения в программу некоторого признака задается в некоторой точке выше цикла; конструкциями типа DO-WHILE или REPEAT-UNTIL осуществляется управление циклом до тех пор, пока названный признак сохраняет заданное значение; некоторыми условиями внутри цикла определяется момент смены значения признака. Таким тбразом, программа продставляется в форме:

...flag:=0…

WHILE flag = 0

DO… If x=y THEN flag:=1 ...

или в какой-нибудь другой эквивалентной форме.

Программной функцией [P] программы P называется множество всех упорядоченных пар {(X,Y)}, где X - исходное состояние данных перед выполнением программы по некоторому пути дерева ее выполнения; Y - состояние данных после окончания выполнения программы по этому пути.

Для ациклической программы P, показанной на рисунке 3.7, программная функция определяется условным правилом:

[P]={(X,Y)|(p(X)Y=f(X)|p(X)&q(X)Y==g(X)|p(X)&q(X)Y=X)

Задание к контрольной работе

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

ТАБЛИЦА 1

Порядок выполнения работы

Нарисовать блок-схему программы, используя сокращенную матрицу смежности. Целесообразно сразу использовать базисные элементы структурного программирования: последовательность, if-then-else,while-do, do-until и др.

Выполнить полный анализ исходной программы. Показать элементы анализа и результирующие блок-схемы для каждого шага анализа.

Выделенные неструктурированные фрагменты преобразовать одним из методов в структурированную форму. При использовании теоремы о структурировании получите помеченную и рекурсивную программы.

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

Содержание отчета

Блок-схема исходной программы.

Элементы анализа и упрощенная блок-схема каждого шага анализа. Выделенный неструктурированный фрагмент программы.

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

E-схемы и программные функции для выделенных фрагментов исходной и структурированной программы.

Какие методы применяются для структурирования программ?

В каких случаях применение метода дублирования кодов эффективно?

Перечислите достоинства метода введения переменной состояния.

Как формулируется теорема о структурировании программ?

ПЛАНИРОВАНИЕ ОРГАНИЗАЦИИ РАБОТ НАД ПРОЕКТОМ ПРОГРАММ

Цель работы: приобрести практические навыки в применении методов сетевого планирования разработки крупных программных систем в заданные сроки и с оценкой необходимых ресурсов.

Современная наука об управлении программными проектами сложна и динамично развивается. Целью этого научного направления является создание подсистемы планирования, которая бы своевременно напоминала разработчику о том, что предстоит сделать в проекте; своевременно предупреждала его об окончании сроков, отведенных на данную работу; следила за его руководителем, чтобы он не переполнял заранее оговоренное число заданий на исполнение и каждое задание оформлял в строгом соответствии с существующей договорен-ностью; чтобы сроки согласовывались, а не назначались, работы распределялись поровну в коллективе, система поощрения была обьективной и соответсвовала выполняемой работе; чтобы система блокировала обращение "через голову" к подчиненным; чтобы исходя из существующего опыта, система подсказывала, обучала, следила и т.д. И все это (или почти все) автоматически благодаря анализу самой системой той информации, которая циркулирует в САПР ПО. Многие перечисленные функции планирования реализованы в современных CASE-системах проектирования программ (Computer Aided Software Engineering): EPOS (Германия), CASE. Аналитик (Россия) и т.д.

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

Рассмотрим пример составления рационального сетевого графика изго-товления программного комплекса Диспетчер, модульная структура которого приведена на рисунке 2.1.

Рисунок 2.1 - Схема иерархии программы Диспетчер.

Под работой будем понимать затраты, которые связаны с проектированием, кодированием и тестированием одного модуля.

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

Диаграмма работ при изготовлении модулей комплекса Диспетчер, напри-мер, по иерархическому способу "снизу-вверх" будет иметь следующий вид:

2.1

3.1 2.3 1.1

Рисунок 2.2 - Диаграмма восходящего проектирования программы

Исходные данные для сетевого планирования готовятся опытными програм-мистами, которые должны на основе опыта, статистических данных и экспертных оценок точно или приближенно оценить длительность каждой k-ой работы (Tk-за-траты на проектирование, кодирование и тестирование модуля, дни), интенсив-ность разработки модуля (Qk,человек/день), средства на выполнение работ (Ck, крб.) и т.д.

По этим исходным данным составляется сетевой график, придерживаясь следующего порядка действий:

проводится упорядочение (ранжирование) работ;

cортируются работы по убыванию веса работ;

для каждой работы находится множество непосредственно предшествую-щих работ ;

для каждой работы находится множество непосредственно следующих ра-бот ;

определяется наиболее ранний срок окончания каждой работы

;

определяется время завершения всего комплекса работ ;

определяется поздний срок окончания каждой работы

, где ;

вычисляются резервы времени для каждой работы ;

вычисляются ранние начала каждой работы .

Результаты расчета сетевого графика проектирования программы Диспет-чер по рассмотренной методике приведены в табл.1.

Поскольку все работы на рисунке 2.3 начинаются в наиболее ранние возможные сроки, то распределение ресурсов по дням получается очень неравномерным (в первый день работает 5 человек, тогда как в последующие дни требуется всего 1 человек). Распределение ресурсов можно сделать более равномерным, если сместить начало некоторых работ, имеющих резервы времени, на более поздний срок в пределах допустимого. После выполнения процедуры смещения начала работ 2.2 и 2.4 получим скорректированный сетевой график (рисунок 2.4).

Составить рациональный сетевой график реализации проекта программного комплекса, разработка которого начата в лабораторной работе N1.

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

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

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

4. Выполнить расчет параметров сетевого графика.

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

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

1. Название лабораторной работы, цель работы.

2. Схема состава разложения программного комплекса. Описание выбранной стратегии (подхода) проектирования комплекса.

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

4. Расчет параметров сетевого графика в табличной и графической форме.

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

1. В чем преимущество сетевого планирования при разработке крупных программных систем?

2. Что является исходными данными при сетевом планировании?

3. Для чего нужен сетевой график работ и как он составляется для программных комплексов?

4. Каким способом ранжируются работы?

5. Как определяется критический путь на сетевом графике и что он обозначает?

6. Благодаря чему возможна оптимизация графика выполнения работ и требуемых ресурсов на реализацию проекта?