Войти / Регистрация
Корзина

  • Ваша корзина пуста
Войти / Регистрация
Корзина

  • Ваша корзина пуста

Статья «Функции без коротких имплицент. Часть II: методы построения, "Дискретная математика"»

Авторы:
  • Ролдугин Павел Владимирович1
  • Тарасов Алексей Вячеславович2
стр. 120-132
Платно
1 Московский государственный университет информационных технологий, радиотехники и электроники, 2 Московский государственный университет информационных технологий, радиотехники и электроники
Ключевые слова:
  • булевы функции
  • имплиценты
  • методы построения функций
  • вес булевой функции
Аннотация:
Статья является продолжением работы Функции без коротких имплицент. Часть I: нижние оценки весов . Во второй части предложены различные методы построения булевых функций от переменных, не имеющих имплицент от переменных. Первый из предложенных методов базируется на градиентном алгоритме, второй и третий методы используют определенное комбинаторное правило построения, четвертый метод основан на случайном выборе элементов носителя функции. В зависимости от значения методы имеют различную эффективность. Выводятся верхние оценки минимального значения весов построенных функций. Вместе с нижними оценками величины из первой части статьи это позволяет получить асимптотически точную оценку вида при .

Архивные статьи (2015 год и ранее) доступны для ознакомления бесплатно, для скачивания их необходимо приобрести. Для просмотра материалов необходимо зарегистрироваться и авторизоваться на сайте.

Чтобы приобрести доступ к материалу для юридического лица, пожалуйста, свяжитесь с администрацией портала с помощью формы обратной связи либо по электронному адресу libnauka@naukaran.com.  

Действия с материалами доступны только авторизованным пользователям.