Комбінаторні алгоритми підтримки прийняття управлінських рішень

Abstract

Наводиться постановка обмеженої та необмеженої задач комбiнаторного розпiзнавання. На прикладi задачi про вимикачi показано, яким способом необхiдно розбити на групи множину вимикачiв, щоб за мiнiмальну кiлькiсть спроб знайти потрiбну кiлькiсть несправних вимикачiв. Розглядається також задача вибору кiлькостi однотипних елементiв з двох заданих множин. Для кожної задачi наводяться формули оцiнок мiнiмальної кiлькостi спроб.

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

The bounded and unbounded combinatorial recognition problems are posed. Using a problem of switches as an example, we show how to divide the subset of switches into groups so that the given number of faulty switches could be found by minimal number of tests. We also consider the problem of choosing the number of elements of the same type from two given sets. For every problem, we give the evaluating formulas for the minimal number of tests.