?

Log in

о нахождении максимума (прогр.) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о нахождении максимума (прогр.) [окт. 21, 2008|05:02 pm]
Anatoly Vorobey
(эта запись будет интересна программистам и математикам)

У Алисы есть число A, у Боба есть число B, оба числа n-битные. Алиса и Боб хотят сделать так, чтобы они оба знали max(A, B). Сколько бит им необходимо затратить, передавая информацию друг другу при помощи детерминистского протокола, чтобы это обеспечить?

Внимание: сообщить max(A,B) обоим участникам - это не то же самое, что сообщить, у кого из них большее число. Сделать, чтобы оба знали, у кого большее число, легко за n+1 бит: один посылает свое число другому, а тот отвечает, больше оно его собственного или меньше. Но после этого информация о max(A,B) есть только у одного из участников.

Внимание: при помощи детерминистского протокола включает в себя, что направление каждого следующего бита - от кого к кому - строго определено содержимым канала до сих пор. Например, можно как бы решить задачу за n+1 бит следующим образом: Алиса посылает свое число бит за битом, начиная с верхнего; как только Боб видит расхождение со своим числом, он тут же отвечает "1" или "0" в зависимости от того, бит Алисы больше бита Боба или меньше, и после этого соответственно либо Алиса, либо Боб посылают в обратную сторону остаток своего числа. Но это недетерминистский алгоритм, потому что после каждого бита Алисы мы не знаем, кто посылает следующим: Алиса свой очередной бит, или Боб свой ответ: они соревнуются друг с другом за один и тот же канал. Условие задачи этого не позволяет.

Учитывая эти ограничения, сколько бит должны потратить Алиса и Боб? Например, тривиально это сделать за 2n бит: Алиса посылает свое число Бобу, Боб отвечает своим числом, и оба знают ответ. Но можно ли затратить меньше? Известны нижние и верхние пределы.

Нижний предел. Легко доказать, что за меньше чем n бит не справиться (оставляю это в качестве упражнения для читателя).

Верхний предел, лучший из известных, равен n+O(log(n)) бит (на самом деле чуть меньше). Я сначала объясню, как решить задачу за n+O(sqrt(n)) - это довольно просто - а потом объясню красивый трюк, который позволяет добиться n+O(log(n)).

Может, вы можете сблизить пределы - либо поднять нижний, либо найти еще более хитрый алгоритм и опустить верхний? Если вам это удастся, то сообщите Биллу Гасарчу (ну и мне тоже интересно, конечно).

Итак, алгоритм. Пусть Алиса посылает раз за разом блок из k бит своего числа (начиная с верхних), а Боб отвечает ей так: либо 0 - "у меня пока так же", либо 1 "на этих k битах расхождение", и тогда сразу еще один бит: либо 0 - "у меня больше", либо 1 - "у меня меньше". Если Боб отвечает 10 ("расхождение + у меня больше"), то сразу после этого он также посылает весь остаток своего числа начиная с этого блока и до конца; если отвечает 11, то Алиса после получения посылает весь остаток своего числа, уже не ожидая никаких подтверждений.
Сколько бит мы всего затрачиваем поверх n бит самого числа? Если A и B одинаковые, то дополнительные биты - только ответы B на каждый блок, так что всего затрачено n+n/k бит (n/k - количество блоков); если разные, и расхождение нашлось на m-ном блоке, то всего бит затрачено то ли n+m+1, то ли n+m+1+k (m+1 - биты ответов Боба; k затрачено, если Боб отвечает 10 и должен заново передать m-ный блок). Значит, если выбрать размер блока k=sqrt(n), так что n/k = sqrt(n), и m <= sqrt(n), то всего количество бит будет точно не больше n+2sqrt(n) + O(1). В худшем случае мы потеряем sqrt(n) бит на подтверждения одинаковых блоков почти до самого конца числа, и еще sqrt(n) бит на то, что Боб передаст последний блок Алисе, после того, как она ему уже послала свой последний блок.

