journal.isu.ru

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

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

УДК

Раздел
     

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

Название RU

Авторы RU

Аннотация RU
<p>В статье рассматривается сложность полиномиальных представлений булевых функций. Предложены условия, которым должна удовлетворять функция, имеющая сложность больше заданной. С помощью генетического алгоритма минимизации получены верхние оценки сложности таких булевых функций, и как следствие получена новая верхняя оценка сложности для всех булевых функций.</p>

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

Литература RU
1. Винокуров С. Ф. Верхняя оценка сложности булевых функций в классе ПНФ / С. Ф. Винокуров, А. С. Казимиров // Algebra andModel Theory 4. – Novosibirsk: Novosibirsk State Tech. University, 2003. – P. 160–165. 2. Казимиров А. С. Оценка числа классов LP-эквивалентности булевых функций / А. С. Казимиров // Вестн. Бурят. ун-та. Сер. 13, Математика и информатика. – 2005. – Вып. 2. – С. 17–22. 3. Казимиров А. С. Параллельные генетические алгоритмы в задачах минимизации булевых функций / А. С. Казимиров // Вестн. ТГУ. Приложение. – 2006. – № 17. – С. 226–230. 4. Кириченко К. Д. Верхняя оценка сложности полиномиальных нормальных форм булевых функций / К. Д. Кириченко // Дискретная математика. – 2005. – Т. 17, № 3. – С. 80–88. 5. Реймеров С. Ю. О сложности полиномиальных представлений булевых функций 7 переменных / С. Ю. Реймеров // Студент и научно-технический прогресс: Математика : материалы XLVIII междунар. науч. студ. конф. – Новосибирск : Новосиб. гос. ун-т, 2010. – С. 177. 6. Рябец Л. В. Нахождение минимальных полиномов булевых функций с использованием специальной операторной формы / Л. В. Рябец // Технологии Microsoft в теории и практике программирования : тез. докл. – Новосибирск, 2006. – С. 215–217. 7. Even S. On minimal modulo 2 sums of products for switching functions / Even S // IEEE Trans. Electron. Comput. – 1967. – Vol. EC-16, N 10. – P. 671–674. 8. Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002. Freiberg, Germany, Sept. 19-20. – 2002. – P. 141–148.

Название EN

Авторы EN

Аннотация EN
<p>This paper concerns complexity of exclusive-or-sum-of-products expressions representing Boolean functions. Conditions for functions having complexity over a given number are introduced. Genetic minimization algorithm gave obtained upper bounds on complexity of such functions. As a result a new upper bound on complexity for all Boolean functions is obtained.</p>

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

Литература EN