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

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

2014-04-10
"RIFS" Рандомизированная система итерированных функций

Назначение – Библиотека "RIFS" обеспечивает построение и отображение реализаций предфрактальных множеств в Rn с помощью рандомизированной системы итерированных функций. 

Область применения – Компьютерное моделирование и анализ данных, обладающих фрактальной структурой.

Используемый алгоритм: Применяемая в библиотеке "RIFS" рандомизированная система итерированных функций (РСИФ) строится на основе формулы: xi+1 = (xi + muj*zj)/(1+muj), где xi – i-ая итерационная точка предфрактала; zj – j-ая псевдослучайная точка протофрактала Z, выбранная согласно распределению вероятностей P(Z); muj – коэффициент разбиения итерационных отрезков, соответствующий j-ой псевдослучайной точке Z.

Под протофракталом понимается множество точек Z вместе с множеством коэффициентов разбиения итерационных отрезков M и заданным распределением вероятностей P(Z), которое определяет характеристики порождаемого фрактала A. Под предфракталом понимается счетное множество точек Х, соответствующее выборке A и порождаемое в результате итераций РСИФ.
  • Функция R2ngon() вычисляет координаты вершин правильного многоугольника с заданным разбиением ребер, вписанного в окружность заданного радиуса и используемого в качестве протофрактального множества.
  • Функция preRIFS() выполняет построение предфрактального множества X в Rn с помощью РСИФ для дискретного протофрактального множества Z с произвольным распределением вероятностей P(Z) и переменным коэффициентом разбиения итерационных отрезков M=var.
  • Функция preRSum0() выполняет построение предфрактального множества X в Rn с помощью матрицы случайных сумм для заданного протофрактального множества Z с произвольным распределением вероятностей P(Z) и постоянным коэффициентом разбиения итерационных отрезков M=const.
  • Функция plotR2pre() выполняет визуализацию предфрактального множества X в R2 с описанием основных параметров порождающего протофрактального множества Z.

Базовая рандомизированная система итерированных функций была предложена и исследована А.Г. Буховцом с соавторами [1,2]. Алгоритм построения реализаций фрактальных структур на основе рандомизированной системы итерированных функций был реализован П.В. Москалевым и А.Г. Буховцом [3,4]. Алгоритм построения реализаций фрактальных структур на основе матрицы случайных сумм был реализован П.В. Москалевым, А.Г. Буховцом и Т.Я. Бирючинской [4]. 

  1. Буховец А.Г., Буховец Е.А. Моделирование фрактальных структур данных // Системы управления и информационные технологии.– 2008. – Т.33, №3.– С.4–7.
  2. Буховец А.Г., Бирючинская Т.Я., Буховец Е.А. Использование фрактальных моделей в задачах классификации // Системы управления и информационные технологии.– 2009. – Т.37, №3.1.– С.117–121.
  3. Москалев П.В., Буховец А.Г. О размерности подобия рандомизированной системы итеративных функций // Компьютерные исследования и моделирование.– 2012.– Т.4, №4.– С.681–691.
  4. Moskalev P.V., Bukhovets A.G., Biruchinskay T.Ya. RIFS: Random iterated function system, CRAN.– 2012.– URL: http://cran.r-project.org/package=RIFS/ (online; accessed: 04.06.2012). R package version 0.1-5.

Инструментальные средства создания – R версии 2.14.0.
2014-03-31
Программа для интеграции различных источников данных с ядром обработки данных

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

Область применения - Любая сфера бизнеса, где необходимо для наполнения БД получать данные из внешних систем (например, автомобильный дилер: получение данных по клиентам, автомобилям, маркам, моделям, модификациям, прайс-листам, запчастям и сервисным работам из внешней базы данных импортера с контролем целостности и релевантности).

Используемый алгоритм - Алгоритм разработан автором. В качестве алгорима обработки данных выступает логика разбиения синхронизируемых запросов на очередь и обработка этой очереди как в синхронном, так и асинхронном режимах, в зависимости от настройки пользователя. Для уменьшения нагрузки на программно-аппаратную часть реализована клиент-серверная архитекутура с основной обработкой очереди в системном сервисе, связь с которым клиентская часть поддерживает за счет очереди сообщений. Для уменьшения нагрузки на стандартные методы доставки сообщений в ОС  Windows  в очереди сообщений передаются только информация о состоянии сервиса интеграции (запущен или остановлен), времена начала и окончания синхронизации каждого из синхронизируемых запросов. Выборка релевантных записей для ускорения получения результатов строится на анализе последней даты изменения записи, получаемой из системной таблицы баз данных. Контроль целостности строится на рассчете контрольной суммы, отвечающей за содержимой таблицы. В случае, если синхронизируемый запрос получает данные не из реляционной базы данных, а из файла типа  XML,  релевантность записи определяется системными битами релевантности файла на жестком диске, что позволяет обрабатывать только актуальные записи на диске. Программное решение позволяет производить и настраивать через пользовательский интерфейс интеграцию с различными источниками данных, в качестве которых могут выступать как традиционные базы данных, так и файлы XML  типа. Задание синхронизации может выполняться как по расписанияю, так и по запросу. Запросы на получение данных могут редактироваться во встроенном редакторе запросов, изменения в котором применяются сразу же, без необходимости перезапуска процесса интеграции.

Функциональные возможности - На данный момент отсутствуют какие-либо ограничения на объем обрабатываемых данных. В процессе тестовых испытаний и опытной эксплуатации проводилась успешная интеграция и обработка данных суммарным объемом 898000 строк. Общая загрузка системы не превышала 10%  в пиковые периоды обработки данных. 

