Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях




НазваниеАлгоритмы на топологических моделях Часть Алгоритмы на топологических моделях
Дата конвертации20.05.2013
Размер445 b.
ТипПрезентации


Алгоритмы на топологических моделях Часть 3.

  • Алгоритмы на топологических моделях

  • Представление графов в ЭВМ.

  • Матрицы смежности, изоморфности, достижимости и контрдостижимости, списочные формы.

  • Алгоритмы на графах.

  • Алгоритмы поиска путей, выделения контуров, поиск касающихся контуров.


Сортировка модели на топологическом ранге неопределенности

  • Предлагаемый алгоритм, схема которого представлена далее, предполагает приведение системы к форме, при которой образовывается ленточная матрица (рис.1). Приведение к матрице специального вида происходит на уровне топологических моделей, а не на вычислительной стадии расчета.

  • Алгоритм построен на основе традиционных обменных методов сортировок.



Сортировка модели на топологическом ранге неопределенности

  • В блоке 1 формируется булевская матрица ненулевых значений матрицы Якоби. Ненулевые элементы в матрице Якоби образуются за счет переменных, являющихся причиной и переменных, являющихся следствием каждого уравнения.

  • Очевидно что это можно записать в матричной форме следующим образом (рис.2). где I - единичная матица, C - матрица смежности, т - символ транспонирования, A - матрица наличия ненулевых значений матрицы Якоби. Учитывая, что большинство элементов системы составляют элементы типа SISO (один вход и один выход), то матрица будет сильно разряжена.



Сортировка модели на топологическом ранге неопределенности

  • Блок схема алгоритма сортировки на топологических моделях



Сортировка модели на топологическом ранге неопределенности

  • В блоке 2 создается копия матрицы A, на которой производятся перестановки (r).

  • В блоках 3, 5 организуют основной цикл по переменной flag, устанавливаемый в блоке 4 в нуль.

  • В матрице A, в блоке 5, определяется максимальное расстояние от ненулевого эле­мента до единичной диагонали lmax, и его номер i.



Сортировка модели на топологическом ранге неопределенности

  • Блоки 6,7,14 организуют цикл, где N размерность системы.

  • Блок 9 производит обмен в матице r i и j элементов. При этом, в матрице r, определяется макси­мальное расстояние до ненулевого элемента (блок 9).

  • Если оно больше определенного lmax, то присваивается новое значение lmax и запоминается при какой перестановке строк оно было достигнуто.

  • Переменная flag устанавливается в 1 (блоки 10,11,12).



Сортировка модели на топологическом ранге неопределенности

  • В блоке 13 возвращается исходное значение матрице A. После завершения цикла (6,7,14) проверяется значение переменной flag. Если flag == 1 (истина) то производятся перестановки в СНГГ, и в соответствующих ему матричных формах представлений C,A (блоки 15,16).

  • Если была произведена перестановка, то работа алгоритма возвращается на п. 4.

  • Если перестановка не была произведена, то получено минимальное значение lmax и алгоритм завершает свою работу.



Сортировка модели на топологическом ранге неопределенности

  • Пример, показанный на рис.1 и рис.2, иллюстрирует работу этого алгоритма.

  • Он позволяет использовать для решения линеаризованной системы ленточные методы, за счет чего можно достигнуть увеличения скорости расчета.

  • Данное преобразование позволяет получить вычислительный эффект, связанный с увеличением скорости расчетов, в 5 раз.



Сортировка модели на топологическом ранге неопределенности

  • Еще лучше достоинства этого подхода видны на примере системы представленной на рис. 1. Результаты сортировки показаны на далее. Эффект от применения предлагаемой сортировки составил 5,7 раз.



Сортировка модели на топологическом ранге неопределенности

  • Рис.1 и рис.2. Матрица смежности исходной и отсортированной модели.



Сортировка модели на топологическом ранге неопределенности

  • Предложенный алгоритм сортировки элементов приводит к получению матрицы Якоби известного вида, что позволяет использовать более быстрые алгоритмы решения систем нелинейных уравнений в процессе моделирования по неявной схеме.

  • Данный подход отличается от встречаемых в литературе тем, что учитываются все переменные, без исключения части из них, соответствующих слабым связям.



Сортировка модели на топологическом ранге неопределенности

  • Кроме того, приведение к матрице специального вида происходит на уровне топологических моделей, а не на вычислительной стадии расчета.

  • Эффект от применения такой сортировки, выполняемой однократно, получается на каждой итерации расчета для каждого момента времени



Нахождение сильных компонент графа

  • Нахождение сильных компонентов графа широко используется в процессе декомпозиции исходной модели на подсистемы, приведение множества уравнений к блочному виду. Возможно, привести пример – размещение компонентов принципиальной схемы на плате и многое другое.

  • Наиболее простым является следующий алгоритм:

  • Пусть дана некая система, строим матрицу пересечений представленной на рисунке далее.

  • В матрице пересечений W, w i j =1, если есть путь и из i-й вершины в j-ю, и обратно.



Нахождение сильных компонент графа



Нахождение сильных компонент графа

  • Многие задачи исследования систем могут быть решены на топологическом уровне.

  • Повышение эффективности всех стадий исследования системы возможно в первую очередь за счет учета топологических особенностей модели.



Похожие:

Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconАлгоритмы на топологических моделях Часть Алгоритмы на топологических моделях
Матрицы смежности, изоморфности, достижимости и контрдостижимости, списочные формы
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconДоклад на XII международной конференции «Информационные средства и технологии». Москва. Мэи. 2009
Полуквантовое кодирование в компьютерных многомерных комбинаторно-топологических моделях
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconТеория автоматов Машины Тьюринга
Иными словами, автоматы это ус­тройства, механически выполняющие алгоритмы. Можно строить различные мо­дели устройств, автоматически...
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconЦели и задачи образовательного комплекса Освоение теоретических основ комбинаторной топологии
...
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconПриближенные алгоритмы Комбинаторные алгоритмы

Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconАлгоритмы обработки информации алгоритмы обработки информации
В области скоростных информационно-телекоммуникационных систем и массово используемых мобильных коммуникаций сложилось
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconОбщие комбинаторные алгоритмы Общие комбинаторные алгоритмы
Кнут Д. Искусство программирования, т Сортировка и поиск. М.: Вильямс, 2011. 824 с
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconВведение в компьютерные методы метрико-топологических построений. Г. Г. Рябов (мгу)
Проведение оперативных преобразований среды.(кластеризация и разбиение для распараллеливания вычислений)
Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconРезонансы Фано в некоторых физических задачах и моделях План рассказа

Алгоритмы на топологических моделях Часть Алгоритмы на топологических моделях iconВ существующих моделях управления качеством в сфере производства продуктов и услуг в качестве обязательного направления деятельности является стратегия и стратегическое планирование
В существующих моделях управления качеством в сфере производства продуктов и услуг в качестве обязательного направления деятельности...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница