В.Г. Абрамов, Н.В. Баева, С.Ю. Соловьев

Таблицы точных произведений

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

 

КЛЮЧЕВЫЕ СЛОВА: алгоритм, применимость алгоритма, перебор, сомножители, таблица