Более подробное описание функционала и методики работы - в прикрепленном файле.

Инструментальные средства создания - Microsoft Visual Studio 2012, EntityFramework, Microsoft Visual C++
2013-12-31
Метод обнаружения атакующего воздействия специального вида в беспроводной сенсорной сети

Назначение - Противодействие разрушающим воздействиям DoB (Depletion of Battery), направленным на быструю разрядку батареи сенсора в беспроводных сенсорных сетях.
Область применения - Обеспечение безопасности информационных технологий.

Используемый алгоритм - опубликован в статье: Vladimir V. Shakhov: Protecting Wireless Sensor Networks from Energy Exhausting Attacks. Lecture Notes in Computer Science, Volume 7971, 2013, pp 184-193. (ISSN0302-9743). Алгоритм основан на методе кумулятивных сумм для обнаружения «разладки» случайного процесса. 

Функциональные возможности -  Требуется настройка параметров алгоритма, в частности порогового значения, для того, чтобы запаздывание в обнаружении "разладки" было приемлемым в конкретном случае.  Априорная информация о характере распределения моментов возникновения «разладки» не требуется. Уменьшение порогового значения приводит к более быстрому обнаружению атаки, однако при этом увеличивается вероятность ложной тревоги. Во вложении имеется график зависимости оценики математического ожидания времени до объявления ложной тревоги от величины порога. Кроме того, в прилагаемом архиве содержится С++ файл (example_alg.cpp), демонстрирующий возможности программы  (создание потока случайных наблюдений, по которым делается вывод о наличии атаки, инициализация параметров атаки, вычисление порогового значения, обнаружение атаки)  и скриншот с результатом работы.  

Инструментальные средства создания - MSVC 2008, библиотека libRNGnet.
2013-12-31
Библиотека программ для анализа производительности элементов в системах сетевой структуры

Назначение: Оценка  вероятностно-временных характеристик надёжности и живучести сетей
Область применения: Мониторинг, анализ и оптимизация систем сетевой структуры

Используемый алгоритм: Вычисление вероятности блокировки пакета и средней задержки пакета в сетевом узле проводится с использованием СМО специального вида, разработанных с учетом специфики различных типов сетей (IP сети, WSNs, OBS).

В программах реализованы алгоритмы оценки вероятностно-временных характеристик, описанные в публикациях: 

  1. Vladimir V. Shakhov, Sangyep Nam, Hyunseung Choo: Flooding attack in energy harvesting wireless sensor networks. Proceedings of the 7th International Conference on Ubiquitous Information Management and Communication, ACM New York, USA 2013, Article No. 49, ISBN: 978-1-4503-1958-4; 
  2. Vladimir V. Shakhov: Experiment Design for Parameter Estimation in Sensing Models. Springer Lecture Notes in Computer Science, Volume 8072, 2013, pp 151-158, ISSN0302-9743; 
  3. Шахов В.В. К вопросу обеспечения дифференцированного качества обслуживания в мультисервисных сетях // Проблемы информатики, 2011, № 3. С. 64-78; 
  4. Vladimir Shakhov and Hyunseung Choo // An Efficient Method for Proportional Differentiated Admission Control Implementation. EURASIP Journal on Wireless Communications and Networking, vol. 2011, Article ID 738386, 5 pages, 2011. doi:10.1155/2011/738386; 
  5. Vladimir V. Shakhov. DDoS flooding attacks in OBS networks // IEEE 7th International Forum on Strategic Technologies (г. Томск, 18-21 сентября 2012 г.), P.704-707; 
  6. Vladimir V. Shakhov, Sangyep Nam, Seung-Jung Shin, Hyunseung Choo. Potential intrusions in wireless networks. Proceedings of the 6th International Conference on Ubiquitous Information Management and Communication (ACM ICUIMC 2012), Kuala Lumpur, Malaysia, 2012;
  7. V.V. Shakhov, Hyunseung Choo: On Modeling Counteraction against TCP SYN Flooding. Springer Lecture Notes in Computer Science, vol. 5200, 2008, pp 574-583; 
  8. Vladimir V. Shakhov, Jahwan Koo, Hyunseung Choo: On Modelling Reliability in RED Gateways. Springer Lecture Notes in Computer Science, Volume 3991, 2006, pp 948-951.

Кроме того, для тестирования алгоритмов реализованы формулы расчета характеристик некоторых СМО (см. Клейнрок Л. Теория массового обслуживания. — М.: Машиностроение, 1979. — С. 432.)

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

Инструментальные средства создания - MSVC, библиотека libRNGnet
2013-12-30
Расчет вероятности связности случайного графа. Версия №2

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

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

Программа производит точный расчет вероятности связности подмножества вершин в случайном графе с ненадёжными ребрами. Расчёт данной характеристики представляет собой NP-трудную задачу, однако применение различных методов, в первую очередь, методов редукции и декомпозиции, позволяет за приемлемое время осуществлять расчет для графов средней размерности (около сотни элементов).

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

Входные данные программы – граф, вероятности присутствия рёбер.

Выходные данные программы – значение вероятности связности графа.

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

[1] Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, vol. 4097, 2006. - P.702-709.

[2] Мигов Д.А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики, № 2(6), 2010. –  С.10-17.

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

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

По сравнению с 1 версией программы (№ PR10003) внесены следующие изменения:

- выбор разрешающего ребра для ветвления осуществляется по критерию минимума суммы степеней смежных вершин, что увеличивает быстродействие;

- ветвление прекращается по достижению графов с пятью и менее вершинами, для расчёта надёжности которых используются специальные формулы, что также увеличивает быстродействие;

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