Новости

Программа производит точный расчет вероятности связности подмножества вершин в случайном графе с ненадёжными ребрами. Расчёт данной характеристики представляет собой 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) внесены следующие изменения:

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

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

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

2013-12-25

Гистограммный иерархический алгоритм поиска кластеров с отделимостью ниже заданной по текстурным признакам

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

Область применения - Программа может быть использована для исследования и автоматизации сегментации по текстурным признакам черно-белых изображений в химии, биологии, медицине, аэрокосмических изображений в сельском хозяйстве, лесничестве при оценке площадей, занятых различными культурами, типами и фазами развития лесов, их картировании и инвентаризации.
Используемый алгоритм -разработанный автором дивизимный гистограммный иерархический алгоритм [1]. В результате работы алгоритма отыскиваются унимодальные кластеры с отделимостью ниже заданной и предельно детальная сеть квантования векторного пространства текстурных признаков. Алгоритм не требует задания числа кластеров и никакой информации о распределениях a priory, а находит их автоматическми . Алгоритм учитывает особенности сбора статистических текстурных признаков по окну конечных размеров: он позволяет автоматически выбрать этот размер и избавиться от ложных кластеров, возникающих на границах текстур. В [1] показано применение алгоритма к неконтролируемой классификации изображений лесных ландшафтов на аэроснимках и их сегментации по текстурным признакам. На сайте можно посмотреть дополнительную информацию и иллюстрации - результат работы программы: http://loi.sscc.ru/lab/RFFI2013/RU/sidorova_separability_TEXTURA.htm

[1] Sidorova V.S. Segmentation of image textures using well separated clusters //The 11th International Conference "Pattern recognition and image analysis: new information technologies" PRIA-11-2013, Samara, The Russian Federation, 2013,Vol.II, – P.731-734.

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

Инструментальные средства создания - Алгоритм реализован в программной среде системы объектно-ориентированного программирования Visual C++ версии 5.0 фирмы Microsoft c библиотекой классов MFC, разработанной для ОС Windows. При разработке программы использовался механизм многодокументного интерфейса MDI.

2013-12-25

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

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

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

Используемый алгоритм - Программа реализует алгоритм сегментации изображения с предварительным выделением областей, связных в плоскости изображения и однородных по признакам [1]. Входной файл может содержать спектральные или текстурные признаки. Он должен быть представлен как многоспектральное изображение в формате BMP (если признаков не больше трех) или RAW. Алгоритм является параметрическим. При последовательном однократном просмотре исходного изображения производится его предварительная локальная сегментация на связные области, дисперсия в которых не превосходит заданные пороги d1 по строке изображения и d2 между строками. Средние вектора признаков областей затем объединяются кластерным алгоритмом с заданием еще двух порогов внутрикластерного расстояния с учетом площадей кластеров. Характеристики областей и кластеров могут быть выведены на экран в виде таблиц и сохранены в файл. Алгоритм был применен для автоматизации распознавания лесных ландшафтов на аэроснимках с использованием текстурных признаков Харалика [2]. Файл вложения иллюстрирует результаты работы алгоритма, адаптированного к персональному компьютеру.

[1] В.И.Борисенко, Л.С.Чесалин. Алгоритмы тематического дешифрирования многоспектральной аэрокосмической видеоинформации. // Ж.: Космические исследования, т. XVI, вып. 3, Москва 1978, С. 388 - 393.

[2] Алексеев А.С., Васильев С.В., Мозалевский В.Г., Пяткин В.П., Седых В.Н., Сидорова В.С. Автоматизация процесса обработки аэрокосмических снимков в целях инвентаризации лесов // Ж.: Исследование Земли из космоса. АН СССР. 1981. № 6. С. 93-100.

Функциональные возможности - Может быть использовано до десяти спектральных или текстурных признаков, файл входного изображения объемом до 5 мегабайт.
Инструментальные средства создания - Алгоритм реализован в программной среде системы объектно-ориентированного программирования Visual C++ версии 5.0 фирмы Microsoft c библиотекой классов MFC, разработанной для ОС Windows. При разработке программы использовался механизм многодокументного интерфейса MDI.

