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