В данной статье предложен систематический подход к разработке алгоритмов комбинаторной генерации для множеств дискретных структур, мощность которых задается коэффициентами алгебраических производящих функций и их степеней. Исследование базируется на наличии связи между операциями над производящими функциями и комбинаторными множествами. В качестве основы использован математический аппарат деревьев И/ИЛИ, который позволяет комбинировать алгоритмы комбинаторной генерации для простых подструктур в сложные комбинаторные объекты. При этом основным теоретическим результатом работы является вывод новых эффективных рекуррентных формул для вычисления значений коэффициентов алгебраических производящих функций и их степеней с полиномиальной вычислительной сложностью O ((n1 + … + nm + m) n2)по времени и O( n2) по памяти. На основе доказанных теорем о рекуррентных формулах, предложенный подход позволяет строить алгоритмы с полиномиальной оценкой вычислительной сложности, что делает их применимыми для решения практических задач в области прикладной дискретной математики и теоретической информатики. Кроме того, использование коэффициентов степеней производящих функций расширяет возможности генерации, так как это позволяет строить не только объекты исходного комбинаторного множества, связанного с производящей функцией, но и кортежи таких объектов. Апробация предложенного подхода показана на примерах получения рекуррентных формул и алгоритмов генерации на их основе для классических числовых последовательностей, таких как числа Фибоначчи, Пелля, Каталана, Моцкина и Шредера. Предложенный подход открывает новые возможности для решения задач оптимизации, моделирования и кодирования сложных дискретных структур, например, в таких областях как биоинформатика и криптография.
При моделировании социальных процессов и явлений зачастую приходится обрабатывать данные, относящиеся к категоризованным признакам, выявлять причинно-следственные связи между такими данными, выделять наиболее существенные показатели. Исследование существующих подходов к анализу зависимостей между категоризованными переменными выявило ряд проблем при применении этих методов для многомерных категоризованных данных (тензоров). Поэтому в статье предлагается подход для изучения зависимостей между такими переменными с использованием многомерного компонентного анализа. Данный подход предполагает применение матриц развертки тензора, полученных для каждой его оси (категоризованного признака). Метод позволяет построить интегральные характеристики (компоненты) по элементам исходного тензора, сформировать матрицы компонентных нагрузок и рассчитать ядро тензора, имеющего меньшее число градаций категоризованных признаков (меньшее число измерений на осях тензора), чем исходный тензор. В статье предложен метод ранжирования градаций категоризованных переменных по степени совокупного влияния на них компонентных нагрузок, основанный на вычислении векторных норм. Изложенный подход к изучению зависимостей между многомерными категоризованными переменными продемонстрирован на примере трехмерного тензора с формой (4;10;10) и категоризованными признаками: группа нозологии, сфера деятельности, группа профессионально значимых качеств. Рассмотренный в статье алгоритм изучения многомерных категоризованных данных с применением многомерного компонентного анализа предполагается включить как аналитический инструмент информационно-аналитического регионального портала «ПЕРСПЕКТИВА-PRO», который может быть использован для разработки траекторий цифрового сопровождения лиц с инвалидностью и лиц с ОВЗ с учетом их личностных и вариативных характеристик.
В статье рассматривается аналоговая схема (аналоговый компьютер), в которой динамика изменения напряжений описывается системой Чуа. Найдены начальные состояния (установка начальных напряжений), которые выводят схему на предельный режим работы — скрытый аттрактор — устойчивый предельный цикл с частотой примерно 0,5 Гц. При этом получаемые сигналы имеют форму, близкую к гармоническому сигналу. Разработанная схема-генератор колебаний содержит семь операционных усилителей, не имеет мемристора, что дает значительное удешевление стоимости сборки; не имеет катушек индуктивности, что устраняет проблемы их изготовления, и гираторов. Определены значения номиналов сопротивлений и емкостей, соответствующих рассматриваемым параметрам системы. Один из инверторов схемы на базе операционного усилителя моделирует нелинейность типа упора, присутствующую в системе Чуа, периодически входя в состояния насыщения. После сборки устройства выходные сигналы схемы, соответствующие фазовым координатам системы Чуа, записаны в текстовый файл через шаг по времени с помощью цифрового осциллографа. Уточнены (идентифицированы) параметры математической модели в разработанной автором компьютерной программе, проверена адекватность модели по коэффициенту детерминации и критерию Фишера. Также численно исследуя устойчивость по Пуассону найденного режима в системе Чуа, определен период и частота полученного цикла, проведено сравнение с частотой, которую дает цифровой осциллограф.
Рассматривается важное в математической экологии логистическое уравнение с запаздыванием и диффузией. Предполагается, что граничные условия на одном из концов отрезка [0,1] содержат параметр. Исследован вопрос о локальной — в окрестности состояния равновесия — динамике соответствующей краевой задачи при всех значениях параметров граничных условий. Выделены критические случаи в задаче об устойчивости состояния равновесия и построены нормальные формы — скалярные комплексные обыкновенные дифференциальные уравнения первого порядка. Их нелокальная динамика определят поведение решений исходной задачи в малой окрестности состояния равновесия.
Исследование различных процессов приводит к необходимости уточнения (расширения) границ применимости вычислительных конструкций и инструментов моделирования. Целью данной статьи является развитие разложения Тейлора для функций нескольких переменных на основе понятия -дифференцируемости. Функцию из, где — -мерный куб, назовём -дифференцируемой во внутренней точке этого куба, если существует алгебраический многочлен степени не выше первой, для которого равномерно по всем векторам единичной сферы интеграл по с пределами и от выражения есть при. Показано, что при таком определении справедливо дифференцирование сложной функции с линейной внутренней компонентой, имеет место принцип вектора-градиента. Доказан следующий результат. Пусть функция имеет в некоторой окрестности внутренней точки непрерывные частные производные до порядка включительно, которые -дифференцируемы в точке, тогда в этой окрестности справедливо разложение Тейлора функции с точностью.
Рассматриваются полносвязные сети осцилляторов и их предельные системы интегро-дифференциальных уравнений с периодическими краевыми условиями. Предполагается, что связь слабая, то есть мал коэффициент при интегральном члене. В задаче об устойчивости нулевого состояния равновесия выделяются простейшие критические случаи потери устойчивости. В этих ситуациях строятся квазинормальные формы, представляющие собой интегро-дифференциальные уравнения, для которых аналитически определяются несколько континуальных семейств кусочно-постоянных двухступенчатых решений. Исследуется устойчивость этих решений. Показано существование кусочно-постоянных решений, имеющих более одной точки разрыва. Выполнен численный эксперимент, иллюстрирующий аналитические построения.
Обеспечение безопасности движения на железнодорожном транспорте требует постоянного мониторинга состояния рельсов для своевременного выявления и устранения дефектов. Одним из методов неразрушающего контроля рельсов является вихретоковая дефектоскопия. Данные (дефектограммы), получаемые от вихретоковых дефектоскопов, отличаются значительным объёмом, что делает необходимым разработку эффективных методов их автоматической обработки и анализа. Анализ дефектограмм может быть осложнён присутствием в данных различных помех и шумов. Одними из наиболее опасных помех, существенно искажающих форму полезных сигналов, являются продолжительные импульсные помехи. Они характеризуются выраженной прямоугольной формой. В отличие от мгновенных импульсных помех, продолжительные шумы классическими методами не устраняются. Не существует зарекомендовавших себя эффективных методов не только для подавления прямоугольных помех, но даже для их обнаружения. Данная статья пытается устранить этот недостаток и предлагает действенный метод для обнаружения таких помех на вихретоковых дефектограммах, обладающий хорошей объясняющей способностью. Прямоугольные сигналы исследуются с точки зрения их вероятностного распределения. Введена SW-характеристика, позволяющая оценить правдоподобие данных для распределения биполярных импульсных сигналов. Чем меньше значение SW-характеристики, тем более распределение данных похоже на распределение биполярных импульсных сигналов. Прямоугольные сигналы являются частным случаем биполярных импульсных сигналов. Исследованы свойства SW-характеристики. SW-характеристика вычислена для нормального распределения и распределения гомоскедастичной смеси двух гауссиан. Показано, что значение SW-характеристики нормального распределения примерно разграничивает бимодальную смесь двух гауссиан от унимодального случая. Эти и другие свойства SW-характеристики позволяют использовать её для обнаружения прямоугольных сигналов в данных. Применение критерия на основе SW-характеристики продемонстрировано на реальных примерах вихретоковых дефектограмм, проведено сравнение с критериями на основе EM-алгоритма и многомасштабной дисперсной энтропии. Предложенный в данной статье критерий показал лучшие результаты. Использование SW-характеристики для обнаружения прямоугольного шума доказало свою эффективность на практике при анализе вихретоковых дефектограмм рельсов. Подход может быть адаптирован для работы с другими видами данных.
Данная статья посвящена проблеме верификации параллельных программ, которые могут содержать особые виды ошибок, связанных с синхронизацией параллельно исполняемых потоков и доступом к общей памяти. К таким ошибкам относятся тупики и гонки данных. Существует разделение методов верификации параллельных программ на статические и динамические. Последние требуют запуска кода и позволяют проверить на гонки лишь текущую реализацию программы, что при наличии большого числа ветвлений может привести к пропуску гонок. Среди статических методов наибольшее применение нашли аналитические методы (например, на основе дедуктивного анализа) и методы проверки моделей. Однако они сложны в реализации, а последние по-прежнему требуют от программиста значительного объёма ручной работы для построения модели. В этой связи необходимо использование моделей, которые могут быть построены автоматически. Ранее авторами была разработана модель на основе расширения сетей Петри, позволяющая автоматическое построение на основе последовательного кода и преобразование её в параллельный код. Автоматическое построение модели параллельной программы вводит новые, ранее не использовавшиеся требования, связанные со взаимодействием параллельных потоков. Таким образом, в данной статье рассматриваются особенности моделирования с использованием расширенных сетей Петри с семантическими связями основных примитивов синхронизации, реализуемых в большинстве языков и технологий параллельного программирования для систем с общей памятью. В дальнейшем на основе этих моделей будет проводится поиск гонок данных и тупиков для параллельных программ.
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или вершину соответственно. Связанные ребра могут использоваться только согласованно. Делимые графы представляют собой специальный класс кратных графов. Их основная особенность состоит в возможности разделить граф на k частей, которые будут согласованы на связанных ребрах и не будут иметь общих ребер. Каждая часть является обычным графом. Кратное дерево представляет собой кратный граф без кратных циклов. Количество ребер может быть разным для кратных деревьев с одинаковым количеством вершин. Также можно рассмотреть остовные деревья в кратном графе. Остовное дерево является полным, если кратный путь, соединяющий любые две выбранные вершины, существует в дереве тогда и только тогда, когда такой путь существует в исходном графе. Задача о минимальном полном остовном дереве в кратном графе NP-трудна даже в случае делимого графа. В данной статье мы получим точный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графе. Также мы определим подкласс делимых графов, для которых алгоритм будет выполняться за полиномиальное время.
Рассматривается NP-трудная задача динамического распределения виртуальных машин по серверам с группами размещения. Для каждой виртуальной машины известны такие параметры, как необходимое количество ресурсов и временные метки создания и удаления. Каждый сервер представляет собой композицию NUMA-узлов и размещается в некоторой стойке. Рассматриваются большие виртуальные машины, размещаемые на два узла одного сервера, и маленькие, что накладывает дополнительные условия для их размещения. Группы размещения представляют собой объединения подмножеств виртуальных машин с условиями конфликта между подмножествами. Задача состоит в том, чтобы упаковать все виртуальные машины с использованием минимального количества стоек серверов в течение рассматриваемого временного горизонта. Для решения данной задачи предлагается эвристика, основанная на методе генерации столбцов. Анализируется набор статических задач в различные моменты времени, необходимых для формирования общего набора шаблонов, используемых при построении верхних оценок. Результаты вычислительных экспериментов на реальных открытых примерах указывают на незначительные расхождения между нижними и верхними границами.