|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 18 Apr 2002 12:19:54
To : Max Alekseyev
Subject : задача про xor
--------------------------------------------------------------------------------
Wed Apr 17 2002 23:31, Max Alekseyev wrote to Sergey Kabikov:
MA>>> Есть набор чисел S, нужно найти базое число (или просто "базу") и
MA>>> минимальный набор масок M такой, что каждое число из S есть XOR базы
MA>>> и каких-то масок из M? Пример: для чисел 0x61..0x7A (представляющие
MA>>> ASCII коды букв a..z) в качестве базы можно взять 0x60 и положить M
MA>>> = { 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> Если пойти в твоих рассуждениях дальше, то можно утверждать, что
MA> существует минимальный набор, который содержит _все_ однобитовые маски,
MA> получаемые как xor двух элементов из S.
Hе совсем так. Я имел в виду следующее : если произвольно выбрать из S i-тое
число Si и и принять его за базу, а затем обнаружить среди чисел такие Sj и
Sk, что :
Sj = Si XOR 0x01
Sk = Si XOR 0x02
то найдется такое минимальное решение, в котором M0=0x01, M1=0x02.
Доказательство :
1. 0х01 должна быть линейной комбинацией Mi для любого минимального решения,
поскольку 0х01 = Si XOR Si = (B XOR Ma XOR Mb ...) XOR (B XOR Mc XOR Md...).
Легко видеть, что В после раскрытия скобок сокращается.
2. Аналогичные рассуждения можно проделать и для 0х02.
3. Поскольку 0х01 <> 0х02, то и наборы "отображающие" их на множество Mi также
не равны, и в смысле "линейных комбинаций" они ортогональны, т.е. заменив
некое Mp (входящее в комбинацию для 0х01) на 0х01 мы тем не менее остаемся
вправе заменить некое Mq (входящее в комбинацию для 0х02) на 0х02, получая
после этого по-прежнему эквивалентное решение.
Ключевое ограничение здесь - однобитовые маски, которые мы вправе подставлять
в решение, должны быть результатом XOR _одного_и_того_же_ Si с любыми другими
числами из S.
SK>> По поводу вышеприведенного набора (0х61..0х7А) : выделяем "вектор" :
SK>> - "основа" (может быть принята в качестве базы В) - 0х68,
SK>> - отличающиеся от "основы" одним битом - 0х69, 0х6А, 0х6С, 0х60, 0х78,
SK>> - убеждаемся, что данный (минимавльный) вектор покрывает все числа из
SK>> S.
SK>> Таким образом, приведенный (МА) выше вектор М является
SK>> минимальным, точнее, одним из множества эквивалентных минимальных,
MA> Это сразу следует из неравенства |M|>=log(|S|), которое можно усилить до
MA> |M|>=ceil(log(|S|)).
MA> Так как |S|=26, то ceil(log(|S|))=5.
Естественно, четырьмя масками 26 элементов не покроешь 8-)
Hо я-то не о том...
MA>>> Частная проблема: можно ли для S = { 0x61..0x7A, 0x5F } найти базу и
MA>>> набор из 5 масок?!
SK>> Строим тот же вектор, приняв за основу опять-же 0х68.
MA> Почему? Может быть, с другой базой нам повезёт больше?
База точно так же подчиняется "линейному комбинированию". Hетрудно показать,
что если база В порождает минимальное решение из М0..М4, то и база B XOR M0
породит эквивалентное ему решение, и база B XOR M2 XOR M3, и любая другая
комбинация В и Мi-тых тоже. Следовательно, базу можно с равным успехом выбрать
любой из 0х60 ... 0х7F.
SK>> Видим, что
SK>> вектор из пяти масок (обязательных к применению) не покрывает числа
SK>> 0х5F. Следовательно, требуется введение шестой маски, и ответ на
SK>> вопрос - нет.
MA> Я согласен, что ответ "нет", но вот как показать это не перебирая
MA> всевозможные базы?
В данном случае - пожалуйста : база 0х7F, как показано выше - эквивалентная
любой другой базе для любой комбинации масок, являющихся опять же линейными
(строго говоря, еще и линейно независимыми) комбинациями из 0х01..0х10,
отличается от 0х5F на 0х20. А это, очевидно, никак не покрывается набором
указанных масок (и их комбинаций, ессно, тоже).
С уважением
Сергей
...the blood and destruction because of one man... (c) J.C.S.
--- ifmail v.2.15
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
задача про xor 