Разработки СО РАН - каталоги программ и БД

Поиск по каталогам:

2015-12-30

Назначение – позволяет вычислять точное значение надёжности K-терминальной сети с ограничением на диаметр.
Область применения - анализ надёжности сетей различного назначения.

Одним из важных показателей сетевой надежности является вероятность связности заданного подмножества узлов. Однако существует также множество случаев, когда обычной связности терминалов недостаточно и необходимо, чтобы длина связующего пути не превышала заранее заданного числа D. Как и задача расчёта надёжности сети, задача расчёта надёжности сети с ограничением на диаметр NP-трудна [1]. В данной программе используется метод Cancela  и Petingi вычисления точного значения K-терминальной надёжности сети с ограничением на диаметр, а также методы ускорения работы программы, предложенные в [2]: предварительные сортировка рёбер, а также редукции рёбер.

[1] Cancela H., Petingi L. Reliability of communication networks with delay constraints: computational complexity and comlete topologies // Int. J. of Mathematics and Mathematical Sciences. 2004. V. 29. P. 1551-1562.

[2] D. Migov and S. Nesterov. Methods of Speeding up of Diameter Constrained Network Reliability Calculation // Springer Lecture Notes in Computer Science (in ICCSA 2015). Volume 9156, 2015, pp. 121-133.

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия).

Выходные данные программы – значение надёжности сети.

Программа работает с графом, представленным полным файлом предшественников (списки KAO,FO), а также списком терминалов. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы. Информация в файле располагается следующим образом: первая строка и вторая строка – списки KAO и FO соответственно, в третьей строке располагается список терминалов сети (Ki=1, в случае, если i-я вершина сети является терминалом, и 0 иначе). Четвёртая строка – значение надёжности каждого ребра, пятая – значение диаметра сети.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Функциональные возможности – расчёт надёжности сетей с количеством элементов около  сотни.

Инструментальные средства создания – Microsoft Visual Studio 2012.

2015-12-30

Назначение – позволяет устанавливать, является ли сеть достаточно надёжной(ненадёжной) по отношению к заранее заданному порогу надежности для  сети с ограничением на диаметр.

Область применения - анализ надёжности сетей различного назначения.

Рассматриваются сети, в которых отказам подвержены только каналы связи. Под надёжностью понимается вероятность того, что все выделенные узлы связаны между собой с помощью исправных каналов связи путями оганиченной длины. Точный расчет надёжности сети является NP-трудной задачей. Однако при анализе сети иногда достаточно знать, превосходит ли надёжность исследуемой сети величину заданного порога. Используя метод Cancela и Petingi [2], можно организовать итерационный процесс уточнения верхней и нижней границы надёжности сети с ограничением на диаметр и остановить его при достижении одной из границ значения заданного порога. Подобный подход для сетей без ограничения на диаметр был предложен в [1]. Программа позволяет устанавливать, является ли сеть достаточно надёжной по отношению к заданному порогу надежности, а также можно выбрать максимальное время работы, через которое программа остановится, показав верхнюю и нижнюю границы надёжности сети.

[1] Won J.-M., Karray F. Cumulative Update of All-Terminal Reliability for Faster Feasibility Decision // IEEE Trans. On Reliability. September 2010. Vol 59, no 3. P. 551-562.  

[2] Hector Cancela and Louis Petingi. Diameter constrained network reliability: exact evaluation by factorization and bounds. In ICIL’2001 (International Conference on Industrial Logistics), pages 359– 366, 2001.                                                                    

Входные данные программы – структура сети в виде графа, значения надёжности каналов связи (т.е. вероятности их присутствия), значение порога (число от 0 до 1) (можно отключить), ограничение на время расчёта в секундах (можно отключить).

Выходные данные программы – ответ о достаточной надёжности/ненадёжности сети. Если расчёт не был окончен за отведённое время, выводятся полученные к данному моменту значения границ надёжности.

Программа работает с графом, представленным полным файлом предшественников (списки KAO,FO), а также списком терминалов. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы. Информация в файле располагается следующим образом: первая строка и вторая строка – списки KAO и FO соответственно, в третьей строке располагается список терминалов сети (Ki=1, в случае, если i-я вершина сети является терминалом, и 0 иначе). Четвёртая строка – значение надёжности каждого ребра, пятая – значение диаметра сети.

Алгоритм разработан в рамках гранта РФФИ № 14-07-31069.

