Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v16(1-4)/levedev-025-048.pdf Дата изменения: Mon Nov 26 08:12:00 2012 Дата индексирования: Thu Feb 27 22:20:24 2014 Кодировка:

. .

­ , ­ . - . NP- , . : , .

1.
, . [9]. , , data mining [10], . . [3, 4] : - ,


26

. .

- , . ( ), . - . , , NP- , .

2.
, = {0, 1, . . . , - 1}, , - . , ( ). , - : , [0; 1]. ( ) , ( ). , . , , , : = , = {( , ), , } ; : [0; 1) ; : [0; 1]2 [0; 1] - , , , : (0, ) = 0, (1, ) = (- . - . ., , [5])




27

: [0; 1], , ( 1 , . . . , ) , ( ) : 1) = {( , ( )), }; 2) ; 3) ( ) = 1. , , ( , , , ). max = max ( ).

,

= , ,

( ) - , ( ) = T ( ). ,


()

, , , 0 < 1 , , max . , , , ( ), , max . ( )= , . . 1. 0 < ( , , , ) NP- 2, 3, 1 - .

2. = ,


28

. .

, . , . , : : ­ / ; ­ / ; ­ / ; ­ / ; ­ , ; ­ , ; ; . 3. ( , 2, , min), ( 2 ) . . , 2 , . , ( , ), ( + , ), . ( , , , ). 4. ( , , , ), , ( + +1 ) . , ( , ) ( , ) , max - 1. ( , , , ).




29

5. ( , , , ), ,

= 1 ( 2 ) , 2 NP-.

3.
1, 2 5. . , , - ( 1 , . . . , ) ( , ) = {( , ), , }, , ( ) [0; 1), - . : ( ) = T ( ), T-.


: 1) ( , ) ; ,

2) , , 1, , , . . , 0, : , = {( , ), , }, , , , ( , ) , -


30

. .

. 0,1-. 1. 2 3 0,1- NP-. . NP- NP- - [8] = , , . - : (


=

)

( , ( = ) ). ( = )


((

= ) (

= ))

(( = ) ( = ))


( ( , ), (( = ) ( = )) ( , ) ( , ). , , 1 , , , {( , ), } ). . 1 2.




31

1. , 0,1- , . 2. , , 1, 0 , 1, , . 5. . 2. 3 0,1- {( , , ), , , } , ( 1 , 1 , ) ( 2 , 2 , ), 1 - 2 1 1 - 2 1, NP. . NP- - = , , . = , , , : 1) = { 1 , . . . , }. = }). }, {( , , ), = 1, . . . , ; mod 2. ( , . = 2 (, {( , , ), , , = = - 1, = 2( - 1) + , )(
+1

,

+1

, ),

=


32

. .

2) , < - ); }, , = {( , , , , ), = 1, . . . , 2( - ), , = 2( - 1) + , = 1, . . . , 2( , = . ( , , , > 1 ( .
, 2 ,

= 2( +
2( - ) ,

)+
2( - )-1 ,

mod 2,

= 2, . . . , 2(

- ) - 1,

1 ,

= = ,)

, 1 ,

, )( ,+1 , , 1, , )(

+1 , , ), 2,2 , ,

. 1. . . 1. {( , , ), } , ( 1 , 1 , )( 1 , 1 , ), = , ( 1 , 1 , )( 2 , 2 , ). , , . , , , . , , : = , = , , , = , ( , ) = ( , ), , = , = , = ),




33

, . ( , ): 2 , = {( , , ( , )), ( , ) 2 } , . , : 1) ( );

, < , 2) , , , , , , , . , ( , ) . , , , , , , . , - , 2. 3. ( , , , ), 2 NP-. . , : 1) = 2 0,1 , ;


34

. .

2) ( , , 2, ) ( , , , ) 3.

4.
, [4], .

4.1.
. : , ( ). : [0; 1]. - ( 1 , . . . , ) ( ( )). 1 , ( ). , = (0, . . . , 0) ( ), 1 = 0 0 . = (0, . . . , 0) ( ) : 0 1 1 0.8 2 0.4 3 0 ... ... -1 0

()




35

{( , ), }. ( ) ( ( ) = 1, ).

4.2.
, . : , . . , , , . , ( ) ( + 1) , ( ) = ( + 1) = . , ( ) : ( + 1) () 0 1 2 3 4 5 0 0 0 0 0 0 0 1 1 0 0 0 0 0 2 1 1 0 0 0 0 3 1 1 1 0 0 0 4 1 1 1 1 0 0 5 1 1 1 1 1 0

( = 6): ( + 1) () 0 1 2 3 4 5 0 0.2 0 0 0 0 0 1 1 0.2 0 0 0 0 2 1 1 0.2 0 0 0 3 0.6 1 1 0.2 0 0 4 0.2 0.6 1 1 0.2 0 5 0 0.2 0.6 1 1 0.2


36

. .

- , . , ( , ) = , () () 0 1 1 0.8 2 0.4 3 0 ... ... -1 0

, , : ( ) = (0) (1) (1) (2) (2) (3) (3) (4) (4) (5) = 01 12 22 24 45 = 1 1 0.2 1 1 = 0.2. : , = , = , = + 1, ( , ) : , , , , ( , ) ( , ) : , ( , ) , . .

4.3.
, . : . . , . .

4.4.
- [1].




37

: , - ( 1 , . . . , ) (1 min( , ) - 2), : (
1

- - .

,...,

) - ( 1, . . . ,

)

,



: max
=1,...,

: ( , ) : , : max -
=1,...,

: - , ( , ) : , ( , ) ( , ) 0 ( , , , (0; 1)). , 1- . 2 .

4.5.
. , {( , ), , } , . . , - . . - . (- , , , : (0, ) = , (1, ) = 1. - . - : ( , ) = + - ).


