Расшифровка монотонных функций с исправлением одной ошибкистатья

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 4 мая 2020 г.

Работа с статьей


[1] Селезнева С. Н., Лю Ю. Расшифровка монотонных функций с исправлением одной ошибки // Дискретная математика. — 2019. — Т. 31, № 4. — С. 53–69. Задача расшифровки монотонных функций хорошо известна. Из работ В.К. Коробкова и Ж. Анселя следует, что сложность расшифровки монотонных функций алгебры логики n переменных равна сумме биномиальных коэффициентов из n по [n/2] и по [n/2]+1. В работе рассматривается задача расшифровки монотонных функций в случае, когда на вопросы о значении неизвестной монотонной функции на наборе один раз можно получить неверный ответ, но даже при этом ошибочном ответе остается возможность правильно восстановить неизвестную функцию. Показано, что сложность расшифровки монотонных функций алгебры логики при возможном одном неверном ответе такая же, как в случае без неверных ответов. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть