journal.isu.ru

Начальная страница

Конечная страница

УДК

Раздел
     

Файл
Скачать Изменить файл

Название RU

Авторы RU

Аннотация RU
<p>В данной работе рассматривается одна новая комбинаторная задача, возникающая в связи с изучением сложности представлений булевых функций полиномиальными нормальными формами. В теории сложности минимальная сложность представления самой сложной функции называется функцией Шеннона. Таким образом, верхняя оценка функции Шеннона гарантирует наличие представления данной сложности для любой булевой функции, что имеет существенное прикладное значение.</p> <p>Обычно для нахождения верхней оценки функции Шеннона используются конструктивные алгоритмы минимизации, работающие на классе всех булевых функций. Ранее автором был разработан алгоритм минимизации полиномиальных нормальных форм булевых функций, основанный на комбинаторной технике, связанной с задачами нахождения покрытий и упаковок на множестве двоичных наборов. Полиномиальная форма для заданной булевой функции строится на основе шаблона, который описывается невырожденной матрицей над полем Z2, где каждая строка и столбец соответствует некоторому двоичному набору. При этом для получения хорошей верхней оценки требуется, чтобы множества наборов в строках и столбцах обладали упаковками с плотностью 1 +<em>o</em>(1).</p> <p>При построении матрицы шаблона естественно воспользоваться линейными кодами, исправляющими одну ошибку, в частности, может быть использован код Хэмминга. Это позволяет использовать понятия теории линейных кодов в формулировках соответствующих комбинаторных задач. Задачу, рассматриваемую в настоящей работе также можно отнести к классу задач на нахождение покрытий и упаковок. При этом на покрытие накладывается ряд дополнительных условий, вытекающих из требований к матрице. В работе приводятся некоторые из возможных покрытий, описанные на языке линейных кодов, исправляющих ошибки.</p>

Ключевые слова RU

Литература RU
1. Кириченко К. Д. Оценки сложности шаблонов минимизации полиномиальных форм булевых функций / К. Д. Кириченко // Изв. Иркут. гос. ун-та. Сер. Математика. – 2009. – Т. 2, № 2. – С. 67–76. 2. Башов М. А. О длине функций k-значной логики в классе полиномиальных нормальных форм по модулю k / М. А. Башов, С. Н. Селезнева // Дискрет. математика. – 2014. – Т. 26, № 3. – C. 3–9. 3. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь. — 1979. — 744 c. 4. Cooper J. N. Asymmetric binary covering codes / J. N. Cooper, R. B. Ellis, A. B. Kahng // Journal of Combinatorial Theory. – 2001. – Vol. 100, N 2. – P. 232–249. 5. Rodl V. On a packing and covering problem / V. Rodl // European Journal of Combinatorics. – 1985. – Vol. 6. – P. 69–78. 6. Turan P. Reseach Problems / P. Turan // Magyar Tud. Acad. Mat. Kutato Int. Kozl. – 1961. – Vol. 6. – P. 417–423.

Название EN

Авторы EN

Аннотация EN
<p>In this paper we introduce a new combinatorial problem for covering binary sets. This problem appears in connection to research of complexity of ESOP. Shannon function is called maximum from complexities of the shortest representation of each Boolean function. Hence the upper bound of the Shannon function guarantees the existence of the representation of any Boolean function with this complexity. It is important for applications.</p> <p>As usual implicit algorithms of minimisation working with any Boolean function are used for defining the upper bound of Shannon function. Previously we have developed the algorithm of minimisation of Boolean functions in ESOPs which uses the combinatorial technique connected with tasks of finding covering and packing of binary sets. ESOP for given Boolean function is built by pattern which is described of non-singular matrix over the field Z2 in that earch row and column matches any binary set. These binary sets should have the packing with density 1 + <em>o</em>(1) for getting the effective upper bound.</p> <p>It is normal to use error-correcting linear codes for building a matrix of pattern. In this case Hamming code may by used. And so it lets use terms of the linear codes theory in definitions of combinatorial problems. In this paper we investigate a problem which belongs to covering and packing design. In doing so requirements to matrix impose several conditions to cover. In this work some of possible covers are introduced which have been described in terms of error-correcting linear codes.</p>

Ключевые слова EN

Литература EN
1. Kirichenko K.D. Bounds of the minimization patterns’ complexity of ESOP (in Russian). IIGU Ser. Matematika, 2009, vol. 2, pp. 67–76. 2. Bashov М.A., Selezneva C.N. On the length of functions of k-valued logics in modulo k ESOP (in Russian). Diskretnaya matematika, 2014, vol. 26, no 3, pp. 3–9. 3. Cooper J.N., Ellis R.B., Kahng A.B. Asymmetric binary covering codes. Journal of Combinatorial Theory, 2001, vol. 100, no 2, pp. 232–249. 4. MacWilliams F.J., Sloane N.J.A. The Theory of Error Correction Codes. North-Holland Publishing Company, 1977. 5. Rodl V. On a packing and covering problem. European Journal of Combinatorics, 1985, vol. 6, pp. 69–78. 6. Turan P. Reseach Problems. Magyar Tud. Acad. Mat. Kutato Int. Kozl, 1961, vol. 6, pp. 417–423.