[FONT="]MỤC LỤC

[FONT="]LỜI NÓI ĐẦU[FONT="] - 6 -

[FONT="]Chương 1 : GIỚI THIỆU THIẾT KẾ, ĐÁNH GIÁ THUẬT TOÁN[FONT="].- 8 -

[FONT="]I. Định nghĩa trực quan về Thuật toán[FONT="] .- 8 -

[FONT="]1. Định nghĩa[FONT="] .- 8 -

[FONT="]2. Các đặc trưng cơ bản của thuật toán[FONT="] - 9 -

[FONT="]3. Đặc tả thuật toán[FONT="] - 9 -

[FONT="]II. Các dạng diễn đạt thuật toán[FONT="] - 9 -

[FONT="]1. Dạng lưu đồ ( sơ đồ khối )[FONT="] .- 10 -

[FONT="]2. Dạng ngôn ngữ tự nhiên[FONT="] - 10 -

[FONT="]3. Ngôn ngữ lập trình.[FONT="] - 10 -

[FONT="]4. Dạng mã giả[FONT="] - 10 -

[FONT="]III. Thiết kế thuật toán[FONT="] - 12 -

[FONT="]1. Modul hóa và thiết kế từ trên xuống (Top-Down)[FONT="] .- 13 -

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

[FONT="]3. Một số phương pháp thiết kế[FONT="] .- 15 -

[FONT="]IV. Phân tích thuật toán[FONT="] .- 17 -

[FONT="]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[FONT="] - 17 -

[FONT="]2. Các ký hiệu tiệm cận[FONT="] - 18 -

[FONT="]3. Một số lớp các thuật toán[FONT="] .- 19 -

[FONT="]4. Phân tích thuật toán đệ qui.[FONT="] .- 21 -

[FONT="]5. Các phép toán trên các ký hiệu tiệm cận[FONT="] - 25 -

[FONT="]6. Phân tích trường hợp trung bình[FONT="] - 26 -

[FONT="]V. Tối ưu thuật toán[FONT="] - 27 -

[FONT="]1. Kỹ thuật tối ưu các vòng lặp[FONT="] - 27 -

[FONT="]2. Tối ưu việc rẽ nhánh[FONT="] .- 30 -

[FONT="]Bài tập[FONT="] .- 30 -

[FONT="]Chương 2 : PHƯƠNG PHÁP CHIA ĐỂ TRỊ [FONT="] - 33 -

[FONT="]I. Mở đầu[FONT="] .- 33 -

[FONT="]1. Ý tưởng[FONT="] - 33 -

[FONT="]2. Mô hình[FONT="] .- 33 -

[FONT="]II. Thuật toán tìm kiếm nhị phân.[FONT="] - 33 -

[FONT="]1. Phát biểu bài toán[FONT="] - 33 -

[FONT="]2. Ý tưởng[FONT="] - 33 -

[FONT="]3. Mô tả thuật toán[FONT="] - 33 -

[FONT="]4. Độ phức tạp thời gian của thuật toán[FONT="] .- 34 -

[FONT="]5. Cài đặt[FONT="] .- 34 -

[FONT="]III. Bài toán MinMax[FONT="] - 35 -

[FONT="]1. Phát biểu bài toán[FONT="] - 35 -

[FONT="]2. Ý tưởng[FONT="] - 35 -

[FONT="]3. Thuật toán[FONT="] .- 35 -

[FONT="]4. Độ phức tạp thuật toán[FONT="] - 36 -

[FONT="]5. Cài đặt[FONT="] .- 36 -

[FONT="]IV. Thuật toán QuickSort[FONT="] .- 36 -

[FONT="]1. Ý tưởng[FONT="] - 37 -

[FONT="]2. Mô tả thuật toán[FONT="] - 37 -

[FONT="]3. Độ phức tạp của thuật toán[FONT="] - 38 -

[FONT="]V. Thuật toán nhân Strassen nhân 2 ma trận[FONT="] - 39 -

[FONT="]1. Bài toán[FONT="] .- 39 -

[FONT="]2. Mô tả[FONT="] .- 39 -

[FONT="]VI. Bài toán hoán đổi 2 phần trong 1 dãy[FONT="] - 41 -

[FONT="]1. Phát biểu bài toán[FONT="] - 41 -

[FONT="]2. Ý tưởng[FONT="] - 41 -

[FONT="]3. Thuật toán[FONT="] .- 41 -

[FONT="]4. Độ phức tạp thuật toán[FONT="] - 43 -

[FONT="]5. Cài đặt[FONT="] .- 43 -

[FONT="]VII. Trộn hai đường trực tiếp[FONT="] .- 44 -

[FONT="]1. Bài toán[FONT="] .- 44 -

[FONT="]2. Ý tưởng[FONT="] - 44 -

[FONT="]3. Thiết kế[FONT="] .- 45 -

[FONT="]Bài tập[FONT="] .- 50 -

[FONT="]Chương 3 : PHƯƠNG PHÁP QUAY LUI[FONT="] .- 53 -

[FONT="]I. Mở đầu[FONT="] .- 53 -

[FONT="]1. Ý tưởng .- 54-

[FONT="]2. Mô hình[FONT="] .- 53 -

[FONT="]II. Bài toán Ngựa đi tuần[FONT="] .- 54 -

[FONT="]1. Phát biểu bài toán[FONT="] - 54 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 55 -

[FONT="]III. Bài toán 8 hậu[FONT="] .- 57 -

[FONT="]1. Phát biểu bài toán[FONT="] - 57 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 57 -

[FONT="]IV. Bài toán liệt kê các dãy nhị phân độ dài n[FONT="] - 59 -

[FONT="]1. Phát biểu bài toán[FONT="] - 59 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 59 -

[FONT="]V. Bài toán liệt kê các hoán vị[FONT="] - 60 -

[FONT="]1. Phát biểu bài toán[FONT="] - 60 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 60 -

[FONT="]VI. Bài toán liệt kê các tổ hợp[FONT="] - 61 -

[FONT="]1. Phát biểu bài toán[FONT="] - 61 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 61 -

[FONT="]VII. Bài toán tìm kiếm đường đi trên đồ thị[FONT="] - 61 -

[FONT="]1. Phát biểu bài toán[FONT="] - 61 -

[FONT="]2. Thuật toán DFS ( Depth First Search)[FONT="] .- 62 -

[FONT="]3. Thuật toán BFS ( Breadth First Search)[FONT="] .- 64 -

[FONT="]Bài tập[FONT="] .- 66 -

[FONT="]Chương 4: PHƯƠNG PHÁP NHÁNH CẬN[FONT="] - 69 -

[FONT="]I. Mở đầu[FONT="] .- 69 -

[FONT="]1. Ý tưởng[FONT="] - 69 -

[FONT="]2. Mô hình[FONT="] .- 69 -

[FONT="]II. Bài toán nguời du lịch[FONT="] .- 70 -

[FONT="]1. Bài toán[FONT="] .- 70 -

[FONT="]2. Ý tưởng[FONT="] - 70 -

[FONT="]3. Thiết kế[FONT="] .- 71 -

[FONT="]4. Cài đặt[FONT="] .- 73 -

[FONT="]III. Bài toán cái túi xách[FONT="] - 74 -

[FONT="]1. Bài toán[FONT="] .- 74 -

[FONT="]2. Ý tưởng[FONT="] - 74 -

[FONT="]3. Thiết kế thuật toán[FONT="] - 75 -

[FONT="]4. Cài đặt[FONT="] .- 78 -

[FONT="]Bài tập[FONT="] .- 79 -

[FONT="]Chương 5: PHƯƠNG PHÁP THAM LAM[FONT="] - 81 -

[FONT="]I. Mở đầu[FONT="] .- 81 -

[FONT="]1. Ý tưởng[FONT="] - 81 -

[FONT="]2. Mô hình[FONT="] .- 81 -

[FONT="]II. Bài toán người du lịch[FONT="] .- 82 -

[FONT="]1. Bài toán[FONT="] .- 82 -

[FONT="]2. Ý tưởng[FONT="] - 82 -

[FONT="]3. Thuật toán[FONT="] .- 82 -

[FONT="]4. Độ phức tạp của thuật toán[FONT="] - 83 -

[FONT="]5. Cài đặt[FONT="] .- 83 -

[FONT="]III. Thuật toán Dijkstra -Tìm đường đi ngắn nhất trong đồ thị có trọng số[FONT="] .- 84 -

[FONT="]1. Bài toán[FONT="] .- 84 -

[FONT="]2. Ý tưởng[FONT="] - 85 -

[FONT="]3. Mô tả thuật toán[FONT="] - 85 -

[FONT="]4. Cài đặt[FONT="] .- 87 -

[FONT="]5. Độ phức tạp của thuật toán[FONT="] - 90 -

[FONT="]IV. Thuật toán Prim – Tìm cây bao trùm nhỏ nhất[FONT="] .- 90 -

[FONT="]1. Bài toán[FONT="] .- 90 -

[FONT="]2. Ý tưởng[FONT="] - 90 -

[FONT="]3. Mô tả thuật toán[FONT="] - 90 -

[FONT="]4. Cài đặt[FONT="] .- 91 -

[FONT="]5. Độ phức tạp thuật toán[FONT="] - 93 -

[FONT="]V. Bài toán ghi các bài hát[FONT="] - 93 -

[FONT="]1. Phát biểu bài toán[FONT="] - 93 -

[FONT="]2. Thiết kế[FONT="] .- 93 -

[FONT="]3. Độ phức tạp của thuật toán[FONT="] - 94 -

[FONT="]4. Cài đặt[FONT="] .- 94 -

[FONT="]VI. Bài toán chiếc túi xách (Knapsack)[FONT="] - 95 -

[FONT="]1. Phát biểu bài toán[FONT="] - 95 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 95 -

[FONT="]3. Độ phức tạp của thuật toán[FONT="] - 96 -

[FONT="]4. Cài đặt[FONT="] .- 96 -

[FONT="]VII. Phương pháp tham lam và Heuristic[FONT="] - 97 -

[FONT="]Bài tập[FONT="] .- 98 -

[FONT="]Chương 6 : PHƯƠNG PHÁP QUY HOẠCH ĐỘNG[FONT="] .- 100 -

[FONT="]I. Phương pháp tổng quát[FONT="] - 100 -

[FONT="]II. Thuật toán Floyd -Tìm đường đi ngắn nhất giữa các cặp đỉnh[FONT="] .- 100 -

[FONT="]1. Bài toán[FONT="] .- 100 -

[FONT="]2. Ý tưởng[FONT="] - 101 -

[FONT="]3. Thiết kế[FONT="] .- 101 -

[FONT="]4. Cài đặt[FONT="] .- 103 -

[FONT="]5. Độ phức tạp của thuật toán[FONT="] - 104 -

[FONT="]III. Nhân tổ hợp nhiều ma trận[FONT="] - 104 -

[FONT="]1. Bài toán[FONT="] .- 104 -

[FONT="]2. Ý tưởng[FONT="] - 104 -

[FONT="]3. Thiết kế[FONT="] .- 105 -

[FONT="]4. Độ phức tạp của thuật toán[FONT="] - 106 -

[FONT="]5. Cài đặt[FONT="] .- 106 -

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

[FONT="]1. Phát biểu bài toán[FONT="] - 108 -

[FONT="]2. Ý tưởng[FONT="] - 108 -

[FONT="]3. Thiết kế thuật toán[FONT="] - 109 -

[FONT="]4. Độ phức tạp của thuật toán[FONT="] - 110 -

[FONT="]5. Cài đặt[FONT="] .- 111 -

[FONT="]V. Dãy chung dài nhất của 2 dãy số[FONT="] - 111 -

[FONT="]1. Bài toán[FONT="] .- 111 -

[FONT="]2. Ý tưởng[FONT="] - 112 -

[FONT="]3. Thuật toán[FONT="] .- 112 -

[FONT="]4. Độ phức tạp của thuật toán[FONT="] - 114 -

[FONT="]5. Cài đặt[FONT="] .- 114 -

[FONT="]VI. Bài toán người du lịch[FONT="] .- 115 -

[FONT="]1. Ý tưởng[FONT="] - 116 -

[FONT="]2. Thiết kế thuật toán[FONT="] - 116 -

[FONT="]3. Độ phức tạp của thuật toán[FONT="] - 118 -

[FONT="]Bài tập[FONT="] .- 118 -

[FONT="]PHỤ LỤC[FONT="] - 120 -