Питер Уинклер и корректирующие коды 1899-1925

Сообщение №1930 от - 07 декабря 2001 г. 11:23
Тема: Питер Уинклер и корректирующие коды 1899-1925

Питер Уинклер и корректирующие коды

С №1899 по №1925

04 декабря 2001 г. 11:48:№1899 от zet ,
04 декабря 2001 г. 12:07:№1900 от Михалыч ,
04 декабря 2001 г. 13:02:№1901 от Михалыч ,:
04 декабря 2001 г. 14:56:№1904 от Михалыч ,
04 декабря 2001 г. 15:37:№1905 от Михалыч ,
04 декабря 2001 г. 18:19:№1906 от kalenka ,
05 декабря 2001 г. 14:37:№1912 от Михалыч ,
05 декабря 2001 г. 16:27:№1914 от Volody ,
05 декабря 2001 г. 18:39:№1917 от zet ,
06 декабря 2001 г. 11:22:№1919 от zet ,
06 декабря 2001 г. 13:30:№1922 от Михалыч ,
06 декабря 2001 г. 19:54:№1925 от kalenka ,
------------------------------


Сообщение №1899 от zet , 04 декабря 2001 г. 11:48:
В основном для Михалыча.

Михалыч, если не трудно, есть ли какая ценность в этом сообщении?

Взято сегодня по этой ссылке:
http://www.cnews.ru/topnews/2001/12/03/content3.shtml

"Задача о шляпах": головоломка
Логическая головоломка, представленная впервые в 1998 году в кандидатской диссертации профессора-кибернетика Тодда Эберта (Todd Ebert) из университета штата Калифорния в Ирвине, не перестает будоражить умы математиков и кибернетиков: столь пристальное внимание, в частности, объясняется тем, что в основе решения головоломки лежит идея так называемых корректирующих кодов, или кодов с исправлением ошибок, используемых в ПК и электронике.

Головоломка, привлекшая впоследствии внимание Питера Уинклера (Peter Winkler) из Bell Labs и других ученых американского континента, стала предметом оживленных дискуссий в научных кругах - как среди исследователей из компаний высокотехнологичного сектора, так и на математических и кибернетических отделениях университетов.

Постановка задачи такова: три человека один за другим входят в комнату, и на голову каждому из них надевается красная (К) или синяя (С) шляпа, в зависимости от того, как выпадет монетка - орлом или решкой. Уже находясь в комнате, человек видит цвета шляп двух других играющих, но не цвет собственной шляпы. Игроки не могут никаким образом общаться между собой, однако каждый из них может вслух предположить, какого цвета его шляпа. Если хотя бы один из троих угадает, и никто не выскажет неверное предположение, каждый из игроков получит по $1 млн. Если никто из игроков не угадает цвета своей шляпы, или хотя бы один выскажет неверное предположение, игроки уходят с пустыми руками.
Перед тем, как зайти в комнату, игрокам разрешается выработать совместную стратегию. Они могут договориться, к примеру, о том, что только один определенный игрок попробует угадать цвет своей шляпы, а двое других не будут высказывать предположений. Эта стратегия дает 50-процентный шанс выигрыша. Однако могут ли игроки выработать стратегию, дающую большую вероятность успеха?

Большинство исследователей полагают, что это невозможно, так как цвета шляп не зависят друг от друга, и никто из троих игроков не может сделать никаких выводов относительно цвета собственной шляпы, видя цвета шляп остальных. Любое же предположение с одинаковой вероятностью может оказаться как правильным, так и неверным.

На самом же деле, существует стратегия, дающая игрокам 75-процентный шанс на успех. По ней игрок, видя цвета шляп своих коллег по команде, должен сделать следующие выводы: если цвета шляп у них одинаковы, то цвет его шляпы - другой. Если же шляпы разного цвета, игрок не должен высказывать свое предположение.
Перечислив все возможные комбинации цветов шляп игроков, легче понять смысл стратегии. Для трех человек существует восемь различных сочетаний цветов: ККК, ККС, КСК, СКК, ССК, СКС, КСС и ССС. Первая комбинация означает, что на всех трех игроков надеты красные шляпы, вторая - что на двух надеты красные, а на оставшегося - синяя и т.д.

