Разработка в среде C# программной реализации алгоритма выделения структурных особенностей | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 15 августа, печатный экземпляр отправим 2 сентября.

Опубликовать статью в журнале

Библиографическое описание:

Разработка в среде C# программной реализации алгоритма выделения структурных особенностей / Д. Л. Павлов, О. А. Кащеева, А. А. Иванова [и др.]. — Текст : непосредственный // Молодой ученый. — 2020. — № 27 (317). — С. 54-59. — URL: https://moluch.ru/archive/317/72298/ (дата обращения: 07.08.2020).



В работе описана реализация алгоритма выделения структурных особенностей матриц на языке C#. Представлена архитектура программы. Были проведены вычислительные эксперименты, результаты которых продемонстрированы в виде графиков.

Ключевые слова: разработка приложения, реализация алгоритма, структурные особенности, C#, архитектура приложения, анализ работы программы.

Структурный метод интегрирования систем m уравнений общего вида [1], [2].

предполагает, что существует преобразование, приводящее систему (1) к виду (2)-(4)

Группы (3), (4) структурно тождественны. Каждое уравнение одной из этих групп занимает определенное место в последовательности уравнений всей группы. Его правая часть не зависит от искомых функций, поведение которых описывается этим и всеми последующими уравнениями этой же группы. Группа уравнений (1) называется <<общей>> и включает в себя все уравнения, не имеющие структурных особенностей, описанных выше.

Алгоритм выделения структурных особенностей предполагает, что существует преобразование, приводящее случайную структурную матрицу к виду блочной нуль-диагональной матрицы. Задача состоит в том, чтобы найти такую перестановку π=(π(1), π(2), …, π(m)), при которой эффект от структурного подхода будет максимизирован.

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

Архитектура

Следующим шагом является разработка архитектуры программы. В работе активно используются списки (List), так как изначально неизвестен размер множеств и списки позволяют эффективно перемещаться по уровням дерева перебора. В качестве стандартов наименования была принята статья [3].

Логика работы алгоритма описана в исполняемом классе Program. Поля, начиная с omega, представлены в виде массива из двух элементов, каждый элемент массива отвечает за свое дерево перебора. Для удобства, каждый пункт алгоритма вынесен в отдельную функцию, названия которых совпадают с наименованием шага алгоритма. Основные поля и методы приведены в Листинге 0.

Листинг 0 . Класс Program

public class Program

{

public static int n; //размерность матрицы

public static List weights; //весовые коэффициенты

public static int [] transition; //перестановка

public static int taskType; //тип задачи

private static Matrix A; //исходная структурная матрица

private static int [,] B; //преобразованная структурная матрица

private static List > [] omega;//множествa Омега

private static OrderedMultitude recordMultitude;//рекордное можество

private static OrderedMultitude orderedMultitude;//упорядоченное множество

private static List > [] supportingMultitudeF;//первое вспомогательное множество

private static List > [] supportingMultitudeQ;//второе вспомогательное множество

private static int [] searchTreeLevel; //уровни дерева перебора

private static CentralElement centralElement;//центральный элемент

private static PossibleExtension knotElement;//узловой элемент

private static List > [] quantityOfPossibleExtension;//Множество возможных продолжений для первого множества

public static void Main(string [] args){…}

static void FirstStep(){…}

private static void SecondStep(){…}

private static void SecondStepA(){…}

private static void SecondStepA1(){…}

private static void SecondStepA1b(){…}

private static void SecondStepA1c(){…}

private static void SecondStepB(){…}

private static void ThirdStep(){…}//перебор для задачи 1 начинается с этого пункта

private static void FourthStep(){…}

private static void FourthStepA(){…}

private static void FourthStepA0(){…}

private static void FourthStepA1a(){…}

private static void FourthStepA1b(){…}

private static void FourthStepA1c(){…}

private static void FourthStepB(){…}

private static void FourthStepB1(){…}

private static void FourthStepB1a(){…}

private static void FourthStepB2(){…}

private static void FifthStep(){…}

private static void SixthStep(){…}

private static void OrderFirstMultitude(){…}

private static void OrderSecondMultitude(){…}

}

Сущностью, на основе которой строится работа с входными и выходными данными, является класс Matrix. В данном классе существуют методы, определяющие подготовительную работу алгоритма и выполняющие перестановку матрицы. Объекты данного класса необходимы для работы со структурными матрицами. Поля и методы класса Matrix приведены в листинге 1.

Листинг 1. Класс Matrix

public class Matrix

