solution (Задание 1), страница 2
Описание файла
Файл "solution" внутри архива находится в следующих папках: Задание 1, Reliability_Task1 (answer) (UTF-8). Текстовый-файл из архива "Задание 1", который расположен в категории "". Всё это находится в предмете "надёжность программного обеспечения" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр 2 страницы текстового-файла онлайн
void f (int a, int b)
{
0: int x, y; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1)
1: x = 9; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {#}; f_y = {#}
2: y = 3; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {#}
3: h = 3; // h = {#, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}
4: h = a + y; // h = {3, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}
5:} // заключительный оператор
// h = {f_a+3, 5, g_b}; (-2^31 <= f_a <= 2^31 -1); (-2^31 <= f_b <= 2^31 -1); f_x = {9}; f_y = {3}
// Исходя из уже проанализированной функции f (т.е. за вычетом недостижимых участков) - h на входе может быть равна {#} или {f_a+3, 3}, причём т.к. функции выполняются параллельно и мы не знаем времени присваивания h в фукнции f, то придётся всё время считать, что h может быть изменено на {f_a+3, 3}
void g (int a, int b)
{
0: int x, y; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1)
1: x = 2; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {#}; g_y = {#}
2: y = 7; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {#}
3: h = 5; // h = {#, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}
4: x = 4; // h = {5, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {2}; g_y = {7}
5: h = b; // h = {5, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}
6: if (h < y) // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}
{
7: y = 0; // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h < g_y)
}
else
{
8: x = 3; // h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); g_x = {4}; g_y = {7}; (h >= g_y)
}
9:} // Заключительное состояние
// h = {g_b, f_a+3, 3}; (-2^31 <= g_a <= 2^31 -1); (-2^31 <= g_b <= 2^31 -1); ((g_x == 4 && h < 7) || (g_x == 3 && h >= 7)); ((g_y == 7 && h >= 7) || (g_y == 0 && h < 7))
/////////////////////////
После 2-го прохода по функциям количество недостижимых состояний не прибавилось, а значит пора считать количество возможных состояний программы, как это делалось в лекциях
количество операндов: 6 и 10
диапазон для переменных:
(-2^31 <= g_a <= 2^31 -1)
(-2^31 <= g_b <= 2^31 -1)
(-2^31 <= f_a <= 2^31 -1)
(-2^31 <= f_b <= 2^31 -1)
f_x - 2 состояния (в операндах 0 и 1)
f_y - 2 состояния (в операндах 0 и 2)
g_x - 4 состояний (в операндах 0, 1, 4 и 8)
g_y - 3 состояния (в операндах 0, 2 и 7)
h - 5 состояний (для f - в операндах 3 и 4, а для g - в операндах 3, и 5, и ещё одно неинициализированное состояние)
таким образом количество достижимых состояний в программе = 6*10*(2^(32*4))*2*2*3*4*5 = 14400 * 2^128
Ответ: 6*10*(2^(32*4))*2*2*3*4*5 = 14400 * 2^128
//====================================== ======================================== ======================================== ===============================
//====================================== ======================================== ======================================== ===============================
//====================================== ======================================== ======================================== ===============================
3 часть задания:
После выкидывания недостижимых состояний, будут обрабатываться следующие функции:
(Будет так же использовано инструментирование)
int h;
void f (int a, int b)
{
int x, y;
x = 9;
y = 3;
h = 3;
h = a + y;
}
void g (int a, int b)
{
int x, y;
x = 2;
y = 7;
h = 5;
x = 4;
h = b;
if (h < y)
{
y = 0;
}
else
{
x = 3;
}
}
Описание идеи работы программы:
Для того, чтобы получить все возможные состояния программы при её запуске будет применяться следующий приём:
Будет создан массив, в котором будут записаны true или false, true будет соответствовать выполнению очередной операции в функции f, а false будет соответствовать очередной операции в фукнции g. Длинна массива будет равна суммарному количеству операндов в обеих фукнциях.
Каждое состояние будет записываться в std::set, оно само разберётся с дубликатами, единственное что - это придётся переопределить функцию сравнения.
Для перебора всех комбинаций в массиве нужно использовать std::next_permutation
УСТАРЕЛО:
(Для того, чтобы создавать все возможные распределения true и false в массиве будет использован рекурсивный спуск, функция в котором будет поочереди заполнять одним полем true все допустимые значения поочереди, и рекурсивно вызывать себя для дальнейшего заполнения полем true, потому что нам нужно количество полей true равное количеству операндов в фукнции f
При этом глубина рекурсии будет равна количеству самих операторов в фукнции f (поэтому и была выбрана f, т.к. там меньше операндов, а значит и короче рекурсия)
На последней итерации рекурсивная фукнция, сформировав очередное заполнение, вызовет обработчик для данной возможной последовательности выполнения.)
