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

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

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

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

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

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

Добавлен: 21.10.2024

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

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

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

Rbsmax (a, n, m, y, i, k,)
array a, integer	n.m.i.k.	realy.
T
enter
integer	p^o
y-0
p-m)x	signti)&0	F	exit
p-m)x	signti)&0		exit

p =p*l

a-im) x

signu)&0

absia[p,g])>y

enter

y=absiafp,a]j

• F ,

I-P

к4

exit

Рис. 42. Блок-схемный граф

§ 8. 2. ДРУГИЕ НАПРАВЛЕНИЯ ПРИМЕНЕНИЯ

ТЕОРИИ ГРАФОВ

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

Современные запоминающие устройства обеспечивают возмож-

200

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

В настоящее время известны работы [89], в которых семантика структуры данных представляется ориентированным графом с по меченными вершинами. Эти графы носят название У-графов.

Вершинами У-графа являются части структуры данных.

Дуги графа представляют пути доступа в структуре, или, дру гими словами, связи в У-графе.

Таким образом, У-граф представляет собой семантику структу ры данных и пути доступа к ним.

Операции по преобразованию структур данных могут задавать ся специальным языком описания данных. В случае представления структур данных в виде У-графа таким языком является язык yERS [89], который полностью освобождает программиста от опи сания структур данных.

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

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

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

В этой связи особое значение приобретает понятие уровня [31} или яруса [62] графа. Введение понятия уровня позволяет произ водить идентификацию вершин структурного графа путем указа ния уровня, на котором вершина находится. Кроме того, появляет ся возможность определения показателей, характеризующих конфигурацию структурного графа. Примерами таких показателей могут служить: удельный вес уровня, средняя полустепень вершин графа, средняя полустепень вершин уровней графа, коэффициенты связности уровней и другие.

Показатели конфигурации структурного графа позволяют про изводить количественный анализ структуры и связей между эле

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

20)

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

Графы являются удобным математическим аппаратом и для моделирования различных процессов, характеризующихся боль шим числом взаимосвязанных или иерархически соподчиненных факторов.

Уже сейчас известны примеры использования графов для опи сания различных социологических исследований [44]. Примерами таких исследований могут служить модели взаимоотношения и по ведения людей в малых коллективах, модели социальной психо логии. В этих моделях вершины графа представляют индивиду умов, а ребра — некоторые отношения между соответствующими индивидуумами. Так как взаимоотношения между двумя индиви дуумами могут носить положительный характер, отрицательный характер или отсутствовать, то используются графы с помеченны ми ребрами. Ребра в таких графах помечаются знаками «плюс» или «минус».

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

ЛИ Т Е Р А Т У Р А

1.Материалы X X I I I съезда Коммунистической партии Советского Союза. М., Политиздат, 1966.

2. Б р е ж н е в		Л.	И. Отчетный	доклад	Центрального	Комитета			КПСС
X X I V съезду Коммунистической партии Советского Союза. М., Политиздат, 1971.
3.	К о с ы г и н А. Н. Директивы			X X I V съезда КПСС по пятилетнему плану
развития народного		хозяйства СССР		на 1971—1975 годы. М., Политиздат, 1971.
4. Автоматизация			программирования. Сб. переводов под ред. Ершова						А. П.
М., Физматгиз, 1961.
5. А л ф е р о в а		3.	В., Е з ж е в а	В. П. Применение теории графов в эконо
мических расчетах. М., «Статистика», 1971.
6.	А л ф е р о в а	3. В. Принцип построения логических схем программ							обра
ботки информации при учете. Вопросы расчета					и конструирования АВМ. Вып. 1.
М., Машгиз, 1960.
7. А л ф е р о в а		3. В. Новый метод расчета подетальных цеховых планов.
Вопросы радиоэлектроники. ГКРЭ при СМ СССР. Серия V I I , № 4,								1960.
8.	Б а р з д и н ь	Я. М. Сложность		программ, распознающих			принадлежность
натуральных чисел, не превышающих				П, рекурсивно перечисленному				множеству.
Доклады АН СССР. Т. 182, № 6, М„ «Наука», 1968.
9.	Б а р з д и н ь	Я. М. Сложность программ. Доклады				АН	СССР. Т. 182,
№ 6.
10.	В а с и л ь е в	Ю. Анализ свойств структурного графа — основа модели

рования организации больших систем управления. Статистика, информация, вы числительная техника (Материалы научных совещаний молодых специалистов). Вып. 1, ЦСУ СССР, М., 1969.

11.

Б а р з д и н ь

Я. М.

Сложность

распознавания

симметрии

на

машинах

Тьюринга. — В

сб.: Проблемы

