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


DOWNLOAD TÀI LIỆU

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 -

 

MẸO: Like để tham gia cộng đồng CÔNG PHÁ TRẮC NGHIỆM
Các em có thể share tài liệu này trên FB của mình nếu cảm thấy hay-->

THÀNH VIÊN MỚI NHẤT

  • quanghit96@gmail.com
  • Tranthuphuong2922000@gmail.come
  • trongdinhnth@gmail.com
  • pvtinh1988@gmail.com
  • ngocthanh.tinhoc@gmail.com

THÀNH VIÊN VIP MỚI

  • amvspr@gmail.com
  • Tahoangthaomien@gmail.com
  • phamkhanvl@gmail.com
  • thuyuyen11ss2@gmail.com
  • lekhan009988@email.com
Scroll