|
Большие системы
Геометрия сдвигов в булевом кубе
М. Н. Вялыйabc, В. К. Леонтьевb a Московский физико-технический институт (государственный университет)
b Вычислительный центр им. А.А. Дородницына РАН
c Национальный исследовательский университет "Высшая школа экономики"
Аннотация:
У операции сложения Минковского геометрических фигур есть дискретный аналог — сложение подмножеств булева куба как векторного пространства над полем из двух элементов. Относительно такой операции подмножества булева куба (или булевы функции от нескольких переменных) образуют моноид. Этот моноид представляет интерес как в классическом дискретном анализе, так и в ряде задач, связанных с теорией информации. Рассматриваются различные аспекты сложности этого моноида: структурный, алгоритмический, алгебраический.
Ключевые слова:
сложение Минковского, булев куб, моноид, порождающие элементы, примитивные элементы, последовательности кратных.
Поступила в редакцию: 24.02.2019 После переработки: 26.04.2019 Принята к печати: 21.05.2019
Образец цитирования:
М. Н. Вялый, В. К. Леонтьев, “Геометрия сдвигов в булевом кубе”, Пробл. передачи информ., 55:2 (2019), 58–81; Problems Inform. Transmission, 55:2 (2019), 152–173
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ppi2290 https://www.mathnet.ru/rus/ppi/v55/i2/p58
|
Статистика просмотров: |
Страница аннотации: | 274 | PDF полного текста: | 113 | Список литературы: | 30 | Первая страница: | 14 |
|