DOI: 10.17587/prin.8.300-309

УДК: 519.722

Об эквиморфном вычислении действия элемента группы Джевонса над булевыми функциями

А. М. Кукарцев, канд. физ.-мат. наук, ст. преподаватель, e-mail: amkukarcev@yandex.ru, А. А. Кузнецов, д-р физ.-мат. наук, проф., e-mail: kuznetsov@sibsau.ru, Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, г. Красноярск

Рассмотрены алгоритмы вычисления действия множителей канонического представления элемента группы Джевонса над булевыми функциями. Предлагаемые алгоритмы позволяют обрабатывать параллельно массивы значений булевой функции. В результате производительность вычислений повышается в сотни и тысячи раз по отношению к алгоритмам обработки отдельных значений функции. Они сформулированы для абстрактного арифметико-логического устройства, которое соответствует как архитектуре IA-32/IA-64 процессоров ЭВМ, так и другим архитектурам. Для возможности работы с различными разрядностями приведены необходимые рекомендации и расчетные формы для формирования констант под конкретную архитектуру. Также приведены доказательства корректности алгоритмов и оценка их сложности. Они могут быть использованы как для решения уравнений действия группы Джевонса над булевыми функциями, так и для реализации самих таких действий.

Ключевые слова: действие группы на множестве, группа Джевонса, булевы функции, уравнения действия группы на множестве, эквиморфные группы, абстрактные машины

Стр. 300–309

Работа выполнена при поддержке РФФИ и правительства Красноярского края (проект № 17-47-240318).