|
Диагностические тесты для дискретных функций, определённых на кольцах
Г. В. Антюфеев МГУ имени М. В. Ломоносова
Аннотация:
В статье изучаются источники неисправностей, связанные с конечными коммутативными кольцами главных идеалов. Таблицы неисправностей таких источников соответствуют таблицам Кэли для умножения в кольцах, элементы которых заменяются значениями двоичной функции от них. Для таких колец естественным образом вводятся понятия диагностического теста и функции Шеннона длины диагностического теста. Показано, что если $A$ — кольцо главных идеалов, имеющее только один простой идеал $p \neq A$, и $p^n = 0$ для некоторого $n \in \mathbb {N}$, то функция Шеннона длины диагностического теста на этом кольце имеет вид $L^{{\rm diagn}}(A,n) = \Theta(n).$ Вводится понятие легкотестируемых функций, т. е. функций, относительно которых длина диагностического теста по порядку роста равна логарифму числа попарно не равных столбцов таблицы неисправностей. Показана связь между легкотестируемостью и отделимостью столбцов таблиц неисправностей для двух конкретных источников неисправностей.
Ключевые слова:
источник неисправностей, сдвиги, тесты, функция Шеннона, кольцо главных идеалов.
Статья поступила: 18.01.2021
Образец цитирования:
Г. В. Антюфеев, “Диагностические тесты для дискретных функций, определённых на кольцах”, Дискрет. матем., 33:1 (2021), 3–11; Discrete Math. Appl., 32:3 (2022), 147–153
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1627https://doi.org/10.4213/dm1627 https://www.mathnet.ru/rus/dm/v33/i1/p3
|
|