|
|
Семинар Добрушинской математической лаборатории ИППИ РАН
4 апреля 2017 г. 16:00, г. Москва, комн. 307 ИППИ РАН (Большой Каретный пер., 19)
|
|
|
|
|
|
Поиск со лжецом или кодирование при наличии бесшумной обратной связи
В. С. Лебедев Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, г. Москва
|
Количество просмотров: |
Эта страница: | 123 |
|
Аннотация:
В классической постановке задача поиска со лжецом может быть сформулирована
следующим образом. Сколько надо задать вопросов с ответами "да-нет", чтобы
найти некоторое загаданное число от 1 до M, если среди ответов может быть
не более t неправильных? При выборе следующего вопроса мы можем использовать
результаты предыдущих. Такую задачу называют задачей Улама и она имеет много
важных приложений. Большую роль в исследовании этой задачи сыграли результаты,
полученные Берлекампом. Доклад будет посвящен обобщению данной задачи на
q-ичный случай. Будет описан простой, но эффективный алгоритм поиска и
предложены некоторые новые идеи по его улучшению.
|
|