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

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