кибернетики. Вып. 15, 1965, с. 245—248.

12.

Б л ю м

М. Об объеме

машин. — В сб.: Проблемы

математической

логи

ки. М., «Мир»,

1970.

13. Б е р ж

К. Теория графов и ее применение. М., ИЛ, 1962.

14.

Г л е б о в

Н. И. Синтез операторов. — В

сб.: Проблемы

кибернетики.

Вып. 8, М., Физматгиз, 1962.

|1б. Г л е б о в

Н. И. Об

алгоритмической

эквивалентности подмножеств ка

тегории.— В сб.: Проблемы

кибернетики. Вып. 8, М., Физматгиз,

1962.

16.

Г л у ш к о в

В. М. О

простых алгоритмах анализа и синтеза

магазин

ных автоматов. — «Кибернетика», № 5, АН УССР, Киев, 1968.

17.

Г л у ш к о в

В. М. Введение в кибернетику. АН УССР, Киев,

1964.

18.

Г л у ш к о в

В. М. [и

др.]. Вопросы развития

структуры

УВМ в

связи

с системами их математического обеспечения. — «Кибернетика», №

5, Киев,

1967.

il9. Г о р е л ь

Э. Л. Об операторных

схемах

Янова с

отношением

конечной

эквивалентности. — «Кибернетика»,

№

АН

УССР, Киев,

1971.

20.

Г р о с с

М.,

Л а н т е н

А.

Теория формальных

грамматик. М.,

«Мир»,

1971.

21.

Д а н е л я н

Т. Я. К вопросу повышения качества транслирующих

систем.

Диссертация

на

соискание

ученой

степени

кандидата

экономических

наук

МЭСИ, 1971.

203

22.

Е в р е и н о в

Э. В., К о с а р е в

Ю. Г. Матричный

Р-язык

для

описания

параллельных

алгоритмов. — В сб.: Вычислительные

системы. Вып. 17,

Новоси

бирск,

1965.

23.

Е в р е и н о в

Э. В., К о с а р е в

Ю. Г. Однородные универсальные

вы

числительные

системы

высокой

производительности.

«Наука»,

СО, АН

СССР,

1966.

24.

Е р ш о в

А. П. Сведение задачи распределения памяти при составлении

программ к задаче раскраски вершин графов. Доклады АН СССР. Т.

142, № 4,

1962.

25.

Е р ш о в

А.

П.,

Л я п у н о в

А. А.

О формализации

понятия

програм

мы. — «Кибернетика», № 5, АН УССР, Киев,

1967.

26.

Е р ш о в

А. П. Операторные

алгоритмы. Ч. I . — В

сб.: Проблемы

кибер

нетики. Вып. 3, М., Физматгиз, 1960.

27.

Е р ш о в

А. П. Операторные алгоритмы. Ч.

I I . — В

сб.: Проблемы

ки

бернетики. Вып. 8, М., Физматгиз,

1962.

28.

Е р ш о в

А. П. Об операторных схемах над общей и распределенной

памятью. — «Кибернетика», 1968, № 4.

29.

Е р ш о в

А.

П.

Теория

программирования

и вычислительные

системы.

М., «Знание»,

1972.

30.

3 в о н к и н А. К., Л е в и н

Л. А. Сложность

конечных

объектов

обо

снование

понятий

информации и случайности с помощью теории

алгоритмов. —

«Успехи

математических

наук». Т. 25,

вып. 6,

1970.

31.Е р ш о в А. П. Об операторных схемах Янова.— В сб.: Проблемы ки бернетики. Вып. 20, 1968.

32.Е р ш о в А. П. Аксиоматика распределения памяти. Теория языков и

методы	построения		систем		программирования. Труды		симпозиума.			Киев —
Алушта, 1972.
33.	К а р п	Р. М. Заметка о приложении теории графов к						программированию
для цифровых		вычислительных машин. — «Кибернетический						сборник».		Вып. 4,
М., ЙЛ,	1962.
34.	К а л у ж н и н		Л. А. Об алгоритмизации математических						задач. — В		сб.:
Проблемы кибернетики. Вып. 2, М., Физматгиз, 1959.
35.	К а н о в и ч		М. И.,		П е т р и	Н. В. Некоторые теоремы		о	сложности		нор
мальных алгоритмов			и	вычислений. Доклады АН СССР. Т. 184, № 6,						1969.
36.	К а н о в и ч М.			И.	О сложности разрешающих		алгоритмов.			Доклады
АН СССР. Т. 186, № 5,				1969.
37.	К л о с с	Б. М.		Определение		сложности алгоритмов. Доклады АН СССР.

Т.157, № 1, 1964.

