Вычисление надежности рекурсивно определимых сетей

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

Статья представлена к публикации членом редколлегии: Б. Г. Волик