|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 18 Apr 2002 03:33:30
To : Sergey Kabikov
Subject : задача про xor
--------------------------------------------------------------------------------
Replying to a message of Sergey Kabikov to Max Alekseyev:
MA>>>> Есть набор чисел S, нужно найти базое число (или просто "базу") и
MA>>>> минимальный набор масок M такой, что каждое число из S есть XOR
MA>>>> базы и каких-то масок из M? Пример: для чисел 0x61..0x7A
MA>>>> (представляющие ASCII коды букв a..z) в качестве базы можно взять
MA>>>> 0x60 и положить M = { 0x01, 0x02, 0x04, 0x08, 0x10 }.
SK>>> Легко заметить, что существует множество эквивалентных решений,
SK>>> относительно которых задачу можно считать в некотором смфсле
SK>>> линейной. Так, если существует решение B,M0,M1..Mn, то и B,M1..Mn,K
SK>>> тоже будет решением тогда и только тогда, когда К является линейной
SK>>> (в смысле XOR) комбинацией из M0 и любого количества Mi, например K
SK>>> = M0 XOR M2 XOR M5. Следовательно, если в наборе S присутствуют два
SK>>> числа, отличающиеся только одним битом, обязательно найдется
SK>>> решение, в котором одно из M равно тому самому биту.
MA>> Согласен.
SK>>> Hапример, если в S имеются числа 0х68 и 0х69, хотя бы одно из
SK>>> эквивалентных (и минимальных !) решений содержит M0=0х01. Более
SK>>> того, если в том же S присуствует число 0х6А (или 0х6В), то можно
SK>>> утверждать, что М1=0х02.
MA>> Если пойти в твоих рассуждениях дальше, то можно утверждать, что
Утверждение 1.
MA>> существует минимальный набор, который содержит _все_ однобитовые
MA>> маски, получаемые как xor двух элементов из S.
Доказывается оно в точности следуя твоим рассуждениям выше и используя факт
линейной независимости однобитовых масок (каждая маска - это двоичный вектор,
xor - это сложение по модулю 2).
SK> Hе совсем так. Я имел в виду следующее :
Утверждение 2.
SK> если произвольно выбрать из S
SK> i-тое число Si и и принять его за базу, а затем обнаружить среди
SK> чисел такие Sj и Sk, что :
SK> Sj = Si XOR 0x01
SK> Sk = Si XOR 0x02 то
SK> найдется такое минимальное решение, в котором M0=0x01, M1=0x02.
Утверждение (1) более сильное. Во-первых, оно справедливо для любой базы, для
которой минимальное решение существует; во-вторых, утверждение 2 из него
моментально следует.
Очевидно, утверждение 1 можно усилить до
Утверждение 3. Рассмотрим множество 2S = S xor S = { u xor v : u, v из S }.
Для любого линейно-независимого подмножества 2S существует минимальный набор
масок, содержащий это подмножество.
[...]
MA>>>> Частная проблема: можно ли для S = { 0x61..0x7A, 0x5F } найти базу
MA>>>> и набор из 5 масок?!
SK>>> Строим тот же вектор, приняв за основу опять-же 0х68.
MA>> Почему? Может быть, с другой базой нам повезёт больше?
SK> База точно так же подчиняется "линейному комбинированию". Hетрудно
SK> показать, что если база В порождает минимальное решение из М0..М4, то
SK> и база B XOR M0 породит эквивалентное ему решение, и база B XOR M2
SK> XOR M3, и любая другая комбинация В и Мi-тых тоже.
Это так, но от какой-то базы ты должен отталкиваться! Про ее выбор и идёт речь.
SK> Следовательно,
SK> базу можно с равным успехом выбрать любой из 0х60 ... 0х7F.
Согласен, что базы 0x60 ... 0х7F все эквивалентны между собой. Hо есть же
другие...
SK>>> Видим, что
SK>>> вектор из пяти масок (обязательных к применению) не покрывает числа
SK>>> 0х5F. Следовательно, требуется введение шестой маски, и ответ на
SK>>> вопрос - нет.
MA>> Я согласен, что ответ "нет", но вот как показать это не перебирая
MA>> всевозможные базы?
SK> В данном случае - пожалуйста : база 0х7F, как показано выше -
SK> эквивалентная любой другой базе для любой комбинации масок,
SK> являющихся опять же линейными (строго говоря, еще и линейно
SK> независимыми) комбинациями из 0х01..0х10, отличается от 0х5F на 0х20.
SK> А это, очевидно, никак не покрывается набором указанных масок (и их
SK> комбинаций, ессно, тоже).
Ты доказал, что для любой базы из набора 0x60 ... 0х7F не существует набора из
пяти масок, покрывающего данное S.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
