Bài tập phân tích và thiết kế giải thuật năm 2024
[PDF]Phân Tích Và Thiết Kế Giải Thuật - Đh Bách Khoa Hcm - Pgs.Ts Dương Tuấn Anhappendix_a heap bottom-up construction.pdf chap1_các khái niệm căn bản.pdf chap2_chiến lược chia-để-trị (divide-and-conquer).pdf chap3_chiến lược giảm-để-trị(decrease-and-conquer).pdf chap4_chiến lược biến thể-để-trị(transform-and-conquer).pdf chap5_qui hoạch động và giải thuật tham lam.pdf chap6_giải thuật quay lui.pdf chap7_vấn đề np-đầy đủ.pdf chap8_approximation algorithms.pdf chap8_approximation algorithms partii.pdf all_exercises.pdf all_exercises_new.pdf da_fin2012_tn.pdf ex03_ans.pdf ex06_ans.pdf linhtinh&baitap.pdf all_exercises.pdf fin_2012_tn.pdf fin_2013.pdf fin_2014.pdf hình1310.jpg hình1311.jpg hình1313.jpg hình1314.jpg hình1315.jpg img_0118.jpg img_0119.jpg mid2014.pdf mid_2013.pdf các bạn tự tìm sách trên google theo gợi ý bên dưới nhé! Co3031_Phantichthietkegiaithuat.Pdf Mit.Press Introduction To Algorithms.Pdf The Algorithm Design Manual.Pdf Thiết Kế Và Đánh Giá Thuật Toán.Pdf 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ỉ 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 đủ 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. |
