Tài liệu Thiết kế và đánh giá thuật toán

ĐỀ TÀI: Thiết kế và đánh giá thuật toán

[FONT=]MỤC LỤC[/COLOR]
[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=tahoma][FONT=]4. Phân tích thuật toán đệ qui.[FONT=] .- 21 -[/FONT]
[COLOR=#363636][FONT=tahoma][FONT=]5. Các phép toán trên các ký hiệu tiệm cận[FONT=] - 25 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]6. Phân tích trường hợp trung bình[FONT=] - 26 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]V. Tối ưu thuật toán[FONT=] - 27 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Kỹ thuật tối ưu các vòng lặp[FONT=] - 27 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Tối ưu việc rẽ nhánh[FONT=] .- 30 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]Bài tập[FONT=] .- 30 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]Chương 2 : PHƯƠNG PHÁP CHIA ĐỂ TRỊ [FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]I. Mở đầu[FONT=] .- 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Ý tưởng[FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Mô hình[FONT=] .- 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]II. Thuật toán tìm kiếm nhị phân.[FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Phát biểu bài toán[FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Ý tưởng[FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]3. Mô tả thuật toán[FONT=] - 33 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]4. Độ phức tạp thời gian của thuật toán[FONT=] .- 34 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]5. Cài đặt[FONT=] .- 34 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]III. Bài toán MinMax[FONT=] - 35 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Phát biểu bài toán[FONT=] - 35 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Ý tưởng[FONT=] - 35 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]3. Thuật toán[FONT=] .- 35 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]4. Độ phức tạp thuật toán[FONT=] - 36 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]5. Cài đặt[FONT=] .- 36 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]IV. Thuật toán QuickSort[FONT=] .- 36 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Ý tưởng[FONT=] - 37 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Mô tả thuật toán[FONT=] - 37 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]3. Độ phức tạp của thuật toán[FONT=] - 38 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]V. Thuật toán nhân Strassen nhân 2 ma trận[FONT=] - 39 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Bài toán[FONT=] .- 39 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Mô tả[FONT=] .- 39 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]VI. Bài toán hoán đổi 2 phần trong 1 dãy[FONT=] - 41 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Phát biểu bài toán[FONT=] - 41 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Ý tưởng[FONT=] - 41 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]3. Thuật toán[FONT=] .- 41 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]4. Độ phức tạp thuật toán[FONT=] - 43 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]5. Cài đặt[FONT=] .- 43 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]VII. Trộn hai đường trực tiếp[FONT=] .- 44 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]1. Bài toán[FONT=] .- 44 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]2. Ý tưởng[FONT=] - 44 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]3. Thiết kế[FONT=] .- 45 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]Bài tập[FONT=] .- 50 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]Chương 3 : PHƯƠNG PHÁP QUAY LUI[FONT=] .- 53 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][FONT=]I. Mở đầu[FONT=] .- 53 -[/FONT][/COLOR][FONT=tahoma]
[COLOR=#363636][FONT=tahoma][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 .- 118 -[/FONT][/COLOR][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font][/font]