АЛГОРИТМ ПОКРЫТИЯ РАЗРЕЖЕННЫХ БУЛЕВЫХ МАТРИЦ

Abstract

Предлагается алгоритм решения задачи о наименьшем покрытии множества, известной в литературе как задача нахождения кратчайшего столбцового покрытия булевой матрицы. Сравнивается эффективность разработанного алгоритма, реализованного в программе Tie, c эффектив­ностью алгоритма программы Espresso и алгоритма GANP. Приводятся результаты экспериментально-статистических испытаний алгоритма на  стандартных примерах серий Benchmark, CLR и Stein, а также на псевдослучайных системах булевых функций.