ĐỀ CƯƠNG MÔN HỌC

Tên môn học     : Phân tích và thiết kế thuật toán nâng cao

Mã môn học       : COM604

Số tín chỉ            : 3 tín chỉ

1. MÔ TẢ MÔN HỌC

• Môn học nhằm mục đích giúp cho học viên làm quen với thiết kế các thuật toán máy tính cũng như phương pháp phân tích các thuật toán phức tạp.
• Môn học này là phần tiếp theo của các môn học Cấu trúc dữ liệu và Thuật giải ở bậc đại học. Ngoài ra, học viên cần có những kiến thức cơ sở của môn Toán Tin học.

2. MỤC TIÊU MÔN HỌC

2.1. Mục tiêu chung: Sau khi hoàn tất môn học, học viên sẽ có khả năng áp dụng các mô hình phân tích và thiết kế thuật toán vào các bài toán kỹ thuật.

2.2. Mục tiêu cụ thể:

• Phân tích hiệu suất của thuật toán.
• Chứng minh tính đúng đắn của thuật toán.
• Nắm được các thuật toán và cấu trúc dữ liệu chính.
• Áp dụng được các mô hình phân tích và thiết kế thuật giải quan trọng.
• Chứng minh tính đúng đắn của thuật toán.
• Phân tích thời gian chạy của thuật toán.
• Mô tả và áp dụng các mô hình: chia để trị, thuật giải ngẫu nhiên, lập trình động, giải thuật tham lam, phân tích khấu hao, so khớp chuỗi và hình học tính toán.
• Có tinh thần làm việc nghiêm túc, trung thực.
• Có khả năng giải quyết vấn đề độc lập.

​3. NỘI DUNG GIẢNG DẠY

• Chia để trị
• Phân tích xác suất và thuật giải ngẫu nhiên
• Lập trình động
• Giải thuật tham lam
• Phân tích khấu hao
• So khớp chuỗi
• Hình học tính toán
• Độ phức tạp thuật toán

4. HỌC LIỆU

4.1. Giáo trình

• [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009. 

• [2] Mark Allen Weiss, Data structures and algorithm analysis in Java, Pearson, 2014.

4.2. Tài liệu tham khảo

• [3] Anuj Bhardwaj, Parag Verma, Design and Analysis of Algorithm, Alpha Science Intl Ltd, 2016.

• [4] Thư viện học liệu MIT OpenCourseWare - khóa học Design and Analysis of Algorithms (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015)

5. ĐÁNH GIÁ MÔN HỌC

• Quá trình/Giữa kỳ: 50%
• Cuối kỳ: 50%

6. SỐ GIỜ HỌC

• Số giờ học tại lớp  : 45 tiết