о нахождении максимума (прогр.)
Oct. 21st, 2008 05:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avva(эта запись будет интересна программистам и математикам)
У Алисы есть число 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).
У Алисы есть число 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).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-10-21 05:02 pm (UTC)no subject
Date: 2008-10-21 07:12 pm (UTC)no subject
Date: 2008-10-21 05:17 pm (UTC)Только вот в этом предложении перепутаны A' и B':
"Теперь Алиса знает, что если она получает кусок A', то это не обычный следующий блок из k бит от Боба, а "сигнальный" блок; и то же самое Боб знает о B'."
no subject
Date: 2008-10-21 05:20 pm (UTC)no subject
Date: 2008-10-21 05:23 pm (UTC)Алиса посылает блок из k бит; если у Боба расхождение с Алисой в этом блоке, он посылает ей обратно под-блок из последних m бит аналогичного блока (m<=k), и Алиса знает, что это корректировка. Если же блок у Боба точно такой же, он становится "посыльным" и посылает в ответ новый блок из k+1 битов своего числа, после чего отвечает уже Алиса. Таким образом, "сигналом" является всего лишь длина блока. А в конце, когда останется хвост меньше последнего k, можно использовать общее знание об n и накинуть один битик для подтверждания последнего куска. Вот и получается, что можно справиться за n+1 битов в случае одинаковых чисел и за n+1+число_различных_битов в случе разных чисел. Где я неправ?
no subject
Date: 2008-10-21 06:46 pm (UTC)Но длина блока - это не часть сигнала (в решениях, описанных мной, о ней договариваются заранее). Откуда Алиса знает, она получила m бит или k+1? For all she knows, она еще сейчас продолжит получать. Временные границы, терминирующие символы - всего этого в протоколе нет. Только биты, и только по ним можно что-то заключать.
no subject
Date: 2008-10-21 06:02 pm (UTC)Следователь и преступник. Следователь задаёт бинарные вопросы. Если претупник всегда отвечает правдиво - то за 100 вопросов всё выяснится.
Теперь известно. что преступник может один раз соврать. Сколько вопросов надо теперь?
no subject
Date: 2008-10-21 06:49 pm (UTC)no subject
Date: 2008-10-21 08:20 pm (UTC)no subject
Date: 2008-10-21 07:20 pm (UTC)no subject
Date: 2008-10-21 07:34 pm (UTC)no subject
Date: 2008-10-21 08:33 pm (UTC)http://en.wikipedia.org/wiki/8/10_encoding
no subject
Date: 2008-10-21 09:08 pm (UTC)no subject
Date: 2008-10-21 09:15 pm (UTC)no subject
Date: 2008-10-21 09:18 pm (UTC)no subject
Date: 2008-10-21 09:24 pm (UTC)Впрочем, тут мы уже слишком далеко от исходной темы удаляемся...
no subject
Date: 2008-10-21 09:01 pm (UTC)Выбирают стартовое значение T = 2^n/2.
На каждом шаге Алиса передает один бит = A < T, Боб передает один бит - B < T.
Если оба бита равны 0, T = T - T/2
Если оба бита равны 1, T = T + T/2
Если биты не равны, то тот, кто передал 1 понимает, что max находится у него (пусть это будет X) и он должен передать это число второму. Второй знает, что число превышает текущее T, следовательно нужно передат
no subject
Date: 2008-10-21 09:09 pm (UTC)no subject
Date: 2008-10-21 09:41 pm (UTC)no subject
Date: 2008-10-21 10:14 pm (UTC)no subject
Date: 2008-10-22 03:47 am (UTC)Потому 2n-1 будет.
no subject
Date: 2008-10-21 10:10 pm (UTC)Начинает Алиса и шлет бит, Боб смотрит на него если он соответствует его биту то Боб шлет свой следующий бит, если Алисин бит меньше то Боб шлет 00 Алиса видит 00 и шлет остаток своего числа. Если Алисин бит больше то Боб шлет остаток своего числа.
no subject
Date: 2008-10-21 10:16 pm (UTC)no subject
Date: 2008-10-21 10:55 pm (UTC)no subject
Date: 2008-10-21 11:03 pm (UTC)no subject
Date: 2008-10-22 03:05 am (UTC)А то, если это мультибайтовые целые применяющиеся для одного и того же назначения, можно с высокой вероятностью сказать, что совпадение в старших разрядах гораздо вероятнее и блоки можно больше слать.
no subject
Date: 2008-10-22 03:14 am (UTC)На практике, конечно, может случиться как вы говорите.