Лекция №1. Введение. Предмет "Теория вычислительных процессов"

  • Published on
    02-Jul-2015

  • View
    5.029

  • Download
    8

Embed Size (px)

Transcript

<ul><li> 1. . .. : . - , www.grebenshikov.ru </li></ul> <p> 2. , , : ? 10 . .1 3. 18 9 46 2 4. 4 4 8 : 87 , 73 , 60 - 3 5. 59 . . . : 1 . 4 6. - .. -. . -: . . - .:, 1989. - 264 . .., .. . -.: , 1991. - 248 . . -: . . - .: , 1984. - 264 .5 7. ? depottutorials - 6 8. - - , - , , , - . . ( , ,, , ) . ( - ) . ( , )7 9. () . (, , - ) .( ) 8 10. - - - , . . - , . - - .9 11. - () - , - . - , - - . - - . - 10 12. - - . ! ? 11 13. - . - . ? - . 12 14. . - - ().:D = {, , , , , , },D1 = {, , , , , , }.D D113 15. x A - x Ax A - x A /A = {x|p(x)} - - {} - 14 16. A B - , - A = B - A B .15 17. A= {x|x A} - -/ U .A B = {x|x A x B} - ;A B = {x|x A x B} - ;A B = {x|x A x } - ./ 16 18. :(A B) C = A (B C), (A B) C = A (B C) : A B=B A, A B=BA : AA = U, AA= : AU = U, A U =A : A = ,A= : (A)= A17 19. : (A B)= A B, (A B)= A B :A (B C) = (A B) (AC), A (B C) = (A B) (A C)18 20. X X - X Y Y Z X Z - . 19 21. A1 A2 . . . An = {&lt; a1, a2, . . . , an &gt; |a1 A1, a2 A2, . . . , an An} - () .An = A A A . . . A (n ) - A20 22. R - A B, R A B.&lt; x, y &gt; R xRydR = {x|y, &lt; x, y &gt; R} - rR = {x|y, &lt; y, x &gt; R} - R1 = {&lt; x, y &gt; | &lt; y, x &gt; R} - 21 23. R(X) = {y|x X, &lt; x, y &gt; R} - X - RR1(X) - X RR1R2 = {&lt; x, y &gt; |z, &lt; x, z &gt; R1 &lt; z, y &gt; R2} - - R1 = A B R2 = B C22 24. R A : , &lt; x, x &gt; R x A; , &lt; x, y &gt; R &lt; y, x &gt; R; , &lt; x, y &gt; R &lt; y, x &gt; R x =y; , &lt; x, y &gt; R &lt; y, z &gt; R &lt; x, z &gt; R. 23 25. - - , .[x]R = x/R = {y| &lt; x, y &gt; R} - x R.A/R - - ( - ) A R.24 26. - - . () - , - , . - A, A .25 27. f A B ( A B), df = A, rf B x, y1, y2 &lt; x, y1 &gt; f &lt; x, y2 &gt; f y1 = y2. f : A B. y = f (x) &lt; x, y &gt; f y f . f : A B - A B, df = A, rf = B y = f (x1), y = f (x2) x1 = x2.26 28. A B f A B. f - , x1 x2 f (x1) f (x2) x1, x2 A. f : X Y n- A, Y = A X = An. , - - {0, 1}. - , P : X {0, 1} x X, P (x) = 1, , P (x) = 0. X P : X 2 {0, 1}.27 29. - .V1 = {a, b}, V2 = {0, 1}, V3 = {a, +, 1, =} .a + 1 = 1 + a V3, 101011 - V2, abbab V1. , - . V V .n- V - n- V , . . V V . . . V (n ) V . 28 30. G = (V, E, ) - , V - - , , (V {w})2, w V ./ e , (e) = (w, u), u V {w}; , (e) = (u1, u2), u1, u2 V ; - , (e) = (u, w), u V {w}. e, - , ; (e) = (w, w)., , - . 29 31. , e u, e u u. , . u u, , (e) = (u, u). G . . . , ui, ei, ui+1, . . . , , i(ei) = (ui, ui+1). - , - . u1, u2 G , u1 = u2 1, . . . , n G , 1 u1, n u2. 30 32. 31 </p>