Александр Витвицкий

Реализация булевых функций на непересекающихся множествах переменных

В примитивном жадном алгоритме для нахождения минимальной супестроки, выбираются две строки с максимальным перекрытием. В статье предлагается понятие оптимального множества и обобщается примитивный жадный алгоритм. Обобщенный жадный алгоритм может быть сведен к примитивному если относительное оптимальное множество пусто. Следовательно новый алгоритм достигает лучшей границы ценой времени выполнения. Но эта цена приемлема на практике.