Теория алгоритмов. Полный конспект лекций по курсу

  • Published on
    08-Dec-2016

  • View
    235

  • Download
    11

Embed Size (px)

Transcript

<ul><li><p> 1</p><p> , . .-. . . . , 2003 2004.</p><p>1 ( -, 9 . .) , . , , .</p><p> 1 , - , - .</p><p> :</p><p>1. . , , , - , - .</p><p>2. , - . , .</p><p>3. . - , - ( ).</p><p> , . , , </p><p>1 , PD02-1.1-475</p><p>1</p></li><li><p>: ( ) , , , - . - ( : , , - ). ; - , , .</p><p> , , , . , , , , - - . , , , , . , - .</p><p> : , - - . , , , ,, . , , , , , : , -, . , , . , . , , . , -, . . , , , , ... .</p><p> , , , -</p><p>2</p></li><li><p> . . , , : , , 2.</p><p>, : , - . , , . , : . - . . : , , : , . . - , . :</p><p>1. - : , , .</p><p>2. (. . 10- )., , , .</p><p>3. . - , : ?</p><p>, - , ( ) - , . , - - . </p><p>2 , - . , - , . , -, - , , . , ( ).</p><p>3</p></li><li><p>, ? , !</p><p>, - , - ( , 1). , . 3.</p><p> , ( - ) . , , , . ,, . , , , .</p><p> , , /. ( ) , - - (, ). , - ( , ). , , . - , . - , , .</p><p> , , - . , , , , . , - , , . , -, , </p><p>3 -, . .</p><p>4</p></li><li><p> - , .</p><p> , , - .</p><p> 2 , - .</p><p> .</p><p>1. . - , -, . ; , , .</p><p>2. - . , - .</p><p>3. - -. - -, ( - ).</p><p>4. . - , .</p><p>5. - . , - , .</p><p>5</p></li><li><p>6. - . , .</p><p>7. N N . - , -.</p><p>8. . - 1, . - .</p><p> 3 - .</p><p> N Q, - N2, . N N2 : , . - N, , : , .</p><p> 4 , , .</p><p> - : - . , ( , - ), , . - .</p><p>6</p></li><li><p> . , , .</p><p> , - , .</p><p>1. , . - , , , : " , - ?"</p><p>2. , . , ( ) , .</p><p>3. , , , computer science. .</p><p>4. , , - . - .</p><p> , . . , . . - , - . , ( ), .</p><p>2 , , .</p><p>7</p></li><li><p> - . , - 4 . w |w|. w - 0 &lt; i 6 |w| (w)i i- w. . , e ( , e -).</p><p> - , ( 2 3). , ( e ).</p><p> , - . w v , w, v. w v - wv.</p><p> , ( wv vw, u, v w - u(vw) = (uv)w). : , w we = ew = w.</p><p> , w v, u, v = wu. w v, w 4 v.</p><p> .</p><p> 5 - Q, , , s, F , Q , s Q, F Q, : Q Q 5 Q Q.</p><p>4 . , N {0, 1, 2, . . .}.</p><p>5 , q Q, a (q, a) (q, a)</p><p>8</p></li><li><p> M = Q, , , s, F . M ( , ; , ). Q - M , . s Q, . s - M M . F M , - . , -; q1, q2 Q a q2 = (q1, a), , M q1 q2 a.</p><p> , - , - . - - . .</p><p> :</p><p>s</p><p>k</p><p>q0 q1</p><p>b</p><p>a</p><p>a b</p><p>. 1:</p><p> , a b, {q0, q1}, q0 , - {q1}, </p><p>9</p></li><li><p> :</p><p>q x (q, x)q0 a q0q0 b q1q1 a q0q1 b q1</p><p> M = Q, , , s, F pM :Q Q, , M M . q Q w pM(q, w) w :</p><p>1. pM(q, e) = q;</p><p>2. w a pM(q, wa) = (pM(q, w), a)., pM , .</p><p> q1, q2 Q w pM(q1, w) = q2, , - M q1 q2 w. pM : pM(q, w) - , , , q, w - . , , M , 1, , q0 baba - : , b, q0 q1, a q1 q0, , b, q1, q0. , pM(q0, baba) = q0. pM(q1, baba) = q0, pM(q0, abb) = q1 . .</p><p> pM : w, v q - M , pM(q, wv) = pM(pM(q, w), v). , , v.</p><p> , w M =Q, , , s, F , pM(s, w) F , M </p><p>10</p></li><li><p> w -. , M , L(M) , M .</p><p> , -. , {, }. , M , , w, : , w L(M)?</p><p> , . , . , -, ; , . . , . , - , , . , , . , , - , .</p><p> , . -, - (, ), - . - , . -, - , - . ... -, , , , , - , . , , , , - . -</p><p>11</p></li><li><p> 6. , - (, , 256 , - 28256220 , ). , , - .</p><p> , - , , .</p><p> 6 A A A.</p><p> . - , ( ), . . , - x, y x y, x y. R - A a, b A , : aRb. , a, b R, - . , , 2 6 3 , 2, 3 6.</p><p>6 , . , -. , , : . - : - , . , , , , .</p><p>12</p></li><li><p> R A. , R:</p><p>1. , a A aRa;2. , a, b, c A, aRb bRc,</p><p> aRc;</p><p>3. , a, b A aRb bRa;4. , a, b A aRb bRa </p><p>a = b.</p><p> . , -. - ( , -). , ; , - , - 7.</p><p> 7 -, , .</p><p> - . - .</p><p> 1 R - A. B, :</p><p>1. B A;</p><p>2. b1, b2 B b1 6= b2, b1 b2 = ;7 . -</p><p>, , - .</p><p>13</p></li><li><p>3. A =</p><p>bB b;</p><p>4. a1, a2 A a1Ra2 , b B a1, a2 b.</p><p>. a A. [a] A, x A, x a R, {x A : aRx}. B = {[a] : a A}. , B .</p><p> B , [a] B, , R, a [a] [a] 6= . - : , a A B (, [a]), , B A, B.</p><p> a1, a2 A a1 [a2]; , [a1] = [a2]. a [a1]. a1Ra. a1 [a2], a2Ra1. R , a2Ra, a [a2]. , , a [a2]. a2Ra. a1 [a2], a2Ra1 , R, a1Ra2. R a1Ra, a [a1].</p><p> . [a1], [a2] B [a1] [a2] 6= . a [a1] [a2]. [a1] = [a] [a] = [a2]; , [a1] = [a2].</p><p> . a1Ra2, a2 [a1], [a1] = [a2] a1, a2 [a1]. , a1, a2 [a]. [a1] = [a],[a2] = [a] [a1] = [a2]. a2 [a2], a2 [a1], , a1Ra2.</p><p> B. B - 1 4; , B = B.</p><p> b B, a A a b. , b = [a]. a b, , 4, aRa a [a]. , , a [a]. aRa , 4, a a - B., 2, a B, b. , a b.</p><p>, B B. b B. 1 a A, a b. b = [a] , , b B.</p><p> . b B. b = [a] - a A. 3 b B, a b. , , b = [a]. b = b b B. </p><p>14</p></li><li><p> B, - 1, - A R A/R. - - . a A , a, [a]R( [a], , ) x A, aRx. A - , R. - A/R A . 1 -, . : - , .</p><p> - : R = {n,m : n m (mod 5)}. - . - N/R - : [0] = {0, 5, 10, . . .}, [1] = {1, 6, 11, . . .}, [2] = {2, 7, 12, . . .},[3] = {3, 8, 13, . . .}, [4] = {4, 9, 14, . . .}.</p><p> . M = Q, , , s, F - . : w, v w M v , pM(s, w) = pM(s, v). : , , . w - [w]M , - M -, w. - </p><p>/M :</p><p> , M . - - </p><p>/M </p><p> M , .</p><p> . L . L : L=</p><p>{w, v : u wu L , vu L}. 8. ( -</p><p>8, , , c.</p><p>15</p></li><li><p>- /L) o(L). L</p><p>o(L) , .</p><p> 1 L . -:</p><p>1. l /L , l L, l L = ;</p><p>2. w, v, u w L v, wu L vu.</p><p>. l /L . l , w, v l, w L v 6 L. we L, ve 6 L w 6L v. , w v .</p><p> . w L v. , x (wu)x L (vu)x L. , (wu)x = w(ux) (vu)x = v(ux). </p><p> 1 , l L, u w l wu . lu. : w, v (lw)v = l(wv). , x l. x(wv) l(wv), xw lw (xw)v (lw)v. x(wv) =(xw)v. , (lw)v l(wv) , , .</p><p> 2 (-) L - . .</p><p>1. L - , o(L) - .</p><p>2. o(L) &lt; , - , o(L), L.</p><p>16</p></li><li><p>. L M = Q, , , s, F . w, v w M v w L v. , pM(s, w) =pM(s, v), u pM(s, wu) = pM(pM(s, w), u) =pM(pM(s, v), u) = pM(s, vu) wu L pM(s, wu) F pM(s, vu) F vu L.</p><p> , m /M - l /L , m l. , m </p><p>/M .</p><p> w , w m. w - l /L , w l. v m, w M v,w L v v l.</p><p> , l /L , - m /M , m l ( l 6= , m = [w]M w l). , L , M 9. M ; , M .</p><p> ; . Q = /L .</p><p> s Q, [e]L , F Q, {q Q : q L}. q Q a (q, a) qa10., M = Q, , , s, F ., M L.</p><p> , w pM(s, w) = sw. w. w = e , se = s = pM(s, e). w = va a v . pM(s, w) = (pM(s, v), a) = (sv)a = s(va) =sw.</p><p> , w M w , w L. ,w L ew L sw L, ew sw , 1, L , , L. sw </p><p>9 . , , .</p><p>10 a , .</p><p>17</p></li><li><p>L sw F , sw = pM(s, w). 2 . </p><p> ( ) - .</p><p> M = Q, , , s, F - L. L , - L11 - . , , l /L l = [w]L , w l , . , .</p><p> 2 , - L - M . - M M , , - - . , , . , , .</p><p> , M Q, , - M . q Q - , w, pM(s, w) = q. - M L. , Q - , Q -</p><p>11 - o(L), - </p><p>/L . </p><p>, , .</p><p>18</p></li><li><p> , M L. -, Q, - q q , q q M L.</p><p>, q q , (u )(pM(q, u) F pM(q, u) F ). , m m - M , q q v m,v m . q = pM(s, v), q = pM(s, v) q q v L v. , v L v , (u )(vu L vu L), , , - (u )(pM(s, vu) F pM(s, vu) F ). pM(s, vu) =pM(pM(s, v), u) = pM(q, u) pM(s, vu) = pM(pM(s, v), u) = pM(q, u), .</p><p> 0,1, . . . Q : n N n= {q, q : u , |u| 6 n, pM(q, u) F pM(q, u) F}.12 01 . . . =</p><p>nN n. Q Q -</p><p>, - n n=n+1 =n. : n+1=n {q, q : (a )((q, a) n (q, a))}. -, q n+1 q , , -, u 6 n pM(q, u) F pM(q, u) F , , -, u, 1 6 |u| 6 n + 1, pM(q, u) F pM(q</p><p>, u) F . , q n q, - , a (q, a) n (q, a), &gt; 1 au, a |u| 6 n.</p><p> - , n+1 n, - n. , n=m, n+1=m+1. , n=n+1</p><p>12 , , Q. , , , - .</p><p>19</p></li><li><p> n+1=n+2 01 . . . - , , , ., , 0 - , 0,1, . . ., , n N n n+1 -. n , , =n.</p><p>, , - - </p><p>/L </p><p>Q/ , - 2 </p><p>/L , </p><p> L Q</p><p>/. l </p><p>/L l -</p><p> Q/ ( f(l)) {pM(s, w) :</p><p>w l}. , f([e]L) = [s], l L f(l) F a l = la , 13 q f(l) (q, a) f(l). , , Q</p><p>/, [s], </p><p> {p Q/ : p F}, p Q/ a - Q</p><p>/, -</p><p> [(q, a)] q p, L .</p><p> - . . - M = Q, , , s, F = {a, b} 2.</p><p>, q3 q7 q0. . Q {q0, q1, q2, q4, q5, q6}. , Q, n, 0 . . . n=n+1.</p><p> i, i 6 n, - ( -). q, q Q q 0 q , w 0 pM(q, w) F pM(q, w) F . 0, e, q 0 q </p><p>13, , q f(l). , q q (q, a) (q, a) a .</p><p>20</p></li><li><p>K</p><p>U ?</p><p>]</p><p>U</p><p>]</p><p>U</p><p>- </p><p>- j</p><p>Y</p><p>K</p><p> q0 q1 q2 q3</p><p>q4 q5 q6 q7</p><p>ab</p><p>a</p><p>b</p><p>b a a b a a b</p><p>b b a</p><p>a, b</p><p>. 2:</p><p>q = pM(q, e) F F 3 pM(q, e) = q 0 2 , {q0, q2} {q1, q4, q5, q6}14.</p><p>, q, q Q q 1 q , q 0 q (a )((q, a) 0 (q, a)). , q 1 q, q 0 q. (q0, a) = q1 0 q1 =(q2, a) (q0, b) = q4 0 q6 = (q2, b), q0 1 q2. q5 (q5, a) = q5 60 q0 = (q4, a), (q5, a) = q5 60 q2 = (q6, a) (q5, b) = q5 60 q2 = (q1, b) , , q5 61 q4, q1, q6. q1(q1, b) = q2 60 q5 = (q4, b) = (q6, b) q1 61 q4, q6. , (q4, a) =q0 0 q2 = (q6, a), (q4, b) = q5 0 q5 = (q6, b) q4 1 q6. , 1 4 : {q0, q2}, {q1}, {q4, q6} {q5}.</p><p> 2 2 . q0, q2 (q0, a) = q1 1 q1 = (q2, a) (q0, b) = q4 1 q6 = (q2, b), q0 2 q2. q4, q6 (q4, a) = q0 1 q2 = (q6, a), (q4, b) = q5 1q5 = (q6, b) q4 2 q6. , 2 1 </p><p>14 , - Q/0 {{q Q : q F}, {q Q : q 6 F}} \ {}.</p><p>21</p></li><li><p> . M = Q, , , s, F ( </p><p> Q), M - , , p0 ={q0, q2}, p1 = {q1}, p2 = {q4, q6} p3 = {q5} (. 3). M s = p0, p0 3 q0 q0 M . F - {p0}, p0 Q, M . . q0 p0 (q0, a) = q1 p1, (q0, b) = q4 p2, (p0, a) = p1 (p0, b) = p2. - (p1, a) = p3, (p1, b) = p0 (q1 p0 (q1, a) p3, (q1, b) p0);(p2, a) = p0, (p2, b) = p3 (q4 p2 (q4, a) p0, (q4, b) p3); (p3, a) =(p3, b) = p3 (q5 p3 (q5, a), (q5, b) p3). M . - Q</p><p>/ </p><p>/L p0</p><p> [e]L , p1 [a]L , p2 [b]L p3 [aa]L = [bb]L .</p><p>K</p><p>U</p><p>j</p><p>Y</p><p>-</p><p>?N</p><p> p0 p1</p><p>p2 p3</p><p>a</p><p>b</p><p>b a a</p><p>b</p><p>a, b</p><p>. 3:</p><p> ( 38) , 2 - , .</p><p> -, .</p><p>22</p></li><li><p> 8 - Q, , , s, F , Q , s Q, F Q, Q({e})Q.</p><p>, -, , . , , Q . . , , . q1, q2 Q, a q1, a, q2 , , q1 - q2 a. q1, e, q2 , , q1 q2.</p><p> , - . - , , - , , - . , . , - q1, q2 a q1 q2 a, , q1 , q2, a. q1 q2, q1 q2 , e.</p><p> , - , , -. , , . -, , , . , , . , Q, , , s, F - , q1 Q, x - q2 Q, q1, x, q2 ( q2 q1 x) </p><p>23</p></li><li><p> q1, q2, q1, e, q2 - .</p><p> , , , , - . , - q x. - , q x, . , , - - . , , , - , (. . , e, ).</p><p> , , . , , , - , , - . , , - ; , : , . , , , . , - , .</p><p> . , - Q, , , s, F q Q p Q w , - q0, q1, . . . , qn Q t : {0, . . . , n} N, q0 = q, qn = p, t(0) = 0, t(n) = |w| i &lt; n t(i+1) = t(i) qi, e, qi+1 , t(i+1) = t(i)+1 qi, (w)t(i+1), qi+1 .</p><p> -, , q0, . . . , qn , , w, t(i) </p><p>24</p></li><li><p> w, - qi.</p><p> , - M = Q, , , s, F q Q w , PM(q, w). , w, PM(s, w) - F , PM(s, w) F 6= . , , M L(M) , .</p><p> - ., , , = {a, b, c}, , - . (, , , - 3). - , .</p><p>-</p><p>@@</p><p>@@</p><p>@@@R</p><p>-</p><p>-</p><p>-</p><p>@@</p><p>@@</p><p>@@@R</p><p>-</p><p>a, b, c a</p><p>b</p><p>c</p><p>a</p><p>b</p><p>c</p><p>a</p><p>b</p><p>c</p><p>. 4:</p><p> , -</p><p>25</p></li><li><p> , , . , - , , . -, , , , . , , - , , , , , , , .</p><p>, . 1, - , , . -.</p><p> , , - , , , . - . 3, - .</p><p> 2 M = Q, , , s, F , w a , PM(s, wa) =</p><p>qPM (s,w) PM(q, a).</p><p>. , p , . p PM(s, wa). - q0, . . . , qn Q t : {0, . . . , n} N, q0 = s, qn = p, t(0) = 0, t(n) = |wa| i &lt; n t(i+1) = t(i) qi, e, qi+1 , t(i+1) = t(i)+1 qi, (wa)t(i+1), qi+1 . , t - {0, . . . , n} {0, . . . , |wa|}15., k &lt; n, t(k) = |w|.</p><p>15 . m 6 |wa|, </p><p>26</p></li><li><p> q = qk. q PM(s, w), q0, . . . , qk t, {0, . . . , k} N, . - q0, . . . , qnk t : {0, . . . , n k} N, i 6 nk qi = qk+i t(i) = t(k+ i)|w|. , , p PM(q, a). p PM(q, a) q PM(s, w), , , p .</p><p> . p qPM (s,w) PM(q, a), q PM(s, w) p PM(q, a). q. q PM(s, w), q0, . . . , qk t : {0, . . . , k} N, q0 = s,qk = q, t(0) = 0, t(k) = |w| i &lt; k t(i + 1) = t(i) qi, e, qi+1 , t(i + 1) = t(i) + 1 qi, (w)t(i+1), qi+1 . p PM(q, a), q0 , . . . , qm t : {0, . . . , m} N, q0 = q, qm = p, t(0) = 0, t(m) =1 i &lt; m t(i+1) = t(i) qi , e, qi+1 , t(i+1) = t(i) + 1 qi , (a)t(i+1), qi+1 . q0, . . . , qk+m t : {0, . . . , k +m} N, i 6 k qi = qi t(i) = t(i), k &lt; i 6 k+m qi = qik t(i) = t(ik)+ |w|. , , p PM(s, wa). </p><p> 1 M =Q, , , s, F , w, v a PM(s, w) = PM(s, v), PM(s, wa) = PM(s, va).</p><p>. . </p><p> 3 - , .</p><p> t. t(0) = 0, m &gt; 0. m , i 6 n, t(i) = m 1. i0 i. t(n) = |wa| &gt; m &gt; m 1 = t(i0), i0 6= n. t(i0 + 1) = t(i0), i0 . t(i0 + 1) =t(i0) + 1, , t(i0) = m 1, t(i0 + 1) = m m t. .</p><p>27</p></li><li><p>. , , , - . .</p><p> M = Q, , , s, F -. M , L(M ) = L(M).</p><p> M Q = {PM(s, w) : w }. , w - , Q , Q, . M Q, PM(s, e), S. F Q, {PM(s, w) : w PM(s, w)F 6= }., , . - .</p><p> P = PM(s, w) Q a . (P, a) PM(s, wa). , P = PM(s, v) v, w, , 1, PM(s, wa) = PM(s, va).</p><p> M . , - , , w pM (S, w) = PM(s, w). . w a . pM (S, wa) = (pM (S, w), a) = (PM(s, w), a) = PM(s, wa). - pM , , .</p><p> , w...</p></li></ul>