RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


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

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

И. П. Чухров


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

DOI: https://doi.org/10.4213/dm1136

Полный текст: PDF файл (749 kB)
Список литературы: PDF файл   HTML файл

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

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

Тип публикации: Статья
УДК: 512.95
Статья поступила: 08.09.2010

Образец цитирования: И. П. Чухров, “О тупиковых комплексах граней в единичном кубе”, Дискрет. матем., 23:1 (2011), 132–158; Discrete Math. Appl., 21:2 (2011), 243–274

Цитирование в формате AMSBIB
\RBibitem{Chu11}
\by И.~П.~Чухров
\paper О тупиковых комплексах граней в~единичном кубе
\jour Дискрет. матем.
\yr 2011
\vol 23
\issue 1
\pages 132--158
\mathnet{http://mi.mathnet.ru/dm1136}
\crossref{https://doi.org/10.4213/dm1136}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2830702}
\elib{http://elibrary.ru/item.asp?id=20730379}
\transl
\jour Discrete Math. Appl.
\yr 2011
\vol 21
\issue 2
\pages 243--274
\crossref{https://doi.org/10.1515/DMA.2011.015}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79959999919}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1136
  • https://doi.org/10.4213/dm1136
  • http://mi.mathnet.ru/rus/dm/v23/i1/p132

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. П. Чухров, “О соотношении тупиковых и минимальных комплексов граней в единичном кубе”, Дискрет. матем., 24:2 (2012), 46–74  mathnet  crossref  mathscinet  elib; I. P. Chukhrov, “On the relation between the irredundant and minimal complexes of faces in the unit cube”, Discrete Math. Appl., 22:3 (2012), 273–306  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:342
    Полный текст:88
    Литература:33
    Первая стр.:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020