Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.

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

Гасанов Э.Э.
Кафедра математической теории интеллектуальных систем, механико-математический факультет МГУ им М.В.Ломоносова

Скачать статью полностью в формате PDF (280 кб): nizhotinfset.pdf
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x

 

Резюме:

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


Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 95-01-00597)

Дискретная математика (1992) 4, N 3.

Наверх