Giáo trình Thiết kế và đánh giá thuật toán

MỤC LỤC

LỜI NÓI ĐẦU.

- 6 -Chương 1 : GIỚI THIỆU THIẾT KẾ, ĐÁNH GIÁ THUẬT TOÁN.

-8-I. Định nghĩa trực quan về Thuật toán.- 8 -1.

Định nghĩa.- 8 -2.

Các đặc trưng cơ bản của thuật toán.- 9 -3.

Đặc tả thuật toán.- 9 -II.

Các dạng diễn đạt thuật toán.

- 9 -1. Dạng lưu đồ ( sơ đồ khối ).-

10 -2. Dạng ngôn ngữ tự nhiên.- 10 -3.

Ngôn ngữ lập trình.

- 10 -4. Dạng mã giả.- 10 -

III.Thiết kế thuật toán.- 12 -1.

Modul hóa và thiết kế từ trên xuống (Top-Down).- 13 -2.

Phương pháp làm mịn dần (hay tinh chế từng bước ).- 13 -3.

Một số phương pháp thiết kế.

- 15 -IV. Phân tích thuật toán.- 17 -1.

Các bước trong quá trình phân tích đánh giá thời gian chạy của

thuật toán.- 17 -2. Các ký hiệu tiệm cận.- 18 -3.

Một số lớp các thuật toán.- 19 -4.

Phân tích thuật toán đệ qui.- 21 -5.

Các phép toán trên các ký hiệu tiệm cận.- 25 -6.

Phân tích trường hợp trung bình.- 26 -V.

Tối ưu thuật toán.- 27 -1.

Kỹ thuật tối ưu các vòng lặp.- 27 -2.

Tối ưu việc rẽ nhánh.- 30 -

Bài tập.- 30 -Chương 2 : PHƯƠNG PHÁP CHIA ĐỂ TRỊ .

- 33 -I. Mở đầu.

-1. Ý tưởng.- 33 -2.

Mô hình.- 33 -II. Thuật toán tìm kiếm nhị phân.-33

-1. Phát biểu bài toán.- 33 -2.

Ý tưởng.- 33 -3.

Mô tả thuật toán.- 33 -

Trần Tuấn Minh Khoa Toán-Tin

Thiết kế và đánh giá thuật toán - 2 -

4. Độ phức tạp thời gian của thuật toán.- 34 -5.

Cài đặt.- 34 -III.

Bài toán MinMax.- 35

-1. Phát biểu bài toán.- 35 -2.

Ý tưởng.- 35 -3. Thuật toán.- 35 -4.

Độ phức tạp thuật toán.- 36 -5.

Cài đặt.- 36 -IV. Thuật toán QuickSort.- 36 -1.

Ý tưởng.- 37 -2.

Mô tả thuật toán.- 37 -3.

Độ phức tạp của thuật toán.- 38

-V. Thuật toán nhân Strassen nhân 2 ma trận.- 39 -1.

Bài toán.- 39 -2.

Mô tả.- 39 -VI.

Bài toán hoán đổi 2 phần trong 1 dãy.- 41 -1.

Phát biểu bài toán.- 41 -2.

Ý tưởng.- 41 -3. Thuật toán.- 41 -4.

Độ phức tạp thuật toán.- 43 -5.

Cài đặt.- 43 -VII. Trộn hai đường trực tiếp.- 44 -1.

Bài toán.- 44 -2.

Ý tưởng.- 44 -3. Thiết kế.- 45 -

Bài tập.- 50 -Chương 3 : PHƯƠNG PHÁP QUAY LUI.- 53 -I. Mở đầu.- 53 -1. Ý tưởng .- 54-

2. Mô hình.- 53 -II. Bài toán Ngựa đi tuần.- 54 -1. Phát biểu bài toán.- 54 -2. Thiết kế thuật toán.- 55 -

III. Bài toán 8 hậu.- 57 -1. Phát biểu bài toán.- 57 -2. Thiết kế thuật toán.- 57

-IV. Bài toán liệt kê các dãy nhị phân độ dài n.- 59 -Trần Tuấn Minh Khoa Toán-Tin

Thiết kế và đánh giá thuật toán - 3 -

1. Phát biểu bài toán.- 59 -2. Thiết kế thuật toán.- 59

-V. Bài toán liệt kê các hoán vị.- 60 -1. Phát biểu bài toán.- 60 -2. Thiết kế thuật toán.- 60

-VI. Bài toán liệt kê các tổ hợp.- 61 -1. Phát biểu bài toán.- 61 -2. Thiết kế thuật toán.- 61

-VII. Bài toán tìm kiếm đường đi trên đồ thị.- 61 -1. Phát biểu bài toán.- 61 -2. Thuật toán DFS ( Depth First Search).- 62 -3. Thu?t toán BFS ( Breadth First Search).- 64

-Bài tập.- 66 -Chương 4: PHƯƠNG PHÁP NHÁNH CẬN.- 69 -I. Mở đầu.- 69 -1. Ý tưởng.- 69 -2. Mô hình.- 69

-II. Bài toán nguời du lịch.- 70 -1. Bài toán.- 70

-2. Ý tưởng.- 70 -3. Thiết kế.- 71

-4. Cài đặt.- 73 -III. Bài toán cái túi xách.- 74

-1. Bài toán.- 74

-2. Ý tưởng.- 74 -3. Thiết kế thuật toán.- 75

-4. Cài đặt.- 78

-Bài tập.- 79 -Chương 5: PHƯƠNG PHÁP THAM LAM.- 81 -I. Mở đầu.- 81 -1. Ý tưởng.- 81 -2. Mô hình.- 81

-II. Bài toán người du lịch.- 82 -1. Bài toán.- 82

-2. Ý tưởng.- 82 -3. Thuật toán.- 82

-4. Độ phức tạp của thuật toán.- 83 -Trần Tuấn Minh Khoa Toán-Tin

Thiết kế và đánh giá thuật toán - 4 -

5. Cài đặt.- 83 -III. Thuật toán Dijkstra -Tìmđường đi ngắn nhất trong đồ thị có

trọng số.- 84 -1. Bài toán.- 84

-2. Ý tưởng.- 85 -3. Mô tả thuật toán.- 85 -

4. Cài đặt.- 87 -5. Độ phức tạp của thuật toán.- 90

-IV. Thuật toán Prim – Tìm cây bao trùm nhỏ nhất.- 90 -1. Bài toán.- 90

-2. Ý tưởng.- 90 -3. Mô tả thuật toán.- 90

-4. Cài đặt.- 91 -5. Độ phức tạp thuật toán.- 93

-V. Bài toán ghi các bài hát.- 93 -1. Phát biểu bài toán.- 93 -2. Thiết kế.- 93

-3. Độ phức tạp của thuật toán.- 94 -4. Cài đặt.- 94

-VI. Bài toán chiếc túi xách (Knapsack).- 95 -1. Phát biểu bài toán.- 95 -2. Thiết kế thuật toán.- 95

-3. Độ phức tạp của thuật toán.- 96 -4. Cài đặt.- 96

-VII. Phương pháp tham lam và Heuristic.- 97 -Bài tập.- 98 -Chương 6 : PHƯƠNG PHÁP QUY HOẠCH ĐỘNG.- 100 -I. Phương pháp tổng quát.- 100 -II. Thuật toán Floyd -Tìm đường đi ngắn nhất giữa các cặp đỉnh.-

100 -1. Bài toán.- 100 -2. Ý tưởng.- 101 -3. Thiết kế.- 101

-4. Cài đặt.- 103 -5. Độ phức tạp của thuật toán.- 104 -III. Nhân tổ hợp nhiều ma trận.- 104

-1. Bài toán.- 104 -Trần Tuấn Minh Khoa Toán-Tin

Thiết kế và đánh giá thuật toán - 5 -

2. Ý tưởng.- 104 -3. Thiết kế.- 105

-4. Độ phức tạp của thuật toán.- 106 -5. Cài đặt.- 106

-IV. Cây nhị phân tìm kiếm tối ưu (Optimal Binary Search Tree).-

107 -1. Phát biểu bài toán.- 108 -2. Ý tưởng.- 108 -3. Thiết kế thuật toán.- 109

-4. Độ phức tạp của thuật toán.- 110 -5. Cài đặt.- 111

-V. Dãy chung dài nhất của 2 dãy số.- 111 -1. Bài toán.- 111

-2. Ý tưởng.- 112 -3. Thuật toán.- 112

-4. Độ phức tạp của thuật toán.- 114 -5. Cài đặt.- 114

-VI. Bài toán người du lịch.- 115 -1. Ý tưởng.- 116 -2. Thiết kế thuật toán.- 116

-3. Độ phức tạp của thuật toán.- 118

-Bài tập.- 118 -PHỤ LỤC.- 120

-TÀI LIỆUTHAM KHẢO.- 122 -