Đồ Án 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 .- 33 -
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 -
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 -
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 -
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 -
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 -