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

  • View
    235

  • Download
    11

Embed Size (px)

Transcript

  • 1

    , . .-. . . . , 2003 2004.

    1 ( -, 9 . .) , . , , .

    1 , - , - .

    :

    1. . , , , - , - .

    2. , - . , .

    3. . - , - ( ).

    , . , ,

    1 , PD02-1.1-475

    1

  • : ( ) , , , - . - ( : , , - ). ; - , , .

    , , , . , , , , - - . , , , , . , - .

    : , - - . , , , ,, . , , , , , : , -, . , , . , . , , . , -, . . , , , , ... .

    , , , -

    2

  • . . , , : , , 2.

    , : , - . , , . , : . - . . : , , : , . . - , . :

    1. - : , , .

    2. (. . 10- )., , , .

    3. . - , : ?

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

    2 , - . , - , . , -, - , , . , ( ).

    3

  • , ? , !

    , - , - ( , 1). , . 3.

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

    , , /. ( ) , - - (, ). , - ( , ). , , . - , . - , , .

    , , - . , , , , . , - , , . , -, ,

    3 -, . .

    4

  • - , .

    , , - .

    2 , - .

    .

    1. . - , -, . ; , , .

    2. - . , - .

    3. - -. - -, ( - ).

    4. . - , .

    5. - . , - , .

    5

  • 6. - . , .

    7. N N . - , -.

    8. . - 1, . - .

    3 - .

    N Q, - N2, . N N2 : , . - N, , : , .

    4 , , .

    - : - . , ( , - ), , . - .

    6

  • . , , .

    , - , .

    1. , . - , , , : " , - ?"

    2. , . , ( ) , .

    3. , , , computer science. .

    4. , , - . - .

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

    2 , , .

    7

  • - . , - 4 . w |w|. w - 0 < i 6 |w| (w)i i- w. . , e ( , e -).

    - , ( 2 3). , ( e ).

    , - . w v , w, v. w v - wv.

    , ( wv vw, u, v w - u(vw) = (uv)w). : , w we = ew = w.

    , w v, u, v = wu. w v, w 4 v.

    .

    5 - Q, , , s, F , Q , s Q, F Q, : Q Q 5 Q Q.

    4 . , N {0, 1, 2, . . .}.

    5 , q Q, a (q, a) (q, a)

    8

  • 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.

    , - , - . - - . .

    :

    s

    k

    q0 q1

    b

    a

    a b

    . 1:

    , a b, {q0, q1}, q0 , - {q1},

    9

  • :

    q x (q, x)q0 a q0q0 b q1q1 a q0q1 b q1

    M = Q, , , s, F pM :Q Q, , M M . q Q w pM(q, w) w :

    1. pM(q, e) = q;

    2. w a pM(q, wa) = (pM(q, w), a)., pM , .

    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 . .

    pM : w, v q - M , pM(q, wv) = pM(pM(q, w), v). , , v.

    , w M =Q, , , s, F , pM(s, w) F , M

    10

  • w -. , M , L(M) , M .

    , -. , {, }. , M , , w, : , w L(M)?

    , . , . , -, ; , . . , . , - , , . , , . , , - , .

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

    11

  • 6. , - (, , 256 , - 28256220 , ). , , - .

    , - , , .

    6 A A A.

    . - , ( ), . . , - x, y x y, x y. R - A a, b A , : aRb. , a, b R, - . , , 2 6 3 , 2, 3 6.

    6 , . , -. , , : . - : - , . , , , , .

    12

  • R A. , R:

    1. , a A aRa;2. , a, b, c A, aRb bRc,

    aRc;

    3. , a, b A aRb bRa;4. , a, b A aRb bRa

    a = b.

    . , -. - ( , -). , ; , - , - 7.

    7 -, , .

    - . - .

    1 R - A. B, :

    1. B A;

    2. b1, b2 B b1 6= b2, b1 b2 = ;7 . -

    , , - .

    13

  • 3. A =

    bB b;

    4. a1, a2 A a1Ra2 , b B a1, a2 b.

    . a A. [a] A, x A, x a R, {x A : aRx}. B = {[a] : a A}. , B .

    B , [a] B, , R, a [a] [a] 6= . - : , a A B (, [a]), , B A, B.

    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].

    . [a1], [a2] B [a1] [a2] 6= . a [a1] [a2]. [a1] = [a] [a] = [a2]; , [a1] = [a2].

    . a1Ra2, a2 [a1], [a1] = [a2] a1, a2 [a1]. , a1, a2 [a]. [a1] = [a],[a2] = [a] [a1] = [a2]. a2 [a2], a2 [a1], , a1Ra2.

    B. B - 1 4; , B = B.

    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.

    , B B. b B. 1 a A, a b. b = [a] , , b B.

    . b B. b = [a] - a A. 3 b B, a b. , , b = [a]. b = b b B.

    14

  • B, - 1, - A R A/R. - - . a A , a, [a]R( [a], , ) x A, aRx. A - , R. - A/R A . 1 -, . : - , .

    - : 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, . . .}.

    . M = Q, , , s, F - . : w, v w M v , pM(s, w) = pM(s, v). : , , . w - [w]M , - M -, w. -

    /M :

    , M . - -

    /M

    M , .

    . L . L : L=

    {w, v : u wu L , vu L}. 8. ( -

    8, , , c.

    15

  • - /L) o(L). L

    o(L) , .

    1 L . -:

    1. l /L , l L, l L = ;

    2. w, v, u w L v, wu L vu.

    . l /L . l , w, v l, w L v 6 L. we L, ve 6 L w 6L v. , w v .

    . w L v. , x (wu)x L (vu)x L. , (wu)x = w(ux) (vu)x = v(ux).

    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) , , .

    2 (-) L - . .

    1. L - , o(L) - .

    2. o(L) < , - , o(L), L.

    16

  • . 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.

    , m /M - l /L , m l. , m

    /M .

    w , w m. w - l /L , w l. v m, w M v,w L v v l.

    , l /L , - m /M , m l ( l 6= , m = [w]M w l). , L , M 9. M ; , M .

    ; . Q = /L .

    s Q, [e]L , F Q, {q Q : q L}. q Q a (q, a) qa10., M = Q, , , s, F ., M L.

    , 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.

    , w M w , w L. ,w L ew L sw L, ew sw , 1, L , , L. sw

    9 . , , .

    10 a , .

    17

  • L sw F , sw = pM(s, w). 2 .

    ( ) - .

    M = Q, , , s, F - L. L , - L11 - . , , l /L l = [w]L , w l , . , .

    2 , - L - M . - M M , , - - . , , . , , .

    , M Q, , - M . q Q - , w, pM(s, w) = q. - M L. , Q - , Q -

    11 - o(L), -

    /L .

    , , .

    18

  • , M L. -, Q, - q q , q q M L.

    , 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), .

    0,1, . . . Q : n N n= {q, q : u , |u| 6 n, pM(q, u) F pM(q, u)