Phân Tích Và Thiết Kế Giải Thuật

Giáo trình Tiếng Anh

CO3031_Phantichthietkegiaithuat_MIT.Press.Introduction.to.Algorithms.2nd.Edition.eBook-TLFeBOOK.pdf
CO3031_Phantichthietkegiaithuat_Introduction to the Design and Analysis of Algorithms 3rd ed Levitin.pdf
CO3031_Phantichthietkegiaithuat.pdf

Giáo trình, bài giảng

chap8_approximation algorithms partii.pdf
chap8_approximation algorithms.pdf
chap7_vấn đề np-đầy đủ.pdf
chap6_giải thuật quay lui.pdf
chap5_qui hoạch động và giải thuật tham lam.pdf
chap4_chiến lược biến thể-để-trị(transform-and-conquer).pdf
chap3_chiến lược giảm-để-trị(decrease-and-conquer).pdf
chap2_chiến lược chia-để-trị (divide-and-conquer).pdf
chap1_các khái niệm căn bản.pdf
appendix_a heap bottom-up construction.pdf

Bài tập, thực hành

linhtinh&baitap.pdf
ex06_ans.pdf
ex03_ans.pdf
da_fin2012_tn.pdf
all_exercises_new.pdf
all_exercises.pdf

Đề thi

mid_2013.pdf
mid2014.pdf
img_0119.jpg
img_0118.jpg
hình1315.jpg
hình1314.jpg
hình1313.jpg
hình1311.jpg
hình1310.jpg
fin_2014.pdf
fin_2013.pdf
fin_2012_tn.pdf
all_exercises.pdf

Giới thiệu, nội dung môn học

Môn học này nhằm giới thiệu những kỹ thuật khác nhau để phân tích và thiết kế giải thuật. Sinh viên sẽ được học về khung thức để phân tích độ phức tạp (trường hợp xấu nhất và trường hợp trung bình) của giải thuật và lý thuyết NP-đầy đủ. Ngoài ra sinh viên còn được học về những chiến lược thiết kế giải thuật tiêu biểu như brute-force, giảm để trị, chia để trị, biến thể để trị, qui hoạch động, tham lam, quay lui, nhánh và cận và giải thuật xấp xỉ. * Nội dung tóm tắt môn học - Các khái niệm căn bản về phân tích độ phức tạp giải thuật và thiết kế giải thuật - Chiến lược chia-để-trị - Chiến lược giảm-để-trị - Chiến lược biến thể-để-trị - Quy hoạch động và giải thuật tham lam - Giải thuật quay lui và giải thuật nhánh-và-cận - Vấn đề NP-đầy đủ - Giải thuật xấp xỉ

Kết quả cần đạt được

Có thể phân tích độ phức tập của giải thuật lặp và đệ quy, và như vậy có thể ước lượng được tính hữu hiệu của các giải thuật. L.O.1.1 – Phân tích độ phức tạp trong trường hợp xấu nhất của những giải thuật lặp đơn giản L.O.1.2 – Phân tích độ phức tạp trong trường hợp xấu nhất của những giải thuật đệ quy, dựa vào hệ thức truy hồi L.O.1.3 – Phân biệt được những lớp khác nhau của độ phức tạp của giải thuật L.O.1.4 – Phân tích độ phức tạp trong trường hợp trung bình của một số giải thuật đơn giản L.O.1.5 – Có thể sử dụng ký hiệu O lớn để phát biểu về cận trên của độ phức tạp thời gian /chỗ bộ nhớ của giải thuật L.O.1.6 – Có thể xác định được tác vụ căn bản của một giải thuật để dựa trên đó tính toán độ phức tạp của giải thuật ấy. L.O.1.7 – Có thể cho thí dụ về sự đánh đổi giữa thời gian thực thi và chỗ bộ nhớ của các giải thuật Cải thiện được khả năng thiết kế giải thuật trong nhiều lãnh vực khác nhau. L.O.2.1 – Đối với mỗi chiến lược thiết kế giải thuật, có thể nêu ra một thí dụ thực tế có áp dụng chiến lược đó. L.O.2.2 – Dùng chiến lược chia để trị để giải một bài toán thích hợp với chiến lược này. L.O.2.3 – Dùng chiến lược giảm để trị để giải một bài toán thích hợp với chiến lược này. L.O.2.4 – Dùng chiến lược biến thể để trị để giải một bài toán thích hợp với chiến lược này. L.O.2.5 – Dùng chiến lược quy hoạch động để giải một bài toán thích hợp với chiến lược này. L.O.2.6 – Dùng chiến lược tham lam để giải một bài toán thích hợp với chiến lược này. L.O.2.7 - Dùng chiến lược quay lui đệ quy để giải một bài toán thích hợp với chiến lược này. L.O.2.8 - Dùng chiến lược nhánh-và-cận để giải một bài toán thích hợp với chiến lược này. L.O.2.9 - Dùng giải thuật xấp xỉ để giải một bài toán thích hợp với chiến lược này. Hiểu biết về vấn đề NP-đầy đủ L.O.3.1 - Định nghĩa được các lớp bài toán P và NP L.O.3.2 - Định nghĩa được lớp bài toán NP-đầy đủ L.O.3.3. - Có thể cung cấp một số thí dụ về bài toán NP-đầy đủ L.O.3.4 - Có thể chứng minh một bài toán là NP-đầy đủ bằng cách thu giảm một bài toán NP-đầy đủ đã biết về nó. L.O.3.5 - Nắm vững một số phương pháp để đối phó với các bài toán NP đầy đủ

Tài liệu tham khảo

Sách, Giáo trình chính: [1] Introduction to Algorithms, 3rd Edition – T. H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, The MIT Press, 2009. [2] Introduction to the Design and Analysis of Algorithms, 3rd Edition- A. Levitin, Pearson- Addison-Wesley, 2012. Sách tham khảo: [1] Algorithms in C++ – R. Sedgewick, Addison-Wesley, 1998. [2] Problems on Algorithms, 2nd Edition – I. Parberry & W. Gasarch, 2002.