Задачка на побитные операции

[Евгений Машеров]

MGM в сообщении #1601450 писал(а):

А вот XOR почему-то в Булеву алгебру не включают. Проблемы с дистрибутивностью?

Алгебра Жегалкина.

[MGM]

svv в сообщении #1601458 писал(а):

MGM в сообщении #1601450 писал(а):

А вот XOR почему-то в Булеву алгебру не включают. Проблемы с дистрибутивностью?

Наверное, потому, что там эта операция — производная, выражается через исходные. Это не значит, что она "под запретом", никто не мешает изучать её свойства.

А вот в поле Галуа $\mathbb F_2$ сложение по модулю 2 $\oplus$ играет роль той операции "сложения", которая требуется самим определением поля.
Поле из двух элементов
Ну, а в поле проблем с дистрибутивностью точно нет: $(a\oplus b)\cdot c = (a\cdot c)\oplus (b\cdot c)$.

Да. Прочитал про полиномы Жегалкина. Ничего не понял. Точнее с первого взгляда все понятно, то для чего они нужны?
То есть при n переменных число всех возможных полиномов ${2^{{2^n}}}$. Допустим. Но ответ-то только 0 и единица. Где такие полиномы можно использовать?

[mihaild]

MGM в сообщении #1601505 писал(а):

То есть при n переменных число всех возможных полиномов ${2^{{2^n}}}$. Допустим. Но ответ-то только 0 и единица. Где такие полиномы можно использовать?

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

[MGM]

А вот если ли сверточные графы на основе Булевой алгебры?
Типа такого:
$\begin{array}{l} G = \left\{ {E,V} \right\}\\ {v_{i,j}} \in V,i,j \in \left\{ {0,1,..,\infty } \right\}\\ {e_{i,j,k}} \in \left\{ {{v_{i,j}} \to {v_{i + 1,j + k}}} \right\},k \in {Z_n} \end{array}$
Со сверточной функцией на каждом слое $i$
$f\left( {{v_{i,j}}} \right) = \bigcup\limits_{{e_{l,m,k}} \in {N_e}\left( {{v_{i,j}}} \right)} {{g_k}\left( {{v_{l,m}}} \right)} $

Если есть, то в каких задачах используют?

-- Вт июл 18, 2023 19:46:00 --

mihaild в сообщении #1601507 писал(а):

Вообще, длина записи булевой функции в любом фиксированном конечном базисе растет не медленнее чем двойная экспонента от числа переменных (просто потому что разным функциям соответствует разная запись), что тут удивительного?

Согласен. Кстати, по поводу Алгоритма Форда-Беллмана, на свежей, самой топовой конференции по computer vision, CVPR, Таки меня опередили, и проактически "мой" (а по форме Ф-Б) алгоритм опубликовали, как совершено новый. Не читают в Америке классиков.

[mihaild]

(Оффтоп)

MGM в сообщении #1601513 писал(а):

Кстати, по поводу Алгоритма Форда-Беллмана, на свежей, самой топовой конференции по computer vision, CVPR, Таки меня опередили, и проактически "мой" (а по форме Ф-Б) алгоритм опубликовали, как совершено новый

А на эту статью можно ссылку? В целом такие ситуации конечно случаются, в 1994 году открыли метод трапеций, но это данный случай по описанию выглядит еще более странно.

[MGM]

(Оффтоп)

У этой статьи несколько вариантов, наиболее понятная эта https://arxiv.org/pdf/2210.09461.pdf.
Основное достижение - ускорение ранее разработанного алгоритма.
Хотя теперь понял, что этот алгоритм нечто среднее, между моим другим, и Ф-Б.