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

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

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

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

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

Метод дублирования кодов. Рассмотрим программу, блок-схема которой приведена на рисунке 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

Номер варианта

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лабораторная работа №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. Благодаря чему возможна оптимизация графика выполнения работ и требуемых ресурсов на реализацию проекта?