Этот результат можно улучшить до n+sqrt(2n)+O(1) (главная разница во втором члене: sqrt(2n) по сравнению с 2sqrt(n)). Будем каждый раз уменьшать размер блока на один бит: k, k-1, k-2... Тогда в случае расхождения Бобу надо передать заново всего k-i бит, а не k, и это хорошо суммируется с i бит-подтверждений, которые он передавал до того. Зато количество блоков растет. Если выбрать начальный размер блока k = sqrt(2n), то после sqrt(2n) блоков, несмотря на постепенное уменьшение размера блока, мы передадим все число (оставляю точный подсчет заинтересованному читателю); а если в какой-то момент будет расхождение, то i подтверждений до него и k-i бит на передачу заново этого блока после вместе тоже дают sqrt(2n). Так что общее количество затраченных бит равно n+sqrt(2n)+O(1).

Как добиться еще лучшего результата? Основная проблема, "съедающая" биты - необходимость отвечать на каждый блок. Даже если мы тратим (обычно) один бит ответа на блок, то получается tradeoff между количеством блоков (по биту на каждый) и размером блока (один блок, возможно, надо заново передать). Как избавиться от этого? Один красивый прием достигает лучшего результата, маскируя подтверждающие биты под обычные биты числа. Вот как это делается.

Будем опять считать, что мы передаем блок из k бит за раз, где k постоянно; но теперь Алиса и Боб посылают попеременно: сначала Алиса первые k бит, потом Боб вторые k бит, и так далее. Но нам все равно нужно как-то обозначить расхождение, потому что после расхождения необходимо, чтобы только один из участников передавал все остальные биты - иначе слишком дорого выходит.

Предположим, что Алиса и Боб могут заранее найти такие куски из k бит, которые не встречаются в качестве "обычных" блоков в их числах. Алиса находит такой кусок A', и посылает его Бобу; Боб находит такой кусок B', и посылает его Алисе. Теперь Алиса знает, что если она получает кусок B', то это не обычный следующий блок из k бит от Боба, а "сигнальный" блок; и то же самое Боб знает о A'. Теперь они начинают обмениваться обычными блоками, пока один из них не видит расхождение между тем, что получил, и своим числом; тогда этот участник посылает свой "сигнальный" блок, а после него 1 или 0 в зависимости от того, расхождение в его пользу или нет. Затем либо он, либо другой участник посылают остаток числа (текущий блок из k бит, возможно, надо переслать заново). Сколько всего затрачено дополнительных бит? 2k на начальный обмен A'/B', еще k на сигнальный блок, и еще k на передачу заново (возможно) текущего блока; всего n+4k+O(1). Но мы не можем выбрать k очень малым: что если k так мало, что в исходном числе A есть все возможные комбинации из k бит в виде обычных блоков? - тогда мы не сможем подобрать A' и алгоритм не сработает. Возможных комбинаций есть 2^k, а число блоков равно n/k. Значит, условие на k выглядит так: 2^k > n/k. Если подставить k = log(n), то это условие выполняется; значит, этот алгоритм дает нам n+O(log(n))+O(1) бит. Можно даже взять k чуть меньше, чем log(n) и все еще соблюсти условие: например, k = log(n)-log(log(n)-log(log(n))) выполняет нужное условие.

Есть другое решение за n+O(log(n))+O(1) бит, которое использует другой трюк, и в итоге требует лишь 2*log(n) дополнительных бит, не считая O(1) (решение выше требует 4*log(n)). Это решение основано на том, что исходное число из алфавита {0,1} перекодируется в другой алфавит таким образом, чтобы внутри каждого блока оставалось место для подтверждающих битов. Оно описано в этой недавней статье (appendix B, Lemma 1).
СсылкаОтветить

