Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений

Исследуются вопросы построения эффективных алгоритмов для труднорешаемых дискретных задач. Рассматриваются перечислительные задачи, труднорешаемость которых имеет два аспекта: экспоненциальный рост числа решений при увеличении размера задачи и сложность их нахождения (перечисления). Главной перечислительной задачей считается дуализация монотонной конъюнктивной нормальной формы. Эквивалентной задачей является поиск неприводимых покрытий булевой матрицы. Для задачи поиска неприводимых покрытий булевой матрицы и обобщений этой задачи на случай целочисленной матрицы получены асимптотики типичного числа решений. Эти оценки необходимы, в частности, для обоснования существования асимптотически оптимальных алгоритмов монотонной дуализации и её обобщений.

Ключевые слова

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

Источник финансирования

Работа выполнена при финансовой поддержке РФФИ (код проекта 16-01-00445-а).

Получено

23.01.2019

Дата публикации

23.01.2019

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Дюкова Е. В. , Журавлёв Ю. И. Задача монотонной дуализации и ее обобщения: асимптотические оценки числа решений // Журнал вычислительной математики и математической физики – 2018. – Tом 58. – Номер 12 C. 2153-2168 [Электронный ресурс]. URL: http://ras.jes.su/zvmmf/s004446690003559-5-1 (дата обращения: 05.05.2024). DOI: 10.31857/S004446690003559-5
MLA	Dyukova, E., Zhuravlev, Yu "The problem of monotone dualization and its generalization: asymptotic estimates of the number of solutions." Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58.12 (2018):2153-2168. DOI: 10.31857/S004446690003559-5
APA	Dyukova E., Zhuravlev Y. (2018). The problem of monotone dualization and its generalization: asymptotic estimates of the number of solutions. Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58(12), pp.2153-2168 DOI: 10.31857/S004446690003559-5

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 899

Оценка читателей: голосов 0

1. Дюкова Е.В. О сложности реализации некоторых процедур распознавания // Ж. вычисл. матем. и матем. физ. 1987. Т. 27. № 1. С. 114–127.

2. Дюкова Е.В. Алгоритмы распознавания типа "Кора": сложность реализации и метрические свойства // Распознавание, классификация, прогноз (матем. методы и их применение). М.: Наука, 1989. Вып. 2. С. 99–125.

3. Дюкова Е.В. Асимптотические оценки некоторых характеристик множества представительных наборов и задача об устойчивости // Ж. вычисл. матем. и матем. физ. 1995. Т. 35. No 1. С. 123–134.

4. Дюкова Е.В., Журавлев Ю.И. Дискретный анализ признаковых описаний в задачах распознавания большой размерности // Ж. вычисл. матем. и матем. физ. 2000. Т. 40. №8. С. 1264–1278.

5. Дюкова Е.В. О сложности реализации дискретных (логических) процедур распознавания // Ж. вычисл. матем. и матем. физ. 2004. Т. 44. № 3. С. 551–561.

6. Djukova E.V., Nefedov V.Yu. The Complexity of Transformation of Normal Forms for Characteristic Functions of Classes // Pattern Recognition and Image Analysis, 2009, Vol. 19, No. 3, pp. 435–440.

7. Jonson D.S., Yannakakis M., Papadimitriou C.H. On general all maximal independent sets // Information Processing Letts. 1988. V. 27. P. 119–123.

8. Fredman M.L., Khachiyan L. On the complexity of dualization of monotone disjunctive normal forms // J. Algorithms. 1996. V. 21. P. 618–628.

9. Дюкова Е. В. Об асимптотически оптимальном алгоритме построения тупиковых тестов // ДАН СССР. 1977. Т. 233. № 4. С. 527–530.

10. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания // Пробл. кибернетики. М.: Наука, 1982. Вып. 39. С. 165–199.

11. Дюкова Е.В., Инякин А.С. Асимптотически оптимальное построение тупиковых покрытий целочисленной матрицы // Математические вопросы кибернетики. М.: Наука, 2008. №17. С. 235–246.

12. Дюкова Е.В., Прокофьев П.А. Об асимптотически оптимальном перечислении неприводимых покрытий булевой матрицы // Прикладная дискретная математика, 2014. № 1(23). С. 96–105.

13. Дюкова Е.В., Прокофьев П.А. Об асимптотически оптимальных алгоритмах дуализации // Журнал вычислительной математики и математической физики. 2015. Т. 55, № 5. С. 895–910.

14. Носков В.Н., Слепян В.А. О числе тупиковых тестов для одного класса таблиц // Кибернетика. 1972. № 1. С. 60–65.

15. Андреев А.Е. Об асимптотическом поведении числа тупиковых тестов и длины минимального теста для почти всех таблиц // Пробл. кибернетики. М: Наука, 1984. Вып. 41. С. 117–142.