39276
23
35

̳



:

.131.13 01 81 01

1 131


..
..

______________________

ʳ : __________

: ECTS _____

񳿠 ________________ ___________________________

() ( )

________________ ___________________________

() ( )

________________ ___________________________

() (

. 2014

, .

, , .

. .

, (x1,x2,,xn),

(x1, x2, , xn, x1, x2, , xn).



:

1 .131.13 01 91 01

1. .

2. matrix.

3. next_top.

4. dejkstra (start).

5. .

6. heapify.

7. .

8. .

9. 00.

10. 00.


̲

7

1. 8

1.1 8
1.2 8
1.3 9
1.4 9
1.5 11
1.6 17
1.7 24

2. 25

2.1 25
2.2 26
2.3 26
2.4 27
2.5 29
2.6 31
2.7 38

3. 39

3.1 39
3.2 39
3.3 39
3.4 40
3.5 41
3.6 42
3.7 44
3.8 44
3.9 44
3.10 46

51

52

1.jpg









- , , . , . :

Ø .

Ø , .

Ø , . , , .

Ø .

. .

, . , , , , . . 0, . 0 , u U, (u=L), (u=R) (u=S).


1.

1.1 .

' G(V, U). a V.

1.2

. ( ), . .

. 1 . , , . 1.

u , , V , di u i, w(i, j) (i, j).

1. U, {u}.

2. , (U=V), .

3. Di V\U.

4. (i, j), i∈U j∈V\U, Dj>di+w(i, j), Dj di+w(i, j).

5. i∈V\U, Di .

6. Di , . di Di, U U∪{i} 2.

1.3

const int N

const int INT_MAX , -

int cost[N][N]

bool adj_matrix[N][N] : adj_matrix[i][j]== true,

i j

int dist[N]

int parent[N] ;

int start ,

bool in_tree[N] i

in_tree[i]==true

int cur ,

int d

int min_dist

int i,j

1.4

1. cost[N][N].

2. matrix, : adj_matrix[i][j]== true, i j .

3. dijkstra(start), start .

4. dist[N] , parent[N] , .


1.4.1 .

2.jpg


1.5

1.5.1 matrix

1. , 1, .

2. , 1, .

3. , . , 5, 4.

4. adj_matrix[i][j]== false.

5. adj_matrix[i][j]== true.

6. .

7. .


1.5.2 C matrix

3.jpg


1.5.3 dejkstra (start)

1. 1, .

2. in_true[i]== false; ( ) dist[i]=INT_MAX ( ).

3. .

4. dist[start] = 0; ( ), cur=start; (, ).

5. , .

6. .

7. 1, .

8. , , . , 9, 12.

9. .

10. , 9 , dist. , 11, 12.

11. dist 9, parent .

12. , 7.

13. next_top, , .

14. , 1.


1.5.4 dejkstra (start)

4.jpg

1.5.5 next_top

1. min_dist=INT_MAX ( ).

2. 1, .

3. , min_dist. , 4, 5.

4. min_dist , , , .

5. , 2.


1.5.6 next_top

5.jpg

1.6

, . 1- . , ( ).

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_m6f5f3b51.png

cur

0

1

2

3

4

5

0

0

7

9

0

0

14

1

0

0

10

15

0

0

2

0

0

0

11

0

2

3

0

0

0

0

6

0

4

0

0

0

0

0

9

5

0

0

0

0

0

0

in_tree

0

0

0

0

0

0

dist

INT_MAX

INT_MAX

INT_MAX

INT_MAX

INT_MAX

INT_MAX

start=0

, - . - 1.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_1b919a36.png

. ̳ 1. 2, 3 6.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_m1b266ff3.png

cur=start=0

dist

0

INT_MAX

INT_MAX

INT_MAX

INT_MAX

INT_MAX

1 - 2, . 1 1 + , 1 2, 0 + 7 = 7. 2, 2- 7.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_61c98bc.png

dist

0

7

INT_MAX

INT_MAX

INT_MAX

INT_MAX

1- 3- 6-.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_6d5c0f3b.png

dist

0

7

9

INT_MAX

INT_MAX

INT_MAX

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_68114e66.png

dist

0

7

9

INT_MAX

INT_MAX

14

1 . 1 (, , ). , , .

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_m5f219574.png

in_tree

1

0

0

0

0

0

. . "" . 2 7.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_a2514f9.png

cur=1

, 2-. 2 1, 3, 4.

( ) 2 - 1. , 1- .

, 2-. 2 - 4 3. 2-, = 2 + 2 4 = 7 + 15 = 22. 22<∞, 4 22.

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_m4e1a8ddd.png

dist

0

7

9

22

INT_MAX

14

2 - 3. 2, = 7 + 10 = 17. 9<17, .

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_4aa1440a.png

dist

0

7

9

22

INT_MAX

14

2 , .

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_ma977032.png

in_tree

1

1

0

0

0

0

. , 3. ϳ "" :

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_m517980d.png

cur=2

dist

0

7

9

20

INT_MAX

11

in_tree

1

1

1

0

0

0

, . ( 6, 4 5).

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_mda7a10d.png

cur=5

dist

0

7

9

20

20

11

in_tree

1

1

1

0

0

1

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_a90ad70.png

cur=3

dist

0

7

9

20

20

11

in_tree

1

1

1

1

0

1

http://ru.convdocs.org/pars_docs/refs/10/9364/9364_html_69df4c55.png

cur=4

dist

0

7

9

20

20

11

in_tree

1

1

1

1

1

1

. , . : 1 2- 7, 3- - 9, 4- - 20, 5- - 20, 6- - 11.

1.7

O(n2) . . ( ), . .

. 1 . , , . 1.


2.

2.1

.

, . , , . , .

'. , , ( ) Θ ( n log n ) n .

, / , . . A B , A B. , . ³ .

ϳ - , . , , . .

, . , , , .

³ , .


2.2

1. :

A[i] ≥ A[2i + 1]

A[i] ≥ A[2i + 2]

0<i<n/2

2. .

3. A[1] A[n], A[1], A[2], ..., A[n-1] .

4. A[1] A[n-1], A[1], A[2], ..., A[n-2] .

5. , .

6. A[1], A[2], ..., A[n] - .

2.3

N i .

Array[N] i , i i,

i ii.

temp ,

.

l_s, r_s i .

start i , i ii.

end i

ii.

i, j , ii i.


2.4

1. N array[N], N ii i .

2. i , .

3. i -1, [N/2]-1 -1.

4. Heapify (i, N), i i i.

5. i.

6. i -1, N-1 0.

7. i i ii.

8. i , i.

9. j -1, [i/2]-1 -1.

10. Heapify (j, i) , i i c j.

11. j.

12. i.

13 i array[N].


2.4.1

21.jpg

2.5.

2.5.1 heapify

1. i i.

2. , i i i ii. , 4, 3.

3. , i i i i ii. , 5, .

4. , i i . , 8, 6.

5. , i i i . , 7, .

6. , i . , 8, .

7. Swap (root, l_s), i i i .

8. , i i . , 10, 9.

9. , i i . , 11, .

10. Swap (root, r_s), i i .

11. Swap (root, l_s), i i i .


2.5.2 heapify

22.jpg

2.6

1.

. N=8; array = {6, 10, 15, 8, 20, 18, 7, 23}

23.jpg

2.

i:=[N/2]-1; i=3.

3.

1) i=3, end=8, start=3.

