Thuật toán Thiết kế và Đánh giá - Trần Tuấn Minh

Su tm bi:

www.daihoc.com.vn

Thieát keá vaø ñaùnh giaù thuaät toaùn - 1 -

MUÏC LUÏC

LÔØI NOÙI ÑAÀU..................................................................................- 6 -

Chöông 1 : GIÔÙI THIEÄU THIEÁT KEÁ, ÑAÙNH GIAÙ THUAÄT TOAÙN .- 8 -

I. Ñònh nghóa tröïc quan veà Thuaät toaùn...........................................- 8 -

1. Ñònh nghóa.............................................................................- 8 -

2. Caùc ñaëc tröng cô baûn cuûa thuaät toaùn......................................- 9 -

3. Ñaëc taû thuaät toaùn ..................................................................- 9 -

II. Caùc daïng dieãn ñaït thuaät toaùn....................................................- 9 -

1. Daïng löu ñoà ( sô ñoà khoái ) ...................................................- 10 -

2. Daïng ngoân ngöõ töï nhieân ......................................................- 10 -

3. Ngoân ngöõ laäp trình...............................................................- 10 -

4. Daïng maõ giaû........................................................................- 10 -

III. Thieát keá thuaät toaùn................................................................- 12 -

1. Modul hoùa vaø thieát keá töø treân xuoáng (Top-Down)...............- 13 -

2. Phöông phaùp laøm mòn daàn (hay tinh cheá töøng böôùc )...........- 13 -

3. Moät soá phöông phaùp thieát keá...............................................- 15 -

IV. Phaân tích thuaät toaùn...............................................................- 17 -

1. Caùc böôùc trong quaù trình phaân tích ñaùnh giaù thôøi gian chaïy cuûa

thuaät toaùn ................................................................................- 17 -

2. Caùc kyù hieäu tieäm caän..........................................................- 18 -

3. Moät soá lôùp caùc thuaät toaùn ...................................................- 19 -

4. Phaân tích thuaät toaùn ñeä qui..................................................- 21 -

5. Caùc pheùp toaùn treân caùc kyù hieäu tieäm caän ............................- 25 -

6. Phaân tích tröôøng hôïp trung bình ..........................................- 26 -

V. Toái öu thuaät toaùn ....................................................................- 27 -

1. Kyõ thuaät toái öu caùc voøng laëp................................................- 27 -

2. Toái öu vieäc reõ nhaùnh ...........................................................- 30 -

Baøi taäp.....................................................................................- 30 -

Chöông 2 : PHÖÔNG PHAÙP CHIA ÑEÅ TRÒ ..................................- 33 -

I. Môû ñaàu.....................................................................................- 33 -

1. YÙ töôûng................................................................................- 33 -

2. Moâ hình...............................................................................- 33 -

II. Thuaät toaùn tìm kieám nhò phaân.................................................- 33 -

1. Phaùt bieåu baøi toaùn................................................................- 33 -

2. YÙ töôûng................................................................................- 33 -

3. Moâ taû thuaät toaùn ..................................................................- 33 -

Traàn Tuaán Minh Khoa Toaùn-Tin

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com

Su tm bi:

www.daihoc.com.vn

Thieát keá vaø ñaùnh giaù thuaät toaùn - 2 -

4. Ñoä phöùc taïp thôøi gian cuûa thuaät toaùn...................................- 34 -

5. Caøi ñaët.................................................................................- 34 -

III. Baøi toaùn MinMax..................................................................- 35 -

1. Phaùt bieåu baøi toaùn................................................................- 35 -

2. YÙ töôûng................................................................................- 35 -

3. Thuaät toaùn ...........................................................................- 35 -

4. Ñoä phöùc taïp thuaät toaùn ........................................................- 36 -

5. Caøi ñaët.................................................................................- 36 -

IV. Thuaät toaùn QuickSort...........................................................- 36 -

1. YÙ töôûng................................................................................- 37 -

2. Moâ taû thuaät toaùn ..................................................................- 37 -

3. Ñoä phöùc taïp cuûa thuaät toaùn..................................................- 38 -

V. Thuaät toaùn nhaân Strassen nhaân 2 ma traän..............................- 39 -

1. Baøi toaùn...............................................................................- 39 -

2. Moâ taû...................................................................................- 39 -

VI. Baøi toaùn hoaùn ñoåi 2 phaàn trong 1 daõy..................................- 41 -

1. Phaùt bieåu baøi toaùn................................................................- 41 -

2. YÙ töôûng................................................................................- 41 -

3. Thuaät toaùn ...........................................................................- 41 -

4. Ñoä phöùc taïp thuaät toaùn ........................................................- 43 -

5. Caøi ñaët.................................................................................- 43 -

VII. Troän hai ñöôøng tröïc tieáp .....................................................- 44 -

1. Baøi toaùn...............................................................................- 44 -

2. YÙ töôûng................................................................................- 44 -

3. Thieát keá...............................................................................- 45 -

Baøi taäp.....................................................................................- 50 -

Chöông 3 : PHÖÔNG PHAÙP QUAY LUI .......................................- 53 -

I. Môû ñaàu.....................................................................................- 53 -

1. YÙ töôûng…………………………………………………………………………………………………….- 54-

2. Moâ hình...............................................................................- 53 -

II. Baøi toaùn Ngöïa ñi tuaàn.............................................................- 54 -

1. Phaùt bieåu baøi toaùn................................................................- 54 -

2. Thieát keá thuaät toaùn ..............................................................- 55 -

III. Baøi toaùn 8 haäu.......................................................................- 57 -

1. Phaùt bieåu baøi toaùn................................................................- 57 -

2. Thieát keá thuaät toaùn ..............................................................- 57 -

IV. Baøi toaùn lieät keâ caùc daõy nhò phaân ñoä daøi n ............................- 59 -

Traàn Tuaán Minh Khoa Toaùn-Tin

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com

Su tm bi:

www.daihoc.com.vn

Thieát keá vaø ñaùnh giaù thuaät toaùn - 3 -

1. Phaùt bieåu baøi toaùn................................................................- 59 -

2. Thieát keá thuaät toaùn ..............................................................- 59 -

V. Baøi toaùn lieät keâ caùc hoaùn vò....................................................- 60 -

1. Phaùt bieåu baøi toaùn................................................................- 60 -

2. Thieát keá thuaät toaùn ..............................................................- 60 -

VI. Baøi toaùn lieät keâ caùc toå hôïp ....................................................- 61 -

1. Phaùt bieåu baøi toaùn................................................................- 61 -

2. Thieát keá thuaät toaùn ..............................................................- 61 -

VII. Baøi toaùn tìm kieám ñöôøng ñi treân ñoà thò ................................- 61 -

1. Phaùt bieåu baøi toaùn................................................................- 61 -

2. Thuaät toaùn DFS ( Depth First Search).................................- 62 -

3. Thuật toaùn BFS ( Breadth First Search) .............................- 64 -

Baøi taäp.....................................................................................- 66 -

Chöông 4: PHÖÔNG PHAÙP NHAÙNH CAÄN....................................- 69 -

I. Môû ñaàu.....................................................................................- 69 -

1. YÙ töôûng................................................................................- 69 -

2. Moâ hình...............................................................................- 69 -

II. Baøi toaùn nguôøi du lòch.............................................................- 70 -

1. Baøi toaùn...............................................................................- 70 -

2. YÙ töôûng................................................................................- 70 -

3. Thieát keá...............................................................................- 71 -

4. Caøi ñaët.................................................................................- 73 -

III. Baøi toaùn caùi tuùi xaùch..............................................................- 74 -

1. Baøi toaùn...............................................................................- 74 -

2. YÙ töôûng................................................................................- 74 -

3. Thieát keá thuaät toaùn ..............................................................- 75 -

4. Caøi ñaët.................................................................................- 78 -

Baøi taäp.....................................................................................- 79 -

Chöông 5: PHÖÔNG PHAÙP THAM LAM......................................- 81 -

I. Môû ñaàu.....................................................................................- 81 -

1. YÙ töôûng................................................................................- 81 -

2. Moâ hình...............................................................................- 81 -

II. Baøi toaùn ngöôøi du lòch.............................................................- 82 -

1. Baøi toaùn...............................................................................- 82 -

2. YÙ töôûng................................................................................- 82 -

3. Thuaät toaùn ...........................................................................- 82 -

4. Ñoä phöùc taïp cuûa thuaät toaùn..................................................- 83 -

Traàn Tuaán Minh Khoa Toaùn-Tin

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com

Su tm bi:

www.daihoc.com.vn

Thieát keá vaø ñaùnh giaù thuaät toaùn - 4 -

5. Caøi ñaët.................................................................................- 83 -

III. Thuaät toaùn Dijkstra -Tìm ñöôøng ñi ngaén nhaát trong ñoà thò coù

troïng soá .......................................................................................- 84 -

1. Baøi toaùn...............................................................................- 84 -

2. YÙ töôûng................................................................................- 85 -

3. Moâ taû thuaät toaùn ..................................................................- 85 -

4. Caøi ñaët.................................................................................- 87 -

5. Ñoä phöùc taïp cuûa thuaät toaùn..................................................- 90 -

IV. Thuaät toaùn Prim – Tìm caây bao truøm nhoû nhaát .....................- 90 -

1. Baøi toaùn...............................................................................- 90 -

2. YÙ töôûng................................................................................- 90 -

3. Moâ taû thuaät toaùn ..................................................................- 90 -

4. Caøi ñaët.................................................................................- 91 -

5. Ñoä phöùc taïp thuaät toaùn ........................................................- 93 -

V. Baøi toaùn ghi caùc baøi haùt..........................................................- 93 -

1. Phaùt bieåu baøi toaùn................................................................- 93 -

2. Thieát keá...............................................................................- 93 -

3. Ñoä phöùc taïp cuûa thuaät toaùn..................................................- 94 -

4. Caøi ñaët.................................................................................- 94 -

VI. Baøi toaùn chieác tuùi xaùch (Knapsack) ......................................- 95 -

1. Phaùt bieåu baøi toaùn................................................................- 95 -

2. Thieát keá thuaät toaùn ..............................................................- 95 -

3. Ñoä phöùc taïp cuûa thuaät toaùn..................................................- 96 -

4. Caøi ñaët.................................................................................- 96 -

VII. Phöông phaùp tham lam vaø Heuristic....................................- 97 -

Baøi taäp.....................................................................................- 98 -

Chöông 6 : PHÖÔNG PHAÙP QUY HOAÏCH ÑOÄNG..................... - 100 -

I. Phöông phaùp toång quaùt ..........................................................- 100 -

II. Thuaät toaùn Floyd -Tìm ñöôøng ñi ngaén nhaát giöõa caùc caëp ñænh..... -

100 -

1. Baøi toaùn.............................................................................- 100 -

2. YÙ töôûng.............................................................................. - 101 -

3. Thieát keá.............................................................................- 101 -

4. Caøi ñaët...............................................................................- 103 -

5. Ñoä phöùc taïp cuûa thuaät toaùn................................................- 104 -

III. Nhaân toå hôïp nhieàu ma traän..................................................- 104 -

1. Baøi toaùn.............................................................................- 104 -

Traàn Tuaán Minh Khoa Toaùn-Tin

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com

Su tm bi:

www.daihoc.com.vn

Thieát keá vaø ñaùnh giaù thuaät toaùn - 5 -

2. YÙ töôûng.............................................................................. - 104 -

3. Thieát keá.............................................................................- 105 -

4. Ñoä phöùc taïp cuûa thuaät toaùn................................................- 106 -

5. Caøi ñaët...............................................................................- 106 -

IV. Caây nhò phaân tìm kieám toái öu (Optimal Binary Search Tree) ..... -

107 -

1. Phaùt bieåu baøi toaùn..............................................................- 108 -

2. YÙ töôûng.............................................................................. - 108 -

3. Thieát keá thuaät toaùn ............................................................- 109 -

4. Ñoä phöùc taïp cuûa thuaät toaùn................................................- 110 -

5. Caøi ñaët...............................................................................- 111 -

V. Daõy chung daøi nhaát cuûa 2 daõy soá..........................................- 111 -

1. Baøi toaùn.............................................................................- 111 -

2. YÙ töôûng.............................................................................. - 112 -

3. Thuaät toaùn .........................................................................- 112 -

4. Ñoä phöùc taïp cuûa thuaät toaùn................................................- 114 -

5. Caøi ñaët...............................................................................- 114 -

VI. Baøi toaùn ngöôøi du lòch.........................................................- 115 -

1. YÙ töôûng.............................................................................. - 116 -

2. Thieát keá thuaät toaùn ............................................................- 116 -

3. Ñoä phöùc taïp cuûa thuaät toaùn................................................- 118 -

Baøi taäp...................................................................................- 118 -

PHUÏ LUÏC..............................................................................- 120 -

TAØI LIEÄU THAM KHAÛO .....................................................- 122 -

Traàn Tuaán Minh Khoa Toaùn-Tin

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com

thiết kế và đánh giá thuật toán - trần tuấn minh -1

Ta dùng một mảng logic Daxet[ ] để đánh dấu các đỉnh được thăm, mảng này được khởi động bằng 0 tất cả để chỉ rằng lúc đầu chưa đỉnh nào được thăm. Một mảng trước để lưu trữ các đỉnh nằm trên đường đi ngắn nhất.

Chủ đề:

Tài liệu liên quan

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Hỗ trợ

Phương thức thanh toán

Theo dõi chúng tôi