Поиск со лжецом или кодирование при наличии бесшумной обратной связи

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