Функциональные возможности – анализ надёжности сетей с количеством элементов  в несколько сотен.

Инструментальные средства создания – Microsoft Visual Studio 2012.

2015-12-01

Назначение - для ввода всех промежуточных и окончательных формул решения линейного дифференциального уравнения первого порядка методом Лагранжа с контролем каждого введенного символа.

Область применения - лекции и практические занятия по дифференциальным уравнениям.

Используемый алгоритм - формирование эталонного решения линейного дифференциального уравнения первого порядка методом Лагранжа в виде массива строк языка Java с последующим представлением их массивами символов с информацией о месте расположения каждого символа в окне программы. В программе обрабатывается каждое нажатие клавиши, во время которого для текущего символа находится или не находится соответствующий символ в эталонном решении. В одном случае символ добавляется к решению, в другом - выводится информация об ошибке. Более подробно алгоритм изложен в статье [1].

 1. Попов А.А. Методика программирования на языке Java тренажеров по математике с посимвольным контролем аналитических преобразований. Программная инженерия. 2012. №8, с.38-43.

Функциональные возможности - программа может генерировать различные линейные дифференциальные уравнения с использованием не менее 100 шаблонов уравнений  и обрабатывать каждый введенный символ при решении уравнения методом Лагранжа с генерацией ошибок.

Инструментальные средства создания - программа написана на языке Java с использованием среды Eclipse.

Во вложении файл TrainLagrange.zip содежит 7 файлов: файл с расширением .bat необходим для загрузки TrainLagrange.class, который в процессе выполнения использует остальные файлы.

В файле с расширением .doc показана работа с тренажером на конкретном примере.

2015-11-30

Назначение - для иллюстрации процесса решения линейного дифференциального уравнения первого порядка методом Лагранжа с посимвольным выводом решения.
Область применения - лекции и практические занятия по дифференциальным уравнениям.

Используемый алгоритм - из массива сложных функций, имеющих различные аргументы, составляется линейное дифференциальное уравнение первого порядка и записывается его решение методом Лагранжа в виде массива строк языка Java. Каждая строка имеет управляющие символы, определяющие варианты размещения фрагментов строк в ее графическом представлении. Счетчик выводимых графических символов изменяется в методе run интерфейса Runnable после временной задержки. Более подробно алгоритм изложен в статье [1].

1. Попов А.А. Методика программирования на языке Java тренажеров по математике с посимвольным контролем аналитических преобразований. Программная инженерия. 2012. №8, с.38-43.

Функциональные возможности - программа управляется 4 клавишами, посредством которых запускается или останавливается поток, а также уменьшается или увеличивается время задержки перед выводом текущего символа. Программа является электронным эквивалентом процесса написание символов на аудиторной доске.

Инструментальные средства создания - программа написана на языке Java с использованием среды Eclipse.

Во вложении  файл IllustrLagrange.zip содержит 7 файлов: файл с расширением .bat необходим для загрузки IllustrLagrange.class, который в процессе выполнения использует остальные файлы.

В файле с расширением .doc приведено решение одной из задач.

2015-09-14

Назначение - Решение задач о покрытии множеств

Используемый алгоритм - метод ветвей и границ с определениеи  нижних, верхних границ  на основе приближенного решения двойственных задач с помощью субградиентного метода. Для сокращения размерности по исходным и двойственным переменным используются логические процедуры. Логическое тестирование осуществляется в каждом узле дерева ветвей и границ.  В процедуре ветвления в качестве входных данных используется вектор двойственных оценок, полученный на предшествующем уровне. Для ветвления в начале выбирается строка, соответсвующая максимальной компоненте вектора двойстенных оценок. Столбцы в выбранной строке упорядычиваются по возрастанию их приведенной стоймости.  Для просмотра индексов по столбцам и строкам используются разреженные строчный и столбцовый форматы. При этом  создаются только массивы индексов, а для элементов матрицы нет необходимости отводить память [1]. 

[1]     Забиняко Г.И. Реализация алгоритмов решения задачи о покрытии множеств и анализ их эффективности // Вычислительные технологии -2007,Т.12,№6, с.50-58.                      

Разработаны  варианты программ в однопроцессорном и многопроцессорном режимах.                                         

Функциональные возможности - реально с обоснованием оптимальности решаются задачи с числом строк до 500 и столбцов до 5000.
Инструментальные средства создания - фортран, MPI