root:=3; l_s:=7; r_ch:=8;

, r_ch<end? 8<8? i.

l_s<end? 7<8? .

array[l_s]>array[root]? 23>8. .

temp:=array[root]; temp:=8;

array[root]:=array[l_s]; array[8]:=23;

array[l_s]:=temp; array[7]:=23;

array = { 6, 10, 15, 23, 20, 18, 7, 8}.

24.jpg

2) i=2, end=8, start=2.

root:=2; l_s:=5; r_s:=6;

, r_s<end? 6<8? .

array[root]<array[r_s]? 15<18. .

array[l_s]<array[r_s]? 7<18. .

temp:=array[root]; temp:=15;

array[root]:=array[l_s]; array[2]:=18;

array[l_s]:=temp; array[5]:=15;

array = {6, 10, 18, 23, 20, 15, 7, 8}.

25.jpg

3) i=1, end=8, start=1.

root:=1; l_s:=3; r_s:=4;

, r_s<end? 4<8? .

array[root]<array[r_s]? 10<20. .

array[l_s]<array[r_s]? 23<20. i.

array[r_s]<array[l_s]? 20<23. .

temp:=array[root]; temp:=10;

array[root]:=array[l_s]; array[1]:=23;

array[l_s]:=temp; array[3]:=10;

