Оценка результативности алгоритмов контроля пригодности по назначению информационных объектов с учетом порядка их выбора на проверку

Технологии распределенной обработки информации могут содержать этап предварительной обработки полученной информации с целью отбраковки той ее части, которая не пригодна для дальнейшего использования. Как правило, целевая информация структурно представлена в виде блоков данных (далее – БД) стандартной длины [1–3], а отбраковка негодной информации осуществляется на уровне БД. При этом число непригодных (дефектных) к дальнейшему использованию БД значительно меньше пригодных. Если пред- ставить всю информацию в виде множества O = {01, о 2,..., on } объектов, а под объектом понимать БД, то дефектные объекты могут располагаться в множестве произвольным образом. Для решения задачи рациональной выборки дефектных объектов из множества O необходимо определиться с объемом выборки и алгоритмом (правилом) выбора очередного объекта из множества для проверки на пригодность к дальнейшему использованию.

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

При большом числе объектов объем выборки можно определить из теории статистики [1]. Например, для точности, достаточной для практического применения, можно использовать формулу

n

V=---7----,

n Л2 +1

где n – мощность множества объектов;

v – объем выборки;

Δ – допустимая ошибка.

План выбора очередного объекта из множества O на практике опирается на один из трех наиболее распространенных алгоритмов:

• множество O = {Oi, o 2,..., on } информационных объектов, среди которых могут быть пригодные к дальнейшему использованию или дефектные;

• множество U = {Ui,и2,.,un } алгоритмов выбора из множества O очередного объекта для проверки пригодности по назначению, годные объекты остаются в множестве O, а дефектные удаляются.

Требуется:

• •    найти значение показателя качества алгоритма выбора из множества очередного объекта для проверки его пригодности по назначению;

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

Оценка качества алгоритмов выбора из множества очередного объекта для проверки его пригодности по назначению

Назначением любого алгоритма выборки очередного объекта из множества подобных является обнаружение дефектных объектов с целью дальнейшей их отбраковки. Для оценивания качества алгоритма исходя из его назначения целесообразно выбрать такой показатель, как вероятность обнаружения дефектного объекта в множестве O при заданной выборке v ( v <<  n ). Обозначим данную вероятность как P ( Ui , V , n ); так как априори не известно, какой из n объектов является дефектным, то номер объекта из множества О , который является дефектным, можно считать дискретной случайной величиной N со значениями [1,2, …, n ]. Пусть случайная величина N может иметь одно из известных законов распределения вероятностей дискретной случайной величины и отражать характер размещения дефектных объектов в множестве О . К таким распределениям можно отнести равномерный и биноминальный законы. Например, равномерный закон хорошо описывает равномерное распределение дефектных объектов среди объектов множества О , а биноминальный закон можно применять, когда дефектные объекты чаще встречаются в какой-то области множества O .

Вычислим вероятность P ( Ui , V , n ) для двух дискретных законов (равномерный и биноминальный) распределения дефектного объекта среди объектов множества O и трех распространенных алгоритмов выборки:

• 1)    алгоритм u ₁ заключается в том, что очередной объект из множества O выбирается

для проверки его пригодности по назначению последовательно, начиная с первого;

Оценка результативности алгоритмов контроля пригодности по назначению информационных объектов с учетом порядка их выбора на проверку

• 2)    алгоритм u ₂ заключается в том, что очередной объект из множества O выбирается для проверки его пригодности для дальнейшего использования по методу половинного деления;

• 3)    алгоритм u ₃ заключается в том, что очередной объект из множества O выбирается случайным образом.

Вычисление вероятности P ( u 1 , v , n ) для алгоритма u 1

Рассмотрим вычисление вероятности P ( Ui , v , n ) для биноминального закона распределения вероятностей случайной величины N . Для данного закона значениями случайной величины N являются натуральные целые числа [1,2, …, n ], а их вероятности определяются по формуле Бернулли p_t = C n - I p i ^{- 1} qⁿ - i , где 0 <  p , q < 1 и p + q = 1. От значений p и q зависит, в какой области множества О наиболее вероятно появление дефектного объекта.

В Таблице 1 ( а , б , в ) показаны распределения вероятностей случайной величины N для n = 10 и различных значений p и q.

Таблица 1

Распределения вероятностей случайной величины N для n = 10 и различных значений p и q

а ) при p = q = 0,5
x i	1	2	3	4	5	6	7	8	9	10
p i	0,002	0,018	0,07	0,164	0,246	0,246	0,164	0,07	0,018	0,002
б ) при p = 0,2 и q = 0,8
x i	1	2	3	4	5	6	7	8	9	10
p i	0,134	0,302	0,302	0, 176	0, 066	0,017	0,003	0,000	0,000	0,000
в ) при p = 0,8 и q = 0,2
x i	1	2	3	4	5	6	7	8	9	10
p i	0,000	0,000	0,000	0,003	0,017	0, 066	0, 176	0,302	0,302	0,134

Вероятность попадания дефектного объекта в диапазон номеров [1,2, …, v ] равна сумме вероятностей v первых значений в законе распределения случайной величины N. Тогда

P ( u , v , n ) = £ P i ,                                  (1)

