Теоретическая и системная информатика. Рубрика в журнале - Проблемы информатики
Можно ли добиться дальнейшего ускорения расчета характеристик связности случайного графа?
Статья научная
В статье рассматриваются новые приемы ускорения расчета некоторых характеристик связности случайного графа (вероятность связности подмножества вершин, средняя вероятность парной связности, математическое ожидание размера связного подграфа, содержащего выделенную вершину и некоторые другие). Эти задачи имеют доказано неполиномиальный характер сложности, и, как правило, ищутся приближенные решения. Однако, с развитием вычислительной техники и разработкой параллельных алгоритмов, нахождение точных решений стало возможным для графов достаточно большой размерности для решения практических задач (до сотен вершин в случае небольшой их средней степени). Кроме того, найденные за годы решения этих задач, в том числе автором доклада, различные приемы редукции и декомпозиции позволили еще больше поднять размерность рассчитываемых графов. Точные решения необходимы также для оценки качества приближенных алгоритмов. Предлагаются различные приемы развития известного метода факторизации, когда вместо рассмотрения одного разрешающего ребра рассматривается некоторое небольшое подмножество специальным образом выбранных ребер.
Бесплатно
Нахождение хроматического числа графа с помощью методов глубокого обучения
Статья научная
Алгоритмы глубокого обучения сильно развились в последнее десятилетие и стали стандартом во многих сферах. Притом количество архитектур глубокого обучения растет и существуют модели, работающие со структурой графа Graph Neural Network или GNN, которые показали свою эффективность в различных доменах. Также глубокое обучение применяют и для решения задач комбинаторной оптимизации. Поскольку многие задачи комбинаторной оптимизации изначально формулируются в терминах теории графов или же могут быть конвертированы в подобное представление, то архитектура GNN может стать эффективным методом для их приблизительного решения. В этой работе рассматривается задача о нахождении хроматического числа графа и ее приблизительное решение с помощью GNN. Вершины и цвета, в которые предположительно можно раскрасить граф, задаются случайными эмбеддингами, далее GNN, с учетом структуры графа, преобразовывает все эмбеддинги и производит на их основе бинарную классификацию, может граф быть раскрашен в данное количество цветов или нет. Данные для обучения сети являются сгенерированными и представляют собой сложные случаи раскраски. Также для тестирования обобщенности приведены замеры на данных, сильно отличающихся от тренировочных. Натренированная на синтетических данных GNN сравнивается по точности и времени исполнения с эвристиками: tabucol и жадный алгоритм.
Бесплатно
Нейросетевой подход к решению задачи самовоздействия волновых полей в нелинейных средах
Статья научная
В работе рассматривается возможность применения технологий глубинного обучения для численного решения задачи о распространении оптических импульсов в средах с нелинейностью Керра. В качестве математической модели, описывающей процессы эволюции огибающей электромагнитного излучения, выбрано обобщенное параболическое уравнение, которое в безразмерных переменных имеет вид одномерного модифицированного нелинейного уравнения Шредингера. Была предложена постановка указанной проблемы, позволяющая задействовать для расчетов методы искусственного интеллекта, и реализован один из возможных вариантов данного подхода с применением полносвязной нейронной сети для решения физических задач. При этом был проведен анализ различных алгоритмов подбора параметров, ответственных за передачу информации от слоя к слою такой сети в ходе ее обучения. Выполненные исследования показали, что наиболее перспективными с точки зрения скорости вычислений и адекватности предсказаний являются квази-ньютоновские функции оптимизации, которые в стандартных библиотеках имеют аббревиатуру L-BGFS.
Бесплатно
Нелинейная стационарная задача теории переноса в диффузионном приближении
Статья научная
Одним из наиболее эффективных математических приближений для описания процессов переноса рентгеновского излучения является многогрунновое диффузионное приближение. Уравнения одногруннового диффузионного приближения представляют собой систему двух дифференциальных уравнений относительно двух неизвестных функций: плотности и потока излучения. В работе рассматривается нелинейная задача теории переноса излучения в диффузионном приближении, формулируется линеаризующий итерационный алгоритм решения нелинейной задачи. Кроме того, исследуется возможность применимости соответствующего линеаризующего итерационного алгоритма для нелинейной системы интегро-дифференциальных уравнений переноса излучения и статистического равновесия для модели двухуровневого атома. Следует отметить, что модель двухуровневого атома отражает важные содержательные задачи, а также может рассматриваться как составная часть исследования более сложных задач многоуровнего атома. Для решения возникающей системы уравнений предлагается и численно исследуется линеаризующий итерационный алгоритм решения. Приводятся результаты численного анализа предлагаемого итерационного алгоритма, подтверждающие возможность его применения. Обсуждаются свойства используемой разностной схемы.
Бесплатно
О функциональном программировании и модульности
Статья научная
В связи С грядущим переходом к использованию экзафлопСных вычислителей, актуальна разработка методов программирования для нетрадиционных моделей вычислений, допускающих выполнение на очень большом числе процессоров. В этом плане весьма перспективной представляется функциональная модель, возможности которой но отношению к модуляризации программ, обсуждаются в сопоставлении С модульностью в императивных языках. Показана несостоятельность претензии на универсальность как функционального, так и императивного стилей каждый из них имеет свою область адекватного применения.
Бесплатно
Об одной задаче оптимизации распределения ресурсов в иерархических сетях
Статья научная
В работе рассматривается одна из прикладных проблем в области оптимизации пунктов распределения различных услуг (например, газо-, нефте-, и водоснабжения) проблема оптимального размещения производств и распределения ресурсов между потребителями и поставщиками с учетом различных ограничительных условий. Рациональное размещение элементов сетей инженерных коммуникаций но переработке и распределению ресурсов между потребителями является сложной технико-экономической задачей. При ее решении необходимо учесть не только ресурсные ограничения, но план переработки и распределения ресурсов между потребителями, обеспечивающие эффективную схему функционирования проектируемой сети. В работе рассматривается задача оптимального распределения однородного ресурса в иерархических сетях и ее решение методом последовательных расчетов. Предлагаемый метод позволяет, хотя и посредством частичного перебора, находить глобальный экстремум многоэкстрсмальной задачи с высокой степенью точности.
Бесплатно
Обзор современных подходов искусственного интеллекта для систем управления сложными объектами
Статья научная
В статье проведен аналитический обзор интеллектуальных систем управления сложными объектами, построенных на основе генетических алгоритмов, оптимизации роя частиц и алгоритмов оптимизации муравьиных колоний за период с 2015 по 2018 год. Показаны важность применения биоинсперированных подходов искусственного интеллекта и перспективы их развития. Приведены основные достоинства и недостатки применения различных интеллектуальных алгоритмов при построении интеллектуальных систем управления сложными объектами. Показана актуальность разработок интеллектуальных систем при создании инновационных интеллектуальных технологий для различных практических приложений в промышленности, нефтегазовой отрасли, транспорте и других областях.
Бесплатно
Статья научная
В работе рассматривается компьютерная реализация моделей нетрадиционного алгоритма шифрования, основанного на непозиционной полиномиальной системе счисления. Описаны методы объектно-ориентированного программирования, упрощающие процесс исследования разработанных моделей. Проведен анализ компьютерной программы, реализующей функции генерации полного ключа шифрования и выполняющей шифрование с использованием режимов блочных шифров.
Бесплатно
Статья научная
В статье представлены результаты решения задачи стабилизации ротора в системе электромагнитного подвеса на основе применения нечетких моделей Takagi-Sugcno. Рассмотрены две задачи управления: построение стабилизирующих регуляторов и построение оптимальных регуляторов по заданному квадратичному критерию качества. Для решения поставленных задач исходная нелинейная математическая модель преобразовывалась к определенному виду, а затем заменялась эквивалентной нечеткой моделью, состоящей из совокупности линейных подсистем. Для построения нечеткой математической модели использовались функции распределения треугольного вида. Результирующая нечеткая модель представлялась как взвешенная сумма всех линейных подсистем. Для синтеза законов управления применялся аппарат линейных матричных неравенств, расширенный на случай нечетких систем. В этом случае каждой линейной подсистеме соответствовала своя система линейных матричных неравенств. В результате проведения численных расчетов были получены нечеткие регуляторы обоих типов, которые затем поочередно подставлялись в исходный нелинейный объект, замкнутый нечетким регулятором. Для проверки работоспособности регуляторов выполнялось математическое моделирование динамики ротора. В качестве результатов моделирования представлены переходные процессы в замкнутой системе. Результаты численных расчетов и проведенного математического моделирования показали, что с помощью нечетких моделей Takagi-Sugcno можно построить как стабилизирующий регулятор, так и оптимальный регулятор по заданному квадратичному критерию качества для управления ротором в электромагнитном подвесе. Найденные регуляторы обеспечивали стабилизацию ротора в достаточно широком диапазоне начальных возмущений, вплоть до максимально возможных значений. Основываясь на полученных результатах, можно заключить, что представленный подход, основанный на использовании нечетких моделей Takagi-Sugcno, позволяет в широком диапазоне начальных возмущений стабилизировать ротор в системе электромагнитного подвеса.
Бесплатно
Статья научная
Рассматривается линейная нестационарная система при неточно известных началвном состоянии и действующем возмущении, удовлетворяющих единому ограничению. Ограничение представляет собой сумму квадратичной формы начального состояния и интеграла по времени от квадратичной формы возмущения (квадратичные формы могут быть вырожденными). Для такой системы приведен способ оценки эллипсоидального множества достижимости с использованием матричного дифференциального уравнения Риккати. Его использование позволяет найти минимальное множество достижимости (то есть оценка оптимальна), которое определено при помощи оптимального наблюдателя. Помимо этого, рассматривается линейная нестационарная система, включающая в себя параметрическую неопределенность, которая также является нестационарной. Для нее также приводится оценка эллипсоидальных множеств достижимости. Применение обоих методов продемонстрировано на примере уравнения Матье-Хилла с затуханием, которое описывает параметрические колебания и резонанс и уравнения маятника. Для вычислений применяется итерационная процедура с использованием метода Эйлера.
Бесплатно
Оптимизация динамики функционирования сети больниц с учетом ошибок результатов наблюдений
Статья научная
В России за последние несколько лет наблюдается тенденция роста числа престарелых граждан и заболеваемости данной категории лиц. Возникшая ситуация требует повышения эффективности работы существующей системы медицинских учреждений для каждого конкретного субъекта в условиях ограничения финансовых и других ресурсов в здравоохранении. Указанную задачу невозможно решить без аналитического исследования, направленного на экономическую оптимизацию расходов в каждом медицинском учреждении и в сети медицинских учреждений субъекта в целом. В данной работе используется представление процесса функционирования сети медицинских учреждений в виде управляющей кибернетической системы. Авторами, с использованием кибернетического подхода, проведен синтез математической модели функционирования типового медицинского учреждения сети в виде управляющей системы. Созданная математическая модель позволяет по единственному измерению с заданной точностью генерировать значения основных показателей работы медицинского учреждения в течении каждого отчетного периода и, таким образом, получать дополнительную статистику любого конечного объема но этим показателям. Полученные с помощью построенной модели данные можно использовать для изучения качества и динамики функционирования медицинского учреждения. А также для исследования влияния ошибочной информации на показатели эффективности функционирования сети медицинских учреждений субъекта. В работе на основании полученной дополнительной статистики предлагается решение задачи определения механизма оптимального распределения ресурсов между медицинскими учреждениями сети конкретного субъекта на примере Нижнего Новгорода.
Бесплатно
Оптимизация размещения контрольных устройств на каналах в сетях мониторинга
Статья научная
При анализе или проектировании больших сетей мониторинга часто возникает проблема выбора контрольных устройств (b-узлов) для сбора информации. После некоторой предварительной обработки или напрямую b-узлы передают информацию центральному узлу (с-узлу) по надежным каналам. Одним из основных показателей качества таких сетей является размер территории, находящейся под надежным контролем, которую можно оценить с помощью MENC - математического ожидания количества узлов, связанных с одним специальным узлом. Гиперсети используются для представления сети. Задача вычисления MENC является NP-сложной задачей. Поэтому для оптимизации дорогостоящего размещения Ь-узлов был применен алгоритм имитации отжига.
Бесплатно
Статья обзорная
В статье исследуется надежность привязных беспилотных телекоммуникационных платформ длительного функционирования с использованием математических моделей систем типа k- из-n. Разработаны новые методы и алгоритмы расчета стационарных характеристик таких систем, а также имитационные модели для оценки параметров надежности при произвольных функциях распределения времени жизни и восстановления элементов системы. Для предсказания характеристик надежности системы k-тз-и, адекватно описывающей функционирование привязной беспилотной платформы, впервые применены методы машинного обучения. Полученные результаты иллюстрируются численными примерами.
Бесплатно
Параллельная реализация алгоритма логических операций над множествами ортогональных многоугольников
Статья научная
В рамках разработки отечественных САПР для верификации норм конструкторско- технологических ограничений (КТО) необходима разработка библиотеки выполнения логических операций над ортогональными многоугольниками, составляющими топологию интегральной схемы. Функции библиотеки выполняют операции над слоями. Под слоем понимается множество ортогональных прямоугольников (полигонов). К этим операциям предъявляются жесткие требования по времени выполнения. Существует реализация, построенная на основе алгоритма заметающей прямой и позволяющая добиться времени работы алгоритма порядка O(NlogN ). Для эффективного функционирования в высокопроизводительной вычислительной среде разработана параллельная реализация, основанная на геометрической декомпозиции исходных данных. Проведенное теоретическое исследование показало линейную масштабированность данной реализации на системах с распределенной памятью, но реализация в виде многопоточного приложения выявила конкуренцию за разделяемый ресурс. В работе приводятся результаты вычислительного эксперимента и намечаются пути устранения эффекта конкуренции. Представленные в работе реализации алгоритмов и процедур вошли в состав подключаемой библиотеки функций работы со слоями топологического описания, которая, в свою очередь, является частью разрабатываемой системы верификации норм КТО. Данная библиотека реализована на языке C++ с использованием стандарта C++17. Имплементация параллельных схем реализации логических операций выполнена с использованием библиотеки OpenMP.
Бесплатно
Статья научная
В работе рассматривается методика получения системы линейных дифференциальных уравнений для решения нестационарной задачи распространения тепла в стержне с использованием вариационного подхода с привлечением квадратичной аппроксимации температуры элементов стержня. При этом сначала исследуются случаи, когда стержень разбивается на два и три элемента, когда с левого торца стержня подается поток тепла, правый торец стержня не теплоизолирован, а элементы боковой поверхности стержня теплоизолированы в различной комбинации. Далее, анализируя системы линейных дифференциальных уравнений, полученные для различных вариантов теплоизоляции боковой поверхности элементов стержня, определены правила составления систем линейных дифференциальных уравнений для решения нестационарной задачи распространения тепла в стержне, состоящей из любого количества элементов стержня с использованием квадратичной аппроксимации, когда элементы стержня теплоизолированы произвольным образом. При этом сформулированы правила получения стационарной и нестационарной части, а также правой части системы линейных дифференциальных уравнений. Разработано программное обеспечение с использованием инструментального программирования Delphi для получения системы линейных дифференциальных уравнений для решения нестационарной задачи распространения тепла в стержне. Рассмотрены конкретные примеры решения нестационарной задачи распространения тепла в стержне, когда левая половина стержня теплоизолирована, а правая нет, и наоборот.
Бесплатно
Представление графов и графовых моделей: базовые средства языка GraphML
Статья научная
Статья посвящена международному проекту GraphML, инициированному сообществом по рисованию графов в 2000 г. с целью создания стандартизованного языка описания графов на основе языка XML, и содержит описание базовых средств языка GraphML, достаточных для представления графовых моделей в большинстве приложений. В ней рассматривается, как графы и графовые данные представляются в формате GraphML с использованием базовой графовой модели, которая охватывает графы, содержащие ориентированные и неориентированные ребра, петли, кратные ребра и различные пометки (атрибуты) вершин, ребер и частей графа.
Бесплатно
Статья научная
Задача о качении без скольжения однородного шара по неподвижной поверхности под действием силы тяжести является одной из классических задач механики неголономных систем. Обычно при рассмотрении этой задачи, следуя подходу, предложенному в трактате Э.Дж.Рауса, принято задавать в явном виде поверхность, по которой движется центр шара, а не опорную поверхность, по которой катится шар. Поверхность, по которой движется центр шара, является эквидистантной к поверхности, по которой движется точка контакта. Еще из работ Э.Дж.Рауса и Ф.Нетера было известно, что если при качении шара по поверхности под действием силы тяжести его центр движется по поверхности вращения, то задача сводится к интегрированию одного линейного дифференциального уравнения второго порядка относительно компоненты скорости центра шара в проекции на направление касательной к параллели поверхности вращения. В общем случае (для произвольной поверхности вращения) получить решение этого уравнения в явном виде невозможно. Поэтому представляет интерес вопрос, для каких поверхностей вращения соответствующее линейное дифференциальное уравнение второго порядка допускает общее решение, выражающееся в явном виде, например, с помощью лиувиллевых функций. Лиувиллевы функции - это функции, которые строятся последовательно из рациональных функций с использованием алгебраических операций, неопределенного интегрирования и взятия экспоненты заданного выражения{Kovacic, Kaplansky}. Необходимые и достаточные условия существования решения линейного дифференциального уравнения второго порядка, выражающегося через лиувиллевы функции, дает так называемый алгоритм Ковачича. В данной работе мы приводим наш собственный способ получения линейного дифференциального уравнения второго порядка, к интегрированию которого сводится задача о качении тяжелого шара по неподвижной поверхности такой, что центр шара при качении движется по заданной поверхности вращения. Затем при помощи замены независимой переменной мы приводим коэффициенты этого уравнения к виду рациональных функций. Применяя затем к полученному линейному дифференциальному уравнению второго порядка алгоритм Ковачича, мы показываем, что для случая, когда центр шара принадлежит параболоиду вращения, общее решение данного уравнения выражается через лиувиллевы функции.
Бесплатно
Статья научная
Описано применение метода множества эквивалентности для решения задач многокритериальной оптимизации и обратных некорректных задач математической физики. Показаны преимущества метода множества эквивалентности по сравнению с другими методами, часто использующимися при решении многокритериальных задач. Сформулированы и доказаны теоремы, отражающие основные свойства метода множества эквивалентности и показывающие соотношение и взаимосвязь множества парето-оптимальных решений и множества эквивалентности. На примере задачи самофокусировки плоских рентгеновских импульсов в плазме описано применение метода множества эквивалентности для решения обратных задач математической физики. Показано, что метод множества эквивалентности можно считать обобщением метода регуляризации для некорректных задач в многомерном псевдометрическом пространстве критериев в дискретном случае.
Бесплатно
Статья научная
При помощи метода выделения характерных фаз поведения, основанного на расчете локальных ляпуновских показателей, получены основные характеристики перемежаемости на границе обобщенной синхронизации. Установлено, что данный метод позволяет проводить исследование не только в случае однонаправленной, но и взаимной связи. В качестве анализируемых систем выбраны однонаправленно и взаимно связанные системы Ресслера со сравнительно простой топологией аттрактора (ленточный тип) и осцилляторы Лоренца со сравнительно сложной топологией (двулистный тип). При этом, в первом случае реализуется перемежаемость ,,on-off“ типа, а во втором - перемежаемость типа перескоков. В работе были оценены основные характеристики перемежаемости, такие как распределения длительностей ламинарных (синхронных) фаз при фиксированном значении параметра связи и зависимость средней длительности ламинарных фаз от параметра надкритичности. Показано, что наблюдается хорошее соответствие между характеристиками, рассчитанными при помощи численного метода, и теоретическими закономерностями. Результаты работы хорошо согласуются с данными других работ и демонстрируют, что метод расчета локальных показателей Ляпунова может быть успешно применен для анализа систем, характеризующихся различной сложностью топологии аттрактора, как при однонаправленной, так и взаимной связи.
Бесплатно
Применение нестационарных сетей в задачах мониторинга
Статья научная
В статье исследуется тема моделирования современных сетей передачи данных с узлами на движущихся объектах транспортных средствах, беспилотных летательных аппаратах. Описаны основные задачи, возникающие при оптимизации сбора и передачи информации в нестационарных сетях (кластеризация узлов, использование мобильных стоков и др.). Приведен обзор публикаций последних лет с описанием систем имитационного моделирования функционирования таких сетей, а также предлагается разработанная авторами модель сети с узлами на беспилотных летательных аппаратах.
Бесплатно
