Học phần cung cấp các kiến thức cơ bản giúp học viên có thể đánh giá được độ phức tạp tính toán của một thuật toán khi giải một bài toán, cũng như phân biệt được độ khó của một số bài toán. Các lớp bài toán quan trọng trong lí thuyết độ phức tạp như P, NP- đầy đủ, NP- khó được nghiên cứu, phân tích và chứng minh. Bên cạnh đó, học viên sẽ được nghiên cứu một số bài toán ứng dụng quan trọng trong thực tế, phân tích độ phức tạp của chúng nhằm đánh giá và đưa ra thuật toán phù hợp.
Tài liệu bắt buộc
- Cormen T., Leiserson C., Rivest R. (1990), Introduction to Algorithms, McGraw-Hill.
- Vanderbei R. (2001), Linear Programming: Foundations and Extensions, 2nd edition, Springer.
Tài liệu tham khảo thêm
