Программа позволяет рассчитывать среднее время выполнения алгоритма, а также минимальную, среднюю и максимальную трудоёмкость.
Трудоёмкость алгоритма – количество вычислительной работы, требуемой для реализации алгоритма. В задачах оценки трудоемкости операторы алгоритма разделяют на функциональные, перехода и ввода-вывода. Функциональный оператор задает преобразование на множестве данных, т.е. задает некоторую совокупность вычислительных операций. Оператор перехода задает порядок вычисления функциональных операторов и правило выбора одного из возможных путей развития вычислительного процесса, соответствующего текущим значениям данных. Оператор ввода-вывода задает обращение к определенному файлу с целью передачи некоторого количества информации. Функциональные операторы и операторы перехода называют основными операторами.
Совокупность операторов и связей между ними наиболее наглядно представляется графом алгоритма, где вершины соответствуют основным операторам алгоритма, а дуги отображают связи между операторами.
Вершины графа бывают трех типов: начальная, конечная и операторная. Начальная вершина определяет начало алгоритма. Эта вершина не имеет ни одного входа и имеет только один выход. Конечная вершина определяет конец алгоритма и имеет не менее одного входа и ни одного выхода. Операторная вершина соответствует основному оператору или оператору ввода-вывода. Если она представляет функциональный оператор или ввода-вывода, то может иметь не меньше одного входа и только один выход. Если она представляет оператор перехода, то может иметь не меньше одного входа и не меньше двух выходов.
Граф алгоритма является корректным, если выполняются условия:
• имеется только одна начальная и только одна конечная вершина;
• для каждой вершины кроме начальной существует по крайней мере один путь, ведущий в эту вершину из начальной;
• из каждой вершины кроме конечной существует по крайней мере один путь, ведущий из этой вершины в конечную;
• выход из любой вершины должен вести только к одной вершине графа;
• при любых значениях логических условий существует путь из начальной вершины в конечную, причем любому фиксированному набору значений условий соответствует только один такой путь.
Среда разработки: Microsoft Visual C++
1)Порядок работы с программой:
а)рисование вершин:
При запуске программы на экране появятся пунктирные окружности - это те ме-
ста, где можно ставить вершины графа. Перед тем как рисовать вершины, необ-
ходимо выбрать в меню пункт 'Project->Рисование вершин' или нажать кнопку с
изображением вершины на панели инструментов, которая находится в верхней ча-
сти экрана. Вершина ставится путём нажатия левой кнопки мыши.В появившемся
окне необходимо ввести номер и трудоёмкость вершины. Если вершина конечная,
то следует поставить соответствующую отметку.
На параметры вершины накладываются следующие ограничения:
- трудоёмкость и номера вершин должны быть целыми положительными числами;
- нумерация вершин должна быть последовательной и начинаться с нуля;
- вершины могут ставиться в любом порядке и месте;
- номера вершин не должны повторяться.
Быстрый вызов: Ctrl+V
б)рисование дуг:
Для того, чтобы перейти к рисованию дуг графа - необходимо выбрать пункт ме-
ню 'Project->Рисование дуг' или нажать на панели кнопку c изображением стре-
лочки. Чтобы нарисовать дугу, необходимо левой кнопкой мышки нажать на вер-
шине из которой должна исходить дуга, а затем на вершине, в которую она до-
лжна входить. После чего появится диалоговое окно, в котором необходимо вве-
сти вероятность перехода.
Ограничения на параметры и порядок рисования дуг:
- все вершины должны быть соединены дугами;
- в вершину может входить(исходить) несколько дуг;
- между двумя вершинами должна быть только одна дуга;
- вероятность перехода должна находиться в интервале (0;1];
- cумма вероятностей перехода из вершины должна быть равна 1.
Быстрый вызов: Ctrl+D
в)расчёт параметров графа:
Для того, чтобы рассчитать параметры графа необходимо выбрать в меню пункт
'Project->Произвести расчёт' или нажать кнопку на панели с изображением вос-
клицательного знака. Если в графе не было ошибок, то появится окно с резуль-
татами(см.п.2). При обнаружении ошибок в нижней части экрана появится инфор-
мация о типе ошибок (см.п.3).
Быстрый вызов: Ctrl+R
2)Результаты расчётов:
Результат работы программы - три числа:
- средняя трудоемкость;
- минимальная трудоемкость;
- максимальная трудоемкость.
Кроме этого, в процессе работы, рассчитываются корни системы уравнений. Эти
цифры могут совпадать, при этом минимальная трудоёмкость всегда меньше или
равна максимальной. Поскольку значения минимальной и максимальной трудоёмко-
стей зависят от кратности выполнения циклов, то минимальная трудоёмкость мо-
жет оказаться, например, больше чем средняя. Если граф содержит циклы, то в
процессе работы программа запросит Вас ввести дополнительные данные: минима-
льное и максимальное число повторений цикла для каждого обнаруженного цикла.
На циклы накладываются следующие ограничения:
- циклы не могут пересекаться;
- из каждого цикла имеется только один выход.
3)Типы ошибок:
При расчётах параметров графа могут возникнуть различного рода ошибки. Ниже
приведены основные их типы и возможные способы решения:
- <Отсутствует конечная вершина К!>
[необходимо поставить конечную вершину]
- <Неправильная нумерация вершин! Отсутствует вершина с номером X>
[Вероятнее всего, количество вершин не соответствует нумерации. Необхо-
димо проверить правильность нумерации вершин]
- <Сумма вероятностей перехода из вершины X должна быть равна 1!>
[Необходимо проверить правильность указания вероятностей перехода из
вершины X]
- <Нет выхода из вершины X!>
[Не все вершины соединены]
- <Нет входа в вершину X!>
[Не все вершины соединены].
| 