RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2019, том 31, выпуск 4, страницы 53–69 (Mi dm1585)

Эта публикация цитируется в 1 статье

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

С. Н. Селезнева, Ю. Лю

МГУ имени М.В. Ломоносова, факультет ВМК

Аннотация: Задача расшифровки монотонных функций хорошо известна. Из работ В. К. Коробкова и Ж. Анселя следует, что сложность $\varphi_M(n)$ расшифровки монотонных функций алгебры логики равна $C_n^{\lfloor n/2\rfloor} + C_n^{\lfloor n/2\rfloor+1}$ ($\varphi_M(n)$ обозначает наименьшее число вопросов о значении неизвестной монотонной функции на наборе, которое достаточно для восстановления любой монотонной функции $n$ переменных). В работе рассматривается задача расшифровки монотонных функций в случае, когда на вопросы о значении неизвестной монотонной функции на наборе один раз можно получить неверный ответ, но даже при этом ошибочном ответе остается возможность правильно восстановить неизвестную функцию. Показано, что сложность расшифровки монотонных функций алгебры логики при возможном одном неверном ответе такая же, как в случае без неверных ответов.

Ключевые слова: функция алгебры логики (булева функция), монотонная функция, расшифровка функции, сложность расшифровки, единичный $n$-мерный куб, цепь, разбиение на цепи, цепи Анселя, ошибка, исправление ошибки.

УДК: 519.7

Статья поступила: 22.07.2019
Переработанный вариант поступил: 07.11.2019

DOI: 10.4213/dm1585


 Англоязычная версия: Discrete Mathematics and Applications, 2021, 31:3, 193–205

Реферативные базы данных:


© МИАН, 2024