В шести из восьми возможных сочетаний на двоих из трех игроков надеты шляпы одного цвета, и эти игроки не будут высказывать свое предположение, так как два других по отношению к каждому из них игрока будут иметь шляпы разного цвета, а оставшийся игрок назовет свой цвет шляпы - не такой, как у товарищей по игре. В двух из восьми случаях, у всех троих игроков шляпы одного цвета, и все три выскажут ошибочное предположение. Так что в 6 случаях из 8 игроки получат свои деньги, что составляет 75-процентную вероятность.
При увеличении количества игроков до 7, развитие данной стратегии (по принципу "в большинстве случаев никто не высказывается неверно, в какой-то раз все не правы") позволит выиграть деньги с вероятностью 7/8, с 15 игроками шансы на успех составят 15/16.

Исследователи задались вопросом - могут ли возникать такого рода ситуации в реальной жизни, скажем, на фондовом рынке? Будет ли справедлива вышеизложенная стратегия, когда членам группы доступны лишь не зависящие друг от друга части информации, и каждый из них владеет информацией о других - но не о себе?
Кроме того, идею, лежащую в основе такого рода стратегий, можно выразить в терминах корректирующих кодов, используемых в компакт-дисках, модемах, мобильных телефонах и огромном количестве другой электроники. Сюда относится и контрольная цифра на конце штрих-кода, представляющая сумму всех предыдущих цифр. Области применения корректирующих кодов разнообразны - возможно, именно эта идея приблизит идеальное "цифровое будущее", когда компьютеры и бытовая техника станут удобной повседневностью, а о программных ошибках будут вспоминать как о "темных временах" прогрессивного человечества.

-------------------------------------------------------------------
Re: о селедках
№1900 от Михалыч , 04 декабря 2001 г. 12:07:
В ответ на: Питер Уинклер и корректирующие коды от zet , 04 декабря 2001 г.:

Большое спасибо. Задачи не знал, буду думать.
В качестве моральной компенсации за набор подробного текста предлагаю
ЗАДАЧУ О СЕЛЕДКАХ.
Имеется бочка. В (верхнем) днище четыре ненумерованные дырки по размеру руки в вершинах квадрата.
В бочке напртив дырок висят на крючках селедки. В дырке доступна для ощупывания только одна селедка.
Шаг 1. Клиент (двурукий!) может сунуть руки в дырки и, если хочет, поменять их ориентацию (хвостом или головой вверх).
После чего вынимает руки. Бочка начинает вращаться. Останавливается.
Шаг 2. Аналогично.
и т.д.
Сбоку лампочка. Загорается, если селедки "сонаправлены". Неважно как именно.
Цель игры - зажечь лампочку за минимальное число ходов.
Успехов.
Ваш,
Михалыч

---------------------------------------------------------------------------
Re: Питер Уинклер и Дж.Литтлвуд
№1901 от Михалыч , 04 декабря 2001 г. 13:02:
В ответ на: Питер Уинклер и корректирующие коды от zet , 04 декабря 2001 г.:

Уважаемый zet!
Очень смутные ассоциации...
Не ли у Вас книги Дж.Литтлвуд "Математическая смесь"?
Там рассматривается и обсуждается разница в вероятностной постановке задач
а) некто получил информацию, что у партнера в бридж есть на руках туз и
б) некто получил информацию, что у партнера есть туз пик.
Какова вероятность двух тузов у партнера?
Ответы в случаях а) и б) различные...

Re: часы и шляпы
№1904 от Михалыч , 04 декабря 2001 г. 14:56:
В ответ на: Питер Уинклер и корректирующие коды от zet , 04 декабря 2001 г.:

Уважаемый zet!
Еще вопрос. Игра "с часами" или без? С часами можно договориться о порядке выступлений: никто не видит N-1 одноцветных шляп - пауза. Следующий такт. Кто видит N-2 шляпы? итд.
Но тогда интересная коллизия в случае, когда двое видят на соответствующем шаге одно и то же количество одинаковых шляп. Поднимать руку - готов отвечать?
Но тогда, например, для случая трех игроков с одноцветными шляпами все трое поднимают руки и этот знак приводит к необходимости отказа от согласованной стратегии (вижу две одинаковые - называю другую).
Михалыч

-----------------------------------------------------
Re: Питер Уинклер и СМИ
№1905 от Михалыч , 04 декабря 2001 г. 15:37:

В ответ на: Питер Уинклер и корректирующие коды от zet , 04 декабря 2001 г.:
Уважаемый zet!
Наконец-то внимательно прочел заметку. Бред, конечно, полный.
То есть, типа, как выирать в орлянку? Ставить после трех орлов на решку???
Вот вариант "с часами", вроде бы небредовый, интересный даже. И ситуация вполне "аукционная". И в технических системах можно реализовать систему тактового голосования.
Интересно, а как увязано содержание первоисточника с корректирующими кодами.
И стал ли все-таки Пит PhD?

почему же бред...
№1906 от kalenka , 04 декабря 2001 г. 18:19:
В ответ на: Re: Питер Уинклер и СМИ от Михалыч , 04 декабря 2001 г.:

Для случая трех человек достаточно перебрать все варианты и убедится что так оно и есть. Действительно стратегия с 75% выигрышем, странно что она позиционируется как недавняя находка, по-моему это действительно давно известная вещь (но настаивать не буду) К примеру есть задача взвешивания монет: есть 12 монет - одна из них фальшивая (т.е. легче или тяжелее остальных, но точно не известно тяжелее или легче). Надо за три взвешивания на рычажных весах определить фальшивую (подсказка - не обязательно узнать тяжелее она или нет). На мой взгляд эти две задачи на одну и ту же тему - именно - эффективное извлечение информации.
В случае с колпаками - эффективное оценивание, в случае монет - задача продвигается дальше и доводится до 100% успеха за наименьшее число действий. Если перфразировать задачу с колпаками то можно было бы сформулировать так - за сколько итераций участники узнают цвет своих колпаков. (очевидно что для трех человек за две итерации - если в первой неуспех, то у всех колпаки одинакового цвета и он перед глазами у каждого участника :)))

------------------------------------------------------------
Пожелуй, готов согласиться...
№1912 от Михалыч , 05 декабря 2001 г. 14:37:
В ответ на: почему же бред... от kalenka , 04 декабря 2001 г.:

Уважаемый kalenka!
Похоже, что в целом Вы правы.
Вспоминается задача, описанная у Мостеллера "негласное соглашение".
ЗАДАЧА.
Играют две команды.
1-я из одного человека, вторая из двух.
Игроки второй команды (осведомленные о правилах игры!!!) задумывают (независимо) по натуральному числу.
Если одинаковые, то они выиграли. Нет - значит нет (Выиграла 1-я команда).
ЦЕЛЬ - ВЫИГРАТЬ!!
Вопрос: какова вероятность выигрыша второй команды.
Ответ: зависит от "человеческого фактора" - интеллекта играющих (без учета этого фактора - вероятность нулевая, ессно).
Набросок решения: нужно быть кретином, чтоб рассчитывать на успех, задумывая 12-значное число; "проще надо жить, проще"; если Вася задумал 1, а Петя нет, то последний был неправ.
Основания для формализации; натуральные числа ограничены снизу, но не сверху и т.д...
И при решении предложенной задачи, очевидно, можно "нажиться" только на "человеческом факторе", включив его формализацию в точную постановку задачи.
Но в отличие от задачи Мостеллера, я не очень хорошо представляю эту формализацию. Надо думать.
С уважением, спасибо
vche
ЗЫ. А в задачу Мостеллера я играл со студентами на лекции. Моя ставка - 5 на экзамене. До сих пор не проиграл ни разу.

---------------------------------------------------------
Re: Пожелуй, готов согласиться...
№1914 от Volody , 05 декабря 2001 г. 16:27:
В ответ на: Пожелуй, готов согласиться... от Михалыч , 05 декабря 2001 г.:

> Но в отличие от задачи Мостеллера, я не очень хорошо представляю эту формализацию. Надо думать.
> С уважением, спасибо
> vche
> ЗЫ. А в задачу Мостеллера я играл со студентами на лекции. Моя ставка - 5 на экзамене. До сих пор не проиграл ни разу.

Ну формализация понятна. Студенты должны заранее знать
что им будет предложен такой способ сдачи экзамена:))

-----------------------------------
Re: *Ну это явно недостаточно - лишь стимул*
№1917 от zet , 05 декабря 2001 г. 18:39:
В ответ на: Re: Пожелуй, готов согласиться... от Volody , 05 декабря 2001 г.:

А что касается PhD и связи статьи с исходным текстом, я знаю не больше Вашего.

------------------------------------------------------------------------------------------
Re: часы и шляпы & Литтлвуд
№1919 от zet , 06 декабря 2001 г. 11:22:
В ответ на: Re: часы и шляпы от Михалыч , 04 декабря 2001 г.:

