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

ПДМ, 2018, номер 39, страницы 107–115 (Mi pdm608)

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

Вычислительные методы в дискретной математике

О сходимости нового алгоритма характеризации $k$-значных пороговых функций

А. В. Бурделев

Белорусский государственный университет, г. Минск, Беларусь

Аннотация: Функция $k$-значной логики $f(x_1,\dots,x_n)$, для которой существует линейная форма $L(x_1,\dots,x_n)=a_1x_1+a_2x_2+\dots+a_nx_n$, $x_i\in\mathbb Z_k$, с вещественными коэффициентами и набор вещественных порогов $b_0<b_1<\dots<b_k$, такие, что для всех $i\in\{0,\dots,k-1\}$ выполняется условие $f(x_1,\dots,x_n)=i\Leftrightarrow b_i\le L(x_1,\dots,x_n)<b_{i+1}$, называется пороговой $k$-значной функцией. Под алгоритмом характеризации пороговой $k$-значной функции понимается процедура нахождения коэффициентов $a_1,a_2,\dots,a_n$ линейной формы $L(x_1,\dots,x_n)$ и множества порогов $b_0,b_1,\dots,b_{k-1}$. В работе доказывается сходимость алгоритма нахождения коэффициентов линейной формы и порогов (характеризации) $k$-значных пороговых функций по столбцу значений. Основная идея алгоритма заключается в раздельном последовательном вычислении коэффициентов линейной формы и порогов. В качестве первичной аппроксимации линейной формы используются коэффициенты роста либо коэффициенты возрастания и итеративно осуществляется корректировка линейной формы. После нахождения коэффициентов линейной формы вычисляются разделяющие пороги.

Ключевые слова: алгоритм характеризации, доказательство сходимости, пороговая функция.

УДК: 512.55

DOI: 10.17223/20710410/39/10



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


© МИАН, 2024