Для авторов
Найти
Результаты поиска
Найдено результатов: 21.
-
МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ
А. В. Касаркин2021-02-25Аннотация ▼При решении графовых NP-полных задач на многопроцессорных системах рост обо-
рудования не приводит к пропорциональному росту производительности системы, поэто-
му не всегда удается решить задачу за приемлемое время. Целью работы, описанной в
статье, является минимизация времени решения задачи поиска максимальных клик графа с
использованием реконфигурируемых вычислительных систем (РВС). При решении задачи
на РВС методом распараллеливания по слоям рост производительности также замедля-
ется, несмотря на лучшую степень масштабируемости по сравнению с многопроцессор-
ными реализациями. В статье предложен метод создания параллельно-конвейерных про-
грамм для реконфигурируемых вычислительных систем на основе распараллеливания по
итерациям для решения графовых NP-полных задач. Рассмотрено, что использовать би-
товый способ представления множеств (как в методе распараллеливания по слоям) для
метода распараллеливания по итерациям не является эффективным. Новый метод отли-
чается организацией вычислений, а именно – обработкой неупорядоченных множеств,
доступ к элементам которых осуществляется не по адресам (как в массивах), а по значе-
ниям (именам вершин и именам дуг графа). Показано, что новый метод на основе распа-
раллеливания по итерациям, несмотря на более низкую удельную производительность, свя-
занную с тем, что вычислительным подструктурам из-за символьного представления
множеств необходимо обработать большее число промежуточных данных, обеспечивает
практически линейный рост реальной производительности РВС при значительно большем
количестве вычислительного ресурса по сравнению с методом распараллеливания по слоям. -
РЕШЕНИЕ ОБРАТНОЙ ЗАДАЧИ СПЕКТРАЛЬНОЙ ТЕОРИИ ГРАФОВ ПРИ ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
А.Н. Целых , В. С. Васильев , Л.А. Целых , С.А. Барковский163-1732025-10-01Аннотация ▼Статья посвящена решению основной обратной задачи спектральной теории графов – определении основных параметров графа по спектру его собственных значений. В данной работе нас интересуют когнитивные причинные графовые модели сложных систем, динамика переменных которых недоступна. Мы рассматриваем нестохастические графовые модели, которые имеют нечисловые значения узлов и связей, а также плохо определенные системные факторы. При отсутствии исходных данных решение обратной задачи для направленного взвешенного знакового графа становится значительно более сложным. Когда графы имеют одинаковую топологию, но разные веса на дугах, то их спектры образуют в пространстве решений некоторое множество нечетких коллинеарных векторов. Линии этих векторов расходятся в пространстве векторов из-за их направленности к разным вершинам. В данной работе предлагается использовать алгоритм, позволяющий точно восстановить веса когнитивного графа, когда известен условный главный собственный вектор и топологический шаблон матрицы смежности. Данный алгоритм учитывает важную особенность матрицы смежности графа – направление главного собственного вектора к целевой вершине, что позволяет найти правильное решение из набора нечетких коллинеарных векторов в пространстве решений. Для того, чтобы добиться полного восстановления весов графа с приемлемой точностью предлагается объединить спектр графа и модель эффективную управления с задачей комбинаторной оптимизации. Восстанавливая веса матрицы смежности с использованием нашего подхода, мы сравниваем их с заданным графом. При сравнении учитываются такие параметры графа, как спектр графа, коэффициенты подобия для реконструированной матрицы, векторы отклика и управления
-
ПРИМЕНЕНИЕ ЗАПРЕЩЕННЫХ ФИГУР В ЗАДАЧЕ РАСКРАСКИ ГРАФА ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ
В. И. Потапов2021-01-19Аннотация ▼Проектирование конструкции печатных плат в виде плоских структур без перемы-
чек является одной из самых сложных задач на этапе схемотехнического проектирования.
Задача в такой постановке особенно актуальна микросборок и для электронных модулей
контрольно-проверочной, бортовой аппаратуры, выполненных по технологии поверхност-
ного монтажа, где, например, по причине металлического теплоотвода или керамического
основания, структура соединений возможна только в одном слое. В работе рассматрива-
ется задача проектирования печатных плат в виде синтеза плоских структур электрон-
ных схем. Целью является расположение соединений на печатной плате без пересечений,
что облегчает условия проведения трасс любому трассировщику современных программ
проектировании. Для её решения предложено большое число различных алгоритмов, основ-
ным недостатком которых является заложенный в них принцип последовательного и
фрагментарного просмотра коммутационного пространства. Сложность алгоритмов
синтеза подобных структур обусловлена также необходимостью учета большого числа
различных требований, связанных со спецификой их изготовления и особенностями разра-
батываемого конструктивно-технологического решения. В настоящей работе предлага-
ется выполнить проектирование печатной платы с высокой эффективностью трассиров-
ки соединений за счет решения задачи расслоения исходного графа-схемы и построения
плоского графа-схемы как на стороне установки ЭРЭ, так и на обратной стороне платы -
стороне пайки, исключая запрещенные фигуры по теореме Потрягина-Куратовского.
Критерием является минимизация переходных отверстий, а также минимизация провод-
ников (ребер) на одной стороне печатной платы. Задача расслоения представляет собой
задачу раскраски графа в два цвета с использованием принципов характеризационного
управления, решение которой базируется на теореме Кенига, определяющей запрещенную
фигуру в виде циклов нечетной длины. Для проектирования печатных плат разработаны
алгоритм и методика построения планарных графов и расслоения графа на две стороны
печатной платы с уменьшением количества неразведенных ребер. Точное решение прини-
мает вид полиномиальной зависимости не выше 5-й степени, позволяет получить резуль-
тат за приемлемое время и повысить эффективность трассировки на 5–15 %. -
ИССЛЕДОВАНИЕ СТРУКТУРНЫХ ХАРАКТЕРИСТИК РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ГРАФОВ С МНОЖЕСТВЕННЫМИ РАЗНОТИПНЫМИ СВЯЗЯМИ
Е.Р. Мунтян , Э.В. Мельник2021-08-11Аннотация ▼В статье рассмотрены вопросы построения отказоустойчивых вычислительных
систем, в части структуры и резервирования. При проектировании распределенных вычис-
лительных систем (ВС) возникает необходимость учета большого количества факторов,
влияющих на производительность, надежность и отказоустойчивость. Для распределен-
ных ВС к таким факторам относятся, в том числе структурные характеристики. В ра-
боте представлены графики зависимости вероятности безотказной работы ПУ распреде-
ленной вычислительной системы от характеристик ее структуры. Применение перспек-
тивных способов резервирования, таких как резервирование производительности, сущест-
венно повышает сложность задачи проектирования структуры. При резервировании про-
изводительности взамен ввода в систему специальных резервных узлов предполагается
использование избыточных вычислительных ресурсов внутри задействованных процессор-
ных узлов (ПУ). В случае отказа узла его задачи перераспределяются на свободный резерв
работоспособных узлов. Для реализации такого способа резервирования системы требует-
ся организация многопрограммного режима работы, когда на каждом узле могут одно-
временно выполняться несколько задач. Необходимость обеспечения мультипрограммного
режима работы приводит к увеличению количества конфигураций системы, подлежащих
анализу на этапе проектирования и в случае реконфигурации при отказе. Для снижения
трудоемкости анализа отдельно взятой конфигурации предложен подход на основе графов
с множественными и разнотипными связями. Использование моделей на основе таких гра-
фов позволяет представить структуру вычислительной системы с учетом мультипро-
граммной обработки информации и при этом существенно сократить время вычисления
базовых характеристик за счет применения связей в виде вектора, позволяющих объеди-
нить несколько разнотипных связей. -
ИСПОЛЬЗОВАНИЕ ИНВАРИАНТОВ НЕЧЕТКОГО ГРАФА ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ СЛОЖНЫХ ТРАНСПОРТНЫХ СИСТЕМ
И.Н. Розенберг , И.А. Дубчак136-1452025-12-30Аннотация ▼Рассматриваются вопросы оценки устойчивости транспортно-логистических систем (ТЛС) в условиях неопределенности, которые играют ключевую роль в обеспечении эффективного функционирования цепей поставок. Устойчивость систем анализируется в контексте их способности адаптироваться к внешним и внутренним воздействиям, таким как экономические колебания, изменение спроса, стихийные бедствия и технологические сбои. В данной статье предлагается использовать инварианты нечетких множеств, а именно нечеткое доминирующее множество, для оценки и анализа устойчивости транспортно-логистических систем в условиях неопределенности. Показано, что нечеткое доминирующее множество позволяет решать задачу размещения распределительных узлов в транспортно-логистической системе. Приведены примеры нахождения нечетких доминирующих множеств для нечетких и нечетких темпоральных графов как моделей транспортно-логистической системы. Нечеткие темпоральные графы также позволяют проводить более адекватное моделирование и анализ систем в случаях, когда параметр времени является одним из важных факторов. Практическая значимость исследования заключается в возможности проектирования более надежных и адаптивных ТЛС, способных эффективно функционировать в условиях неопределенности. Результаты могут быть использованы для оптимизации логистических процессов, снижения затрат и повышения устойчивости цепочек поставок. Полученные выводы также открывают перспективы для дальнейших исследований в области интеграции методов искусственного интеллекта и анализа больших данных в управлении транспортными системами. Дальнейшие исследования предлагается направить на интеграцию методов оптимизации потоков с учетом временных факторов и разработку цифровых двойников ТЛС
-
ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗБИЕНИЯ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Б.К. Лебедев, О. Б. Лебедев, Е. О. Лебедева2020-07-20Аннотация ▼Работа алгоритма разбиения базируется на использовании коллективной эволюцион-
ной памяти, под которой подразумевается информация, отражающая историю поиска
решения и хранится независимо от индивидуумов. Алгоритм, связанный с эволюционной
памятью, стремится к запоминанию и многократному использованию способов достиже-
ния лучших результатов. Коллективная эволюционная память алгоритма разбиения со-
стоит из некоторого количества статистических индикаторов, отображающих для ка-
ждого выполненного варианта число θ его вхождений в состав лучших решений на выпол-
ненных генерациях алгоритма и число, δ определяющее насколько полезна реализованная
альтернатива при формировании результатов на прошлых генерациях алгоритма. Коллек-
тив не имеет централизованного управления, и в связи с этим используется непрямой об-
мен информацией. Непрямой обмен состоит в выполнении неких действий, в различное
время, при которых происходит изменение некоторых частей эволюционной памяти одним
агентом. В дальнейшем происходит использование этой измененной информации другими
агентами, в этих частях. Вначале на каждой итерации конструктивным алгоритмом
формируется nk решений Qk,. Каждое решение Qk является отображением Fk=V→X, пред-
ставляется в виде двудольного подграфа Dk и формируется путем последовательного на-
значения элементов в узлы. Формирование каждого решения Qk выполняется множеством
агентов A, посредством вероятностного выбора каждым агентом ai узла vj. Процесс на-
значения элемента в узел включает две стадии. На первой стадии выбирается агент ai, а
на второй стадии − узел vj. При этом должно выполняться ограничение: каждому агенту
множества A соответствует один единственный узел множества V. Рассчитывается
оценка ξk решения Qk и оценка полезности δk множества альтернатив, реализованных
агентами в решении Qk. На втором этапе агенты увеличивают в интегральной россыпи
альтернатив R* интегральную полезность множества альтернатив на величину δk..
На третьем этапе осуществляется снижение оценок полезности δk интегральной россыпи
альтернатив на величину μ. В работе используется циклический метод формирования ре-
шений. В этом случае наращивание оценок интегральной полезности δk множества пози-
ций P выполняется после полного формирования множества решений Q на итерации l.
Экспериментальные исследования проводились на основе сформированных тестовых при-
меров с полученным ранее оптимальным решением. Полученные результаты сравнивались
с результатами полученными другими известными алгоритмами разбиения схем на части.
Для сравнения был сформирован набор стандартных бенчмарок. Проанализировав получен-
ные результаты, можно сделать вывод, что предложенный метод позволяет получать на
4–5 % решения качественнее, чем его аналоги. -
ОПРЕДЕЛЕНИЕ ХАРАКТЕРА ИЗМЕНЕНИЙ ПАРАМЕТРА НА ОСНОВЕ АНАЛИЗА ДИНАМИКИ ФОРМЫ СОВОКУПНОСТИ ЕГО ЗНАЧЕНИЙ В РЕАЛЬНОМ ВРЕМЕНИ
С. И. Клевцов2020-10-11Аннотация ▼Одной из важных задач мониторинга технических объектов является предотвраще-
ние аварийных ситуаций. Эта задача связана с выполнением достоверной и адекватной
оценки работоспособности объекта. Оценка работоспособности объекта основывается
на анализе поведения его контролируемых параметров в реальном времени. Тогда она бу-
дет актуальной. В работе предложен метод определения характера изменения парамет-
ра, основанный на анализе последовательности специальных пространственных графиче-
ских форм, называемых графиками Пуанкаре. Выбранный параметр должен в значитель-
ной степени определять работоспособность контролируемого объекта. Графики форми-
руются на основе временного ряда контролируемого параметра. Выбирается временноеокно, которое вырезает заданное количество значений параметра. График строится для
каждого шага перемещения окна по временному ряду параметра. Анализируется транс-
формация формы заданного типа, которая накладывается на совокупность значений па-
раметра, представленных в виде графика. По изменению параметров формы делается
вывод о характере изменений параметра. В работе показана возможность использования
графиков Пуанкаре для отслеживания изменения состояния технического объекта в ре-
альном времени. При этом учитываются особенности съема информации с датчиков.
Оценка реализуется с помощью микропроцессорного модуля, входящего в систему монито-
ринга. Также предложена структура обобщенной однофакторной модели, которая от-
слеживает изменение состояния объекта на основе анализа графиков Пуанкаре. Приведен
вариант оценки состояния объекта с помощью сравнения характеристик графика с кри-
териями. Критерии получены после предварительной обработки большого массива данных
о поведении контролируемого параметра. Каждому значению критерия поставлена в со-
ответствие экспертная оценка, определяющая состояние объекта. Оценка позволяет оп-
ределить степень работоспособности объекта и реализовать необходимые действия в
случае опасности. -
СЕМАНТИКО-СТАТИСТИЧЕСКИЙ АЛГОРИТМ ОПРЕДЕЛЕНИЯ КАТЕГОРИЙ АСПЕКТОВ В ЗАДАЧАХ СЕНТИМЕНТ-АНАЛИЗА
А.О. Корней, Е.Н. Крючкова2021-02-13Аннотация ▼В современном мире одним из ключевых каналов коммуникации является Интернет.
Через электронные площадки осуществляется торговля, продвижение услуг. Социальные
сети и мессенджеры становятся важнейшим каналом общения и мощным инструментом
воздействия на общественное мнение. Весомую долю во всем публикуемом контенте зани-
мают тексты, написанные на естественном языке. Поэтому проблемы обработки и по-
нимания естественных языков (ЕЯ) на сегодняшний день являются одними из ключевых.
Под влиянием коммерческих интересов активно развивается область автоматического
анализа тональности на основе аспектов. Данная задача существенно зависит от кон-
кретных предметных областей, и поэтому вопрос быстрой и эффективной адаптации
существующих моделей к новым доменам стоит весьма остро. В работе предлагается
гибридный метод аспектно-ориентированного анализа тональности текстов, основанный
на данных, извлеченных как из общеупотребительных словарей, так и из домен-
ориентированных текстов. Предложен метод построения конденсированного семантиче-
ского графа на основе неструктурированных домен-зависимых текстов. Введены числен-
ные метрики, позволяющие оценивать значимость отдельных терминов в пределе всего
домена. Предложен алгоритм категоризации текстов, основанный на выделении семанти-
ческих кластеров в пределах конденсированного домен-специфического графа. Предложен
метод оценки тональности домен-ориентированных текстов, основанный на статисти-
ческих данных, включая совместное использования тонального словаря и сконденсирован-
ного домен-специализированного графа. Приведены результаты экспериментов, позволяю-
щие оценить качество работы алгоритмов. -
ПРЕОБРАЗОВАНИЕ НЕКОТОРЫХ ВИДОВ ПОСЛЕДОВАТЕЛЬНЫХ ИНФОРМАЦИОННЫХ ГРАФОВ В ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНУЮ ФОРМУ
Д. В. Михайлов2021-02-25Аннотация ▼Многие задачи цифровой обработки сигналов могут быть представлены в виде информа-
ционных графов. Реконфигурируемые вычислительные системы, построенные на основе ПЛИС,
могут иметь структуру, непосредственно соответствующую информационному графу ре-
шаемой задачи. Построение графа задачи и последующее создание вычислительной структуры
может занимать значительное время при выполнении их вручную. В связи с этим возникает
необходимость создания алгоритмов преобразования информационных графов, которые могут
выполняться автоматически. В статье предложены алгоритмы преобразования однородных
графов, содержащих ассоциативные операции, и смешанных графов, содержащих два типа
операций, один из которых является дистрибутивным по отношению к другому. Преобразова-
ния графов первого типа (состоящих из операций одного типа) сводятся к переходу от после-
довательной формы графа к пирамидальной для ускорения выполнения всех операций графа.
В случае если имеющегося количества оборудования недостаточно для реализации всех опера-
ций графа, применяется преобразование, разбивающее исходный граф на изоморфные подгра-
фы. Размер подграфа зависит от имеющегося вычислительного ресурса. В этом случае вычис-
лительная структура будет соответствовать такому подграфу. Преобразования графов вто-
рого типа (состоящих из операций двух типов, одни из которых являются дистрибутивными
по отношению к другим) сводятся к разделению графа на подграфы, содержащие операции
одного типа, соединённые особым образом. После этого эти подграфы могут быть преобра-
зованы в пирамидальную форму для ускорения выполнения всех операций графа. При этом
количество вершин с дистрибутивными операциями может значительно возрасти, в связи с
чем может потребоваться сокращение их числа. Отсюда следует, что при преобразовании
графов второго типа не обходимо выбирать конкретную форму, к которой будет приведён
граф, исходя из соотношения его размера и имеющегося вычислительного ресурса. Таким
образом, предложенные алгоритмы преобразования информационных графов различных типов
могут быть эффективно использованы при разработке вычислительных структур, основанных
на ПЛИС. -
КОМПЛЕКС СРЕДСТВ ТРАНСЛЯЦИИ ПРОГРАММ НА ЯЗЫКЕ C В ПРОГРАММЫ НА ЯЗЫКЕ ПОТОКА ДАННЫХ COLAMO
А. И. Дордопуло, A.A. Гуленок, А.В. Бовкун, И.И. Левин, В. А. Гудков, С.А. Дудко2021-02-25Аннотация ▼Рассматриваются программные средства трансляции последовательных программ
на языке C в масштабируемые параллельно-конвейерные программы на языке программи-
рования реконфигурируемых вычислительных систем COLAMO. В отличие от существую-
щих средств высокоуровневого синтеза, результатом трансляции является не IP-ядро
фрагмента задачи, а комплексное решение задачи для многокристальных реконфигурируе-
мых вычислительных систем с автоматической синхронизацией информационных и управ-
ляющих сигналов. Рассмотрены основные этапы трансляции последовательной программы
на языке C: преобразование в информационный граф, анализ информационных зависимо-
стей и выделение функциональных подграфов, преобразование в масштабируемую ресурсо-
независимую параллельно-конвейерную форму и масштабирование программы на языке
COLAMO для заданной многокристальной реконфигурируемой вычислительной системы.
Масштабирование программы осуществляется с помощью методов редукции производи-
тельности абсолютно-параллельной формы задачи – информационного графа, который
адаптируется под архитектуру реконфигурируемой вычислительной системы. Разрабо-
тан ряд правил, позволяющих существенно сократить число шагов преобразований при
масштабировании задачи и обеспечить плотный поток обработки данных в функциональ-
ных подграфах задачи. Созданный комплекс средств трансляции программ на языке C в
конфигурационные файлы ПЛИС позволяет существенно сократить время синтеза вычис-
лительной структуры задачи для многокристальных РВС и обеспечить сокращение общего
времени решения задачи. -
ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ
В.В. Курейчик , Вл. Вл. Курейчик2021-07-18Аннотация ▼Работа посвящена созданию программной подсистемы для решения NP- трудных и
NP-сложных комбинаторно-логических задач на графах. В статье приведено описание
комбинаторно-логических задач на графах. Для эффективного их решения предлагаются
новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал-
лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек-
туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на
них различных алгоритмов эволюционного моделирования и биоинспирированного поиска.
Это позволяет получать наборы квазиоптимальных решений выполнять параллельную
обработку и частично устранять проблему преждевременной сходимости. В статье при-
ведено подробное описание разработанной программной подсистемы и ее модулей. В каче-
стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо-
танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких
как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо-
даря модульной структуре в подсистеме имеется возможность конструировать более 50
различных вариантов комбинаций поиска. Это позволяет использовать все достоинства
методов биоинспирированной оптимизации для эффективного решения NP-сложных ком-
бинаторно-логических задач на графах. Для подтверждения эффективности разработан-
ной программной подсистемы был проведен вычислительный эксперимент на тестовых
примерах. Проведенные серии тестов и экспериментов показали преимущество использо-
вания программного продукта для решения комбинаторно-логических задач на графах
большой размерности, по сравнению с известными алгоритмами, что говорит о перспек-
тивности применения такого подхода. Временная сложность разработанных алгоритмов
в лучшем случае O(nlogn), в худшем случае – О(n3). -
ПРОБЛЕМА ВЫБОРА ДЕМПИНГ-ФАКТОРА В МОДЕЛИ ЭФФЕКТИВНЫХ УПРАВЛЕНИЙ ДЛЯ НАПРАВЛЕННЫХ ВЗВЕШЕННЫХ ЗНАКОВЫХ ГРАФОВ
А.Н. Целых, В. С. Васильев, Л. А. Целых2020-07-20Аннотация ▼Рассматривается проблема выбора демпинг-фактора в модели эффективных управ-
лений на основе максимизации передачи влияний для нечетких когнитивных моделей, пред-
ставленных направленными взвешенными знаковыми графами. Для передачи влияния ис-
пользуется модель управления, реализующая развитие системы. Алгоритм эффективных
управлений основан на решении оптимизационной задачи отыскания вектора внешних воз-
действий, максимизирующего накопленный рост приращений показателей вершин. Опти-
мальным управляющим воздействием признаётся управление, доставляющее максимум
отношению квадрата нормы вектора отклика системы к квадрату нормы вектора управ-
ления. Демпинг-фактор такой модели управляет сравнительным масштабом прямого и
косвенного влияния всех внутрифакторных связей системы в целом. Целью исследования
является определение таких областей допустимых значений для получаемых решений, при
которых (i) соблюдается условие непротиворечивости результата; (ii) изменение рангов
вершин носит медленный характер. Под непротиворечивостью результата мы понимаем
удовлетворение правилами работы системы в целом. Эти правила могут выражаться в
наложении ограничений на статус вершин, на знак воздействий и откликов. В работе ус-
танавливается значение демпинг-фактора, называемое резонансным, при котором проис-
ходит резонансный всплеск значения целевой функции задачи максимизации влияния, когдасонаправленность между резонансным откликом и вызывающим его воздействием отсут-
ствует. Выбор демпинг-фактора влияет на значение целевой функции задачи максимиза-
ции влияния и на вектор эффективного управления, на котором это решение достигается.
Значение резонансного демпинг-фактора можно интерпретировать как предел возможной
управляемости системы, т.е. предел потенциальной возможности воздействия на систе-
му без причинения ей вреда. Оценка предложенного решения производится по степени ус-
тойчивости ранга узлов модели в зависимости от влияния изменений демпинг-фактора,
алгоритмизации определения области его допустимых значений и форме проявления резо-
нанса в границах значений демпинг-фактора. -
АЛГОРИТМ РЕКОНСТРУКЦИИ МАТРИЦЫ СМЕЖНОСТИ ПРИЧИННЫХ ГРАФОВЫХ МОДЕЛЕЙ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
А. Н. Целых, В.С. Васильев , Л. А. Целых2021-11-14Аннотация ▼Рассматривается проблема моделирования сложных систем при отсутствии на-
блюдаемых переменных. Для решения этой проблемы предлагается использовать причин-
ные графовые модели. Класс причинных моделей, который мы здесь рассматриваем, опре-
деляется как нестохастические причинные модели с ненаблюдаемыми переменными. Эти
модели представляются в виде направленного графа, создаваемого на основе человеческих
ментальных репрезентациях. При этом на дугах причинность выражена в виде некоторых
меток, которые имеют знак, определяющий направление изменений состояния системы.
Рассматриваемые причинные модели включают неоднородные, сложные и качественныетипы переменных, иллюстрирующие нечисловую природу узлов и связей, а, следовательно,
отсутствие и невозможность получения временных рядов данных. В условиях отсутствия
наблюдаемых переменных и невозможности проведения экспериментов, проблема рекон-
струкции матрицы смежности графовой причинной модели становится гораздо более
сложной. Требуется получить модель с определенным спектральным разложением, которое
реализует основную функцию моделируемой системы. На основе этой концепции предлагает-
ся новый метод реконструкции матрицы смежности, реализованный на соответствующей
матрице причинного распространения или передаточной матрице. Идея состоит в том,
чтобы использовать комбинаторную оптимизацию на основе спектральной теории графов
для генерации данных из качественной нестохастической причинной модели и реконструиро-
вать матрицу смежности, используя эти данные. В этом случае собственные векторы
идентифицируются как ключевые цели процесса реконструкции матрицы, что постулирует
фундаментальный подход, основанный на спектральных свойствах графа. Результаты вы-
числительных экспериментов решения задачи реконструкции матрицы смежности для при-
чинных графовых моделей в отсутствии наблюдаемых переменных с использованием разра-
ботанного алгоритма показали, что алгоритм эффективно реконструирует матрицы в за-
данных параметрах с допустимыми показателями схожести. Доказана сходимость при-
ближения к решению алгоритма реконструкции матриц не медленнее, чем со скоростью
геометрической прогрессии. С технической точки зрения, преимуществом алгоритма явля-
ется реализация инструмента автоматической настройки параметра регуляризации, при-
годного для пользователей без предварительных математических знаний. -
ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ
Д. В. Михайлов177-1882021-10-05Аннотация ▼Множество вычислительных задач может быть представлено в виде последова-тельного информационного графа. В общем случае такой информационный граф не может быть приведён к параллельному виду с целью ускорения выполнения его операций. Но в слу-чае если вершины этого графа обладают свойствами ассоциативности, дистрибутивно-сти и т.д., такой граф можно преобразовать в параллельно-конвейерную форму. Эти пре-образования могут быть произведены не только над графами, содержащими элементар-ные операции – сложение, умножение, логическое И и т.д. – но и над графами, содержа-щими макрооперации. Одним из примеров таких графов является информационный граф решения СЛАУ методом прогонки (методом Томаса). В статье рассмотрено решение для трёхдиагональных СЛАУ. Информационный граф метода прогонки состоит из двух час-тей: прямого хода, в котором выполняется переход от трёхдиагональной формы к двух-диагональной, и обратного хода, в котором непосредственно вычисляются значения неиз-вестных. Несмотря на то, что операции, составляющие базовую макрооперацию метода прогонки, обладают свойством ассоциативности, простое преобразование графа к пира-мидальному виду не даст необходимого результата. Необходимо преобразовать базовые макрооперации особым образом и изменить то, какие данные на них поступают. После этого возможно будет привести граф к пирамидальному виду. Для обратного хода приме-няется аналогичное преобразование графа и составляющих его базовых подграфов. По-скольку для того, чтобы начать вычисления в обратном ходе, нам необходимо полное за-вершение вычислений прямого хода, следует перейти от двух специализированных типов вычислительных блоков к одному универсальному, и построить на его основе универсаль-ную вычислительную структуру.
-
МЕТОД И АЛГОРИТМ ПЛАНИРОВАНИЯ ОПЕРАЦИЙ НА ОСНОВЕ МОДЕЛИ НЕЧЕТКОГО КОНЕЧНОГО АВТОМАТА
М. В. Князева , А. В. Боженюк , И. Н. Розенберг2022-05-26Аннотация ▼Рассматривается задача планирования, как важная оптимизационная задача, стоя-
щая перед многими транспортными и роботизированными приложениями. Для решения
задач планирования подходы основаны на методах оптимизации, методах выборки и дис-
кретизации (sampling-based methods), и обычно такого рода задачи являются NP-
трудными и многомерными. В данной статье разработан метод планирования и состав-
ления расписаний на основе нечеткой модели конечного автомата. Дано нечеткое графо-
вое представление задачи составления расписания и планирования операций. В работе при-
ведены два подхода к формальной постановке задачи планирования с ограниченными ресур-
сами и временными переменными: ориентированный на состояния (с переходами между
состояниями), ориентированный на темпоральное упорядочивание (на временной шкале).
Темпоральное моделирование для задач планирования подразумевает качественный подход
к управлению распределением операций или топологическим упорядочением, а также коли-
чественный подход к обработке неточных длительностей, взаимосвязей между операция-
ми по многочисленным параметрам. Введены понятия нечетких интервалов и нечетких
отношений для планирования операций на графе. Разработан алгоритм планирования, ос-
нованный на основе теории автоматов и темпоральном моделировании в условиях неопре-
деленности. Используя формализм теории автоматов, проблема планирования и нахожде-
ния оптимальных путей решается путем последовательного изменения и анализа состоя-
ний планируемой системы с использованием различных операций, пока не будет найдено
решение. В работе обсуждается идея упорядоченного во времени частичного расписания,
связанного с каждым состоянием планируемой системы. Предложена модель конечного
автомата для системы планирования в условиях неопределенности. Разработан метод и
алгоритм планирования операций на основе недетерминированного конечного автомата и
схемы перечислений. Недетерминированные вычисления для задачи планирования пред-
ставляют собой дерево решения, корень которого соответствует началу процесса плани-
рования, а каждая точка ветвления в дереве соответствует точке вычисления, в которой
у машины есть несколько вариантов выбора. -
БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ
О.Б. Лебедев , А.А. Жиглатый2022-11-01Аннотация ▼Предлагается биоинспирированный метод решения набора инвариантных комбина-
торно-логических задач на графах: формирования паросочетания графа, выделения внут-
ренне-устойчивого множества вершин, выделения клики графа. Описывается модифициро-
ванная парадигма муравьиной колонии использующая, в отличие от канонического метода,
механизмы формирования решений на модели пространства поиска в виде звездного графа.
Задача формирования в графе внутренне-устойчивого множества вершин может быть
сформулирована, как задача разбиения. На начальном этапе на всех ребрах звездного графа
H откладывается одинаковое (небольшое) количество феромона ξ/m, где m=|E|. Процесс
поиска решений итерационный. Каждая итерация l включает три этапа. Агенты облада-
ют памятью. На каждом шаге t в памяти агента ak имеется количество феромона фj(t),
отложенного на каждом ребре графа H. На первом этапе каждый агент ak популяции
конструктивным алгоритмом находит решение Ur
0k, рассчитывает оценку решения
ξk(Ur
0k) и значение степени пригодности полученного агентом решения φk (количество фе-
ромона, соответствующее оценке). На втором этапе, после полного формирования всеми
агентами решений на текущей итерации, феромон ωj, накопленный в j-ой ячейке в буфер-
ном массиве КЭПб, добавляется в каждую j-ю ячейку основного массива Q2={qj|j=1,2,…,m}
коллективной эволюционной памяти КЭПo. На третьем этапе происходит общее испаре-
ние феромона на множестве ребер E звездного графа H. Временная сложность алгоритма,
полученная экспериментальным путем, совпадает с теоретическими исследованиями и для
рассмотренных тестовых задач составляет О(n2). -
ПОСТРОЕНИЕ ТРАЕКТОРИИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЕ ПРИ ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
А.Н. Целых , В. С. Васильев , Л.А. Целых , Е.С. Подоплелова224-2332025-07-24Аннотация ▼Построение оптимального управления при полном отсутствии данных о динамике системы является актуальной проблемой. В данной статье предлагается решение линейной квадратичной задачи (ЛК) с конечным горизонтом для инвариантной ко времени системы с матрицей динамики графа. В отличие от задачи регулирования, устойчивость и полная управляемость системы не предполагаются. Построение траектории управления контролируется направлением нарастания изменения состояния переменных за малое число шагов, которое определяется условным главным собственным вектором матрицы смежности графовой модели. Решение классического оптимального управления осуществляется в автономном режиме и требует полного знания динамики системы. В условиях отсутствия полного знания динамики системы решение задач оптимального управления системами с неопределенностью, в том числе дискретными линейными системами, вызывают значительный интерес в последние годы. Основным подходом, когда полная информация о системе недоступна, является дизайн оптимального управления, при котором первоначально определяются параметры системы, а затем решается алгебраическое уравнение в двойственном пространстве. Важным отличием от стандартной задачи дискретного управления является то, что модель управления была модифицирована для оценки изменений состояния переменных при управлениях, передаваемых через матрицу динамики. Предложенный алгоритм с использованием графовой матрицы реализует рекуррентные вычисления динамических и сопряженных уравнений, а также метод Пауэлла для решения системы линейных алгебраических уравнений (СЛАУ). Авторами введена новая интерпретация математической конструкции матрицы динамики системы в стандартной задаче дискретного управления на конечном интервале времени, которая может быть использована для проектирования любой управляемой динамической системы с ненаблюдаемыми параметрами.
-
О ВЫЧИСЛЕНИИ СРЕДНЕГО ВРЕМЕНИ ИНФИЦИРОВАНИЯ В РАМКАХ ДИСКРЕТНОЙ МАРКОВСКОЙ ЭПИДЕМИОЛОГИЧЕСКОЙ МОДЕЛИ В ОТСУТСТВИИ ЛЕЧЕНИЯ
А.А. Магазев , А. Ю. Никифорова53-632025-11-10Аннотация ▼Моделирование распространения вирусов является актуальной областью исследований. Существует множество «непрерывных» эпидемических моделей, основанных на использовании систем дифференциальных уравнений. Недостатком таких моделей является то, что они имеют погрешность при описании начальной стадии распространения вируса и не учитывают особенности связей между индивидуумами. «Дискретные» модели, в которых время и количество инфицированных и восприимчивых узлов являются дискретными величинами, дают более точную картину эпидемического процесса. В этой работе мы изучаем некоторую дискретную марковскую модель в случае, когда лечение отсутствует. Это важный случай, поскольку его можно рассматривать либо как приближение к начальной фазе эпидемии, либо как модель эпидемий вирусов, которые трудно поддаются лечению. В первом разделе мы подробно описываем свойства исследуемой марковской модели. Во втором разделе, используя марковский подход, мы определяем среднее время заражения, то есть количество временных шагов, затраченных на заражение всех особей в популяции. Однако расчет среднего времени заражения в популяциях с большим количеством особей (или в сетях с большим количеством узлов) является сложной вычислительной задачей, поэтому в третьем разделе мы предлагаем соответствующую приближенную формулу для этого параметра при условии, что связность сети и вероятность распространения вируса малы. В четвертом разделе мы используем метод имитационного моделирования для расчета среднего времени заражения, а затем сравниваем результаты, полученные различными методами. Для проведения вычислительного эксперимента нами было разработано консольное приложение, написанное на языке программирования C++. Анализ значений среднего времени инфицирования, определенных тремя методами: методом точного вычисления фундаментальной матрицы M, вычислением с применением приближенной формулы и методом имитационного моделирования, показал, что методы хорошо согласуются между собой при заданных нами условиях. Полученная приближенная формула для среднего времени заражения является более простым в использовании вариантом расчета данного параметра.
-
РАСПОЗНАВАНИЕ И АДАПТИВНАЯ ГЕНЕРАЦИЯ ПСЕВДОСЛУЧАЙНЫХ ТЕСТОВ ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦИФРОВЫХ УСТРОЙСТВ
Ю.Е. Зинченко , Т. А. Зинченко189-2042025-11-10Аннотация ▼Целью статьи является повышение эффективности псевдослучайного тестирования цифровых устройств по сравнению с общепринятым традиционным подходом. Для достижения поставленной цели в работе решаются следующие основные задачи: анализ эффективности традиционных подходов тестирования; разработка нового подхода тестирования на базе распознавания и адаптивного псевдослучайного тестирования цифровых устройств; разработка системы тестирования на базе разработанных подходов и экспериментальные исследования на ее основе.
В качестве объекта диагностики в данной работе выступают последовательностные (с элементами памяти) цифровые устройства, выполненные в виде типовых элементов замены на микросхемах средней и малой степени интеграции. В качестве моделей неисправностей при синтезе и анализе тестов используются константные неисправности. Предметом исследований выступают последовательностные цифровые устройства как объекты диагностики и подходы их псевдослучайного тестирования. В работе представляется подход распознавания и тестирования последовательностных цифровых устройств, который базируется на сочетании традиционного псевдослучайного тестирования на первом этапе с «распознаванием объекта диагностики» и построении «альтернативного графа объекта» на втором этапе с последующим «блужданием» по этому графу с целью повышения эффективности тестирования. На базе предложенного подхода разработана система тестирования цифровых устройств AGAT. Тестирование в системе может выполняться как для одного, так и группы объектов диагностики на одном либо группе персональных компьютеров в локальной компьютерной сети, при этом учитывается «многопоточность» на основе многоядерных процессоров персональных компьютеров сети. Выполняются экспериментальные исследования предложенного подхода и системы AGAT на двух типах объектов диагностики: международном наборе экспериментальных схем ISCAS’89 и наборе типовых элементов замены специализированной радиотехнической системы -
ИССЛЕДОВАНИЕ ПРИМЕНИМОСТИ МУЛЬТИМОДЕЛЬНЫХ ХРАНИЛИЩ ДАННЫХ В ИГРОВОЙ ИНДУСТРИИ
А.А. Коблов , О.М. Ромакина , А.С. Клемешева , А. З. Арсеньева105-1212025-12-30Аннотация ▼Проводится исследование целесообразности и эффективности применения мультимодельных баз данных для хранения и обработки данных в игровой индустрии. Современные игровые проекты характеризуются высокой сложностью и разнородностью данных: от строго структурированной информации об игроках, предметах и квестах до слабоструктурированных и сильносвязанных данных, таких как системы рецептов, диалоговые деревья, отношения между кланами и внутриигровые энциклопедии. Существующие подходы, основанные на реляционных или одномодельных NoSQL-хранилищах, часто не обеспечивают необходимой гибкости, производительности и удобства разработки для таких комплексных сценариев. Целью исследования является проектирование и сравнительный анализ производительности мультимодельного решения в контексте типовых игровых механик. Авторами разработана структура мультимодельного хранилища на базе СУБД ArangoDB, которая интегрирует документную, графовую и ключ-значение модели данных. Архитектура решения охватывает ключевые компоненты RPG-игр: управление игроками и инвентарём, систему квестов, диалогов, рецептов крафта, таблиц добычи, клановых взаимоотношений, а также полнотекстовый поиск по внутриигровой энциклопедии с использованием ArangoSearch. Экспериментальная часть включает подробное сравнение производительности разработанного мультимодельного хранилища с реляционной СУБД PostgreSQL и документной MongoDB на реалистичных наборах данных и запросах. Результаты демонстрируют значительное преимущество мультимодельного подхода при выполнении операций, требующих обхода сложных связей: например, поиск враждебных игроков через граф клановых отношений в ArangoDB выполняется в среднем в 11 раз быстрее, чем аналогичный JOIN-запрос в PostgreSQL.
В то же время, для сценариев с частыми модификациями линейно организованных данных (например, обновление статуса квестов) мультимодельное хранилище показывает несколько более низкую производительность по сравнению с реляционной моделью, что однако является допустимым в контексте общей архитектуры игрового проекта. Исследование подтверждает, что мультимодельные СУБД, в частности ArangoDB, представляют собой перспективное решение для игровой индустрии, позволяя в рамках единой платформы эффективно комбинировать различные модели данных, упрощать разработку и достигать высокой производительности на сложносвязанных данных, что является критически важным для современных многопользовательских игр -
АЛГОРИТМ ЭФФЕКТИВНЫХ УПРАВЛЕНИЙ В НЕСТОХАСТИЧЕСКИХ ПРИЧИННЫХ МОДЕЛЯХ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ ДЛЯ СИСТЕМ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
А. Н. Целых , В. С. Васильев , Л.А. Целых2021-11-14Аннотация ▼Рассматривается проблема репликации процесса принятия человеком управленческих
решений в условиях неопределенности и неполноты исходных данных. Лицо, принимающее
решение, опирается на свою систему взглядов, в которую входит общее видение системы,
относительно которой принимается решение. Система представлена в виде причинной
модели, созданной на основе ментальных представлений человека. Эти модели представ-
ляют собой направленные графы, на дугах которых причинность выражена в виде меток,
которые имеют знак, определяющий направление изменений состояния системы. Вершины
этого направленного графа представляют собой концепты высокого уровня абстракции.
Такой граф моелирует функционирование реальной системы. Таким образом, мы исследуем
проблему предсказания и управления действиями человека на основе нестохастических
причинных моделей в отсутствие наблюдаемых переменных для использования в системах
поддержки принятия решений и экспертных системах. Принятие решений рассматрива-
ется с точки зрения выбора объектов приложения управленческих воздействий – факторов
модели. В настоящем исследовании мы показываем, что применение предложенного алго-
ритма может облегчить принятие решений относительно выбора управляющих воздейст-
вий, которые поддерживают достижение тактических и стратегических целей лица, при-
нимающего решения. Следует отметить, что алгоритм реализует автоматизированный
подбор параметра регуляризации, что делает доступным разработку и применение предложенного алгоритма для пользователей, не имеющих достаточной математической под-
готовки. Сходимость последовательности множителя Лагранжа алгоритма эффектив-
ных управлений доказана. Доказана теорема о резонансе в нестохастической причинной
модели, представленной направленным графом, который определяется областью допус-
тимых значений коэффициента демпфирования в модели управления. Ожидается, что
внедрение этого инструмента в системы поддержки принятия решений повысит надеж-
ность решений, принимаемых в отношении работы системы в целом. Выбор управляющих
воздействий с использованием предложенного алгоритма имеет высокую эффективность
и производительность. Таким образом, результаты, представленные в исследовании, мо-
гут быть полезны для разработки приложений в интеллектуальных системах
1 - 21 из 21 результатов
