RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2011, том 23, выпуск 1, страницы 132–158 (Mi dm1136)

Эта публикация цитируется в 2 статьях

О тупиковых комплексах граней в единичном кубе

И. П. Чухров


Аннотация: Изучение свойств тупиковых комплексов граней связано с задачей минимизации булевых функций в классе дизъюнктивных нормальных форм (д.н.ф.). В работах С. В. Яблонского, Ю. И. Журавлева, В. В. Глаголева, Ю. Л. Васильева, А. А. Сапоженко на основе построения и исследования свойств конкретных булевых функций были получены оценки максимальных значений длины и числа тупиковых д.н.ф.
Автором был предложен другой подход, основанный на построении и оценивании мощности множеств тупиковых комплексов граней. В данной статье, с использованием вероятностного подхода, усовершенствованы методы построения и оценивания характеристик тупиковых комплексов граней, что позволило улучшить известные ранее оценки. На основе метода построения тупиковых комплексов граней в поясе единичного куба $B^n$ ширины $k$ получены оценки максимального числа граней и числа тупиковых комплексов для граней размерности $k<(1/4-\varepsilon)n$, где $\varepsilon$ – сколь угодно малая положительная постоянная. За счет оптимального выбора параметров для логарифма числа тупиковых комплексов граней получена нижняя оценка порядка $n2^n$ с константой $1,355\cdot2^{-5}$ при размерности граней $k\approx0,0526n$.
В силу эквивалентности задачи минимизации булевых функций в классе д.н.ф. и задачи построения комплексов граней, покрывающих подмножества вершин единичного куба, полученные результаты справедливы для оценки максимальных значений длины и числа тупиковых д.н.ф.

УДК: 512.95

Статья поступила: 08.09.2010

DOI: 10.4213/dm1136


 Англоязычная версия: Discrete Mathematics and Applications, 2011, 21:2, 243–274

Реферативные базы данных:


© МИАН, 2024