38

. .

, .

5.
5.1.
5. 4. ( , , 1, ), ( 2 ) , . . NP- , . . : = , , . {( , ), , }, ( , ), ( + 1, ). , , : 1) : , . : ) , s (0, ) ( - 1, ) . 1; ) , . ( , ) ( + 1, ); ) , ( , ) ( + 1, ), . 0. ( , ) ( + 1, );




39

) (a, b) G , , ( , ), ( , ). , ( ). ( , ),

2) ( ) : ((0, )) = 1, ; 0 - 2 (( + 1, )) = max ( (( , ), (( , ), ( + 1, )))


( + 1, ) ( , ) , . 3) = , = ; ( ( ) = ) ( ) = () 4) , ( )



: 1(a) ( ), 1(b) 1(c) ( 2 ), 1(d) ( ). 2 - 1 , , ( ) . , ( 2 ) . 3 ( ) . , ( 2 ) . 4 . 5 4 5.


40

. .

5.2.
3. = min 0,1- : , , 0, . 0,1-. 3, (( = ) ( = )).




(



). ,

2-, , ([7]), . , ( ) , , [6]: ( , 2, , min) [0; 1] 1) ( ) . ,

2) : . ( , )( , ) ( , ) ( , ) ( , ) ( , ). 3) .




4) ( , ) ( , ) , . . ( + ) . = 2 2 2 , ( 2 ). 3 .




41

5.3.
4 , . 1) , = 1, . . . , : ( , ) ( , ) ; , , . , = в ,

2) max = 0, max = = T ( ),


:




, = {( , ( )), } max , max = > max , max . 3)


=

max

.

1 3 ( ) , 2 . = в , ={ + , }. , -1 , ( ) ( ) ,


42

. .

( 2 ). , ( + ) . 4 .

6.
, , . ( 1 , 2 ) ( = = 3). : 1- (); ;
1

;

T- .

6.1.
3 в = 3. 1- , , ( = 3 0 2), , 1. : (0; 0) - (1; 1), (1; 0) - (2; 1), (0; 1) - (1; 2) (1; 1) - (2; 2). 6 . , 48 ( , 0) - ( , 2), , . . 2 . , 0.
2




43

. 2. 1-. : ( + 1) () 0 1 2 0 0 0 0 1 1 0 0 2 1 1 0

, , : ( , , 1) - ( + 1, + 1, 0), ( , , 2) - ( + 1, + 1, 0), ( , , 2)-( +1, +1, 1) ( , , )-( +1, +1, ) , {0, 1}, 3 48 . 0. . 3 . , , : ( + 1) () 0 1 2 0 0.4 0 0 1 1 0.4 0 2 0.8 1 0.4
1

, :

, -


44

. .

. 3. . ( , , 1) - ( + 1, , 0), ( , , 2) - ( + 1, , 0),( , , 2) - ( + 1, + 1, 1), 0; ( , , ) - ( + 1, , ), 0,4; ( , , 0) - ( + 1, , 2), 0,8. ( {0, 1}; , 3 ) . 4 . .

. 4. 1.

6.2.
: ,




45

, . , ( T- ). , ( , , 0) - ( + 1, , 2) 1- 0 1 0,8. , 0.

6.3.
, NP-, . , , , . , , 2. , . , . , . , . (0, 0, ), (1, 1, ), (2, 2, ) , , = 0, = 1, = 2. (0, 0), (1, 1) (2, 2) (0, 0, 1), (0, 0, 1), (1, 1, 0), (1, 1, 2), (2, 2, 0), (2, 2, 1). (0, 0, 0), , (1, 0, 2) (0, 1, 2) ( 1-). , . (1, 2, 0) (2, 1, 0) ( (2, 2, 2)). :


46

. .

1 2

0 0 0;1 0;1;2

1 0;1 1 1;2

2 0;1;2 1;2 2

0 1 2

, (1, 0), (2, 0) (2, 1). (1, 0, 1) - (2, 1, 1), 1 (1, 0, 1) - (2, 0, 0), 1- (1, 0, 0) - (2, 1, 2), (1, 0, 0) - (2, 0, 2) (2, 0, 0) - (2, 1, 2). : (1, 0, 0) - (2, 0, 0/1) - (2, 1, 1) (1, 0, 1) - (2, 0, 1/2) - (2, 1, 2). (0, 1), (0, 2) (2, 1) (0, 1, 0) - (0, 2, 0/1) - (1, 2, 1) (0, 1, 1) - (0, 2, 1/2) - (1, 2, 2). 16 , . , , . , ( 1, 2) = 1 1. , , 1 0.

7.
- . NP- , .




47

, - - , , ., , [2]. , , , (, ) . . . , . . . . .


[1] . . - // . 2011. . 15, . 1­4. . [2] . . . .: - , 1982. [3] . ., . . - // V . , 17­19 1999 . . . . 460­463. [4] . . // . 2001. . 6, . 1­4. . 341­364. [5] . . . .: -, 1998.


48

. .

[6] Aspvall B., Plass M. F., Tarjan R. E. A linear-time algorithm for testing the truth of certain quantified b o olean formulas // Information Pro cessing Letters. 8 (3). 1979. P. 121­123. [7] Even S., Itai A., Shamir A. On the complexity of timetable and multicommo dity flow problems // SIAM J: Comput. 5. 1976. P. 691­703. [8] Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. NY: Plenum Press, 1974. P. 85­103. [9] Ryjov A. P. Basic principles and foundations of information monitoring systems // Monitoring, Security, and Rescue Techniques in Multi-agent Systems. Springer, 2005. P. 147­160. [10] Usama M. Fayyad (Ed.) Advances in Knowledge Discovery and Data Mining. MIT Press, 1996.