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

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

Контрольная работа 2

МЕТОДЫ СТРУКТУРИРОВАНИЯ ПРОГРАММ

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

Методические указания

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


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

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

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


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


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

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

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


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

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


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

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

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

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

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



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

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

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

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


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

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

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

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



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

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


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

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

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

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

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

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

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

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

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

...flag:=0…

WHILEflag = 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

Номер варианта
1 2 3 4 5 6 7 8 9 10
SX0 SA0 SA0 SX0 SA0 SX0 SX0 SA0 SA0 SB0
XZA AX0 AX0 XCA AB0 XAZ XYZ AX0 AX0 BX0
AB0 XDB XYC CD0 BX0 AY0 YBA XZY XDB XBY
BY0 DY0 YBU DV0 XBY YAB ZBC YWV DT0 XQZ
YBP BC0 BU0 VDY YPZ BT0 AP0 ZBW TF0 QVT
PTU CY0 CZ0 AB0 ZCW ZCD PLF BU0 BY0 TJ0
TF0 YZT ZCU BY0 CD0 DT0 FV0 UBW YCF JHN
UGV ZKY UTD YQZ DW0 CT0 VFL WTR CF0 HJ0
FV0 KFH TF0 QFL PTG TP0 LMP TF0 FZ0 VKN
ZDQ FG0 DV0 LW0 TQ0 PUQ BD0 RGN ZHW KW0
QCU GK0 VGK WKN QFV UWV DQ0 FG0 HW0 WKN
CU0 TP0 GW0 KL0 FV0 WKH QDU VQN WVI ZCU
DW0 PQT WHU FG0 GU0 VGH UDM QDC VUE CD0
WGD QHT HV0 GR0 UGV HK0 CW0 CN0 UAK DG0
GE0 HL0 FE0 RNM VHK GK0 WTN DN0 KQ0 GR0
VRH LR0 KL0 NPO KL0 QMN TN0 NHM QKA RLA
REL RMN LP0 MP0 LE0 NGF MLN HK0 ILM LI0
LE0 MU0 PLE ZFT HL0 MFK NMP KM0 LF0 IPM
HK0 NU0 TU0 WHR FK0 PHK GP0 MJ0 MI0
KE0 UER UHM RML KL0 KE0 PLM JPN PE0
HM0 ML0 LE0 HR0 LM0 PG0 NP0
PE0 RGE ME0 NT0 ANP
GH0 GRO UFR
RP0 FR0
OW0
Номер варианта
11 12 13 14 15 16 17 18 19 20
SA0 SX0 SX0 SA0 SA0 SA0 SA0 SA0 SA0 SA0
AB0 XDA XAE AX0 AX0 AX0 AX0 AX0 AX0 AB0
BX0 AB0 AY0 XCB XDB XBD XYB XCB XDB BC0
XBY BY0 YDB CY0 DT0 BC0 YTC BZ0 DT0 CDG
YUZ YCF BZ0 YDZ TZO CY0 CD0 CY0 BC0 GI0
UYV CF0 ZCV DY0 BC0 YBF DT0 YDZ CY0 IQ0
ZVW DZ0 CV0 BZ0 CY0 DZ0 BZ0 DY0 YBZ DF0
WZK ZDT DU0 ZGU YDZ ZTF ZBT ZGU TZ0 FJ0
VCF TU0 UDV UVT ZRU TF0 TU0 UVT ZRU JQF
CP0 UDF VXT GM0 UFV FG0 URV VKH UFW QBP
PTF FV0 TF0 MW0 FV0 GU0 VLW KP0 FV0 PRM
TD0 VGW FH0 WME VGW ULH LF0 PLE VGW ML0
DC0 WFQ HW0 VKH GW0 HV0 FMK LK0 GW0 RL0
KFL GP0 WGQ HE0 WAQ VKL MF0 HE0 WEQ LOY
FY0 PHR GH0 KP0 QRP KH0 KR0 GM0 QRP OW0
LMH HL0 QHP PLE PMR LW0 WGR MW0 PMR WT0
HE0 LG0 PVI LK0 RNH WUP GP0 WME RNH YLT
MGN RGQ IRK TF0 NL0 PEQ PHR TF0 NL0 TCU
GN0 QMK RNJ FN0 LM0 QMR HG0 FN0 LM0 UE0
NME MN0 NR0 NR0 HJ0 MN0 RTN NR0 ME0
NI0 KM0 RNQ JKM NQ0 NJ0 RNQ HJ0
KI0 MJ0 QNZ KH0 RFE JUE QNZ JKM
IFJ JPL ME0 KH0
JQE LX0
EX0

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

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

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

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

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

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

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

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

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

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

Контрольные вопросы

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

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

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

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

Лабораторная работа №2

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

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

Методические указания

Современная наука об управлении программными проектами сложна и динамично развивается. Целью этого научного направления является создание подсистемы планирования, которая бы своевременно напоминала разработчику о том, что предстоит сделать в проекте; своевременно предупреждала его об окончании сроков, отведенных на данную работу; следила за его руководителем, чтобы он не переполнял заранее оговоренное число заданий на исполнение и каждое задание оформлял в строгом соответствии с существующей договорен­ностью; чтобы сроки согласовывались, а не назначались, работы распределялись поровну в коллективе, система поощрения была обьективной и соответсвовала выполняемой работе; чтобы система блокировала обращение "через голову" к подчиненным; чтобы исходя из существующего опыта, система подсказывала, обучала, следила и т.д. И все это (или почти все) автоматически благодаря анализу самой системой той информации, которая циркулирует в САПР ПО. Многие перечисленные функции планирования реализованы в современных 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. Благодаря чему возможна оптимизация графика выполнения работ и требуемых ресурсов на реализацию проекта?