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

На данной странице представлен каталог программ, включенных в Фонд алгоритмов и программ Сибирского отделения РАН. Полный каталог программ и БД, включенных в Фонд, а также любые выборки по научным центрам, объединенным ученым советам и др. вы можете найти на данной странице.

2012-04-25

Приближенное вычисление вероятности несвязности планарного графа

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

Область применения - задача вычисления вероятности связности графа с ненадежными ребрами рассматривалась во многих работах по теории надежности, при изучении электротехнических объектов, компьютерных сетей. Вероятностные оценки связности используются при исследовании сотовых структур и наносистем (нанотрубок, фулленеров, графенов и т.д.).

Разработанная программа позволяет сократить вычисления и определить вероятность связности планарного графа по соответствующей матрице смежности двойственного графа, на основе определения асимптотических констант: (D) - размерность минимального разреза и (C) - количество таких разрезов. Алгоритм построения матрицы смежности двойственного графа и поиска соответствующих асимптотических констант описан в работе [1].
Условия эксплуатации :
1. Расчет связности проводится на основе асимптотических формул, поэтому на входные данные (вероятность отказа ребра) налагаются ограничения - вероятность отказа ребра должна быть порядка 1/N², где N - количество вершин в исходном графе.
2. Вводимая матрица смежности должна быть симметричной, по диагонали стоят нули.

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

Инструментальные средства создания - Среда программирования Delphi 7.

[1] Tsitsiashvili G.Sh. Complete calculation of disconnection probability in planar graphs// Reliability: Theory and Applications. 2012. Vol. 1. No 1. P. 154-159.

2012-04-20

Пакет программ квадратичного программирования

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

Область применения - Исследование операций
Используемый алгоритм - метод приведенного градиента с использованием на этапе безусловной минимизации сопряженного градиента.
Алгоритм опубликован в статье: Котельников Е.А. "Применение приведенного градиента в квадратичном программировании". Сиб. журн. вычисл. математики. 2010.-Т.13, № 1.-С. 23-31.
Функциональные возможности - число строк в матрице ограничений не должно превышать 32765.
Инструментальные средства создания - Фортран

2012-04-17

Программный комплекс сетевого планирования и управления ("ПКСПП")

Назначение - Календарное планирование проектов.

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

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

Используемый алгоритм - В пакете программ реализован алгоритм случайного поиска с самообучением для приближенного решения задач календарного планирования проектов.

Алгоритм опубликован в статьях:

Ляхов О.А. Модель календарного планирования проектов с перераспределением нескладируемых ресурсов // Вестник Бурятского государственного университета / - Улан-Удэ: Изд-во Бурят. госун-та, 2010. - Вып. 9: Математика и информатика. - С.119-124;
Ляхов О.А. Модели передачи заданий в сетевом планировании сложных комплексов работ // IX Международная конференция "Проблемы функционирования информационных сетей": Материалы конференции, Новосибирск, 2006, с.174-179.

Функциональные возможности - Пакет рассчитан на следующие максимальные размеры входных данных: 32765 работ в сводной сетевой модели, 128 видов нескладируемых ресурсов, 256 типовых моделей.

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

2012-01-26

Регистрация радиоизлучения и вариация фона. Radio Registration and Background Monitoring

Назначение - Программа предназначена для считывания данных с АЦП (Аналого-цифровой преобразователь) и визуализации снятых данных.
Область применения - Регистрация вторичных частиц космического происхождения при помощи детекторов ШАЛ (Широких атмосферных ливней) и антенны радиоизлучения.
Функциональные возможности - Работа с АЦП; визуализация вариации фона в реальном времени; сохранение и загрузка файлов; обработка сохраненных файлов; построение дифференциального и интегрального спектров;
В программе реализован алгоритм, разработанный авторами (Петров З. Е., Борщевский Д. С., Петров И. С.), описание работы программы - в приложенном файле.

Инструментальные средства создания - Borland Delphi 6.0

2011-12-26

Определение характеристики надежности сети по отношению к заданному порогу

Назначение - Оценка характеристики надежности сети связи. Принятие решения, является ли сеть достаточно надежной по отношению к заданной величине надежности - порогу.
Область применения - анализ надежности и живучести современных сетей связи.
Задача точного вычисления характеристики надежности сети NP-трудна, точный расчет имеет экспоненциальную сложность. Если же стоит задача определить, превосходит ли надежность исследуемой сети величину заданного порога, не обязательно осуществлять полный перебор. В этом случае при помощи специальных методов объем вычислений можно значительно сократить.
Используемый алгоритм - за основу взят алгоритм из 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.
Алгоритм модифицирован, применяется декомпозиция сети на блоки. Модифицированный алгоритм опубликован в [1].
Функциональные возможности - можно исследовать сети с количеством элементов в несколько сотен.
Инструментальные средства создания - Delphi 5.
[1] Мигов Д.А., Родионов А.С. Принятие решения о надежности сети при помощи ее декомпозиции на двусвязные компоненты // Тезисы докладов Российско-Монгольской конф. молодых ученых по математическому моделированию, вычислительно-информационным технологиям и управлению (Иркутск, Россия – Ханх, Монголия, 2011). Иркутск, ИДСТУ СО РАН, 2011, с. 56.