{

public static int rows; //число строк

public static int cols; //число столбцов

public static int [,] A; //структурная матрица

public Matrix(int row, int column){…}// конструктор

public int this [int row, int column]{…}//индексатор

public void Fill(){…}//Заполнение матрицы из файла

public int [,] Displacement(int [] pi) //применение перестановки, pi- вектор перестановки

private static List > FindE(){…}//горизонтальное структурное множество

private static List > FindH(){…}//вертикальное структурное множество

public List > FindOmegaZero(){…} //омега (1,0)

public static D FindD(List omega){…} //на вход омега, исходя из него строятся множества

public void Print(){…} //печать матрицы в консоль

}

Следуя принципу ООП — декомпозиции [4], были созданы структуры, отвечающие за основные элементы в работе алгоритма, такие как:

− множество D (D);

− элемент множества возможных продолжений (PossibleExtension);

− центральный элемент (CentralElement);

− весовой коэффициент (WeightCoefficient);

− упорядоченное множество (OrderedMultitude).

В каждой структуре существует конструктор. В большинстве структур представлены методы, связанные с поиском нужных элементов. Структуры и их методы представлены в Листинге 2.

Листинг 2 . Класс Matrix

public struct D

{

public List i;

public List j;

public List > index;

public D(List _i, List _j, List > _index){…}

}

public struct PossibleExtension

{

public int i;

public int j;

public int weight;

public List elements;

public PossibleExtension(int _i, int _j, int _weight, List _elements) {…}

public static List FindPossibleExtensions(List omega){…}

public static PossibleExtension FindKnot(List possibleExtensions){…}

}

public struct CentralElement

{

public int index;

public int weight;

public CentralElement(int _index, int _weight){…}

public static CentralElement FindCentral(List newOmega){…}

}

public struct WeightCoefficient

{

public int index;

public int weight;

public WeightCoefficient(int _index, int _weight){…}

}

public struct OrderedMultitude

{

public int weight;

public List elements;

public OrderedMultitude(int _weight, List _elements){…}

}

Анализ результатов работы.

После завершения тестирования алгоритма был проведен анализ работы программы на задаче 2. Анализ производился при помощи встроенных инструментов Visual Studio. Затраты ресурсов памяти проверялись при помощи Visual Studio Diagnostic Tools [5], а времени при помощи System.Diagnostics.Stopwatch [6].

В ходе анализа работы программы была выявлена зависимость ресурсов от размерности при фиксированной плотности и от плотности при фиксированной размерности.

Для тестирования зависимости параметров работы программы от плотности были случайным образом сгенерированы по 10 случайных структурных матриц размерности 10×10 с фиксированной плотностью и брались средние результаты затрат памяти и времени. Таким образом была получена данная зависимость.

Для демонстрации результатов была выбрана логарифмическая шкала, из-за удобства отображения в ней больших диапазонов значений величин. Для этого время (t) переведено в мс., а память (w) в Мб, затем данные значения прологарифмированы по основанию 2. Результаты представлены на рис. (1), (2).

Стоит отметить, что самой ресурсозатратной оказалась плотность 0,2. Это связано с тем, что при такой плотности граф является слабосвязным, работа алгоритма не завершается за один проход алгоритма и существует большое количество перспективных перестановок.

Зависимость времени от плотности

Рис. 1. Зависимость времени от плотности

Зависимость памяти от плотности

Рис. 2. Зависимость памяти от плотности

При тестировании зависимости параметров работы программы от размерности, при фиксированной плотности были сгенерированы матрицы размерностями от 10 до 25 включительно. Данный процесс был повторен для плотностей с 0,35 до 0,65 включительно с шагом 0,5. В связи с тем, что разброс результатов оказался невелик, результаты представлены без преобразований, время (t) в секундах и память (w) в Мб. Результаты работы продемонстрированы на рис. (3), (4).

Зависимость времени от размерности

Рис. 3. Зависимость времени от размерности

Зависимость памяти от размерности

Рис. 4. Зависимость памяти от размерности

Литература:

  1. Олемской И. В. Явный метод типа Рунге — Кутты пятого порядка // ЖВТ. 2005. № 2.
  2. Олемской И. В. Модификация алгоритма выделения структурных особенностей // Вестник СПбГУ. Серия 10. Прикладная математика. Информатика. Процессы управления. 2006. № 2.
  3. C#: требования и рекомендации по написанию кода. https://habr\\.com/ru/post/26077/
  4. Luca Cardelli, Peter Wegner. On Understanding Types, Data Abstraction, and Polymorphism // ACM Computing Surveys. — New York, USA: ACM, 1985. — Vol. 17, n. 4 — pp 471–522 — ISSN 0360–0300.
  5. Measure memory usage in Visual Studio. https://docs.microsoft.com/en-us/visualstudio/profiling/memory-usage?view=vs-2019
  6. Class Stopwatch. https://docs.microsoft.com/en-us/dotnet/api/system\\.diagnostics.stopwatch?view=netcore-3.1
