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

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

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



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






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


Журнал вычислительной математики и математической физики, 2011, том 51, номер 8, страницы 1531–1540 (Mi zvmmf9532)  

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

Асимптотические оценки числа решений задачи дуализации и ее обобщений

Е. В. Дюковаa, Р. М. Сотнезовb

a 119333 Москва, ул. Вавилова, 40, ВЦ РАН
b 119991 Москва, Ленинские горы, МГУ
Список литературы:
Аннотация: Получены асимптотики типичных значений числа неприводимых покрытий и длины неприводимого покрытия булевой матрицы для случая, когда число строк $m$ не меньше числа столбцов $n$. Как следствие получены асимптотики типичных значений числа максимальных конъюнкций и ранга максимальной конъюнкции монотонной булевой функции от $n$ переменных, заданной конъюнктивной нормальной формой из $m$ элементарных дизъюнкций. Приведены аналогичные оценки для числа тупиковых покрытий и длины тупикового покрытия целочисленной матрицы (числа максимальных конъюнкций и ранга максимальной конъюнкции двузначной логической функции, заданной множеством нулей). Дан обзор результатов, полученных ранее в данной области. Библ. 18.
Ключевые слова: сложность задач перечисления, задача дуализации, максимальная конъюнкция, неприводимое покрытие булевой матрицы, тупиковое покрытие целочисленной матрицы, асимптотически оптимальный алгоритм поиска тупиковых покрытий, метрические свойства множества покрытий, метрические свойства дизъюнктивных нормальных форм.
Поступила в редакцию: 13.07.2010
Исправленный вариант: 18.01.2011
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2011, Volume 51, Issue 8, Pages 1431–1440
DOI: https://doi.org/10.1134/S0965542511080069
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.712
Образец цитирования: Е. В. Дюкова, Р. М. Сотнезов, “Асимптотические оценки числа решений задачи дуализации и ее обобщений”, Ж. вычисл. матем. и матем. физ., 51:8 (2011), 1531–1540; Comput. Math. Math. Phys., 51:8 (2011), 1431–1440
Цитирование в формате AMSBIB
\RBibitem{DyuSot11}
\by Е.~В.~Дюкова, Р.~М.~Сотнезов
\paper Асимптотические оценки числа решений задачи дуализации и ее обобщений
\jour Ж. вычисл. матем. и матем. физ.
\yr 2011
\vol 51
\issue 8
\pages 1531--1540
\mathnet{http://mi.mathnet.ru/zvmmf9532}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2906725}
\transl
\jour Comput. Math. Math. Phys.
\yr 2011
\vol 51
\issue 8
\pages 1431--1440
\crossref{https://doi.org/10.1134/S0965542511080069}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000293977100015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80051779568}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf9532
  • https://www.mathnet.ru/rus/zvmmf/v51/i8/p1531
  • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:272
    PDF полного текста:85
    Список литературы:47
    Первая страница:8
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024