> Игра "с часами" или без? С часами можно договориться о порядке выступлений: никто не видит N-1 одноцветных шляп - пауза. Следующий такт. Кто видит N-2 шляпы? итд.
> Но тогда интересная коллизия в случае, когда двое видят на соответствующем шаге одно и то же количество одинаковых шляп. Поднимать руку - готов отвечать?
> Но тогда, например, для случая трех игроков с одноцветными шляпами все трое поднимают руки и этот знак приводит к необходимости отказа от согласованной стратегии (вижу две одинаковые - называю другую).

По-моему, как в любой программе, внутри красивого цикла существуют досадные IF'ы, так и в согласованную стратегию можно включить соглашение об исключительных ситуациях.
Но это для автоматов.

А для игры с "часами" мне вспоминается другая простейшая постановка:
3-м мудрецам надели шляпы, завязав глаза, затем глаза развязали. Шляп было 4: 3 одного цвета, а 1 другого. Они посмотрели друг на друга, а затем одновременно догадались, какого цвета шляпа на каждом.

Очевидно, что здесь 2-х тактовое решение: "Остальные молчат, т.к. не видят на мне ту, единственную, другого цвета. Но и я ее не вижу."
Я это к тому, что люди могут включать в совместную стратегию и условие постоянного анализа ситуации на достаточность.
Впрочем, случай с мудрецами, как и его обобщения, легко формализуется.

P.S.У кого ж нету Литтлвуда, а текст я сам, конечно, не набивал, скопировал.

--------------------------------------------------------------------------------
Серьезная задача "о фрагментах"
№1922 от Михалыч , 06 декабря 2001 г. 13:30:
В ответ на: почему же бред... от kalenka , 04 декабря 2001 г.:

Уважаемые zet, kalenka, etc!
Ясно, что задача "небернуллиевская". Пространство элементарных событий описывается в терминах "играю (по согласованным правилам)" - "пасую".

Интересно, на чем Пит защитился. Не на этом же... Хотелось бы почитать первоисточник.

Теперь о приложениях к кррректирующим кодам. Пока не очень вижу.
Но есть одна уже почти классическая задача о восстановлении по фрагментам. Серьезная задача. Мно кажется, что она имеет отношение к теме.


ЗАДАЧА.
Есть (неизвестный) n-мерный битовый вектор.
Предъявляются ВСЕ "подвекторы" размерности k (Все "Цэ из n по k штук").
1) при каких k(n) возможно гарантированное (= детерминированное) восстановление неизвестного вектора?
2) при каких k(n) не возможно гарантированное (= детерминированное) восстановление неизвестного вектора?
3) алгоритмы такого восстановления?

ЧТО ИЗВЕСТНО.
1) при k > n/2 вектор восстанавливается
2) при k < log n вектор не восстанавливается
3) простейший алгоритм восстановления в случае 1) - покоординатное голосование
4) слышал, но не видел, о работе с алгоритмом восстановления при k > n/4

НЕФОРМАЛЬНЫЕ КОММЕНТАРИИ
Задачу услышал лет 10 назад от крупнейшего специалиста в алгебраической теории кодирования В.И.Левенштейна на одном из координационных совещаний при представлении им проекта (тогда на совещаниях еще распределялись деньги на науку!)
"Спецприложения" задачи достаточно ясные. В докладе излагалась, естественно, "легальная" версия - какая-то "ботва" про восстановление генетического кода динозавра.
Для одного из моих знакомых задача стала навязчивой идеей. Если в случае 2) он получил неулучшаемые оценки, то для случая 1) имеет, по-моему около 2 десятков доказательств и алгоритмов, базирующихся на существенно различных идеях, которые с неотвратимостью приводят к оценке k > n/2 (!)

ПРОБЛЕМА.
ВНЕ "детерминированных" зон (т.е. от log n до n/2 (или n/4))
задачу никто не исследовал.

Думаю, что выбор (исследование) оптимальной с точки зрения каких-то вероятностных критериев стратегии - задача по духу близкая к "задаче о шляпах"
По крайней мере, публикации на эту тему мне неизвестны.

Есть желающие?
Со своей стороны, в случае получения каких-то нетривиальных результатов о восстановлении вне "детерминированных" зон, обещаю содействие в публикации результатов в (приличном) реферируемом журнале.

---------------------------------------------------------------------------------------------
тема очень интересная
№1925 от kalenka , 06 декабря 2001 г. 19:54:
В ответ на: Серьезная задача "о фрагментах" от Михалыч , 06 декабря 2001 г.:

но дел по горло, да боюсь и погружаться в проблематику придется долго. Я же физик а не математик :))

-------------------------------------------------------------------


Отклики на это сообщение:

Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100