i = 1 i - 1 i - 1 n - i где p_t = C n - i p q .

Например:

для Таблицы 1, а P ( u ₁, 3, 10) = 0,002 + 0,018 + 0,07 = 0,09;

для Таблицы 1, б P ( u ₁, 3, 10) = 0,134 + 0,302 + 0,302 = 0,738;

для Таблицы 1, в P ( u ₁, 3, 10) = 0,0 + 0,0 + 0,0 = 0,0.

Рассмотрим вычисление вероятности P(Ui, v, n) для равномерного закона распределения вероятностей случайной величиной N. Для данного закона значениями случайной величины N также являются натуральные целые числа в диапазоне [1,2, …, n] с одинако выми вероятностями их появления p = — (см. Таблицу 2).

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

Таблица 2

Равномерный закон распределения дискретной случайной величины N для n = 10

xi	1	2	3	4	5	6	7	8	9	10
pi	0,1	0,1	0,1	0,1	0,1	0,1	0,1	0,1	0,1	0,1

Выражение (1) справедливо и для равномерного закона распределения дискретной случайной величины N, но p = —. Тогда

^ v

P ⁽ и. , ^v , n ) = ^ p- =- .

¹              ,=1          n

Для Таблицы 2 P ( u ₁,3,10) = 0,1 + 0,1 + 0,1 = 0,3.

Вычисление вероятности P ( и 2 , v , n ) для алгоритма и 2

Алгоритм u ₂ заключается в том, что очередной объект из множества O выбирается для проверки его пригодности для дальнейшего использования по методу половинного деления (метод Ньютона). Суть этого метода проиллюстрируем для множества O .

Номер объекта, который выбирается из множества O первым, определяется как сере дина кортежа {1,2,3, ..., 10} по формуле ^^ = 5.

Здесь и в дальнейшем берется только целая часть результата деления.

Номер объекта, который выбирается из множества O вторым, определяется как середина кортежа {1,2, ..., 5} по формуле ^р = 3 .

Номер объекта, выбираемого третьим, определяется как середина кортежа {1,2,3} по

• 3    + 1 , формуле — = 2 .

Номер объекта, выбираемого четвертым, определяется как середина кортежа {1,2} по

• ^{2    +}1 1

формуле = 1.

Номер объекта, выбираемого пятым, определяется как середина кортежа {3,4,5} по

• 3    + 5 л формуле —-— = 4 .

Номер объекта, выбираемого шестым, определяется как середина кортежа {5,6,…,10}

5 + 10 ₇ по формуле ——— = 7 .

Номер объекта, выбираемого седьмым, определяется как середина кортежа {5,6,7} по

• 5    ⁺ 7 а

• формуле —-— = 6.

Номер объекта, выбираемого восьмым, определяется как середина кортежа {7,8,9,10}

• 7    ⁺ 10 я по формуле —-— = 8 .

Оценка результативности алгоритмов контроля пригодности по назначению информационных объектов с учетом порядка их выбора на проверку

Номер объекта, выбираемого девятым, определяется как середина кортежа {8,9,10}

• 8    + Ю о по формуле —-— = 9 .

Последним выбирается объект с номером 10.

Порядок выборки объектов из множества O для алгоритма u ₂ показан в Таблице 3.

Таблица 3

Порядок выборки объектов из множества O = { O i , о 2 , . , о ^ } для алгоритма и 2

№ объекта	Порядок выборки из множества O = { O i , O 2 , . , 0 ^ }
	1	2	3	4	5	6	7	8	9	10
	5	3	2	1	4	7	6	8	9	10

Как видно из Таблицы 3 и описания алгоритма u ₂, множество номеров объектов, соответствующее множеству O , разбивается на два равных отрезка. Затем один из них, например отрезок с младшими номерами относительно среднего номера, снова разбивается на два отрезка, которые потом также делятся на два, и т. д. Объекты из множества O с номерами, соответствующими серединным номерам отрезков, выбираются для проверки.

Рассмотрим вычисление вероятности P ( и 2 , v , n ) для биноминального закона распределения вероятностей случайной величины N : _v

P ( u 2 , v , n ) = £ h i ,

i = 1

где h _i соответствует вероятности из биноминального закона распределения случайной величины N для номера, который определяется i -м шагом алгоритма u ₂. Рассмотрим примеры определения вероятности P ( и 2 , v , n ) для биноминальных распределений, представленных в Таблице 1, и порядка выборки объектов из множества O = { O i , о 2,..., о^ } для алгоритма u ₂, представленного в Таблице 3:

для Таблицы 1, а P ( u ₂,3,10) = p ₅+ p ₃+ p ₂ = 0,246 + 0,07 + 0,018 = 0,334;

для Таблицы 1, б P ( u ₂,3,10) = p ₅+ p ₃+ p ₂ = 0,066 + 0,302 + 0,302 = 0,67;

для Таблицы 1, в P ( u ₂,3,10) = p ₅+ p ₃+ p ₂= 0,017 + 0,0 + 0,0 = 0,017.

Для равномерного закона распределения дискретной случайной величины N также справедливо выражение (3), но h _i соответствует вероятности из равномерного закона распределения случайной величины N для номера, который определяется i -м шагом алго-1

