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

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

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



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






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


Матем. заметки, 1968, том 4, выпуск 6, страницы 649–658 (Mi mz6785)  

Эта публикация цитируется в 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

    ОТПРАВИТЬ: 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. И. П. Чухров, “О тупиковых комплексах граней в единичном кубе”, Дискрет. матем., 23:1 (2011), 132–158  mathnet  crossref  mathscinet  elib; I. P. Chukhrov, “On irredundant complexes of faces in the unit cube”, Discrete Math. Appl., 21:2 (2011), 243–274  crossref
    2. И. П. Чухров, “О соотношении тупиковых и минимальных комплексов граней в единичном кубе”, Дискрет. матем., 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
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:320
    Полный текст:73
    Первая стр.:1

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019