|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О наибольшей длине тупиковой дизъюнктивной нормальной формы у почти всех булевых функций
А. А. Сапоженко
Институт математики Сибирского отделения АН СССР
Аннотация:
Максимальное число $l(f)$ конъюнкций в тупиковой дизъюнктивной нормальной форме (д.н.ф.) булевой функции $f$ и число $\tau(f)$ тупиковых д.н.ф. являются важными параметрами, характеризующими сложность алгоритмов нахождения минимальных д.н.ф. Показано, что у почти всех булевых функций $l(f)\sim2^{n-1}$, $\log_2\tau(f)\sim2^{n-1}\log_2n\log_2\log_2n$ ($n\to\infty$). Библ. 5 назв.
 Полный текст:
PDF файл (687 kB)
Англоязычная версия:
Mathematical Notes, 1968, 4:6, 881–886
Реферативные базы данных:
 
УДК:
51.01.16
Поступило: 20.05.1968
Образец цитирования:
А. А. Сапоженко, “О наибольшей длине тупиковой дизъюнктивной нормальной формы у почти всех булевых функций”, Матем. заметки, 4:6 (1968), 649–658; Math. Notes, 4:6 (1968), 881–886
Цитирование в формате AMSBIB
\RBibitem{Sap68}
\by А.~А.~Сапоженко
\paper О~наибольшей длине тупиковой дизъюнктивной нормальной формы у~почти всех булевых функций
\jour Матем. заметки
\yr 1968
\vol 4
\issue 6
\pages 649--658
\mathnet{http://mi.mathnet.ru/mz6785}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=243936}
\zmath{https://zbmath.org/?q=an:0177.02001|0169.01702}
\transl
\jour Math. Notes
\yr 1968
\vol 4
\issue 6
\pages 881--886
\crossref{https://doi.org/10.1007/BF01110822}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/mz6785 http://mi.mathnet.ru/rus/mz/v4/i6/p649
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
И. П. Чухров, “О тупиковых комплексах граней в единичном кубе”, Дискрет. матем., 23:1 (2011), 132–158
  ; I. P. Chukhrov, “On irredundant complexes of faces in the unit cube”, Discrete Math. Appl., 21:2 (2011), 243–274 -
И. П. Чухров, “О соотношении тупиковых и минимальных комплексов граней в единичном кубе”, Дискрет. матем., 24:2 (2012), 46–74 ; 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
|
| Просмотров: |
| Эта страница: | 364 | | Полный текст: | 99 | | Первая стр.: | 1 |
|
Пользовательское соглашение