array = {6, 23, 18, 10, 20, 15, 7, 8}.

26.jpg

4) i=0, end=8, start=0.

root:=1; l_s:=1; r_s:=2;

, r_s<end? 2<8? .

array[root]<array[r_s]? 6<18. .

array[l_s]<array[r_s]? 23<18. i.

array[r_s]<array[l_s]? 18<23. .

temp:=array[root]; temp:=6;

array[root]:=array[l_s]; array[1]:=23;

array[l_s]:=temp; array[3]:=6;

array = { 23, 6, 18, 10, 20, 15, 7, 8}.


27.jpg

4.

1) i=7;

temp:=array[0]; temp:=23;

array[0]:=array[i]; array[0]:=8;

array[i]:=temp; array[7]:=23;

array = {8, 6, 18, 10, 20, 15, 7, 23}.

28.jpg

1.1) j=2, end=7, start=2.

root:=2; l_s:=5; r_s:=6;

, r_s<end? 6<7? .

array[root]<array[r_s]? 18<7. i.

array[root]<array[l_s]? 18<15. i.

i .

1.2) j=1, end=7, start=1

root:=1; l_s:=3; r_s:=4;

, r_s<end? 4<7? .

array[root]<array[r_s]? 6<20. .

array[l_s]<array[r_s]? 10<20. .

temp:=array[root]; temp:=6;

array[root]:=array[l_s]; array[1]:=20;

array[l_s]:=temp; array[3]:=6;

array = { 8, 20, 18, 10, 6, 15, 7, 23}.

29.jpg

1.3) j=0, end=7, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 2<7? .

array[root]<array[r_s]? 8<18. .

array[l_s]<array[r_s]? 20<18. i.

array[r_s]<array[l_s]? 18<20. .

temp:=array[root]; temp:=8;

array[root]:=array[l_s]; array[0]:=20;

array[l_s]:=temp; array[1]:=8;

array = { 20, 8, 18, 10, 6, 15, 7, 23}.

30.jpg

2) i=6;

temp:=array[0]; temp:=20;

array[0]:=array[i]; array[0]:=7;

array[i]:=temp; array[6]:=20;

array = { 7, 8, 18, 10, 6, 15, 20, 23}.

31.jpg

2.1) j=2, end=6, start=2.

root:=2; l_s:=5; r_s:=6;

, r_s<end? 6<6? i.

, l_s<end? 5<6? .

array[root]<array[l_s]? 18<15. i.

i .


2.2) j=1, end=6, start=1.

root:=1; l_s:=3; r_s:=4;

, r_s<end? 4<6? .

array[root]<array[r_s]? 8<6. i.

array[root]<array[l_s]? 8<10. .

array[l_s]<array[r_s]? 10<6. i.

array[r_s]<array[l_s]? 6<10. .

temp:=array[root]; temp:=8;

array[root]:=array[l_s]; array[1]:=10;

array[l_s]:=temp; array[3]:=8;

array = { 7, 10, 18, 8, 6, 15, 20, 23}.

32.jpg

2.3) j=0, end=6, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 1<6? .

array[root]<array[r_s]? 1<9. .

array[l_s]<array[r_s]? 10<18. .

temp:=array[root]; temp:=7;

array[root]:=array[l_s]; array[0]:=18;

array[l_s]:=temp; array[2]:=7;

array = { 18, 10, 7, 8, 6, 15, 20, 23}.

