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

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

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



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






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


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

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

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

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

a 119333 Москва, ул. Вавилова, 40, ВЦ РАН
b 119991 Москва, Ленинские горы, МГУ

Аннотация: Получены асимптотики типичных значений числа неприводимых покрытий и длины неприводимого покрытия булевой матрицы для случая, когда число строк $m$ не меньше числа столбцов $n$. Как следствие получены асимптотики типичных значений числа максимальных конъюнкций и ранга максимальной конъюнкции монотонной булевой функции от $n$ переменных, заданной конъюнктивной нормальной формой из $m$ элементарных дизъюнкций. Приведены аналогичные оценки для числа тупиковых покрытий и длины тупикового покрытия целочисленной матрицы (числа максимальных конъюнкций и ранга максимальной конъюнкции двузначной логической функции, заданной множеством нулей). Дан обзор результатов, полученных ранее в данной области. Библ. 18.

Ключевые слова: сложность задач перечисления, задача дуализации, максимальная конъюнкция, неприводимое покрытие булевой матрицы, тупиковое покрытие целочисленной матрицы, асимптотически оптимальный алгоритм поиска тупиковых покрытий, метрические свойства множества покрытий, метрические свойства дизъюнктивных нормальных форм.

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

Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2011, 51:8, 1431–1440

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

Тип публикации: Статья
УДК: 519.712
Поступила в редакцию: 13.07.2010
Исправленный вариант: 18.01.2011

Образец цитирования: Е. В. Дюкова, Р. М. Сотнезов, “Асимптотические оценки числа решений задачи дуализации и ее обобщений”, Ж. вычисл. матем. и матем. физ., 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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000293977100015}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80051779568}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/zvmmf9532
  • http://mi.mathnet.ru/rus/zvmmf/v51/i8/p1531

    ОТПРАВИТЬ: 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. Е. В. Дюкова, Р. М. Сотнезов, “О сложности задачи дуализации”, Ж. вычисл. матем. и матем. физ., 52:10 (2012), 1926–1935  mathnet  mathscinet  zmath; E. V. Dyukova, R. M. Sotnezov, “On the complexity of the dualization problem”, Comput. Math. Math. Phys., 52:10 (2012), 1472–1481  crossref
  • Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Просмотров:
    Эта страница:193
    Полный текст:56
    Литература:25
    Первая стр.:8
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021