Лаба №1
.docЧасть1. Построение операционных графовых моделей (ОГМ) последовательных программ
Задание
Для рассматривавшегося в лабораторных работах курса «Метрология программного обеспечения» индивидуального задания разработать операционную модель управляющего графа программы на основе схемы алгоритма. При выполнении работы рекомендуется исключить диалог при выполнении операций ввода-вывода данных, а также привести программу к структурированному виду.
Выбрать вариант графа с нагруженными дугами, каждая из которых должна представлять фрагмент программы, соответствующий линейному участку или ветвлению. При расчете вероятностей ветвлений, зависящих от распределения данных, принять равномерное распределение обрабатываемых данных в ограниченном диапазоне. В случае ветвлений, вызванных проверкой выхода из цикла, вероятности рассчитываются исходя из априорных сведений о числе повторений цикла.
Вариант 2 Алгоритм Симсона
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
float fx(float x) {
return exp(-x/2.0);
}
float dfx(float x) {
return -(exp(-x/2.0)/2.0);
}
float simps(float lower, float upper, float tol, float sum) {
int i;
float x, delta_x, even_sum,
odd_sum, end_sum, end_cor, sum1;
int pieces;
pieces = 2;
delta_x = (upper - lower)/pieces;
odd_sum = fx(lower + delta_x);
even_sum = 0.0;
end_sum = fx(lower) + fx(upper);
end_cor = dfx(lower) - dfx(upper);
sum = (end_sum + 4.0*odd_sum)*delta_x/3.0;
do {
pieces = pieces*2;
sum1 = sum;
delta_x = (upper - lower)/pieces;
even_sum = even_sum + odd_sum;
odd_sum = 0.0;
for(i = 1; i<=pieces/2; i++) {
x = lower + delta_x*(2.0*i - 1.0);
odd_sum = odd_sum + fx(x);
}
sum = (7.0*end_sum + 14.0*even_sum + 16.0*odd_sum + end_cor*delta_x)*delta_x/15.0;
}while( (sum!=sum1) && ( abs(sum - sum1)<=abs(tol*sum)));
return sum;
}
void main() {
clrscr();
float lower ,
upper ;
float sum;
const tol = 1.0e-6;
randomize();
for (int k=1; k<=100; k++)
{
upper=random(100)+1;
lower=1;
sum = simps(lower, upper, tol, sum);
}
}
После того, как в пакете CSAIII, был построен граф с нагруженными вершинами соответствующей структуре программы, были расставлены контрольные точки следующим образом:
#include <math.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "ctrpoint.h"
float fx(float x) {
return exp(-x/2.0);
}
float dfx(float x) {
return -(exp(-x/2.0)/2.0);
}
float simps(float lower, float upper, float tol, float sum) {
CTRPOINT(0); int i;
float x, delta_x, even_sum,
odd_sum, end_sum, end_cor, sum1;
int pieces;
pieces = 2;
delta_x = (upper - lower)/pieces;
odd_sum = fx(lower + delta_x);
even_sum = 0.0;
end_sum = fx(lower) + fx(upper);
end_cor = dfx(lower) - dfx(upper);
sum = (end_sum + 4.0*odd_sum)*delta_x/3.0;
CTRPOINT(2); do {
CTRPOINT(4); pieces = pieces*2;
sum1 = sum;
delta_x = (upper - lower)/pieces;
even_sum = even_sum + odd_sum;
odd_sum = 0.0;
CTRPOINT(6); for(i = 1;
CTRPOINT(8),
i<=pieces/2; i++) {
CTRPOINT(9);
x = lower + delta_x*(2.0*i - 1.0);
odd_sum = odd_sum + fx(x);
CTRPOINT(10);
}
CTRPOINT(7);
sum = (7.0*end_sum + 14.0*even_sum + 16.0*odd_sum + end_cor*delta_x)*delta_x/15.0;
CTRPOINT(5);
}while( (sum!=sum1) && ( abs(sum - sum1)<=abs(tol*sum)));
CTRPOINT(3);
return sum;
}
void main() {
clrscr();
float lower ,
upper ;
float sum;
const tol = 1.0e-6;
randomize();
for (int k=1; k<=100; k++)
{
upper=random(100)+1;
lower=1;
sum = simps(lower, upper, tol, sum);
}
}
Граф с нагруженными дугами
Граф с удалённой контрольной точкой (t1) переход t3->t1 был невозможен в программе, т.к. после оператора return завершается работа функции и управление не передаётся в контрольную точку t1
XML файл с данными множеств “up” и “down”.
<link type="Graphs::SamplerGraph::Link" name="t0-->t2" info="simpleOp" up="0->2;" down=""
<link type="Graphs::SamplerGraph::Link" name="t3-->t1" info="simpleOp" up="3->1;" down=""
<link type="Graphs::SamplerGraph::Link" name="t2-->t4" info="do-null" up="2->4;" down=""
<link type="Graphs::SamplerGraph::Link" name="t5-->t4" info="do-body" up="5->4;" down="5->3;"
<link type="Graphs::SamplerGraph::Link" name="t5-->t3" info="do-end" up="5->3;" down="5->4;"
<link type="Graphs::SamplerGraph::Link" name="t4-->t6" info="simpleOp" up="4->6;" down=""
<link type="Graphs::SamplerGraph::Link" name="t7-->t5" info="simpleOp" up="7->5;" down=""
<link type="Graphs::SamplerGraph::Link" name="t6-->t8" info="for-init" up="6->8;" down=""
<link type="Graphs::SamplerGraph::Link" name="t8-->t9" info="for-cond" up="8->9;" down="8->7;"
<link type="Graphs::SamplerGraph::Link" name="t9-->t10" info="for-body" up="9->10;" down=""
<link type="Graphs::SamplerGraph::Link" name="t10-->t8" info="for-update" up="10->8;" down=""
<link type="Graphs::SamplerGraph::Link" name="t8-->t7" info="for-exit" up="8->7;" down="8->9;"
Результат работы ПИМ Sampler
100 итераций
Проверка адекватности результата с помощью метода эквивалентных преобразований
После того, как мы получили данные о нагрузке на каждой конкретной дуге графа и провели эквивалентные преобразования графа получилось, что среднее время выполнения программы составляет 220,3555. То, что вероятность выполнения программы равна 1 говорит о том, что расчёты произведены верно.
Описание модели в виде XML
<model type = "Objects::AMC::Model" name = "ArcModel">
<node type = "Objects::AMC::Top" name = "t0"></node>
…
<node type = "Objects::AMC::Top" name = "t10"></node>
<link type = "Objects::AMC::Link" name = "t0-->t2" probability = "1.0" intensity = "1.62" deviation = "0.0" source = "t0" dest = "t2"></link>
<link type = "Objects::AMC::Link" name = "t2-->t4" probability = "1.0" intensity = "0.25" deviation = "0.0" source = "t2" dest = "t4"></link>
<link type = "Objects::AMC::Link" name = "t5-->t4" probability = "0.507389162561576" intensity = "0.48" deviation = "0.0" source = "t5" dest = "t4"></link>
<link type = "Objects::AMC::Link" name = "t5-->t3" probability = "0.492610837438424" intensity = "0.49" deviation = "0.0" source = "t5" dest = "t3"></link>
<link type = "Objects::AMC::Link" name = "t4-->t6" probability = "1.0" intensity = "0.64" deviation = "0.0" source = "t4" dest = "t6"></link>
<link type = "Objects::AMC::Link" name = "t7-->t5" probability = "1.0" intensity = "0.38" deviation = "0.0" source = "t7" dest = "t5"></link>
<link type = "Objects::AMC::Link" name = "t6-->t8" probability = "1.0" intensity = "0.27" deviation = "0.0" source = "t6" dest = "t8"></link>
<link type = "Objects::AMC::Link" name = "t8-->t9" probability = "0.989224481129572" intensity = "0.31" deviation = "0.0" source = "t8" dest = "t9"></link>
<link type = "Objects::AMC::Link" name = "t9-->t10" probability = "1.0" intensity = "0.55" deviation = "0.0" source = "t9" dest = "t10"></link>
<link type = "Objects::AMC::Link" name = "t10-->t8" probability = "1.0" intensity = "0.29" deviation = "0.0" source = "t10" dest = "t8"></link>
<link type = "Objects::AMC::Link" name = "t8-->t7" probability = "0.0107755188704284" intensity = "0.28" deviation = "0.0" source = "t8" dest = "t7"></link>
</model>