Статья: Точный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графе (2025)

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

Обеспечение безопасности движения на железнодорожном транспорте требует постоянного мониторинга состояния рельсов для своевременного выявления и устранения дефектов. Одним из методов неразрушающего контроля рельсов является вихретоковая дефектоскопия. Данные (дефектограммы), получаемые от вихретоковых дефектоскопов, отличаются значительным объёмом, что делает необходимым разработку эффективных методов их автоматической обработки и анализа. Анализ дефектограмм может быть осложнён присутствием в данных различных помех и шумов. Одними из наиболее опасных помех, существенно искажающих форму полезных сигналов, являются продолжительные импульсные помехи. Они характеризуются выраженной прямоугольной формой. В отличие от мгновенных импульсных помех, продолжительные шумы классическими методами не устраняются. Не существует зарекомендовавших себя эффективных методов не только для подавления прямоугольных помех, но даже для их обнаружения. Данная статья пытается устранить этот недостаток и предлагает действенный метод для обнаружения таких помех на вихретоковых дефектограммах, обладающий хорошей объясняющей способностью. Прямоугольные сигналы исследуются с точки зрения их вероятностного распределения. Введена SW-характеристика, позволяющая оценить правдоподобие данных для распределения биполярных импульсных сигналов. Чем меньше значение SW-характеристики, тем более распределение данных похоже на распределение биполярных импульсных сигналов. Прямоугольные сигналы являются частным случаем биполярных импульсных сигналов. Исследованы свойства SW-характеристики. SW-характеристика вычислена для нормального распределения и распределения гомоскедастичной смеси двух гауссиан. Показано, что значение SW-характеристики нормального распределения примерно разграничивает бимодальную смесь двух гауссиан от унимодального случая. Эти и другие свойства SW-характеристики позволяют использовать её для обнаружения прямоугольных сигналов в данных. Применение критерия на основе SW-характеристики продемонстрировано на реальных примерах вихретоковых дефектограмм, проведено сравнение с критериями на основе EM-алгоритма и многомасштабной дисперсной энтропии. Предложенный в данной статье критерий показал лучшие результаты. Использование SW-характеристики для обнаружения прямоугольного шума доказало свою эффективность на практике при анализе вихретоковых дефектограмм рельсов. Подход может быть адаптирован для работы с другими видами данных.

Данная статья посвящена проблеме верификации параллельных программ, которые могут содержать особые виды ошибок, связанных с синхронизацией параллельно исполняемых потоков и доступом к общей памяти. К таким ошибкам относятся тупики и гонки данных. Существует разделение методов верификации параллельных программ на статические и динамические. Последние требуют запуска кода и позволяют проверить на гонки лишь текущую реализацию программы, что при наличии большого числа ветвлений может привести к пропуску гонок. Среди статических методов наибольшее применение нашли аналитические методы (например, на основе дедуктивного анализа) и методы проверки моделей. Однако они сложны в реализации, а последние по-прежнему требуют от программиста значительного объёма ручной работы для построения модели. В этой связи необходимо использование моделей, которые могут быть построены автоматически. Ранее авторами была разработана модель на основе расширения сетей Петри, позволяющая автоматическое построение на основе последовательного кода и преобразование её в параллельный код. Автоматическое построение модели параллельной программы вводит новые, ранее не использовавшиеся требования, связанные со взаимодействием параллельных потоков. Таким образом, в данной статье рассматриваются особенности моделирования с использованием расширенных сетей Петри с семантическими связями основных примитивов синхронизации, реализуемых в большинстве языков и технологий параллельного программирования для систем с общей памятью. В дальнейшем на основе этих моделей будет проводится поиск гонок данных и тупиков для параллельных программ.

Рассматривается NP-трудная задача динамического распределения виртуальных машин по серверам с группами размещения. Для каждой виртуальной машины известны такие параметры, как необходимое количество ресурсов и временные метки создания и удаления. Каждый сервер представляет собой композицию NUMA-узлов и размещается в некоторой стойке. Рассматриваются большие виртуальные машины, размещаемые на два узла одного сервера, и маленькие, что накладывает дополнительные условия для их размещения. Группы размещения представляют собой объединения подмножеств виртуальных машин с условиями конфликта между подмножествами. Задача состоит в том, чтобы упаковать все виртуальные машины с использованием минимального количества стоек серверов в течение рассматриваемого временного горизонта. Для решения данной задачи предлагается эвристика, основанная на методе генерации столбцов. Анализируется набор статических задач в различные моменты времени, необходимых для формирования общего набора шаблонов, используемых при построении верхних оценок. Результаты вычислительных экспериментов на реальных открытых примерах указывают на незначительные расхождения между нижними и верхними границами.

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