Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №8, Москва, 1999
Авторы: Сачков В.Н.
Случайные разбиения множеств
Аннотация:
В первой части данной работы изложена история изучения случайных разбиений множеств, а также описан ряд объектов, которые могут быть представлены в таком виде. Во второй части приводятся полученные автором результаты по противоречивым разбиениям, применяемые к изучению бесповторных конъюнктивных нормальных форм. Рассмотрены разбиения m-множества, имеющие заданное число блоков, общих с фиксированным разбиением, а также случайные разбиения с данным числом блоков. Приведена формула для числа бесповторных конъюнктивных нормальных форм определенного вида, получена асимптотика для числа б.к.н.ф., существенно зависящих от всех переменных. Также автором выведена формула для мощности подкласса булевых функций, для которых соответствующие системы уравнений имеют полиномиальную сложность решения.
Ключевые слова:
случайные разбиения множеств, фиксированное разбиение, противоречивое разбиение, бесповторные конъюнктивные нормальные формы
Язык публикации: русский,  страниц: 22 (с. 33-54)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке: Сведения об авторах:
  • Сачков Владимир Николаевич,  Академия криптографии РФ