logo BDSP

Base documentaire

  1. Fast optimal diagnosis procedures for k-out-of-n : G systems.

    Article - En anglais

    A kappa-out-of-n : G system consists of a set of components, where each component is either faulty or fault-free.

    The system is working if at least kappa components are fault-free.

    The problem of finding an optimal diagnosis procedure for a given kappa-out-of-n : G system has been considered in several research fields including medical diagnosis, redundant-system testing, and searching data-files.

    A polynomial-time algorithm for this problem was presented first by Salloum, and latter by Salloum & Breuer, and independently by Ben-Dov.

    This paper implements the Salloum-Breuer-Ben-Dov algorithm, leading to an optimal diagnosis procedure that can determine the state of any given system in O (n. log (n)) time complexity and O (n) space complexity.

    The efficiency is achieved by using a generalized radix sorting procedure that uses a heap data structure.

    For some kappa-out-of-n : G systems, including those with equal testing costs for all components, the components along the leftmost & rightmost paths in the optimal diagnostic tree uniquely determine the other components in the tree.

    This property is used to devise a faster optimal diagnosis procedure than the one for the general kappa-out-of-n : G system.

    With regard to complexity, these procedures are the best solutions for the problem under consideration.

    This conjecture is supported by the fact that all these procedures require a sorting operation which has O (n. log (n)) as a lower bound on its time complexity.

    Mots-clés Pascal : Diagnostic, Application médicale, Système redondant, Système k parmi n, Fiabilité, Arbre binaire, Essai, Multiprocesseur

    Mots-clés Pascal anglais : Diagnosis, Medical application, Redundant system, K out of n system, Reliability, Binary tree, Test, Multiprocessor

    Logo du centre Notice produite par :
    Inist-CNRS - Institut de l'Information Scientifique et Technique

    Cote : 97-0410296

    Code Inist : 002B30A01A1. Création : 19/12/1997.