1.Граф рассматривается по уровням (послойно). На первом уровне всегда одна вершина (узел).
2.Число вершин (узлов) на втором уровне и всех последующих определяется числом ребер, исходящих и входящих в/ из узлов-родителей. Число этих ребер назначается при помощи датчика случайных чисел. Случайное число должно быть распределено равномерно в диапазоне 0 …1.
3. Настройки датчика случайных чисел производятся исходя из минимального числа ребер, исходящих из каждой вершины (узла) – 0, максимального – (m – 1). Для расчета случайного графа число m – задается в исходных данных. Например, если m – 1 = 3 (m=4), то диапазон случайных значений числа выходящих из узла ребер
либо 0, либо 1, либо 2, либо 3.
4. Вершины (узлы) каждого уровня помещаются в свою строку «таблицы вершин». По каждой строке таблицы проводится подсчет количества вершин.
Расчет графа и строкообразование таблицы не может продолжаться бесконечно. Этот процесс останавливается в соответствии с исходными данными и в соответствии с правилом остановки.
5.Правила остановки вычислений для построения графа.
В работе применено два правила остановки вычислений для построения графа: правило А и правило В.
Правило А – построение графа прекращается при достижении числа узлов заданного значения N.
Правило В-построение графа прекращается при выполнении двух условий. Первое условие - число узлов 
заданному числу N. Второе условие- последний уровень иерархии графа должен быть до конца заполнен висячими узлами иными словами во всех узлах предыдущего уровня процесс генерации узлов должен быть проведен.
Для этого в алгоритме построения графа с правилом остановки В необходимо запоминать имя последнего узла каждого уровня после чего проверять первое условие. Иными словами по правилу В расчет графаведется до тех пор, пока сумма числа узлов Q по всем завершенным строкам(уровням иерархии графа) не станет ³ заданного числа N.
|
|
Как только сумма числа узлов по таблице достигнет числа заданного в правиле остановки, расчет прекращается, и все узлы последней строки объявляются висячими.
Для правила остановки А к висячим узлам надо добавить и узлы предпоследнего уровня, не успевшие дать потомков из-за остановки вычислений
К этому числу висячих узлов добавляются все висячие узлы на предыдущих уровнях, не имеющие потомков, – узлы, у которых число исходящих ребер получилось равным 0.
6. Производится подсчет числа путей на графе. Это число характеризует, трудоемкость отладки ПО. Для дерева – это число висячих вершин. Подсчитывается также число уровней иерархии графа.
Производится подсчет параметра a
Число всех вершин
a = -----------------------------.
Число висячих вершин
Данное число является случайным, так как получено с помощью датчика случайных чисел.
7. Расчет построения повторяется для другого случайного графа, который образуется по описанному алгоритму (в цикле) при других значениях случайного числа ребер исходящих из узлов графа, но при тех же исходных данных m и N
Число построенных случайных графов R задается в исходных данных к заданию
8. Если при первом шаге для верхней вершины (корневой) датчик случайных чисел показывает 0 потомков (такое вполне может быть), то расчет графа прекращается и делается следующая попытка. Это справедливо только для первого шага. Этот случай в отчете и при подсчете R не учитывается.
|
|
9. Если граф обрывается (такое вполне может быть при небольших значениях m в частности при m=3) при числе построенных узлов меньше 10, то эта реализация также в отчет и счетчик R не берется см. п8.
10. В результате построения R случайных деревьев получается R случайных значений параметра a. Необходимо вычислить математическое ожидание этого параметра и привести его в отчете.
Содержание работ N 1-5
Работа 1.Анализ предметной области, синтез модели структуры программы (схема программы).
Работа 2. Построить случайный граф ПО, для которого число выходящих из вершины ребер определяется датчиком случайных чисел. Определить значение структурного параметра 
всех узлов /число висячих узлов. Привести гистограмму для полученных при построении графа значений (m-1). Убедится в правильности построения гистограммы. В тексте программы и в отчете привести «утверждение», подтверждающее правильность. Правило остановки построения графа (А или В) приведено в задании.
Работа 3. Этим же алгоритмом построить детерминированный граф ПО при фиксированном значении числа выходящих из узлов ребер (mфикс -1) = (m-1). Это можно сделать, заглушая обращение к датчику случайных чисел, и для каждого узла использовать заданную константу при определении числа исходящих ребер. Определить число висячих узлов и параметр 
. Убедится в правильности расчета структурного параметра α. В тексте программы и в отчете привести «утверждение».
Работа 4. Подсчитать среднее число висячих вершин у совокупности R случайных графов ПО, определить среднее значение и дисперсию структурного параметра a = отношению общего числа вершин к числу висячих вершин.
Работа 5. Исследовать сходимость значения структурного параметра к устойчивому значению с ростом числа узлов графа Р, построив для этого функцию изменения структурного параметра a с ростом числа узлов Р. Для данного графа построить графический фрагмент из первых двадцати узлов.
Примечание. Наличие циклов и дополнительных связей между узлами влияет на число путей, но не влияет на параметр a.