38.К о л м о г о р о в А. Н. Три подхода к определению понятия количество информации. —«Проблемы передачи информации». Т. 1. 1965, № 1.

39. К о р о л е в

М. А. Некоторые

теоретические

вопросы

механизированной

обработки экономической

информации.

Диссертация на соискание ученой степе

ни доктора экономических наук. МЭСИ,

1966.

40. К о р о л е в

М. А. Обработка

экономической информации

на

электрон

ных машинах. М., «Экономика»,

1964.

41. К о р о л е в

М.

А.

[и

др.].

Сообщение

об

алгоритмическом

языке

АЛГЭК. — «Кибернетика», № 2, АН УССР, Киев, 1966.

42. К о р о л е в

М. А. '[и др.]. Формальное

описание

алгоритмического

языка

АЛГЭК-У. МЭСИ, 1966.

43. К о л м о г о р о в

А.

Н.,

У с п е н с к и й

В. А.

определению

алгорит

ма. — «Успехи математических наук». Т. X I I I , вып. 4

(82), Г958.

•

44. К е м е н и

Дж.,

С н е л л

Д ж .

Кибернетическое

моделирование,

некото

рые приложения. М., «Советское радио»,

1972.

45. К р и н и ц к и й

И. А. Равносильные преобразования

алгоритмов

про

грамм. М., «Советское радио»,

1970.

46. К у л и к

В. Т. Алгоритмизация

объектов управления.

Справочник.

Киев,

«Наукова думка»,

1968.

47. К у ш н е р е в

Н. Т.,

Неменман

М. Е.,

Цагельский

В. И.

Программиро

вание для ЭВМ

«Минск-32». М., «Статистика»,

1972.

204

48.

Л а в р о в

С.

Об

экономии

памяти в

замкнутых

операторных

схе

мах.— «Вычислительная

математика

математическая

физика»,

1962,

№

49.

Л я п у н о в

А. А. О

логических

схемах

программ. — В

сб.:

Проблемы

кибернетики. Вып. 1, М., Физматгиз,

1958.

50.

М а й м и н а с

Е.

Классификация

информации

экономике. — «Эко

номика

и математические

методы». Т. 1, вып. 4,

1965.

51. М а н н а

Правильность

программ. — «Кибернетический

сборник»,

Вып. 7. Новая серия, М., ИЛ,

1970.

52.

М а р к о в

А. А. О

нормальных

алгоритмах,

вычисляющих

булевы

функции. Доклады АН СССР. Т. 157, № 2,

1964.

53.

М а р т и н-Л е ф

П.

О.

понятии

случайной

последовательности. —

«Теория вероятностей

и ее применение». Т. И, № 1,

1966.

54.

М а ц я щ и к

К.,

П о с п е л о в

Д.

А.

Оптимальное поярусное

распреде

ление

программы

на

параллельно

работающие

вычислительные

устройства. —

сб.:

Сети передачи

информации

их

автоматизация;

М.,

«Наука»,

1965.

55.

М а р к о в

А. А.

Теория

алгоритмов. Труды

математического

института

АН

СССР. Т. 42, 1954.

56.

М е р и л

Т.

Вычислительные

цепи

упрощения

машинных

программ.

Экспресс-информация, серия ВТ, № 1,

1963.

57.

М о д и н

А. А.,

З и н г е р

И.

С ,

К о р о т я е в

М.

Ф. Исследование и

анализ

потоков информации на промышленных предприятиях. М., «Наука»,

1970.

58.

М о р о з о в

В. П. Транслирующая

система

МЭСИ-2

с алгоритмического

языка

АЛГЭК-С на ЭВМ «Минск-32». Диссертация

на

соискание ученой

степе

ни кандидата экономических наук. М., МЭСИ,

1970.

59.

Н а р и н ь я н и А. С. Некоторые

вопросы

асинхронного

программирова

н и я . — В

сб.: Труды

I I I Всесоюзной

конференции по информационным поисковым

системам

автоматизированной

обработке

научно-технической

информации».

М., ВИНИТИ,

1967.

60.Описание и анализ потоков информации в системах управления пред приятиями и организациями. Экспериментальная методика. Институт техничес кой кибернетики. М., 1966.

61.О р е О. Теория графов. М., «Наука», 1968.

62.П о с п е л о в Д. А. Введение в теорию вычислительных систем. М., «Со ветское радио», 1972.

63.П е т р и Н. В. Сложность алгоритмов и время их работы. Доклады АН

СССР. Т. 186, № 1, 1969.