ритма и. Так как для равномерного закона p i = , то 2 n

, v

P (и 2, v, n ) = ^ hi = -.

, = i ⁿ

Для Таблицы 2 P ( u ₂,3,10) = 0,3.

Для равномерного закона распределения вероятности P ( и 2 , v , n ) и P ( U i , v , n ) равны.

Это следует из того, что все значения случайной величины N равновероятны ( p i = — ), и вероятность попадания дефектного объекта в выборку будет определяться только ее ⁿ объ-емом, независимо от того, какие объекты из множества O в нее входят. То есть для равно-

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление». 2025. № 3

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

Вычисление вероятности P ( и 3 , v , n ) для алгоритма и 3

Алгоритм u ₃ заключается в том, что очередной объект из множества O выбирается случайным образом, для чего может быть использован программный датчик генерирования случайных чисел, распределенных на интервале [1,2, …, n ]. Как правило, используется датчик равномерно распределенных случайных чисел. При выборке объемом ν датчик последовательно генерирует ν чисел из диапазона [1,2, …, n ], реализуя заложенный закон распределения.

Для биноминального закона распределения вероятностей случайной величины N

P ( и 3 , v , n ) = £ h i ,                                       (5)

i = 1

где h _i соответствует вероятности из биноминального закона распределения случайной величины N для номера, который генерируется датчиком случайных чисел.

Рассмотрим примеры определения вероятности P ( и 3 , v , n ) для биноминальных распределений, представленных в Таблице 1, и трех чисел (6,8,3), сформированных датчиком равномерно распределенных случайных чисел в диапазоне [1,2, …, n ]:

для Таблицы 1, а P ( u ₃,3,10) = p ₆+ p ₈+ p ₃ = 0,246 + 0,07 + 0,07 = 0,386;

для Таблицы 1, б P ( u ₃,3,10) = p ₆+ p ₈+ p ₃ = 0,017 + 0,0 + 0,302 = 0,319;

для Таблицы 1, в P ( u ₃,3,10) = p ₆+ p ₈+ p ₃= 0,066 + 0,302 + 0,0 = 0,368.

Так как для равномерного закона распределения дискретной случайной величины N вероятность попадания дефектного объекта в выборку будет определяться только ее объемом, независимо от того, какие объекты из множества O в нее входят, то

v

P ( и 3 , v , n )= -                                             (6)

n

Для Таблицы 2 P ( u ₃,3,10) = 0,3.

Для сравнения эффективности рассмотренных алгоритмов для биноминального распределения случайной величины N примеры расчета вероятности P ( Ui , v , n ) сведены в Таблицу 4.

Таблица 4

Результаты расчета вероятности P(и^ , v , n ) для биноминального распределения

Реализации биноминального закона распределения	Алгоритмы выборки
	u 1	u 2	u 3
Таблица 1, а	0,09	0,334	0,386
Таблица 1, б	0,738	0,67	0,319
Таблица 1, в	0,0	0,17	0,368

Реализация, представленная в Таблице 1, а , соответствует скоплению дефектных объектов в центре множества O . Реализация, представленная в Таблице 1, б , соответствует

Оценка результативности алгоритмов контроля пригодности по назначению информационных объектов с учетом порядка их выбора на проверку скоплению дефектных объектов в области младших номеров объектов множества O. Реализация, представленная в Таблице 1, в, соответствует скоплению дефектных объектов в области старших номеров объектов множества O.

Примеры расчета вероятности P ( u., v , n ) для трех наиболее распространенных на практике алгоритмов выборки очередного объекта и двух дискретных законов распределения случайной величины, отражающих типовые размещения дефектных объектов в множестве O , несмотря на кажущуюся их простоту, позволяют сделать определенные выводы по эффективности рассмотренных алгоритмов:

• •    при равномерном размещении дефектных объектов среди множества O все алгоритмы выборки равно эффективны, поэтому использовать целесообразно тот из них, который легче реализовать;

• •    при скоплении дефектных объектов в некоторой области множества O эффективнее использовать выборку по методу половинного деления или случайную выборку;

• •    при случайной выборке очередного объекта следует учитывать возможность генерации одинаковых номеров.

Заключение

Представленный в статье подход к оценке качества алгоритмов выбора из множества очередного объекта для проверки его пригодности к дальнейшему использованию наряду с теоретическим значением имеет и прикладную значимость. Новизной является то, что в отличие от известных подходов [4–6] выбор алгоритма опирается на аналитические расчеты. При этом номер объекта, который является дефектным, представлен дискретной случайной величиной с целочисленными значениями, а в качестве законов ее распределения рассматриваются равномерный и биноминальный. Это позволяет в большинстве практических задач предварительной обработки целевой информации обоснованно применять тот или иной алгоритм выбора из множества очередного объекта для проверки его пригодности к дальнейшему использованию.

Прикладной аспект полученных результатов заключается в том, что предложенный подход может быть использован не только для решения задачи предварительной обработки целевой информации, но и в других практических задачах, например, при организации периодического контроля технического состояния РЭА при длительном хранении [7].