Основные термины (генерируются автоматически): исходная структурная матрица.


Ключевые слова

C#, структурные особенности, разработка приложения, реализация алгоритма, архитектура приложения, анализ работы программы

Похожие статьи

Использование матриц комбинаторного типа для построения...

Методы распознавания образов используются в различных прикладных областях. В результате сбора и первичной обработки данных формируются описания объектов или явлений.

Метод структурного и параметрического синтеза и анализа...

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

Исходная матрица

Строки матрицы соответствуют литералам и их отрицаниям . Таким образом, число строк составит 2n, где

Кроме того, матрица дополнительно содержит n столбцов, соответствующих...

Исходная матрица.

Другими словами, траекторная матрица – это матрица. .(1). Очевидно, что и матрица X

Исходная матрица. Для исследования поведения «желоба» неоптимальных решений был...

исходная матрица наблюдений, задача моделирования...

Исследуется задача восстановления матрицы наблюдений «входных-выходных» переменных в задаче идентификации статических систем с помехами. Часто эта задача сводится к...

Развитие у учащихся способности самостоятельного решение...

Структура и проведение метода «Морфологическая матрица». Если рассматривать ее формально, то морфологическая матрица состоит из параметров и выражений.

Обзор методов организации параллельных вычислений

Представим исходную матрицу A в виде набора прямоугольных блоков следующим образом

Рассматриваются три параллельных алгоритма для умножения квадратной матрицы на вектор.

Применение итерационного алгоритма Шульца в рекуррентных...

Обратная матрица — это такая матрица , при умножении на которую исходная матрица

На языке структурного текста МЭК61131–3 для ПЛК в программной среде Unity Pro XL v7.0...

Матричный способ представления алгоритма | Статья в журнале...

Квадратная матрица алгоритма МA, заданная в матрично-предикатном виде, обладает

Проведём такую операцию с матрицей МA, разнеся функциональные и предикативные...

Применение свойств матричных норм к реализуемости...

, . Таким образом, искомая реализация исходной последовательности интервальных матриц имеет вид: Пример 2. Рассмотрим полностью положительную интервальную импульсную...

Похожие статьи

Использование матриц комбинаторного типа для построения...

Методы распознавания образов используются в различных прикладных областях. В результате сбора и первичной обработки данных формируются описания объектов или явлений.

Метод структурного и параметрического синтеза и анализа...

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

Исходная матрица

Строки матрицы соответствуют литералам и их отрицаниям . Таким образом, число строк составит 2n, где

Кроме того, матрица дополнительно содержит n столбцов, соответствующих...

Исходная матрица.

Другими словами, траекторная матрица – это матрица. .(1). Очевидно, что и матрица X

Исходная матрица. Для исследования поведения «желоба» неоптимальных решений был...

исходная матрица наблюдений, задача моделирования...

Исследуется задача восстановления матрицы наблюдений «входных-выходных» переменных в задаче идентификации статических систем с помехами. Часто эта задача сводится к...

Развитие у учащихся способности самостоятельного решение...

Структура и проведение метода «Морфологическая матрица». Если рассматривать ее формально, то морфологическая матрица состоит из параметров и выражений.

Обзор методов организации параллельных вычислений

Представим исходную матрицу A в виде набора прямоугольных блоков следующим образом

Рассматриваются три параллельных алгоритма для умножения квадратной матрицы на вектор.

Применение итерационного алгоритма Шульца в рекуррентных...

Обратная матрица — это такая матрица , при умножении на которую исходная матрица

На языке структурного текста МЭК61131–3 для ПЛК в программной среде Unity Pro XL v7.0...

Матричный способ представления алгоритма | Статья в журнале...

Квадратная матрица алгоритма МA, заданная в матрично-предикатном виде, обладает

Проведём такую операцию с матрицей МA, разнеся функциональные и предикативные...

Применение свойств матричных норм к реализуемости...

, . Таким образом, искомая реализация исходной последовательности интервальных матриц имеет вид: Пример 2. Рассмотрим полностью положительную интервальную импульсную...

Задать вопрос