Comments:
[User Picture]From: mad_ghost
2008-10-21 05:02 pm
скорее это интересно математикам, программерам проще переслать два числа туда обратно, и оба будут знать чье максимум чье минимум. Дальше, пересылать в масштабах чего? сети? бессмысленно, все равно данные будут не меньше допустим тех же 1500байт TCP пакета. А на вычисления уйдет гораздо больше времени чем если зделать более проще ;)
(Ответить) (Thread)
[User Picture]From: akho
2008-10-21 07:12 pm
У mad_ghost маленькие данные.
(Ответить) (Parent) (Thread)
[User Picture]From: spartach
2008-10-21 05:17 pm
Интересный вопрос.

Только вот в этом предложении перепутаны A' и B':

"Теперь Алиса знает, что если она получает кусок A', то это не обычный следующий блок из k бит от Боба, а "сигнальный" блок; и то же самое Боб знает о B'."
(Ответить) (Thread)
[User Picture]From: avva
2008-10-21 05:20 pm
Да, спасибо, сейчас исправлю.
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2008-10-21 05:23 pm
А если так:
Алиса посылает блок из k бит; если у Боба расхождение с Алисой в этом блоке, он посылает ей обратно под-блок из последних m бит аналогичного блока (m<=k), и Алиса знает, что это корректировка. Если же блок у Боба точно такой же, он становится "посыльным" и посылает в ответ новый блок из k+1 битов своего числа, после чего отвечает уже Алиса. Таким образом, "сигналом" является всего лишь длина блока. А в конце, когда останется хвост меньше последнего k, можно использовать общее знание об n и накинуть один битик для подтверждания последнего куска. Вот и получается, что можно справиться за n+1 битов в случае одинаковых чисел и за n+1+число_различных_битов в случе разных чисел. Где я неправ?
(Ответить) (Thread)
[User Picture]From: avva
2008-10-21 06:46 pm
Таким образом, "сигналом" является всего лишь длина блока.

Но длина блока - это не часть сигнала (в решениях, описанных мной, о ней договариваются заранее). Откуда Алиса знает, она получила m бит или k+1? For all she knows, она еще сейчас продолжит получать. Временные границы, терминирующие символы - всего этого в протоколе нет. Только биты, и только по ним можно что-то заключать.
(Ответить) (Parent) (Thread)
[User Picture]From: nikaan
2008-10-21 06:02 pm
Есть похожая задача.
Следователь и преступник. Следователь задаёт бинарные вопросы. Если претупник всегда отвечает правдиво - то за 100 вопросов всё выяснится.
Теперь известно. что преступник может один раз соврать. Сколько вопросов надо теперь?
(Ответить) (Thread)
[User Picture]From: jerom
2008-10-21 06:49 pm
За 107 точно справимся.
(Ответить) (Parent) (Thread)
[User Picture]From: nikaan
2008-10-21 08:20 pm
да ну? Стоит, наверное, упомянуть, что следующие вопросы могут зависеть от ответов на предыдущие. О том, что вопросы независимы, в условии не написано.
(Ответить) (Parent) (Thread)
[User Picture]From: amarao_san
2008-10-21 07:20 pm
перекодируется в другой алфавит таким образом, чтобы внутри каждого блока оставалось место для подтверждающих битов - это обычное 8/10 кодирование, что ли?
(Ответить) (Thread)
[User Picture]From: avva
2008-10-21 07:34 pm
Я не знаю, что такое обычное 8/10 кодирование, но по-моему нет.

(Ответить) (Parent) (Thread)
[User Picture]From: amarao_san
2008-10-21 08:33 pm
Кодирование 8 битов информации 10 битами сигнала. Позволяет гарантировать должную степень скважности (или чего там гигабитному эзернету надо) и возможность засунуть массу служебных кодов в один поток с данными.

http://en.wikipedia.org/wiki/8/10_encoding
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-10-21 09:08 pm
Ясно. Нет, там совсем другое.
(Ответить) (Parent) (Thread)
[User Picture]From: dmarck
2008-10-21 09:15 pm
NRZ/NRZI? Оно обычно всё-таки для другого: чтобы регулярные помехи сигнал не размывали...
(Ответить) (Parent) (Thread)
[User Picture]From: amarao_san
2008-10-21 09:18 pm
Я, конечно, не инженер, но из той литературы, что я читал, следует, что у 8/10 двойное назначение: во-первых держать правильный скрэмблинг, во-вторых, сколько-то из свободных 700+ комбинаций (2^10-2^8) используются для LLC (link control) - служебных команд согласнования кто мастер, кто слейв, переконнектов и т.д.
(Ответить) (Parent) (Thread)
[User Picture]From: dmarck
2008-10-21 09:24 pm
8-10 в чистом виде всё-таки слишком дорог, и при наличии хоть сколь-нибудь внятной синхронизации не применяется вовсе (вспомним модемные протоколы: V42 уже синхронен, и асинхронные пары префикс-постфикс применяет уже не к байтам, а к блокам длиной до 64 байт).

Впрочем, тут мы уже слишком далеко от исходной темы удаляемся...
(Ответить) (Parent) (Thread)
From: sply
2008-10-21 09:01 pm
за от 2*log2(n) до n+2 бит - бинарным поиском.

Выбирают стартовое значение T = 2^n/2.
На каждом шаге Алиса передает один бит = A < T, Боб передает один бит - B < T.
Если оба бита равны 0, T = T - T/2
Если оба бита равны 1, T = T + T/2
Если биты не равны, то тот, кто передал 1 понимает, что max находится у него (пусть это будет X) и он должен передать это число второму. Второй знает, что число превышает текущее T, следовательно нужно передат
(Ответить) (Thread)
From: sply
2008-10-21 09:09 pm
передать разницу. Если Т все время росло, то оба понимают, что разрядность разницы D = X - T составляет log2(2^n - T) и передается этим числом бит. Если Т все время опускалось, то разница D = 0 + X, ее размер log2(T). В остальных случаях для текущего T ищется ближайшее предыдущее значение T вверх от текущего и разница D = X - T, а разрядность этой разницы составит log2(Tpre - T)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-10-21 09:41 pm
Бинарный поиск в пространстве 2^n завершится за n шагов, т.е. вы описали немного усложненный вариант алгоритма за 2n бит.
(Ответить) (Parent) (Thread)
From: sply
2008-10-21 10:14 pm
да, с этим я ошибся. хотя результат чаще будет ближе к n, чем к 2n
(Ответить) (Parent) (Thread)
[User Picture]From: pigmeich
2008-10-22 03:47 am
Средний модуль разницы двух чисел из пространства (1, 2^n) равен (2^n/3).

Потому 2n-1 будет.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: avva
2008-10-21 10:16 pm
Нет, так нельзя. Например, увидев 0 от Боба, Алиса не знает, это его бит или часть его ответа 00, и соответственно не знает, кто следующий бит шлет - Боб или она.

(Ответить) (Parent) (Thread)
From: sply
2008-10-21 10:55 pm
Если не трудно, добавьте прямой линк на статью с решением с алфавитом - http://research.microsoft.com/users/liadbl/papers/overhead.pdf , Appendix B
(Ответить) (Thread)
[User Picture]From: avva
2008-10-21 11:03 pm
Ага, спасибо за ссылку, сейчас.
(Ответить) (Parent) (Thread)
[User Picture]From: pigmeich
2008-10-22 03:05 am
А число совсем фонарное?

А то, если это мультибайтовые целые применяющиеся для одного и того же назначения, можно с высокой вероятностью сказать, что совпадение в старших разрядах гораздо вероятнее и блоки можно больше слать.
(Ответить) (Thread)
[User Picture]From: avva
2008-10-22 03:14 am
Да, совсем.

На практике, конечно, может случиться как вы говорите.
(Ответить) (Parent) (Thread)