|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Оценки сложности одного метода решения задачи включающего поиска
Э. Э. Гасанов
Аннотация:
В работе предлагается метод решения задачи включающего поиска, имеющий три модификации в зависимости от выбранного базового множества: множества монотонных булевых функций, множества элементарных монотонных конъюнкций и множества булевых переменных. Для каждой из модификаций оценивается функция Шеннона сложности метода и среднее значение сложности, причем для функций Шеннона сложности метода найдена асимптотика, совпадающая с асимптотикой функции Шеннона сложности включающего поиска, а для среднего значения — асимптотика логарифма.
Работа выполнена при поддержке Российского фонда фундаментальных исследований,
грант 98-01-00130.
Статья поступила: 13.09.1999 Переработанный вариант поступил: 10.04.2000
Образец цитирования:
Э. Э. Гасанов, “Оценки сложности одного метода решения задачи включающего поиска”, Дискрет. матем., 12:2 (2000), 118–139; Discrete Math. Appl., 10:3 (2000), 295–318
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm329https://doi.org/10.4213/dm329 https://www.mathnet.ru/rus/dm/v12/i2/p118
|
Статистика просмотров: |
Страница аннотации: | 403 | PDF полного текста: | 189 | Список литературы: | 39 | Первая страница: | 1 |
|