tailieunhanh - Bài giảng Cơ sở lập trình nâng cao - Chương 1: Độ phức tạp của thuật toán

Bài giảng cung cấp cho người học các kiến thức: Độ phức tạp của thuật toán, ước lượng độ phức tạp của thuật toán, phân tích thuật toán, thời gian thực hiện thuật toán,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung bài giảng. | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi Mục tiêu môn học Mục tiêu cần đạt được - Nắm vững một số phương pháp Thiết kế thuật toán để giải bài toán tin học - Nắm vững một số phương pháp Tối ưu hóa chương trình 2 Nội dung môn học Chương 1: Độ phức tạp của thuật toán Chương 2: Ôn tập kỹ thuật xử lý File – Mảng – Xâu ký tự Chương 3: Lập trình Đệ quy Chương 4: Phương pháp Quay lui Chương 5: Phương pháp Nhánh cận Chương 6: Phương pháp Chia để trị Chương 7: Phương pháp Tham lam Chương 8: Phương pháp Quy hoạch động Chương 9: Phương pháp Hình học Chương 10: Tối ưu hóa chương trình 3 Tài liệu tham khảo Books Vũ Đình Hòa, Đỗ Trung Kiên, “Thuật toán và độ phức tạp của thuật toán”, NXB ĐHSP, 2007 Steven S. Skiena, “The Algorithm Design Manual”, Springer , 2008 Art Lew, Holger Mauch, “Dynamic Programming – A Computational Tool”, Springer, 2007 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, 2009 Jon Bentley, “Writing Efficient Programs”, Prentice-Hall, 1982 Jon Bentley, “Programming Pearls”, Addison Wesley, 2000 4 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN Chương 1 5 Nội dung Độ phức tạp của thuật toán Ước lượng độ phức tạp của thuật toán 6 ĐỘ PHỨC TẠP CỦA THUẬT TOÁN 7 Thời gian thực hiện thuật toán Phân tích thuật toán: Phân tích thuật toán là xác định lượng tài nguyên cần thiết để thực thi thuật toán: Thời gian thực hiện thuật toán Bộ nhớ cần thực hiện thuật toán Tiêu chí thường được dùng để đánh giá thuật toán là thời gian thực hiện thuật toán. 8 Thời gian thực hiện thuật toán Mục tiêu của phân tích thuật toán So sánh để chọn ra thuật toán nào chạy nhanh nhất Tìm những yếu điểm của thuật toán để Cải tiến thuật toán tốt hơn 2 cách “đo” thời gian thực hiện của thuật toán Thời gian thực hiện thực tế Thời gian thực hiện lý thuyết (Phân tích thuật toán) Thời gian thực hiện thuật toán | CƠ SỞ LẬP TRÌNH NÂNG CAO Biên soạn: Quang Toại TonQuangToai@ TPHCM, NĂM 2013 TRƯỜNG ĐẠI HỌC NGOẠI NGỮ - TIN HỌC KHOA CÔNG NGHỆ THÔNG TIN 1 45T/4 = 11 buoi Mục tiêu môn học Mục tiêu cần đạt được - Nắm vững một số phương pháp Thiết kế thuật toán để giải bài toán tin học - Nắm vững một số phương pháp Tối ưu hóa chương trình 2 Nội dung môn học Chương 1: Độ phức tạp của thuật toán Chương 2: Ôn tập kỹ thuật xử lý File – Mảng – Xâu ký tự Chương 3: Lập trình Đệ quy Chương 4: Phương pháp Quay lui Chương 5: Phương pháp Nhánh cận Chương 6: Phương pháp Chia để trị Chương 7: Phương pháp Tham lam Chương 8: Phương pháp Quy hoạch động Chương 9: Phương pháp Hình học Chương 10: Tối ưu hóa chương trình 3 Tài liệu tham khảo Books Vũ Đình Hòa, Đỗ Trung Kiên, “Thuật toán và độ phức tạp của thuật toán”, NXB ĐHSP, 2007 Steven S. Skiena, “The Algorithm Design Manual”, Springer , 2008 Art Lew, Holger Mauch, “Dynamic Programming – A Computational Tool”, Springer, .