|
Журнал вычислительной математики и математической физики, 2011, том 51, номер 8, страницы 1531–1540
(Mi zvmmf9532)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Асимптотические оценки числа решений задачи дуализации и ее обобщений
Е. В. Дюковаa, Р. М. Сотнезовb a 119333 Москва, ул. Вавилова, 40, ВЦ РАН
b 119991 Москва, Ленинские горы, МГУ
Аннотация:
Получены асимптотики типичных значений числа неприводимых покрытий и длины неприводимого покрытия булевой матрицы для случая, когда число строк $m$ не меньше числа столбцов $n$. Как следствие получены асимптотики типичных значений числа максимальных конъюнкций и ранга максимальной конъюнкции монотонной булевой функции от $n$ переменных, заданной конъюнктивной нормальной формой из $m$ элементарных дизъюнкций. Приведены аналогичные оценки для числа тупиковых покрытий и длины тупикового покрытия целочисленной матрицы (числа максимальных конъюнкций и ранга максимальной конъюнкции двузначной логической функции, заданной множеством нулей). Дан обзор результатов, полученных ранее в данной области. Библ. 18.
Ключевые слова:
сложность задач перечисления, задача дуализации, максимальная конъюнкция, неприводимое покрытие булевой матрицы, тупиковое покрытие целочисленной матрицы, асимптотически оптимальный алгоритм поиска тупиковых покрытий, метрические свойства множества покрытий, метрические свойства дизъюнктивных нормальных форм.
Поступила в редакцию: 13.07.2010 Исправленный вариант: 18.01.2011
Образец цитирования:
Е. В. Дюкова, Р. М. Сотнезов, “Асимптотические оценки числа решений задачи дуализации и ее обобщений”, Ж. вычисл. матем. и матем. физ., 51:8 (2011), 1531–1540; Comput. Math. Math. Phys., 51:8 (2011), 1431–1440
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf9532 https://www.mathnet.ru/rus/zvmmf/v51/i8/p1531
|
Статистика просмотров: |
Страница аннотации: | 272 | PDF полного текста: | 85 | Список литературы: | 47 | Первая страница: | 8 |
|