English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сайта Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу

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

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

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

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

 

Резюме:

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


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

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

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru