ПРИКЛАДНАЯ ДИСКРЕТНАЯ МАТЕМАТИКА

Рассматривается NP-трудная оптимизационная задача корреляционной кластеризации для неориентированных и невзвешенных знаковых графов без кратных рёбер и петель, где функционал ошибки представляет собой линейную комбинацию межкластерной и внутрикластерной ошибок. Предложен системный подход построения и анализа алгоритмов, основанных на структуре графа, для решения этой задачи. Подход представлен в виде общей схемы, состоящей из шести взаимосвязанных блоков, отражающих основные этапы решения задачи корреляционной кластеризации. С использованием данной схемы проанализированы шесть существующих алгоритмов. Согласно общей схеме построен новый алгоритм CarVeR, который является модификацией алгоритма SGClustα с помощью потенциальных функций. Топология общей схемы открывает возможности для анализа и доказательства вычислительной сложности алгоритмов, что продемонстрировано в теореме о вычислительной сложности алгоритма CarVeR. Представлены вычислительные эксперименты на синтетических данных для сравнения пяти алгоритмов. Результаты экспериментов показали конкурентную способность алгоритма CarVeR как по времени выполнения, так и по минимизации значения функционала ошибки.

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

Получен упрощённый вариант формулы суммирования Эйлера - Маклорена. Формула включает в себя интегральную оценку суммы дискретных отсчётов функции и поправку к ней в виде суммы ряда весовых граничных значений её нечётных производных. Упрощением является исключение из результата суммирования полусуммы граничных значений функции и достигается путём смещения hr отсчётов внутрь отрезков интегрирования. Доказывается, что оптимальным является смещение каждого отсчёта в середину отрезка r = 1/2. Это смещение задаёт пределы интегральной оценки yo, ym и значения весовых коэффициентов производных поправочного ряда. Найдено аналитическое выражение этих коэффициентов и их производящая функция. На примерах показана справедливость полученной формулы и производящей функции её коэффициентов. Формула была использована для получения приближённых выражений для дзета-функции Римана, пси-функции, полигамма функций, а также сумм бесконечных обратностепенных рядов и гармонического ряда. На основании анализа погрешности этих выражений показаны преимущества упрощённой формулы перед формулой Эйлера - Маклорена в точности и краткости.

Изучается генерическая сложность проблемы проверки совместности систем уравнений над натуральными числами со сложением. Доказывается NP-полнота этой проблемы, предлагается полиномиальный генерический алгоритм её решения. Доказывается, что при Р ≠ NP и Р = ВРР для проблемы проверки совместности систем уравнений над натуральными числами с нулём не существует сильно генерического полиномиального алгоритма. Для сильно генерического полиномиального алгоритма нет эффективного метода случайной генерации входов, на которых этот алгоритм не может решить проблему.

Модель со случайным оракулом используется для доказательства стойкости криптографических протоколов в случае, когда стандартные предположения об использующейся хеш-функции не позволяют этого сделать. Однако на практике для реализации случайного оракула в конкретном протоколе используется некоторая детерминированная хеш-функция, которая, безусловно, не является случайным оракулом. Следовательно, в реальном мире нарушитель обладает более широкими возможностями, чем предполагалось в доказательстве - он может использовать особенности конструкции конкретной хеш-функции для осуществления угрозы. Если используемая хеш-функция строится на основе некоторого другого примитива (например, блочного шифра), можно рассмотреть нарушителя, который имеет доступ напрямую к этому примитиву, и показать, что даже относительного такого нарушителя используемая хеш-функция ведёт себя как случайный оракул в предположении об идеальности используемого примитива. Таким образом можно доказать стойкость протокола относительно более сильных нарушителей в менее сильных предположениях об использующихся примитивах. Хеш-функции, при использовании которых можно достичь такого результата, называются неразличимыми от случайного оракула. В данной работе показано, что хеш-функция «Стрибог» неразличима от случайного оракула в модели идеального блочного шифра.

Найдены две бесконечные серии полугрупп, свойство внешнепланарности графов Кэли в которвіх эквивалентно свойству обобщённой внешнепланарности их графов Кэли, но не эквивалентно свойству планарности, и одна бесконечная серия полугрупп, свойство обобщённой внешнепланарности графов Кэли которых эквивалентно свойству планарности их графов Кэли, но не эквивалентно внешнепланарности. Доказано, что граф Кэли конечной полугруппы не изоморфен ни одному из запрещённых подграфов Седлачека, взятых с любой ориентацией и раскраской рёбер, по характеристическому свойству обобщённой внешнепланарности.

Представлены результаты, касающиеся основной проблемы алгебраической геометрии над частично упорядоченными множествами с вычислительной точки зрения, а именно задачи разрешимости системы уравнений над частичным порядком. Задача разрешимости систем уравнений разрешима за полиномиальное время, если ориентированный граф, соответствующий частичному порядку, является приведённым интервальным орграфом, и является NP-полной, если основание ориентированного графа соответствующего частичного порядка является циклом длины не меньше 4. Получен также результат, характеризующий возможность перехода от бесконечных систем уравнений над частичным порядком к конечным системам. Алгебраические системы, обладающие указанным свойством, называются нётеровыми по уравнениям. Частично упорядоченное множество обладает свойством нётеровости по уравнениям тогда и только тогда, когда любые его верхние и нижние конусы с базой являются конечно определёнными.