Статья в сборнике "Математические вопросы кибернетики" №17, Москва, 2008
Авторы:Дюкова Е.В., Инякин А.С.
Об асимптотически оптимальном построении тупиковых покрытий целочисленной матрицы
Аннотация:
В статье построен асимптотически оптимальный алгоритм поиска тупиковых покрытий целочисленной матрицы (алгоритм с полиномиальной задержкой на каждом шаге и с числом шагов почти всегда асимптотически равным числу тупиковых покрытий). Данный алгоритм является модификацией построенного ранее авторами алгоритма (алгоритма ОПТ) поиска неприводимых покрытий булевой матрицы (специального вида тупиковых покрытий булевой матрицы). Приведены экспериментальные оценки статистической эффективности алгоритма ОПТ и ряда других алгоритмов поиска неприводимых покрытий булевой матрицы, в том числе асимптотически оптимальных. Аналогичные результаты получены для задачи построения максимальных конъюнкций двузначной логической функции.
Ключевые слова:
логические процедуры распознавания, сложность перечислительных задач, тупиковое покрытие целочисленной матрицы, неприводимое покрытие булевой матрицы, максимальная конъюнкция, алгоритм с полиномиальной задержкой, преобразование нормальных форм логической функции
