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