RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления // Архив

Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 2012, выпуск 2, страницы 66–74 (Mi vspui73)

Информатика

Представление дискретных случайных величин с применением многокорневых диаграмм решений

Д. Ю. Бугайченко, И. П. Соловьев

Санкт-Петербургский государственный университет, математико-механический факультет

Аннотация: В работе предлагается новый метод представления дискретных случайных величин в памяти ЭВМ на основе многокорневых бинарных диаграмм решений (MRBDD). Такая необходимость возникает, например, в задаче вероятностной верификации, где в настоящее время активно используется другой тип диаграмм решений – многотерминальные бинарные диаграммы решений (MTBDD). Многокорневые диаграммы обладают рядом значимых преимуществ по сравнению с многотерминальными. За счет более эффективного повторного использования общих структурных блоков многокорневые диаграммы оказываются более компактной формой представления, что обеспечивает меньший объем потребляемой памяти и во многих случаях лучшее время работы. Приведенные экспериментальные результаты показывают, что многокорневые диаграммы являются перспективной заменой многотерминальных диаграмм, в том числе и в таких задачах как моделирование случайных величин и вероятностная верификация. Библиогр. 17 назв.

Ключевые слова: бинарные диаграммы решений, вероятностная верификация.

УДК: 519.683.8+004.424


Принята к печати: 28 февраля 2012 г.



© МИАН, 2024