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

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

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

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

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

1

2

3

5

7

8

6

4

9

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

1

X

Y

9

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

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

1

X2

X1

2

9

Y1

Y2

2

Метод применим к любой программе, имеющей структуру решетки
Рисунок 3 - Более подробное представление схемы.
или сети, но не может быть применен к циклическим программам.

1

9

2

4

7

8

7

5

3

6

8

7

8

5

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

2   B

3   C

5   E

F

4   D В

1   A

 

Рисунок 5 - Неструктурированная программа
1.                 Каждому блоку неструктурированной схемы приписывается номер.
2.                 В программу вводится новая переменная i целого типа.
3.                 Функциональные блоки неструктурированной схемы заменяются функциональными блоками, которые выполняют те же самые вычисления и присваивают переменной i целое значение, идентифицирующее номер блока-приемника исходной схеме.
4.                 Логические блоки исходной схемы преобразуются таким же образом.

I=1

stop

I=3

I=2

I=5

I=1

B

I=4

I=0

I=2

E

I=0

I=0

A

I=1

I=2

I=3

D

I=4

I=5

C

Теперь перестраиваем блок-схему, придав ей форму, показанную на
Рисунок 6 - Структурированная форма программы
 Начальное значение i=1.
Затем последовательно выполняется опрос значений переменной i и т.д.

q

f

f

и

л

и

л

1

p

1

2

2

Рисунок 7 - Схема выполнения программы.
Программная функция циклической программы описывается системой рекурсивных функций. При этом для каждого i-го узла слияния, начинающего цикл, вводится вспомогательная функция f, определяющая функцию всех узлов схемы выполнения, следующих за i-м узлом.
На рисунке 8 приведен пример построения программной функции циклической программы. В данном случае [P] рекурсивно зависит от f1 и f2.
а) циклическая программа

h

и

л

и

л

3

q

s

t

q

и

л

1

2

p

 

t

q

h

и

и

и

и

л

л

л

л

f1

f1

f2

f2

f2

1

p

1

2

q

sq

2

sq

2

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

t

f1

f1

f2

g

и

л

P=

h

f2

и

и

л

л

f2=

f1=

1

p

2

q

s

Рисунок 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

Порядок выполнения работы
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

3.1

2.2

2.5

2.4

2.3

1.1

 
                                                                                                         
         
 Рисунок 2.1 - Схема иерархии программы Диспетчер.
Под работой будем понимать затраты, которые связаны с проектированием, кодированием и тестированием одного модуля.
Разработку модулей можно спланировать, используя один из следующих подходов: иерархический, операционный или комбинированный
Диаграмма работ при изготовлении модулей комплекса Диспетчер, напри­мер, по иерархическому способу "снизу-вверх" будет иметь следующий вид:
2.1
 

   
3.1    2.3   1.1
Рисунок 2.2 - Диаграмма восходящего проектирования программы
Исходные данные для сетевого планирования готовятся опытными програм­мистами, которые должны на основе опыта, статистических данных и экспертных оценок точно или приближенно оценить длительность каждой k-ой работы (T_k-за­траты на проектирование, кодирование и тестирование модуля, дни), интенсив­ность разработки модуля (Q_k,человек/день), средства на выполнение работ (C_k, крб.) и т.д.
По этим исходным данным составляется сетевой график, придерживаясь следующего порядка действий:
-     проводится упорядочение (ранжирование) работ;
-     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. Благодаря чему возможна оптимизация графика выполнения работ и требуемых ресурсов на реализацию проекта?