Toán rời rạc và thuật toán

Học phần cung cấp các kiến thức về phân tích và thiết kế các thuật toán rời rạc, đặc biệt tập trung vào các vấn đề liên quan tới đồ thị. Bên cạnh phần tổng quan, các nội dung được đi sâu bao gồm cây bao trùm nhỏ nhất, matroid, luồng cực đại và môđun con, độ khó NP, các thuật toán xấp xỉ, các thuật toán ngẫu nhiên hóa, phương pháp xác suất, thưa hóa đồ thị.

Tài liệu tham khảo

• Tài liệu bắt buộc
  • Bài giảng của giảng viên
  • Kleinberg J., Tardos E (2006), Algorithm Design, Addison Wesley,
• Tài liệu tham khảo thêm
  • Alon N., Spencer J. H. (2000), The Probabilistic Method, John Wiley & Sons.
  • Motwani R, Raghavan P. (1995), Randomized Algorithms, Cambridge University Press.
  • Reinhard D (2010), Graph Theory, Springer, 4th edition.
  • Vijay V (2003), Approximation Algorithms, Springer.