ВЕСТНИК МОСКОВСКОГО УНИВЕРСИТЕТА. СЕРИЯ 15: ВЫЧИСЛИТЕЛЬНАЯ МАТЕМАТИКА И КИБЕРНЕТИКА

0137-0782

  • Publisher Федеральное государственное бюджетное образовательное учреждение высшего образования "Московский государственный университет им. М.В. Ломоносова"
  • Country Россия
  • Web https://elibrary.ru/title_about.asp?id=8373

Content

10-th international conference “Discrete models in the theory of control systems”

Alexeev V.B., Lozhkin S.A.

An FPT-algorithm for computing lattice width of simplicies, defined by a convex hull of points

Veselov S.I., Gribanov D.V., Malyshev D.S.

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

On application of the generalized allocation scheme to analysis of a class of sequences generated by a shift register

Kolchin A.V., Bezrodnyy B.F., Leeva M.A.

Рассматривается пример применения обобщенной схемы размещения к изучению асимптотического поведения комбинаторных объектов. В настоящей работе изучаются размещения наборов из $0$ и $1$ на окружности, вырабатываемых регистрами сдвига при определенных условиях.

Discrete model’s analysis of an adaptive control system for conflicting flows of nonhomogeneous demands

Kudryavtsev E.V., Fedotkin M.A.

С использованием кибернетического подхода Ляпунова-Яблонского построена и исследована математическая модель системы адаптивного управления конфликтными потоками неоднородных требований. В качестве состояния управляющей системы выбирается состояние обслуживающего устройства и длины очередей по конфликтным входным потокам. Доказано свойство марковости последовательности состояний системы и проведена их классификация. Найдено необходимое условие существования стационарного режима в системе.

On a certain set of closed classes in $k$-valued logic

Meshchaninov D.G.

Рассматриваются функции $k$-значной логики и связанные с делителями $d$ числа $k$ замкнутые (относительно суперпозиции) классы, содержащие все линейные по модулю $k$ функции. В таких классах определяются канонические формулы для элементов, находятся полные системы и базисы. Описывается решетка введенных классов по отношению включения. Обобщаются и дополняются предыдущие результаты, в частности, о $d$-периодических функциях и сохранении $d$-разностей.

Adjacent vertices can be hard to find by quantum walks

Nahimovs N., Santos R.A.M., Khadiev K.

Большинство статей в данной области посвящено случаю поиска одной отмеченной вершины. В нашей работе показывается, что в случае нескольких отмеченных вершин их взаимное расположение может разительно влиять на время работы алгоритма поиска. Мы показываем широкий класс размещений отмеченных вершин, для которых алгоритму поиска требуется $\Omega(N)$ шагов, т.е. столько же, сколько и классическому полному перебору. Найденные конфигурации состоят из двух и более смежных отмеченных вершин. В статье дается анализ для двумерной сетки, который затем обобщается на случай общего графа. Рассматривается алгоритмическое приложение обнаруженного эффекта. В качестве такого приложения выбрана задача определения наличия совершенного паросочетания в двудольном графе. Рассматривается класс двудольных графов, для которого алгоритм, использующий конфигурации-исключения квантовых блужданий, работает быстрее, чем классические алгоритмы.

The elements of associative stegnanography theory

Raikhlin V.A., Vershinin I.S., Gibadullin R.F.

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

Quantum algorithm for shortest path search is directed acycling graph

Khadiev K., Safina L.

В работе рассматривается задача нахождения кратчайших путей от заданной вершины до всех остальных в ациклическом взвешенном топологичиски отсортированном орграфе. Известно, что временная сложность лучшего детерминированного алгоритма составляет $O(M+N)$, где $N$ - число вершин в графе, а $M$ - число ребер. Предлагается квантовый алгоритм решения рассматриваемой задачи. Временная сложность предложенного алгоритма $O(\sqrt{NM}\log N)$, и вероятность ошибки $O(1/N)$. Данный алгоритм базируется на методе динамического программирования в ациклических орграфах, а также квантовом алгоритме Дюрра и Хойера (C. Dürr, P. Høyer) поиска минимального элемента в неупорядоченной последовательности. При этом алгоритм, описанный в данной работе, работает быстрее, чем лучший известный квантовый алгоритм нахождения кратчайшего пути в графе, предложенный Дюрром и соавторами для неориентированного графа.

This content is a part of the Information science and Information work collection from eLIBRARY.
If you are interested to know more about access and subscription options, you are welcome to leave your request below or contact us by eresources@mippbooks.com

Request

Unfortunately, we have no right to provide any kind of access to this resource in the territory of Western Europe. In any case, we will process your request and contact you with possible variants of solution.