3. Расчет вероятностей переходов

Для оценки вероятностей переходов в ветвлениях, алгоритм сортировки был выполнен 100 раз для случайно сгенерированных массивов размерностью от 2 до 101 элементов. При этом считалось количество выполнений участков алгоритма сразу после ветвления. Отношение количества выполнений после ветвления и давали вероятность переходов.

Вероятность рассчитывалась по формуле:

{Вероятность правой ветви} = {Кол. Проходов по правой ветви} / (Кол. Походов по обоим ветвям)

{Вероятность левой ветви} = 1 – {вероятность правой ветви}

Пример для вершин 15, 16, 17:

{Кол. Проходов по 15} = 3414

{Кол. Проходов по 16} = 1482

{Кол. Проходов по 17} = 1932

{Вероятность для 16} = 1482/3414 = 0.434

{Вероятность для 17} = 1 - 0.434 = 1932/3414 = 0.566

Текст тестирующей программы:

int main()

{

float array[102];

int k,x;

for (x = 2; x <= 101; x++)

{

for (k = 1; k <= x; k++)

{

array[k] = (float)(rand()%1000+1);

}

quicksort(array, x);

}

printf ("================\n");

printf ("n1 %d\n", n1);

printf ("n2 %d\n", n2);

printf ("n3 %d\n", n3);

printf ("n4 %d\n", n4);

printf ("n5 %d\n", n5);

printf ("n6 %d\n", n6);

printf ("n7 %d\n", n7);

printf ("n71 %d\n", n71);

printf ("n72 %d\n", n72);

printf ("n8 %d\n", n8);

printf ("n9 %d\n", n9);

printf ("n10 %d\n", n10);

printf ("n11 %d\n", n11);

return 0;

}

4. Операционная графовая модель в структурированном виде

Для возможности вычисления фундаментальной матрицы методом поуровневой детализации, граф должен быть в структурированном виде:

• граф должен представлять суперпозицию базовых конструкций: следование, ветвление, цикл с предусловием;

• каждая конструкция должна состоять ровно из четырех вершин;

• детализировать можно только определенные вершины: для следования – две внутренние вершины, для ветвления – прямая и обратная ветви, для цикла – тело цикла.

Пунктирные прямоугольники показывают базовые конструкции.

5. Содержание входного файла

tops {

T1(241),

T2(29),

T3(57),

T4(24),

T5(94),

T6(5),

T7(0),

T8(55),

T9(0),

T10(20),

T11(0),

T12(5),

T13(311),

T14(54),

T15(20),

T16(27),

T17(13),

T18(0),

T19(8),

T20(0),

T21(6),

T22(5)

}

