Проблемы алгоритмической сложности решения дискретных оптимизационных задач

Известия ТРТУ

Тематический выпуск

В докладе рассматриваются критерии, по которым осуществляется выбор АБС: интегрируемость, масштабируемость, производительность, открытость системы, надежность и безопасность, темпы модификаций, интерфейсы с другими системами, особенности инсталляции и эксплуатации, перспективы последующего развития АБС.

По экспертным оценкам, базирующимся на указанных критериях, одной из наиболее перспективных российских АБС, на которой и остановил свой выбор Оргбанк, является интегрированная банковская система (ИБС) “Афина”, разработанная фирмой

“ПрограмБанк”. Система реализована по архитектуре “клиент-сервер” на относительно недорогом программно-аппаратном комплексе - промышленной СУБД Oracle, операционной системе Microsoft Windows и многопроцессорном сервере HP.

УДК 658.512

Э. £. Кудряшова ГИПЕРТЕКСТОВАЯ АОС “МОДЕЛИРОВАНИЕ CAD/CAM”

Гипертекстовая автоматизированная обучающая система (АОС) представляет собой реализацию средствами вычислительной техники ассоциативного представления информации. Разработанная гипертекстовая (АОС) ‘Моделирование CAD/CAM’ состоит из содержательной части и гипертекстовой программной оболочки. Содержательная часть включает аппарат моделирования структуры и функционирования интегрированных автоматизированных технических систем CAD/CAM: моделирование параллельных процессов на сетях Петри различной модификации; моделирование вероятностных процессов буферизации цепями Маркова. Гипертекстовая программная оболочка является инвариантным инструментальным средством иерархического представления текстовой и графической информации; предусмотрена возможность экспорта-импорта программных средств. В гипертекстовой программной оболочке присутствуют следующие типы объектов: сеть, тема, рисунок, ссылка. Каждая тема может иметь внутри себя неограниченное число ссылок. Гипертекстовая АОС позволяет создавать иерархическое представление информации на экране дисплея и обеспечивает вызов информации по ссылкам с любого уровня иерархии. Работа пользователя в режиме гипертекста обеспечивает гибкость обучения с максимальным приближением к индивидуальным особенностям обучаемого. Гипертекстовая программная оболочка включает программу форматирования исходного текста, программу компиляции исходной информации в формат гипертекстовой базы данных, программу вывода информации на дисплей и модуль интерфейса, содержащий Help.

Программа разработана с использованием Borland Delphi for Windows и функционирует в ОС MS Windows 95; объем оперативной памяти не менее 8 Мб. Гипертекстовая программная оболочка может использоваться для различных предметных областей.

УДК 519.63

Ю.А. Агранович, Я.Е. Львович, В.Г. Юрасов ПРОБЛЕМЫ АЛГОРИТМИЧЕСКОЙ СЛОЖНОСТИ РЕШЕНИЯ ДИСКРЕТНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Рассматривается дискретная среда (ориентированный граф):

Є = (X, Г, Ь, А), X = {х!..., х„} - вершины графа, Г - множество дуг с весами Ьц = = Цхі, х]) определяемыми заданными соотношениями Ь, Ьу элементы некоторого метрического полукольца А.

Дискретные оптимизационные задачи можно разделить на два класса:

Материалы Международной конференции

“Интеллектуальные САПР”

(О оптимизация в заданной дискретной среде;

(и) проектирование оптимальной дискретной Среды.

Для ориентированного графа известно оперделение энтропии /1 /:

Н(О)- X 0(У) 1) l°g

VsT,/(v)a2

L /М-i I

где | Г | - число вершин графа, | Е | - число рёбер, l(v) - число входящих в вершину рёбер, и сумма берётся по всем вершинам v е Г, для которых l(v) ^2.

С другой стороны, компьютерное решение оптимизационных задач основано на проектировании соответствующего алгоритма S, который в свою очередь имеет собственную метрическую энтропию (сложность) |a(S) 121.

В докладе обсуждаются проблемы определения условий существования и методов получения априорных оценок типа

|j(S) ^ Const.H(G), H(G) ^ Const. (j(S).

Исследования основаны на развитии результатов / 3 /.

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

Оказывается, что для задач класса (i) выполняется первое неравенство, а для задач класса j(ii) - второе, чем по существу, обусловлена данная выше классификация.

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

ЛИТЕРАТУРА

1. J. kieffer and Е. Yang, Ergodic behavior of graph entropy // Electronic Research Announcement of the AMS. V. 3, 1997.

2. A. H. Колмогоров, К определению алгоритма, в кн. “Теория информации и алгоритмов”, М., Наука, 1987.

3. J. Т. Lewis, С. -Е. Pftster and W. G. Sillivan, Entropy, Concentration of Probability and Conditional Limit Theorems //Marcov Proc. and Related Fields 1,319- 386, 1995

УДК 658.512

Б.Х. Санжапов РАНЖИРОВАНИЕ ОБЪЕКТОВ НА ОСНОВЕ НЕЧЕТКОГО ОТНОШЕНИЯ С ИНТЕНСИВНОСТЬЮ ПРЕДПОЧТЕНИЙ

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

Для описания исходной информации используется ориентированный взвешенный граф в = (Х,и) , X - множество вершин в котором каждый объект отождествляется с вершиной, и - множество дуг, определенных отношением Я , т.е. дуга (¡^)е и имеет вес Гу. Вес дуги определяется на основе экспертных оценок, поэтому целесообразно рассматривать его как нечеткое множество. Таким образом,

К={г,Л, ^={(^,10,^)) Я+= (О,-), (¡о)еи}.

Здесь подразумевается , что объект ! предпочтительней объекта ] в ^ раз с достоверностью ц$ц), |0у : Щ—»[0,1].

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