• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Найдено 38 публикаций
Сортировка:
по названию
по году
Статья
Sirotkin D., Malyshev D. Discrete Mathematics and Applications. 2018. Vol. 28. No. 4. P. 249-258.

The independent set problem for a given simple graph is to determine the size of a maximal set of its pairwise non-adjacent vertices. We propose a new way of graph reduction leading to a new proof of the NP-completeness of the independent set problem in the class of planar graphs and to the proof of NPcompleteness of this problem in the class of planar graphs having only triangular internal facets of maximal vertex degree 18

Добавлено: 22 августа 2018
Статья
Chirskii V., Nesterenko A. Discrete Mathematics and Applications. 2017. Vol. 27. No. 1. P. 1-7.

We consider a periodic sequence { ck }k=0 ∞ and investigate a numerical properties of an irrational number α =σk=0 ∞ ck/k!. As an application of our results we present a simple transformation of periodic sequence { ck }k=0 ∞ into aperiodic sequence. 

Добавлено: 21 мая 2017
Статья
Malyshev D. Discrete Mathematics and Applications. 2017. Vol. 27. No. 2. P. 97-101.
Добавлено: 10 мая 2017
Статья
Voronenko A. A., Mikhail N. Vyalyi. Discrete Mathematics and Applications. 2017. P. 319-324.
Добавлено: 16 октября 2017
Статья
Kochergin Vadim V. Discrete Mathematics and Applications. 2017. Vol. 27. No. 2. P. 81-95.
Добавлено: 8 октября 2018
Статья
Malyshev D. Discrete Mathematics and Applications. 2009. Vol. 19. No. 6. P. 619-625.
Добавлено: 13 октября 2010
Статья
Malyshev D. Discrete Mathematics and Applications. 2010. Vol. 19. No. 6. P. 625-630.

Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске.

Добавлено: 25 ноября 2012
Статья
Taletskii D. S., Malyshev D. Discrete Mathematics and Applications. 2017. Vol. 27. No. 5. P. 311-318.
Добавлено: 14 октября 2017
Статья
Matveenko V. D. Discrete Mathematics and Applications. 2009. No. 19 (4). P. 389-409.
Добавлено: 25 января 2010
Статья
Kochergin Vadim V., Mikhailovich Anna V. Discrete Mathematics and Applications. 2017. Vol. 27. No. 5. P. 295-302.

The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only nonmonotone element was completely solved by A. A. Markov. In 1957 he showed that the minimum number of NOT gates sufficient for realization of any Boolean function 𝑓 (the inversion complexity of the function 𝑓) is ]log_2(𝑑(𝑓) + 1)[. Here 𝑑(𝑓) is the maximum number of the changes of the function 𝑓 from larger to smaller values over all increasing chains of tuples of variables values. In the present paper, Markov’s result is extended to the case of realization of 𝑘-valued logic functions. We show that the minimum number of Post negations (that is, functions of the form 𝑥 + 1 (mod 𝑘)) that is sufficient to realize an arbitrary function of 𝑘-valued logic is ]log_2(𝑑(𝑓) + 1)[ and the minimum number of Łukasiewicz negation (that is, functions of the form 𝑘 − 1 − 𝑥) that is sufficient to realize an arbitrary 𝑘-valued logic function is ]log_𝑘(𝑑(𝑓)+1)[. In addition, another classical Markov’s result on the inversion complexity of systems of Boolean functions is extended to the setting of systems of functions of 𝑘-valued logic.

Добавлено: 14 марта 2018
Статья
Шнурков П. В., Иванов А. В. Дискретная математика. 2014. Т. 26. № 1. С. 143-154.

В работе рассматривается дискретная стохастическая модель управления запасом некоторого продукта, основанная на использовании управляемого полумарковского процесса. Определены вероятностные характеристики полумарковского процесса, а также характеристики стационарного стоимостного функционала, связанного с этим процессом. В работе установлено, что оптимальной стратегией управления запасом является детерминированная. Получены явные аналитические представления для стационарного функционала, характеризующего качество управления. Задача оптимального управления сведена к поиску экстремума функции нескольких вещественных переменных.

Добавлено: 30 января 2014
Статья
М.В. Соболева Дискретная математика. 2012. Т. 24. № 1. С. 123-131.

Рассматривается  d-мерная параметрическая модель случайных n-подстановок, для которой устанавливается совместная асимптотическая нормальность чисел конгруэнтных циклов в случайной подстановке. Предложен основанный на этом новый статистический критерий для проверки гипотезы о равновероятности подстановок. 

 

 

 

Добавлено: 25 февраля 2013
Статья
Логачев О. А., Федоров С. Н., Ященко В. В. Дискретная математика. 2018. Т. 30. № 1. С. 39-55.

Предлагается новый подход к изучению алгебраических, комбинаторных и криптографических свойств булевых функций. Инъективное отображение множества булевых функций на сферу в евклидовом пространстве позволило обнаружить новые взаимосвязи между функциями, при этом некоторые классы функций локализуются на сфере крайне регулярным образом. Вводится понятие кривизны булевой функции, характеризующее ее близость (в некотором смысле) к максимально нелинейным функциям.

Добавлено: 12 декабря 2018
Статья
Малышев Д. С. Дискретная математика. 2013. Т. 25. № 2. С. 63-67.

В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин.

Добавлено: 15 января 2014
Статья
Бежаева З. И., Оселедец В. И. Дискретная математика. 2012. Т. 24. № 1. С. 108-122.

В работе изучается один из вариантов задачи Эрдеша. Определяется инвариантная мера Эрдеша на некотором компакте и соответствующая ей скрытая цепь Маркова. Получена формула для вычисления энтропии инвариантной меры Эрдеша.

Добавлено: 21 мая 2012
Статья
Талецкий Д. С., Малышев Д. С. Дискретная математика. 2018. Т. 30. № 4. С. 115-133.

Для любого n в множестве n-вершинных деревьев, в которых любые два листа не имеют общей смежной вершины, полностью описаны деревья с наименьшим количеством максимальных независимых множеств.

Добавлено: 12 декабря 2018
Статья
Малышев Д. С. Дискретная математика. 2016. Т. 28. № 2. С. 44-50.

Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, определяемых запрещёнными подграфами, каждый из которых имеет не более 6 рёбер или не более 7 вершин.

Добавлено: 5 июля 2016
Статья
Энатская Н. Ю. Дискретная математика. 2017. Т. 29. № 1. С. 126-135.

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

Добавлено: 30 ноября 2017
Статья
Ивченко Г. И., Соболева М. В. Дискретная математика. 2011. Т. 23. № 3. С. 23-31.

Рассматривается двухпараметрическая модель случайных n-подстановок, обобщающая классическую модель А-подстановок, для которой изучается совместное распределение чисел А-циклов и -циклов при различных конкретизациях  подмножества .

Добавлено: 12 апреля 2012
Статья
Ивченко Г. И., Миронова В. А. Дискретная математика. 2013. Т. 25. № 1. С. 90-110.

Исследуются свойства спектра Уолша булевых функций от n переменных, случайно выбираемых из некоторых подмножеств всех таких функций. Выводятся соответствующие характеристические функции спектра и находятся точные и асимптотические распределения различных его характеристик.

Добавлено: 20 августа 2013
Статья
Вялый М. Н., Вороненко А. А. Дискретная математика. 2016. Т. 28. № 4. С. 50-57.

Доказана нетривиальная нижняя оценка (2+1/6)n для мощности области определения универсальной функции для класса линейных булевых функций, где n — число переменных. 

Добавлено: 13 января 2017
1 2