64.	П е й д ж е р	Д. О проблеме нахождения		минимальных	программ		для
68.	Проблемы математической логики. М., «Мир», 1970.
65.	П о с п е л о в	Д. А. Классификация структур алгоритмов, реализуемых
на вычислительных		системах; —• «Техническая	кибернетика», №		5,	АН СССР,
1967.
66.	П у ч и н ь я н	В. К-, Ш е и н П. Д. Задача		оптимального	разбиения		гра
фа и компоновка устройств УВМ. — В сб.: Системы распределения						ресурсов	на
графах. ВЦ АН СССР, 1970.
67.	С а в и н к о в	В. М., С и д о р е н к о	Л. А.	Синтаксический		транслятор

анализирующего типа. М., «Статистика», 1972.

68.Проблемы математической логики. М., «Мир», 1970.

69.Т о н о я н Р. Н. Логические схемы алгоритмов и их эквивалентные пре

образования. — В		сб.: Проблемы			кибернетики, Вып. 14,		М.,	Физматгиз,		1964.
70.	Т р а х т е н б р о т			Б. А.	Сложность алгоритмов		и	вычислений.		Новоси
бирск,	1967.
71.	Т у з о в В. А. Проблемы				разрешения для граф-схем			с	перестановочными
операторами. —• «Кибернетика», № 4, АН УССР, Киев, 1971.
72.	Ф а л ь к	В.	Н.,	К у т е п о в		В. П. Функциональные			граф-схемы и их
эквивалентные преобразования. I ВКП, секция А, ИКАН УССР,									1968.
73.	Ф е л л е р	В.	Введение		в	теорию вероятностей	и	ее	приложения. М.,
ИЛ, 1952.
74.	Ф и ш е р	Ф. П.,		С у и н д л		Д. Ф. Системы программирования, М., «Ста
тистика», 1971.

205

75.

Ф о и Н е й м а н

Д ж о н .

Теория

самовоспроизводящихся

автоматов.

М., «Мир», 1971.

76.

Ф о р д

Л., Фулкерсон Д. Потоки в сетях. М., «Мир», 1968.

77. X а р т м а н и с

Дж., С т и р н з

Р. С. О вычислительной сложности

ал

горитмов. — «Кибернетический

сборник»,

№ 4,

М.,

«Мир».

Новая

серия, 1967.

78.

Ц е й т и н Т. С. Оценка

числа

шагов

при применении нормального

ал

горитма. «Математика

в СССР за 40 лет». Т. 1, М., 1959.

79.

Ш о л о м о в

Л. А.

Критерии

сложности

булевых

функций. — В

сб.:

Проблемы кибернетики. Вып. 17, М., Физматгиз, 1966.

80.

Ш у р а к о в

В. В. Вопросы

обработки

массовых

статистических

данных.

Диссертация на соискание ученой степени доктора

экономических наук.

МЭСИ,

1971.

81.

Ш у р а к о в

В. В., Б а л а к и н а С И . Анализ

алгоритмов

данных

на

основе испытаний ИНК-70. Отчет П Н И Л МЭСИ, 1970, декабрь.

82.

Э п ш т е й н

В. Л. О

приложении теории графов для описания

ана

лиза схемы потоков информации в управляющих

системах. — «Автоматика и

телемеханика»,

1965, № 8.

83.

Я н о в

Ю. И. О логических

схемах' алгоритмов. — В сб.: Проблемы

ки

бернетики. Вып. 1, М., Физматгиз,

1958.

84.

Я н о в

Ю. И. О

матричных

схемах. Доклады

АН СССР. Т. Ill3, № 2,

1957.

85.

Я н о в

Ю. И. О локальных

преобразованиях

схем

алгоритмов.—В

сб.:

Проблемы кибернетики. Вып. 20, М., Физматгиз,

1967.

86.

B l u m

М. A

machine-independent

theory of

the

complexity

of recursive

functions,

j . ACM,

14, 2, 1967.

87.

С h a i n t i n

G. T. Of the length of programs

for

computing Unite binary

signences,

j , ACM,

13, 1966.

88.

M a n n a Z. Proportus

programs

onul the

ferst-order predicate

calcu

lus j .

ACM, april, 1969.

89.Communications of the ACM, oct., 1971, vol. 14, N 10.

90.Journal of computer and system Sciences, 5, 1971.

Смотрите также файлы

Бирзниекс, Л. В. Импульсные преобразователи постоянного тока.pdf

Бронский, А. И. Основы выбора конструкций корпуса судна.pdf

Будин, А. Я. Тонкие подпорные стенки.pdf

Бурштейн, Г. Я. Экономика обогащения углей.pdf

Быков, В. В. Методы науки.pdf

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

Смотрите также файлы

Информация

Списки файлов

Дополнительно