Алгоритмы для NP-трудных задач, осень 2009: Алгоритмы расщепления

  • Published on
    12-Feb-2017

  • View
    87

  • Download
    1

Embed Size (px)

Transcript

<ul><li><p> NP- 8: </p><p>. </p><p>Computer Science http://logic.pdmi.ras.ru/infclub/</p><p>. (Computer Science ) 8. 1 / 20</p><p>http://logic.pdmi.ras.ru/~infclub/</p></li><li><p>1 </p><p>2 </p><p>. (Computer Science ) 8. 2 / 20</p></li><li><p>1 </p><p>2 </p><p>. (Computer Science ) 8. 2 / 20</p></li><li><p>1 </p><p>2 </p><p>. (Computer Science ) 8. 3 / 20</p></li><li><p> 2-</p><p> 2- (maximum 2-satisfiability) , 2- ( ). NP- ( 2-). 2- .</p><p>. (Computer Science ) 8. 4 / 20</p></li><li><p> 2-</p><p> 2- (maximum 2-satisfiability) , 2- ( ).</p><p> NP- ( 2-). 2- .</p><p>. (Computer Science ) 8. 4 / 20</p></li><li><p> 2-</p><p> 2- (maximum 2-satisfiability) , 2- ( ). NP- ( 2-).</p><p> 2- .</p><p>. (Computer Science ) 8. 4 / 20</p></li><li><p> 2-</p><p> 2- (maximum 2-satisfiability) , 2- ( ). NP- ( 2-). 2- .</p><p>. (Computer Science ) 8. 4 / 20</p></li><li><p> n K L </p><p> n m </p><p> , . .</p><p>. (Computer Science ) 8. 5 / 20</p></li><li><p> n K L </p><p> n m </p><p> , . .</p><p>. (Computer Science ) 8. 5 / 20</p></li><li><p>: K K2</p><p>(x a) (x b) (x c) (x d) (x e) . . .XXXXXXXXz</p><p>9x = 1 x = 0(d) (e) . . . (a) (b) (c) . . .</p><p>K = 3 K = 2</p><p>K2 = 5 K2 = 5</p><p>K2 K</p><p>K2 : K2(F ) = 0, F </p><p>. (Computer Science ) 8. 6 / 20</p></li><li><p>: K K2</p><p>(x a) (x b) (x c) (x d) (x e) . . .XXXXXXXXz</p><p>9x = 1 x = 0(d) (e) . . . (a) (b) (c) . . .</p><p>K = 3 K = 2</p><p>K2 = 5 K2 = 5</p><p>K2 KK2 : K2(F ) = 0, F </p><p>. (Computer Science ) 8. 6 / 20</p></li><li><p>: K K2</p><p>(x a) (x b) (x c) (x d) (x e) . . .XXXXXXXXz</p><p>9x = 1 x = 0(d) (e) . . . (a) (b) (c) . . .</p><p>K = 3 K = 2</p><p>K2 = 5 K2 = 5</p><p>K2 KK2 : K2(F ) = 0, F </p><p>. (Computer Science ) 8. 6 / 20</p></li><li><p>: K K2</p><p>(x a) (x b) (x c) (x d) (x e) . . .XXXXXXXXz</p><p>9x = 1 x = 0(d) (e) . . . (a) (b) (c) . . .</p><p>K = 3 K = 2</p><p>K2 = 5 K2 = 5</p><p>K2 KK2 : K2(F ) = 0, F </p><p>. (Computer Science ) 8. 6 / 20</p></li><li><p> Ni , i2-.</p><p> 2-: K2 =Ni=1</p><p>i2Ni</p><p> : = N3 + 1.9 N4 +Ni=5</p><p>i2Ni</p><p>K2 -q q q q q q qN1 N2 N3 N4 N5 N60 0.5 1 1.5 2 2.5 3</p><p> -q q q q q qN1,N2 N3 N4 N5 N6</p><p>. (Computer Science ) 8. 7 / 20</p></li><li><p> 2K/5.5</p><p>MAX-2-SAT poly(K ) 2K/5.5, K F .</p><p> 2/5.5; , K2 K , 5.5</p><p>. (Computer Science ) 8. 8 / 20</p></li><li><p> 2K/5.5</p><p>MAX-2-SAT poly(K ) 2K/5.5, K F .</p><p> 2/5.5; , K2 K , 5.5</p><p>. (Computer Science ) 8. 8 / 20</p></li><li><p> 2K/5.5</p><p>MAX-2-SAT poly(K ) 2K/5.5, K F .</p><p> 2/5.5; , K2 K</p><p> , 5.5</p><p>. (Computer Science ) 8. 8 / 20</p></li><li><p> 2K/5.5</p><p>MAX-2-SAT poly(K ) 2K/5.5, K F .</p><p> 2/5.5; , K2 K , 5.5</p><p>. (Computer Science ) 8. 8 / 20</p></li><li><p>0 1 1.9 2.5 3 -q qq qq qq qq q</p><p>N1,N2 N3 N4 N5 N6</p><p> , 2-</p><p> 2-: 3+ 6 0.5 = 6 2-: 2.5+ 5 0.6 = 5.5 2-: 1.9+ 4 0.9 = 5.5</p><p>. (Computer Science ) 8. 9 / 20</p></li><li><p>0 1 1.9 2.5 3 -q qq qq qq qq q</p><p>N1,N2 N3 N4 N5 N6s s</p><p> , 2- 2-: 3+ 6 0.5 = 6</p><p> 2-: 2.5+ 5 0.6 = 5.5 2-: 1.9+ 4 0.9 = 5.5</p><p>. (Computer Science ) 8. 9 / 20</p></li><li><p>0 1 1.9 2.5 3 -q qq qq qq qq q</p><p>N1,N2 N3 N4 N5 N6s s</p><p> , 2- 2-: 3+ 6 0.5 = 6 2-: 2.5+ 5 0.6 = 5.5</p><p> 2-: 1.9+ 4 0.9 = 5.5</p><p>. (Computer Science ) 8. 9 / 20</p></li><li><p>0 1 1.9 2.5 3 -q qq qq qq qq q</p><p>N1,N2 N3 N4 N5 N6s s</p><p> , 2- 2-: 3+ 6 0.5 = 6 2-: 2.5+ 5 0.6 = 5.5 2-: 1.9+ 4 0.9 = 5.5</p><p>. (Computer Science ) 8. 9 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2- F , 2-; , (F ) = N(F ) , ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2-</p><p> F , 2-; , (F ) = N(F ) , ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2- F , 2-; , </p><p>(F ) = N(F ) , ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2- F , 2-; , (F ) = N(F )</p><p> , ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2- F , 2-; , (F ) = N(F ) , </p><p> ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>(n, 3)-MAX-2-SAT</p><p> F 2- F , 2-; , (F ) = N(F ) , ( )</p><p>. (Computer Science ) 8. 10 / 20</p></li><li><p>1 </p><p>2 </p><p>. (Computer Science ) 8. 11 / 20</p></li><li><p> , , , , .</p><p>{y = 0} </p><p>(x y z) (x y) (y z) (y z).</p><p>. (Computer Science ) 8. 12 / 20</p></li><li><p> , , , , .</p><p>{y = 0} </p><p>(x y z) (x y) (y z) (y z).</p><p>. (Computer Science ) 8. 12 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n. t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2. , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n. t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2. , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n. t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2. , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n.</p><p> t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2. , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n. t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2.</p><p> , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p> k-SAT 2n ?</p><p> (x1 x2 xt) F k- F [x1 = 1],F [x1 = 0, x2 = 1],F [x1 = 0, x2 = 0, x3 = 1],. . .F [x1 = 0, x2 = 0, . . . , xt1 = 0, xt = 1].</p><p> (1, 2, . . . , t)- n. t k , (1, 2, . . . , t) (1, 2, . . . , k) = ck &lt; 2. , cnk .</p><p>. (Computer Science ) 8. 13 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)</p><p>F [a = 0] = F C1 Cp F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>,</p><p>F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , .</p><p> F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a).</p><p> , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0.</p><p> F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p>F = F (a C1) (a Cp) (a D1) . . . (a Dq)F [a = 0] = F C1 Cp </p><p>F0</p><p>, F [a = 1] = F D1 Dq F1</p><p>, F0 , . F0 , F [a = 0] ( 1 a). , F0. F [a = 0] , , F . , F [a = 1].</p><p>. (Computer Science ) 8. 14 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p> F F0 , , F</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p> F F0 , , F</p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p> F F0 , , F</p><p> , F </p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> : </p><p>F</p><p>F F0 F F1</p><p>a = 0 a = 1</p><p> F0</p><p> F0 , </p><p> , F0</p><p> F F0 , , F</p><p> , F </p><p>. (Computer Science ) 8. 15 / 20</p></li><li><p> F n .</p><p> F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 . F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1].</p><p> d- a. F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 . F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 . F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1.</p><p> a d-, F0 d F0 . F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 .</p><p> F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 . F0 , F [a = 0] ( 1 a).</p><p> = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p> F n . F a, a, a d ( d = d() ), F [a = 0] F [a = 1]. d- a.</p><p> F [a = 0] = F F0, F [a = 1] = F F1. a d-, F0 d F0 . F0 , F [a = 0] ( 1 a). = {l1, . . . , lt}, F0.</p><p>. (Computer Science ) 8. 16 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0. F [a = 0]. F [a = 0] , F . F [a = 0] , F (F [a = 0] = F F0). , F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0.</p><p> F [a = 0]. F [a = 0] , F . F [a = 0] , F (F [a = 0] = F F0). , F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0. F [a = 0].</p><p> F [a = 0] , F . F [a = 0] , F (F [a = 0] = F F0). , F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0. F [a = 0]. F [a = 0] , F .</p><p> F [a = 0] , F (F [a = 0] = F F0). , F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0. F [a = 0]. F [a = 0] , F . F [a = 0] , F (F [a = 0] = F F0).</p><p>, F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>, a d-, F [a = 0] = F F0,F [a = 1] = F F1, = {l1, . . . , lt} F0. F [a = 0]. F [a = 0] , F . F [a = 0] , F (F [a = 0] = F F0). , F [a = 1] : F [a = 1, l1 = 0],F [a = 1, l1 = 1, l2 = 0], . . . ,F [a = 1, l1 = 1, l2 = 1, . . . , lt1 = 1, lt = 0].</p><p>. (Computer Science ) 8. 17 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1)</p><p> d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1)</p><p> = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd</p><p>&lt; 2n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>(F ) = n(F ) + w m(F )</p><p> (d+, d+)- (1+ wd , 1+ wd) = 2</p><p>11+wd</p><p> d- (1, 2, . . . , d + 1) d , </p><p> w , 21</p><p>1+wd = (1, 2, . . . , d + 1) = 2</p><p>n+wm1+wd &lt; 2</p><p>n+wn1+wd = cn,</p><p> c = 21+w1+wd &lt; 2 </p><p>. (Computer Science ) 8. 18 / 20</p></li><li><p>, cn, c &lt; 2 , n ., ( ) .</p><p>. (Computer Science ) 8. 19 / 20</p></li><li><p>, cn, c &lt; 2 , n .</p><p>, ( ) .</p><p>. (Computer Science ) 8. 19 / 20</p></li><li><p>, cn, c &lt; 2 , n ., ( ) .</p><p>. (Computer Science ) 8. 19 / 20</p></li><li><p> !</p><p>. (Computer Science ) 8. 20 / 20</p></li></ul>

Recommended

View more >