33.jpg

3) i=5;

temp:=array[0]; temp:=9;

array[0]:=array[i]; array[0]:=7;

array[i]:=temp; array[5]:=18;

array = { 7, 5, 1, 3, 0, 18, 20, 23}.

34.jpg

3.1) j=1, end=5, start=1.

root:=1; l_s:=3; r_s:=4;

, r_s<end? 4<5? .

array[root]<array[l_s]? 10<8. i.

array[root]<array[r_s]? 10<6. i.

i .

3.2) j=0, end=5, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 2<5? .

array[root]<array[l_s]? 15<10. i.

array[root]<array[r_s]? 15<7. i.

i .

4) i=4;

temp:=array[0]; temp:=15;

array[0]:=array[i]; array[0]:=6;

array[i]:=temp; array[4]:=15;

array = { 6, 10, 7, 8, 15, 18, 20, 23}.

35.jpg

4.1) j=1, end=4, start=1.

root:=1; l_s:=3; r_s:=4;

, r_s<end? 4<4? i.

, l_s<end? 3<4? .

array[l_s]>array[root]? 8>10. i.

i .


4.2) j=0, end=4, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 2<4? .

array[root]<array[r_s]? 7<6. i.

array[r_s]<array[l_s]? 7<10. .

temp:=array[root]; temp:=6;

array[root]:=array[l_s]; array[0]:=10;

array[l_s]:=temp; array[1]:=6;

array = { 10, 6, 7, 8, 15, 18, 20, 23}.

36.jpg

4) i=3;

temp:=array[0]; temp:=10;

array[0]:=array[i]; array[0]:=8;

array[i]:=temp; array[3]:=10;

array = { 8, 6, 7, 10, 15, 18, 20, 23}.

37.jpg

4.1) j=0, end=3, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 2<3? .

array[root]<array[l_s]? 3<0. i.

array[root]<array[r_s]? 3<1. i.

i .

5) i=2;

temp:=array[0]; temp:=8;

array[0]:=array[i]; array[0]:=7;

array[i]:=temp; array[2]:=8;

array = { 7, 6, 8, 10, 15, 18, 20, 23}.


38.jpg

5.1) j=0, end=2, start=0.

root:=0; l_s:=1; r_s:=2;

, r_s<end? 2<2? i.

, l_s<end? 1<2? .

array[l_s]>array[root]? 6>7. i.

i .

6) i=1;

temp:=array[0]; temp:=7;

array[0]:=array[i]; array[0]:=6;

array[i]:=temp; array[1]:=7;

array = { 6, 7, 8, 10, 15, 18, 20, 23}.

39.jpg

5. : array = { 6, 7, 8, 10, 15, 18, 20, 23}

2.7

ϳ , log2n , . n , - (n*log(n)). 500-1000 . ҳ . .


3

3.1

- , / ( ). , ' (X, Y, Q δ, λ). :

={x0, x1, x2 ., xn} - , x0;

Y={y0, y1, y2.,yn} - ;

Q={q0, q1, q2 ., qm} - , q0 - - ( );

δ: QX →Q - ;

λ: QX →Y - .

, Y=XU, U={R, L, S}- : R , L , S .

3.2

, (x1,x2,,xn). (x1,x2,,xn,x1,x2,,xn).

3.3

x1,x2,,xn 䒺 , . . , , . xn, .

x1. x1 xn. x1 , 2 . xn ( ) .

x1,x2,,xn, , . x1,x2,,xn.

x1,x2,,xn, . , , x1,x2,,xn 3 .

, .

3.4

1 x1 xn. 1 0. 0 - Error(qEr).

2-3 . 1.

4-5 .

6-7 x1,x2,,xn 00. .

8 1

9-10 ﳿ x1,x2,,xn 00. .

11 1, , 0 - 000, , .30

12-13 x1,x2,,xn 00. .

14 1, x1,x2,,xn 1, .22. 0 - x1,x2,,xn 01

15-16 1,

17 1 0.

18-19 x1,x2,,xn 00. .

