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

Скачать файл (8,15Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 21.10.2024

Просмотров: 70

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Участок от метки Н4 по Н5 обеспечивает отбор языков по при

знаку «вспомогательные операции».
Участок алгоритма от метки Н5 по Н6		осуществляет		отбор
языков, у которых указаны время на изучение, нотация и				катего
рия пользователя.
Константа ТС1 является	выделителем	признаков	«нотация»,
«категория пользователя» и	«время на	изучение»,	константа
ТСЗ — признака «категория	пользователя»,	константа	ТС4 — при


знака	«время изучения»,				константа	ТС5—признака			«нотация».
Если отбор языков по времени, нотации							и категории пользова
теля нас не удовлетворил, то пропускаем							этапы	отбора		по при
знакам	«категория		пользователя»,			«нотация»		и	«минимальное
время на изучение».
Участок		алгоритма		от	метки Н6	по Н7	соответствует			отбору
по признаку «нотация».
Участок от метки Н7 по М7 соответствует отбору языков по
признаку «категория			пользователя».
Участок		алгоритма		от	метки М7	по Н8	соответствует			отбору

языков «с минимальным временем на изучение».

Внутри этого участка в свою очередь можно выделить три под-

участка:
а)	с М7		по М9 —выбор констант выделения времени на изуче
ние соответствующей					категории пользователя; в качестве				таких
констант используются константы КВРА и КВРБ;
б)	с	М9	по	Кб — выбор		минимального	времени	на изучение;
в)	с	Кб	по	Н8 — выбор		в новое поле	языков с	минимальным
временем изучения.
Участок			алгоритма		от метки Н8 по Н соответствует отбору язы
ков по этимологическому признаку.
При экспериментальном решении задачи априорного выбора
языка	программирования для экономических исследований								с ис

пользованием теории графов картотека языков содержала следую щие двадцать языков: АЛГЭК, АЛГЭМ, АЛГОЛ-60, АЛГОЛ-68,

КОБОЛ, ФОРТРАН, СИМУЛА,	КОМИТ,	СНОБОЛ,	РЛ - 1,
ЛИСП-2, МИДАК, МИТРА, АПРОКС, MAP,		СИРИУС,	CPL,
CPS, AUTOSTAT, АЛГРА. Язык	АЛГРА — некоторый условный
язык оперирования с графами.

Характеристические параметры проблемы и языков были по лучены путем экспертных оценок. При оценке языку АЛГРА ус ловно были приписаны наиболее оптимальные параметры.

Результаты экспериментального решения при заданных усло виях приведены в диаграмме на рис. 33. Цифры на диаграмме, соответствующие этапам выбора, имеют следующий смысл:

1 —выбор по параметру «область применимости»;

2 — выбор по параметру «внедренность языков»;

3 — выбор по параметру «тип информации»;

4 — выбор по параметру «категория информации»;

5 — выбор по параметру «основные операции»;

166

6 — выбор по параметру «вспомогательные операции»;

7 — выбор по параметру «нотация»;

8 — выбор по параметру «категория пользователя»;

9 — выбор по параметру «минимальное время» на изучение.

Рис. 33. Диаграмма априорного выбора

Очевидно, что в результате экспериментального расчета был выбран язык АЛГРА. Поскольку целью эксперимента была про верка методики отбора, то результаты подтвердили ее правиль ность.

Глава VII П Р О Г Р А М М Н О Е О Б Е С П Е Ч Е Н И Е

Э К О Н О М И Ч Е С К И Х РАСЧЕТОВ С И С П О Л Ь З О В А Н И Е М ТЕОРИИ ГРАФОВ

§ 7. 1. ОСНОВНЫЕ ПОЛОЖЕНИЯ

В теории программирования и в экономических рас

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

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

Программное обеспечение строится в виде пакета простой структуры. Тело пакета состоит из комплекса частично взаимо связанных программ, представленных на языке АЛГЭК-С. Язык АЛГЭК-С выбран с целью реализации данного пакета программ на машине «Минск-22» или любой другой машине, имеющей тран

слятор с данного языка. Пакет			обеспечивает		решение следующих
задач:
Ввод грата Взаимо			Ввод	градзов		алгоритмов
связи документов

Анализ информационного				Перевод		графов
графа (получение		табл!)		о	матрицы
Анализ	потопов			Оценна		стоимости
информации				алгоритма
Ввод графов	документов		Синтез			алгоритмов
I
Подсчет	объемов		Перевод из матрицы
информации				В граф
Рис.	34.	Схема взаимосвязи задач		в	пакете

168

1)анализ потоков информации;

2)расчет объемов информации;

3)	определение вычислительной сложности алгоритмов задач;
4)	синтез алгоритмов.

Исходными данными для решения этих задач являются:

1)графы взаимосвязи документов по задачам;

2)структурные графы документов;

3)графы алгоритмов задач.

Схема взаимосвязи	задач в пакете приведена на рис. 34.
В памяти машины	графы представляются соответствующими

матрицами смежности. Перевод графа в матрицу смежности так же может быть выполнен автоматизированным путем. В том слу

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

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

Порядок представления исходных графов будет указываться при описании каждого из алгоритмов пакета.

§7. 2. АНАЛИЗ ПОТОКОВ ИНФОРМАЦИИ

Всоответствии с математической моделью, изложенной в § 2.4, процесс анализа потоков информации можно разделить на две

части:	получение	характеристик по информационным связям	за
дач и	получение	основных характеристик потока информации.	В

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

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

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

зации алгоритма анализа	потоков информации		матрица смежно
сти представляется вектором ненулевых элементов.
Блок-схема первой части алгоритма анализа потоков инфор
мации — получения данных табл. 1 приведена			на рис. 35.
В блок-схеме приняты	следующие	сокращенные обозначения:
С Р И Д — Счетчик для	определения	числа Разновидностей Ис
ходных Данных;

169

СРЗ — Счетчик Решаемых Задач; СДЗ — Счетчик количества Документов, используемых при ре

шении одной Задачи;

С Д З Р —то же для Результатных документов;
МАХ — ячейка для хранения				максимального		числа документов
для решения задачи;
МАХР — то же для Результатных документов;
СНЗ — Счетчик Независимых				Задач;
С Р П Д — Счетчик числа Разновидностей					Промежуточных		Дан
ных;
ШД — Шифр последнего Документа;
Ш Р Д — ячейка для хранения				Шифра	Результатного		Доку
мента;
С З Р П Д — Счетчик			числа Задач, Решаемых на основании				Про
межуточных Данных;
С Р Р Д — Счетчик числа Разновидностей					Результатных Данных;
С З Р И Д — Счетчик			числа Задач, Решаемых			на основании Ис
ходных Данных;			3
С		Начало	3		СУД- =	СУД+1
	Ввод графа
	взаимосвязи
/?	документов