Аннотация:Изучаются вопросы синтеза эффективных в типичном случае алгоритмов для дискретных
перечислительных задач. Рассматривается одна из центральных перечислительных задач –
задача дуализации. Построены новые асимптотически оптимальные алгоритмы дуализации.
Показано, что эти алгоритмы требуют меньших временных затрат по сравнению с ранее
построенными асимптотически оптимальными алгоритмами дуализации, а также другими
известными алгоритмами дуализации, имеющими иные конструктивные особенности.Библ. 20.
Табл. 16.
Ключевые слова: дуализация, булева матрица, асимптотически оптимальный алгоритм, не
приводимое покрытие, перечисление с полиномиальной задержкой.