Other Meetings

Семинар Добрушинской математической лаборатории ИППИ РАН: Поиск со лжецом или кодирование при наличии бесшумной обратной связи

Tuesday, 04 April 2017
16:00
307 Institute for Information Transmission Problems

В классической постановке задача поиска со лжецом может быть сформулирована следующим образом. Сколько надо задать вопросов с ответами "да-нет", чтобы найти некоторое загаданное число от 1 до M, если среди ответов может быть не более t неправильных? При выборе ледующего вопроса мы можем использовать результаты предыдущих. Такую задачу называют задачей Улама и она имеет много важных приложений. Большую роль в исследовании этой задачи сыграли результаты, полученные Берлекампом. Доклад будет посвящен обобщению данной задачи на q-ичный случай. Будет описан простой, но эффективный алгоритм поиска и предложены некоторые новые идеи по его улучшению.