|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Kruglov 2:5015/70.5 19 Apr 2002 20:05:32
To : Max Alekseyev
Subject : задача про xor
--------------------------------------------------------------------------------
Среда 17 Апреля 2002 17:53, Max Alekseyev wrote to All:
MA> Есть набор чисел S, нужно найти базое число (или просто "базу") и
MA> минимальный набор масок M такой, что каждое число из S есть XOR базы и
MA> каких-то масок из M?
Т.е. надо провести через S данных точек в Z_2^n (n -- max кол-во бит в числе,
Z_2=GF(2)) (гипер)плоскость минимальной размерности. Очевидно, она существует
=> она проходит через все данные точки => в качестве базы можно выбрать
любую данную точку. Вычтем выбранную базу из данных точек (обозначим то, что
получится x_1, ... ,x_s), теперь через них надо провести подпространство min
размерности. Эта размерность = рангу матрицы из векторов x_1, ... x_s (над
GF(2)), маски -- строки из нее, через которые проходит ее базисный минор. Это
все можно сделать, но проще маску (=базис в линейной оболочке {x_1, ... ,x_s})
искать жадным алгоритмом, т.к. линейно независимые подмножества в ^^^^^^^^^^
образуют матроид.
MA> Частная проблема: можно ли для S = { 0x61..0x7A, 0x5F } найти базу и
MA> набор из 5 масок?!
Возьмем B=$70 => {x_i|i\in Z}={0..$0A, $11..$1F, $2F}. e_1=1; e_2=2; e_3=4;
Возьмем B=$70 => e_4=8; e_5=$11; e_6=$2F. (Каждое следующее берем лин.нез. с
Возьмем B=$70 => предыдущими; если бы был меньший базис, этот бы был лин.зав.)
Hадеюсь не ошибся :)
nOkA. Alexey.
--- GoldED+/386 1.1.4.7
* Origin: 6DFA 1186 7576 DE60 6CCB EB39 AD81 1733 EEBB 970A (2:5015/70.5)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