20-21 ﳿ x1,x2,,xn 00, .8.

22-23 1,

24 1 0.

25-26 x1,x2,,xn 00. .

27-28 ﳿ x1,x2,,xn 00,

29 , .8.

30 3 0.

31 1, 1 0, 0 , .38.

32-33 0.

34 0 1

35-37 0.

38 1, 1 0 .32, 0 .

39 1 - (q0), 0, 1.

q0 .

qEr .

3.5

X40.jpg{ 0, 1};

Y40.jpg{ 0, 1, Er };


3.6

42.jpg

43.jpg

3.7

.

3.8

x1.

3.9

Q

0

1

Q1

0SQEr

0LQ2

- (0) . . ( 1) / (1)

Q2

0LQ3

-

Q3

1RQ4

-

Q4

0RQ5

-

Q5

0RQ6

-

Q6

0RQ7

1RQ6

-

Q7

0RQ8

1RQ6

- (0) 00 / (1) , q6

Q8

1LQ9

-

Q9

0LQ10

1LQ9

-

Q10

0LQ11

1LQ9

- (0) 00 / (1) , q9

Q11

0LQ30

1LQ12

- (0) 000, , 3 , q30 / (1) q12

Q12

0LQ13

1LQ12

-

Q13

0LQ14

1LQ12

- (0) 00 / (1) , q12

Q14

ORQ15

1RQ22

- (0) 01 q15/ (1) q22

Q15

1RQ16

-

Q16

0RQ17

-

Q17

0RQ18

-

Q18

0RQ19

1RQ19

-

Q19

0RQ20

1RQ19

- (0) 00 / (1) , q19

Q20

0RQ21

1RQ20

-

Q21

0SQ8

1RQ20

- (0) 00 q8 / (1) , q20

Q22

1RQ23

-

Q23

0RQ24

-

Q24

0RQ25

-

Q25

0RQ26

1RQ25

-

Q26

0RQ27

1RQ25

- (0) 00 / (1) , q25

Q27

0RQ28

1RQ27

-

Q28

0LQ8

1RQ27

- (0) 00 q8 / (1) , q27

Q30

0LQ30

1SQ31

- (0) / (1) q31

Q31

0LQ38

0RQ32

- (0) 0 q38 / (1)

Q32

0RQ33

-

Q33

0RQ34

-

Q34

1LQ35

-

Q35

0LQ36

-

Q36

0LQ37

-

Q37

0LQ31

-

Q38

0RQ39

0RQ32

- (0) 00 q39 / (1) , q32

Q39

0RQ39

1SQ0

- (0) / (1)

Q0

0SQ0

1SQ0

-

QEr

0SQEr

1SQEr

-


3.10

1) 1

q1:

000010000000

q2:

000000000000

q3:

000000000000

q4:

001000000000

q5:

001000000000

q6:

001000000000

q7:

001000000000

q8:

001000000000

q9:

001000010000

q10:

001000010000

q11:

001000010000

q30:

001000010000

q30:

001000010000

q31:

001000010000

q32:

000000010000

q33:

000000010000

q34:

000000010000

q35:

000001010000

q36:

000001010000

q37:

000001010000

q31:

000001010000

q38:

000001010000

q39:

000001010000

q39:

000001010000

q0:

000001010000

ʳ .

1 1.


2) 111

q1:

000001110000000

q2:

000000110000000

q3:

000000110000000

q4:

000100110000000

q5:

000100110000000

q6:

000100110000000

q6:

000100110000000

q7:

000100110000000

q8:

000100110000000

q9:

000100110010000

q10:

000100110010000

q11:

000100110010000

q12:

000100110010000

q12:

000100110010000

q13:

000100110010000

q14:

000100110010000

q22:

000100110010000

q23:

000110110010000

q24:

000110110010000

q25:

000110010010000

q25:

000110010010000

q26:

000110010010000

q27:

000110010010000

q27:

000110010010000

q28:

000110010010000

q8:

000110010010000

q9:

000110010011000

q9:

000110010011000

q10:

000110010011000

q11:

000110010011000

