Контрольная работа 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…
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 — Схемаиерархии программы Диспетчер.
Подработой будем понимать затраты, которые связаны с проектированием, кодированиеми тестированием одного модуля.
Разработку модулей можноспланировать, используя один из следующих подходов: иерархический, операционныйили комбинированный
Диаграммаработ при изготовлении модулей комплекса Диспетчер, например, поиерархическому способу «снизу-вверх» будет иметь следующий вид:
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. Благодаря чему возможна оптимизацияграфика выполнения работ и требуемых ресурсов на реализацию проекта?