Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

^Na

АЛГЭК. В результате работы по этой программе определяется частота использования следующих групп операций:

С помощью этой программы производится анализ алгоритмов задач для получения операционных или временных оценок этих алгоритмов, записанных на алгоритмическом языке.

Желательно иметь такой метод оценки сложности алгоритмов, который позволял бы оценить алгоритм до его представления в алгоритмическом языке. Это необходимо и на этапе проектирова­ ния механизированной обработки информации, и на этапе проекти­ рования АСУ, и на этапе проектирования вычислительных центров.

137

В данной работе для определения числа операций и, в частно­ сти, вектора встречаемости операций в алгоритме без записи его на алгоритмическом языке предлагается использовать аппарат графов.

Для определения числа операций алгоритм представляется в виде графа без контуров. Заметим, что любая логическая схема алгоритма может быть преобразована в бесконтурную путем запи­ си цикла максимальное число раз [23].

Как известно, в любом алгоритме можно выделить два вида элементов: операционные элементы и решающие элементы. Опе­ рационным элементам соответствуют отдельные операции или по­ следовательности операций, не прерываемые условной передачей управления. Решающим элементам соответствуют логические опе­ рации, вызывающие условные передачи управления. В качестве такой операции в большинстве случаев используется операция сравнения.

При построении графа алгоритма каждой элементарной опе­ рации (сложение, вычитание, умножение, деление, переадресация, сравнение и т. п.) сопоставляется вершина графа G(X,U). Вер­ шина графа Xi соединяется с вершиной Xi+\ в том и только в том случае, если операция, соответствующая вершине х%+\, выполняет­ ся непосредственно после операции х\. Таким образом, в графах, отражающих алгоритм, из каждой вершины, соответствующей операционному элементу, будет исходить точно по одной дуге, а из каждой вершины, соответствующей решающему элементу, — точно по две дуги.

Алгоритм строится с учетом циклов, отражающих процесс об­ работки информации. Циклы обработки должны быть строго вло­

Всем вершинам графа присваивается некоторый параметр тг -, равный числу соответствующих операций, выполняемых при од­ нократной реализации цикла вычислений, содержащего эти опе­ рации. Для вершин, соответствующих операциям сравнения, этот параметр т,- будет равен, как было ранее замечено, максимально­ му числу этих операций.

Всем дугам графа присваивается некоторый параметр lj, кото­ рый определяет число прохождений по данной дуге в процессе обработки одной информационной совокупности внутри цикла. Под информационной совокупностью понимается либо документ, либо часть документа, имеющая самостоятельное значение.

Число операций для каждой из вершин графа G (X, U) опре­ деляется в результате умножения значения параметра mit соот­ ветствующего данной вершине, на произведение параметров 1} по пути, ведущему от заданной вершины к конечной:

Ni~miY\lj >

138

где / соответствует номерам тех дуг, которые ведут из вершины Xi в конечную вершину.

Суммарное число операций данного вида получается в резуль­ тате суммирования полученных количеств по всем путям, связы­ вающим соответствующие им вершины с конечной.

Рассмотрим расчет числа операций на примере составления сводки о реализации фондов в отделе строительных материалов. Граф алгоритма этой задачи, построенный с учетом изложенных требований, представлен на рис. 26.

При изображении графа цифры в круглых скобках указывают на связь вершин в алгоритме, прерванную введением операций безусловных переходов. Значения параметра т помещены в круж­ ках, а значения параметра / — без кружков. Чтобы не загромож-

Рис. 26. Граф алгоритма для расчета числа операций

139

Глава VI ВЫБОР Я З Ы К А

П Р О Г Р А М М И Р О В А Н И Я

§ 6. 1. МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА

ПРОБЛЕМЫ ВЫБОРА

В настоящее время вычислительные машины стали необходимой частью любой системы обработки информации и тем более любой автоматизированной системы управления. Расшире­ ние сферы вычислительных машин ставит новые проблемы как в теории программирования, так и в теории алгоритмических язы­ ков. Одной из таких проблем является разработка алгоритмов оценки и выбора языков для оптимального программирования за­ дач из заданного класса проблем. Математическая формулировка этой проблемы приведена в работе Т. Я- Данелян [21].

В целях наиболее эффективного применения языков необходи­ мо не только уметь создавать нужные языки и системы програм­ мирования, но и уметь правильно выбирать хороший язык из уже имеющегося класса созданных языков. Неудачно выбранный язык приводит к неоправданным затратам по созданию систем програм­ мирования. Это объясняется тем обстоятельством, что создание формального аппарата для разработок соответствующих систем программирования, особенно практическая разработка и внедре­ ние последних, является трудным делом, предъявляющим высокие требования к квалификации разработчиков, а также сопряжено с большими затратами сил и средств. В связи с этим практика использования языков выдвигает на передний план проблему раз­ работки формального аппарата по выбору языков и оценке ка­ чества как выбираемых языков, так и создаваемых систем про­ граммирования. Совершенно очевидно, что эта проблема носит комплексный характер и ее решение связано с решением ряда научных, инженерно-технических, организационных и других за­ дач.

В практике автоматизации программирования имеется большое число языков программирования как универсальных, так и ориен­ тированных на проблемы. Многие языки могут определяться как наилучшие для данного класса проблем без дополнительных ис­ следований. Но наличие большого набора языков не всегда позво­ ляет использовать наилучший. Применение универсальных языков часто приводит к противоречию между универсальностью и эко-

141

номичностью систем, использующих эти языки. Чем универсальнее

лесообразнее отыскивать сравнительно узкий класс, содержащий интересующие нас языки, и применять их для описания проблем. В этих целях нужно уметь выделять характерные элементы, па­ раметры, составляющие языки программирования, которые дали бы возможность провести соответствие между элементами проблем и языка. Необходимо выработать определенные меры качества языков, с тем чтобы можно было оценить, в каких случаях и для каких задач нужен тот или иной язык (более универсальный, но менее выгодный или, наоборот, более узкий, но выгодный). Уметь квалифицировать язык — значит уметь оценить, какие и насколь­ ко сложные проблемы может описывать язык. В то же время ко­ нечный результат выбора языка программирования зависит от

уже используемых языков и языковых систем и достаточно пред­ ставительного класса задач, решаемых в информационных систе­ мах управления.

Исходя из сказанного, общий подход к решению конкретной проблемы с использованием вычислительной машины можно пред­ ставить в виде трех этапов:

1.Спецификация проблемы.

2.Выбор и уточнение метода решения.

3.Реализация метода решения.

Первые два этапа известны как анализ и проектирование про­ блемы a.i, которыми занимается аналист. Третий этап носит назва­ ние программирования метода решения, которое реализуется про­ граммистом. Разница между этими двумя концепциями в том,что аналист изучает проблему и специфицирует ее решение в языке, доступном для понимания человеку, в то время как программист преобразует данную спецификацию в вид, удобный для передачи метода вычислительной машине. Собственно этап спецификации проблемы расчленяется на шесть самостоятельно поставленных перед аналистом задач:

1. Анализ представительности и типов данных из предметного {/-множества ^-объектов и уточнение множества f'-операций и процедур, определяющих проблему а;.

142