q12:

000110010011000

q13:

000110010011000

q14:

000110010011000

q22:

000110010011000

q23:

000111010011000

q24:

000111010011000

q25:

000111000011000

q26:

000111000011000

q27:

000111000011000

q27:

000111000011000

q28:

000111000011000

q8:

000111000011000

q9:

000111000011100

q9:

000111000011100

q10:

000111000011100

q11:

000111000011100

q30:

000111000011100

q30:

000111000011100

q31:

000111000011100

q32:

000110000011100

q33:

000110000011100

q34:

000110000011100

q35:

000110001011100

q36:

000110001011100

q37:

000110001011100

q31:

000110001011100

q32:

000100001011100

q33:

000100001011100

q34:

000100001011100

q35:

000100011011100

q36:

000100011011100

q37:

000100011011100

q31:

000100011011100

q32:

000000011011100

q33:

000000011011100

q34:

000000011011100

q35:

000000111011100

q36:

000000111011100

q37:

000000111011100

q31:

000000111011100

q38:

000000111011100

q39:

000000111011100

q39:

000000111011100

q0:

000000111011100

ʳ .

111 111.


3) 11 1

q1:

00000110100000000

q2:

00000010100000000

q3:

00000010100000000

q4:

00010010100000000

q5:

00010010100000000

q6:

00010010100000000

q6:

00010010100000000

q6:

00010010100000000

q7:

00010010100000000

q6:

00010010100000000

q7:

00010010100000000

q8:

00010010100000000

q9:

00010010100100000

q10:

00010010100100000

q11:

00010010100100000

q12:

00010010100100000

q13:

00010010100100000

q12:

00010010100100000

q13:

00010010100100000

q14:

00010010100100000

q22:

00010010100100000

q23:

00011010100100000

q24:

00011010100100000

q25:

00011000100100000

q26:

00011000100100000

q25:

00011000100100000

q26:

00011000100100000

q27:

00011000100100000

q27:

00011000100100000

q28:

00011000100100000

q8:

00011000100100000

q9:

00011000100110000

q9:

00011000100110000

q10:

00011000100110000

q11:

00011000100110000

q12:

00011000100110000

q13:

00011000100110000

q14:

00011000100110000

q15:

00011000100110000

q16:

00011010100110000

q17:

00011010100110000

q18:

00011010000110000

q19:

00011010000110000

q20:

00011010000110000

q20:

00011010000110000

q21:

00011010000110000

q8:

00011010000110000

q9:

00011010000110100

q10:

00011010000110100

q9:

00011010000110100

q9:

00011010000110100

q10:

00011010000110100

q11:

00011010000110100

q30:

00011010000110100

q30:

00011010000110100

q31:

00011010000110100

q32:

00011000000110100

q33:

00011000000110100

q34:

00011000000110100

q35:

00011000010110100

q36:

00011000010110100

q37:

00011000010110100

q31:

00011000010110100

q38:

00011000010110100

q32:

00010000010110100

q33:

00010000010110100

q34:

00010000010110100

q35:

00010001010110100

q36:

00010001010110100

q37:

00010001010110100

q31:

00010001010110100

q32:

00000001010110100

q33:

00000001010110100

q34:

00000001010110100

q35:

00000011010110100

q36:

00000011010110100

q37:

00000011010110100

q31:

00000011010110100

q38:

00000011010110100

q39:

00000011010110100

q39:

00000011010110100

q0:

00000011010110100

ʳ .

11 1 11 1.


ϳ , , . , . , . . , , ' .

, (x1,x2,,xn), (x1, x2, , xn, x1, x2, , xn). , , .


1. . . . , . , 2001 -186 .

2. 7.080403 7.091501/ .. , .. , .. . , 1996 .1 54 .

3. / , , . . 19.701-90 .: , 1990 25 .


« »
: ,
: 39276
: 23
: 35

50107
0
18

... "Ͳ-3", -6 1 . 2.3 ' - . , , , 10 ...

140818
2
0

... .[9] 1.3. , ( 2) , , (, , )[20;36]. , ...

0