1
PHÂN TÍCH VÀ
THI T K GI I THU TẾ Ế Ả Ậ
ANALYS AND DESIGN
ALGORITHMS
1
2
Mục tiêu môn học
Cung cấp kiến thức và kỹ năng trong
việc phân tích độ phức tạp tính toán
của giải thuật.
Tìm hiểu các chiến thuật thiết kế giải
thuật
2
3
Nội dung môn học
3
TT N i dungộS ố
ti tế
Phân b th i gianổ ờ
Ghi
chú
Lý
thuyế
t
Bài
T pậT ự
h cọ
1Các khái ni m căn b n v phân tích ệ ả ề
đ ph c t p gi i thu tộ ứ ạ ả ậ 6 6 0 10
2Phân tích đ ph c t p c a m t s gi i ộ ứ ạ ủ ộ ố ả
thu t s p th t và tìm ki mậ ắ ứ ự ế 8 8 3 20
3Phân tích đ ph c t p c a m t s gi i ộ ứ ạ ủ ộ ố ả
thu t trên c u trúc d li uậ ấ ữ ệ 9 9 3 20
4Phân tích đ ph c t p c a m t s gi i ộ ứ ạ ủ ộ ố ả
thu t đ thậ ồ ị 5 5 3 20
5Các chi n l c thi t k gi i thu tế ượ ế ế ả ậ 8 8 3 15
6V n đ NP-đ y đấ ề ầ ủ 9 9 3 20
T NGỔ60 60 0 105
4
Đánh giá kết quả
1. Ki m tra gi a kỳể ữ : T lu nự ậ
Đi m Ki m tra gi a kỳ < 4 ể ể ữ không đ c thi k t thúc môn ượ ế
h c l iọ ạ
1. Ki m tra cu i kỳể ố : T lu nự ậ
2. Bài t p l nậ ớ : làm các bài t p ậ
3. Đi m Đ tài < 4ể ề không đ c thi k t thúc môn ượ ế h c l iọ ạ
4. Thi k t thúc mônế: T lu nự ậ
5. Ki m tra th ng kỳể ườ
4
5
Tài liệu học tập
Giáo trình:
[1] Cormen, T. H., Leiserson, C. E, and Rivest,
Introduction to Algorithms, The MIT Press,
1997.
Tham khảo:
[2] Sedgewick, Algorithms in C++, Addison-
Wesley, 1998
[3] Weiss, M.A, Data Structures and Algorithm
Analysis in C , The Benjamin/Cummings
Publishing, 1993
5