New means of cybernetics, informatics, computer engineering, and systems analysis
- PDF / 117,085 Bytes
- 8 Pages / 595.276 x 793.701 pts Page_size
- 33 Downloads / 175 Views
NEW MEANS OF CYBERNETICS, INFORMATICS, COMPUTER ENGINEERING, AND SYSTEMS ANALYSIS CONTINUOUS LOGIC AND ALGORITHMS FOR SOLUTION OF SOME COMBINATORIAL PROBLEMS
UDC 519.715
V. I. Levin
The class of combinatorial problems equivalent to the problem of determination of relative positions of n interval sequences is formulated. It is shown that an adequate mathematical model of solving a stated problem is a finite dynamic memoryless automaton and that the adequate mathematical apparatus is continuous logic. Algorithms that solve the problem are constructed. Keywords: continuous logic, combinatorial problem, automaton model. INTRODUCTION Problems of data processing, job scheduling, design of object control systems, and many others are mathematically reduced to the solution of the combinatorial problem of computating suitable indicators of relative positions of n sequences of (time or spatial) intervals and to the determination of conditions under which these relative positions has some qualitative character or other. We give several examples of such problems. 1. Let there be a sequence A of time intervals in which some main technical device is operable and a sequence B of time intervals in which a backup device is operable. The system “main and backup devices” is efficient if at least one of its two devices, i.e., the main or backup device, is operable. Thus, to establish a sequence of operability intervals of the system, one should determine relative positions of sequences of operability intervals of the main device (the sequence A) and backup device (the sequence B) and find the time intervals in which there are intervals of at least one of sequences A or B; it is exactly these intervals that are the operability intervals of the system. In order to determine, for example, the operability of the system over an arbitrary given time interval T, it is necessary to find the conditions under which intervals of the sequence B within this time interval cover interspaces between intervals of the sequence A. 2. Let us consider a sequence A of time intervals during which some organization (a store, a bank, a repair shop, etc.) serves clients and a sequence B of time intervals during which some client can visit his service organization. To determine the sequence of possible time intervals of serving the client by his organization, it is necessary to determine relative positions of sequences of the intervals A and B and to reveal the time intervals that contain intervals of both sequences A and B; it is exactly these intervals that will be time intervals of possible client servicing. To determine when the organization can serve its client visiting it at any time instant suitable for him, one should find conditions under which the intervals of the sequence A cover all the intervals of the sequence B. 3. Let we have a sequence A of time intervals in which the chairman of a board can held a meeting and sequences B1 ,K , B10 of time intervals during which board members 1,K ,10 can participate in this meeting. A board meeting can be hol
Data Loading...