links {

T1->T2(1),

T2->T3(0.986),

T2->T22(0.014),

T3->T4(0.507),

T3->T5(0.493),

T5->T6(1),

T6->T7(0.635),

T6->T8(0.365),

T7->T9(1),

T8->T9(1),

T9->T10(1),

T10->T11(1),

T11->T12(1),

T12->T13(0.697),

T12->T14(0.303),

T13->T12(1),

T14->T15(1),

T15->T16(0.434),

T15->T17(0.566),

T16->T18(1),

T17->T18(1),

T18->T19(1),

T19->T20(1),

T20->T21(1),

T4->T21(1),

T21->T2(1)

6. Фундаментальная матрица

Вызвано распознавание шаблона для подграфа @ROOT:

начальная вершина T1, конечная вершина T22

Текущее состояние фундаментальной матрицы:

*************************

@ROOT ¦ 1 ¦

*************************

Конструкция ЦИКЛ

Вершина проверки условия: T2

Дуга, входящая в тело цикла: T2->T3

Дуга, выходящая из тела цикла: T21->T2

Вероятность повторения тела цикла: 0.986

Вероятность выхода из цикла: 0.014

Матрица для подстановки:

**********************************************************

T1 ¦ 1 71.43 70.43 1 ¦

T2 ¦ 0 71.43 70.43 1 ¦

@TMP0 ¦ 0 71.43 71.43 1 ¦

T22 ¦ 0 0 0 1 ¦

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP0:

начальная вершина T3, конечная вершина T21

Текущее состояние фундаментальной матрицы:

**********************************************************

T1 ¦ 1 71.43 70.43 1 ¦

T2 ¦ 0 71.43 70.43 1 ¦

@TMP0 ¦ 0 71.43 71.43 1 ¦

T22 ¦ 0 0 0 1 ¦

**********************************************************

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

T3 ¦ 1 0.493 0.507 1 ¦

@TMP1 ¦ 0 1 0 1 ¦

@TMP2 ¦ 0 0 1 1 ¦

T21 ¦ 0 0 0 1 ¦

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP1:

начальная вершина T5, конечная вершина T20

Текущее состояние фундаментальной матрицы:

*******************************************************************************************

T1 ¦ 1 71.43 70.43 34.72 35.71 70.43 1 ¦

T2 ¦ 0 71.43 70.43 34.72 35.71 70.43 1 ¦

T3 ¦ 0 71.43 71.43 35.21 36.21 71.43 1 ¦

@TMP1 ¦ 0 71.43 70.43 35.72 35.71 71.43 1 ¦

@TMP2 ¦ 0 71.43 70.43 34.72 36.71 71.43 1 ¦

T21 ¦ 0 71.43 70.43 34.72 35.71 71.43 1 ¦

T22 ¦ 0 0 0 0 0 0 1 ¦

*******************************************************************************************

Конструкция СЛЕДОВАНИЕ

Начало первого оператора: T6

Окончание первого оператора: T9

Начало второго оператора: T10

Окончание второго оператора: T19

Матрица для подстановки:

**********************************************************

T5 ¦ 1 1 1 1 ¦

@TMP3 ¦ 0 1 1 1 ¦

@TMP4 ¦ 0 0 1 1 ¦

T20 ¦ 0 0 0 1 ¦

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP3:

начальная вершина T6, конечная вершина T9

Текущее состояние фундаментальной матрицы:

****************************************************************************************************************************

T1 ¦ 1 71.43 70.43 34.72 34.72 34.72 34.72 35.71 70.43 1 ¦

T2 ¦ 0 71.43 70.43 34.72 34.72 34.72 34.72 35.71 70.43 1 ¦

T3 ¦ 0 71.43 71.43 35.21 35.21 35.21 35.21 36.21 71.43 1 ¦

T5 ¦ 0 71.43 70.43 35.72 35.72 35.72 35.72 35.71 71.43 1 ¦

@TMP3 ¦ 0 71.43 70.43 34.72 35.72 35.72 35.72 35.71 71.43 1 ¦

@TMP4 ¦ 0 71.43 70.43 34.72 34.72 35.72 35.72 35.71 71.43 1 ¦

T20 ¦ 0 71.43 70.43 34.72 34.72 34.72 35.72 35.71 71.43 1 ¦

@TMP2 ¦ 0 71.43 70.43 34.72 34.72 34.72 34.72 36.71 71.43 1 ¦

T21 ¦ 0 71.43 70.43 34.72 34.72 34.72 34.72 35.71 71.43 1 ¦

T22 ¦ 0 0 0 0 0 0 0 0 0 1 ¦

****************************************************************************************************************************

Конструкция ВЕТВЛЕНИЕ

Матрица для подстановки:

**********************************************************

T6 ¦ 1 0.365 0.635 1 ¦

@TMP5 ¦ 0 1 0 1 ¦

@TMP6 ¦ 0 0 1 1 ¦

T9 ¦ 0 0 0 1 ¦

**********************************************************

Вызвано распознавание шаблона для подграфа @TMP5:

начальная вершина T8, конечная вершина T8

Текущее состояние фундаментальной матрицы: ...

	1	2	3	4	5	6	7	8	9	10	11
1	1	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
2	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
3	0	71,429	71,429	36,214	35,214	35,214	22,361	12,853	35,214	35,214	35,214
4	0	71,429	70,429	36,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
5	0	71,429	70,429	35,707	35,721	35,721	22,683	13,038	35,721	35,721	35,721
6	0	71,429	70,429	35,707	34,721	35,721	22,683	13,038	35,721	35,721	35,721
7	0	71,429	70,429	35,707	34,721	34,721	23,048	12,673	35,721	35,721	35,721
8	0	71,429	70,429	35,707	34,721	34,721	22,048	13,673	35,721	35,721	35,721
9	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	35,721	35,721	35,721
10	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	35,721	35,721
11	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	35,721
12	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
13	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
14	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
15	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
16	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
17	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
18	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
19	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
20	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
21	0	71,429	70,429	35,707	34,721	34,721	22,048	12,673	34,721	34,721	34,721
22	0	0	0	0	0	0	0	0	0	0	0

	12	13	14	15	16	17	18	19	20	21	22
1	114,59	79,87	34,721	34,721	15,069	19,652	34,721	34,721	34,721	70,429	1
2	114,59	79,87	34,721	34,721	15,069	19,652	34,721	34,721	34,721	70,429	1
3	116,22	81,005	35,214	35,214	15,283	19,931	35,214	35,214	35,214	71,429	1
4	114,59	79,87	34,721	34,721	15,069	19,652	34,721	34,721	34,721	71,429	1
5	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
6	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
7	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
8	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
9	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
10	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
11	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
12	117,89	82,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
13	117,89	83,171	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
14	114,59	79,87	35,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
15	114,59	79,87	34,721	35,721	15,503	20,218	35,721	35,721	35,721	71,429	1
16	114,59	79,87	34,721	34,721	16,069	19,652	35,721	35,721	35,721	71,429	1
17	114,59	79,87	34,721	34,721	15,069	20,652	35,721	35,721	35,721	71,429	1
18	114,59	79,87	34,721	34,721	15,069	19,652	35,721	35,721	35,721	71,429	1
19	114,59	79,87	34,721	34,721	15,069	19,652	34,721	35,721	35,721	71,429	1
20	114,59	79,87	34,721	34,721	15,069	19,652	34,721	34,721	35,721	71,429	1
21	114,59	79,87	34,721	34,721	15,069	19,652	34,721	34,721	34,721	71,429	1
22	0	0	0	0	0	0	0	0	0	0	1