Nhóm chủ đề 6/7
Thuật toán và lý thuyết tính toán
Algorithms and Computation
Phần lý thuyết của khoa học máy tính: thiết kế và phân tích thuật toán, lý thuyết tính toán, logic, và các hướng mới như tính toán lượng tử, kinh tế thuật toán, sinh học tính toán.
7 chủ đềkhoảng 265 giờ24 khóa học15 sách
Theo cấp độ: 4 Trung bình · 3 Nâng cao
Giới thiệu
Nếu Core subjects dạy dùng thuật toán, nhóm này dạy thiết kế và chứng minh chúng, và hỏi câu hỏi sâu hơn: bài toán nào máy tính giải được, giải nhanh được, hay không bao giờ giải được. Trọng tâm là Thiết kế và phân tích thuật toán, Lý thuyết tính toán và Logic cho khoa học máy tính; ba chủ đề còn lại mở ra các hướng liên ngành: tính toán lượng tử, kinh tế thuật toán (lý thuyết trò chơi, thiết kế cơ chế) và thuật toán cho sinh học tính toán.
Thứ tự nên học
Học thiết kế và phân tích thuật toán cùng lý thuyết tính toán trước, logic song song. Các chủ đề liên ngành học sau, tùy hứng thú: lượng tử cần thêm đại số tuyến tính, kinh tế thuật toán cần xác suất, sinh học tính toán cần quy hoạch động.
Cách học
Đây là nhóm của chứng minh: hãy tự viết chứng minh tính đúng và độ phức tạp, không chỉ đọc. Làm bài tập trong sách (Erickson, Sipser, CLRS…) và luyện thêm bài toán thuật toán khó giúp bạn nhanh chóng nhận ra các kỹ thuật lặp lại: quy hoạch động, tham lam, quy dẫn.
Nên học trước
Thứ tự học
Sắp theo mục "Nên học trước" trong hướng dẫn của từng chủ đề.
Cần học trước
Kiến thức cốt lõi: Cấu trúc dữ liệu và giải thuật, Toán cho khoa học máy tính
Giáo trình: Algorithms
Khóa chính: Design and Analysis of Algorithms · MIT
Cần học trước
Kiến thức cốt lõi: Toán cho khoa học máy tính, Cấu trúc dữ liệu và giải thuật
Giáo trình: Introduction to Theoretical Computer Science
Khóa chính: Lý thuyết tính toán · MIT
Giáo trình: Python Programming and Numerical Methods: A Guide for Engineers and Scientists
- Nâng caokhoảng 35 giờ
Khoa học và công nghệ thông tin lượng tử
Quantum Information Science and Technology
Giáo trình: Understanding Quantum Information and Computation
Khóa chính: Understanding Quantum Information and Computation · IBM Quantum
Giáo trình: Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)
Khóa chính: Algorithmic Game Theory · Stanford
Cần học trước
Trong nhóm: Thiết kế và phân tích thuật toán
Khoa học tự nhiên: Sinh học
Toán học: Xác suất thống kê
Giáo trình: Bioinformatics Algorithms: An Active Learning Approach
Khóa chính: Bioinformatics Specialization · UC San Diego
Cần học trước
Kiến thức cốt lõi: Toán cho khoa học máy tính
Giáo trình: forall x: Calgary — An Introduction to Formal Logic
Khóa chính: Logic for CS · IIT Delhi
Kỹ năng đạt được
- Thiết kế thuật toán bằng chia để trị, quy hoạch động, tham lam, đồ thị
- Chứng minh tính đúng và phân tích độ phức tạp chặt chẽ
- Xác định bài toán khó (NP-đầy đủ) và dùng quy dẫn
- Hiểu mô hình tính toán: ô-tô-mát, máy Turing, tính khả quyết
- Diễn đạt và kiểm chứng tính chất bằng logic hình thức
- Nắm nguyên lý cơ bản của thuật toán lượng tử và lý thuyết trò chơi
Nghề nghiệp
- Nghiên cứu viên thuật toán và lý thuyết tính toán
- Kỹ sư thuật toán (tối ưu hóa, tìm kiếm, định tuyến)
- Lập trình viên thi đấu, kỹ sư ở các công ty coi trọng thuật toán
- Kỹ sư tin sinh học
- Nghiên cứu điện toán lượng tử