2013-12-24

Моделирование траекторий сильного решения автономной системы стохастических дифференциальных уравнений

Назначение:

Программа предназначена для моделирования траекторий решения автономной системы стохастических дифференциальных уравнений (СДУ)

dY(t) = A(Y(t))*dt + B(Y(t))*dW(t), где

Y(t) - вектор состояния системы (размерности n);

W(t) - вектор независимых стандартных винеровских процессов (размерности m);

A(Y) - известная векторная функция размерности n (снос);

B(Y) - известная матричная функция размерности n x m (диффузия).

Область применения: Программа может быть использована для моделирования динамических систем, модели которых заданы системой СДУ, в различных областях: радиотехнике, статистической механике, автоматическом управлении, химии, медицине, теории надежности и т.д.

Используемый алгоритм: Для моделирования решений автономных систем СДУ в смысле Стратоновича используется асимптотически несмещенный с любым шагом интегрирования обобщенный двух-стадийный метод типа Розенброка, описанный в работах [1, 2], а для моделирования решений автономных систем СДУ в смысле Ито используется устойчивый обобщенный двух-стадийный метод типа Розенброка, описанный в работах [3.4]. Предполагается, что в начальный момент времени Т0 известно распределение вектора состояния системы Y(T0).

Программа рассчитана на математиков – вычислителей и может быть использована для решения задач, математические модели которых заданы системой СДУ. Используемый метод рекомендуется для решения жестких осциллирующих систем стохастических дифференциальных уравнений. Описание метода подробно изложено в прикрепленных файлах (см. вложение).

1. Т.А. Аверина, С.С. Артемьев. Новое семейство численных методов решения стохасти-ческих дифференциальных уравнений// Докл. АН СССР, 1986, т.288, N 4, с. 777-780.

2. . Т.А. Аверина, С.С. Артемьев. Некоторые вопросы построения и использования численных методов для решения систем стохастических дифференциальных уравнений. Новосибирск. 1987. – 32 с. – (Препринт / АН СССР Сиб. Отд.-ние, ВЦ; №728).

3. С.С. Артемьев. "Устойчивость численных методов решения стохастических дифференциальных уравнений." Сибирский математический журнал, 1994, т. 35, №6, 1210-1214.

4. Artemiev S.S., Averina T.A. Numerical Analysis Systems of Ordinary and Stochastic Differential Equations. VSP, Utrecht, The Netherlands, 1997 (176 p.)

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

2013-12-24

Принятие решения о надежности (ненадежности) сети по отношению к заданному порогу для различных показателей надежности. Версия №3

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

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

Точный расчет надёжности сети представляет собой NP-трудную задачу. Однако при анализе надёжности сети знать точное значение надёжности не всегда необходимо, иногда достаточно установить факт, превосходит ли надёжность исследуемой сети величину заданного порога. Основываясь на известном методе ветвления (factoring method), можно организовать итерационный процесс уточнения верхней и нижней границы надёжности и остановить его при достижении одной из границ значения заданного порога. Данный подход был предложен в [1].

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

Если в качестве показателя надёжности сети выбрана вероятность связности, то для ускорения расчетов осуществляется предварительная декомпозиция сети на двусвязные компоненты, для каждой из которых проводится декомпозиция по двухвершинным сечениям. После этого запускается процесс уточнения оценок надёжности для каждого из полученных в процессе декомпозиции графов. Данный алгоритм опубликован в [2].

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

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

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

[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] A. Rodionov, D. Migov, and O. Rodionova. Improvements in Efficiency of Cumulative Updating of All-Terminal Network Reliability // IEEE Transactions on Reliability. Vol. 61, issue 2. June 2012. - P. 460-465.

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

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

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

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

- добавлена возможность устанавливать ограничение на время расчёта. Если расчёт не был окончен за отведённое время, выводятся полученные к данному моменту значения границ надёжности;

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

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