О. Л. КУЗЬМИНА
Научный руководитель – Д. Г. МЕЩАНИНОВ, к. ф.-м. н., доцент
Московский энергетический институт (технический университет)
МИНИМИЗАЦИЯ ПОЛИНОМА ЧАСТИЧНОЙ ФУНКЦИИ НАД КОММУТАТИВНЫМ ПОЛУПРОСТЫМ КОЛЬЦОМ
Рассматривается задача о поиске доопределения частичной функции над коммутативным полупростым кольцом, которое представимо полиномом с наименьшим количеством слагаемых (если такое доопределение существует).
Над коммутативным ассоциативным кольцом с единицей A рассматривается частичная функция n переменных f(x), принимающая значения из этого кольца, с множеством неопределенности X. Предполагая, что f(x) обладает доопределением, которое представимо полиномом, мы хотим найти то доопределение f(x), которому соответствует полином с наименьшим числом слагаемых.
Решение этой задачи представляет интерес для многих прикладных областей, связанных с синтезом логических систем [1].
В данной работе рассматривается случай, когда кольцо A является прямой суммой полей Галуа различной характеристики A1, …, Au, где Ai = GF(qi), qi = piri. Известно, что функция, заданная над таким кольцом, имеет полиномиальное представление тогда и только тогда, когда для нее выполняется условие сохранения сравнений: для всяких x, y ∈ A из условия x ≡ y mod a следует f(x) ≡ f(y) mod a для всех a = q1, …, qu [3].
Требуя, чтобы для нашей частичной функции это условие выполнялось, мы можем существенно уменьшить область ее неопределенности. Декартовой оболочкой множества X ⊂ A = A1 ⊕ … ⊕ Au назовем наименьшее содержащее X подмножество B ⊂ A вида B = B1 ⊕ … ⊕ Bu, где Bi ⊂ Ai.
Теорема: Пусть f(x), сохраняющая сравнения, имеет область неопределенности X. Тогда существует и единственна частичная функция f`(x), совпадающая на множестве Y = A\X с f(x) и сохраняющая сравнения, область определенности которой совпадает с декартовой оболочкой множества Y.
Функция f(x), удовлетворяющая условию сохранения сравнений, представима в виде f(x) = f1(x) ⊕ … ⊕ fu(x), где fi(x): Ain → Ai. Разработан алгоритм, позволяющий для каждой частичной функции fi(x) найти оптимальное доопределение, которому соответствует некоторый полином Pi(x) длины li (для поля из двух элементов этот алгоритм изложен в [2]). Длину l кратчайшего полинома P(x), представляющего f(x), можно оценить следующим образом: max(l1, …, lu) ≤ l ≤ ΣI li.
Квазиоптимальным полиномом назовем P`(x) = P1(x) ⊕ … ⊕ Pu(x). В ряде случаев P`(x) окажется и оптимальным полиномом. Для некоторых практических задач достаточно будет найти приближенное решение, которым и является квазиоптимальный полином.
Для случая, когда интерес представляет точное решение нашей задачи, предложен алгоритм, использующий квазиоптимальный полином в качестве начального шага.
Список литературы
, Торопов реализация частичных булевых функций и систем. М.: 2003. , Мещанинов доопределения булевой функции до кратчайшего полинома // Вестник МЭИ. 2004. Вып. 6. С. 73. Мещанинов условия представимости функций из Pk полиномами по модулю k // Доклады АН СССР. 1988. Том 299 № 1. С. 50.
