|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Расшифровка монотонных функций с исправлением одной ошибки
С. Н. Селезнева, Ю. Лю МГУ имени М.В. Ломоносова, факультет ВМК
Аннотация:
Задача расшифровки монотонных функций хорошо известна. Из работ В. К. Коробкова и Ж. Анселя следует, что сложность $\varphi_M(n)$ расшифровки монотонных функций алгебры логики равна $C_n^{\lfloor n/2\rfloor} + C_n^{\lfloor n/2\rfloor+1}$ ($\varphi_M(n)$ обозначает наименьшее число вопросов о значении неизвестной монотонной функции на наборе, которое достаточно для восстановления любой монотонной функции $n$ переменных). В работе рассматривается задача расшифровки монотонных функций в случае, когда на вопросы о значении неизвестной монотонной функции на наборе один раз можно получить неверный ответ, но даже при этом ошибочном ответе остается возможность правильно восстановить неизвестную функцию. Показано, что сложность расшифровки монотонных функций алгебры логики при возможном одном неверном ответе такая же, как в случае без неверных ответов.
Ключевые слова:
функция алгебры логики (булева функция), монотонная функция, расшифровка функции, сложность расшифровки, единичный $n$-мерный куб, цепь, разбиение на цепи, цепи Анселя, ошибка, исправление ошибки.
Статья поступила: 22.07.2019 Переработанный вариант поступил: 07.11.2019
Образец цитирования:
С. Н. Селезнева, Ю. Лю, “Расшифровка монотонных функций с исправлением одной ошибки”, Дискрет. матем., 31:4 (2019), 53–69; Discrete Math. Appl., 31:3 (2021), 193–205
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1585https://doi.org/10.4213/dm1585 https://www.mathnet.ru/rus/dm/v31/i4/p53
|
Статистика просмотров: |
Страница аннотации: | 368 | PDF полного текста: | 42 | Список литературы: | 49 | Первая страница: | 20 |
|