Bỏ qua tới nội dung chính

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ủ đề.

  1. Thiết kế và phân tích thuật toán

    Design and Analysis of Algorithms

    Trung bìnhkhoảng 41 giờ

    Giáo trình: Algorithms

    Khóa chính: Design and Analysis of Algorithms · MIT

  2. Lý thuyết tính toán

    Theory of Computation

    Trung bìnhkhoảng 40 giờ

    Giáo trình: Introduction to Theoretical Computer Science

    Khóa chính: Lý thuyết tính toán · MIT

  3. Giải tích số

    Scientific Computing

    Trung bìnhkhoảng 46 giờ

    Cần học trước

    Toán học: Giải tích, Đại số tuyến tính

    Kiến thức cốt lõi: Lập trình

    Giáo trình: Python Programming and Numerical Methods: A Guide for Engineers and Scientists

  4. Khoa học và công nghệ thông tin lượng tử

    Quantum Information Science and Technology

    Nâng caokhoảng 35 giờ

    Cần học trước

    Toán học: Đại số tuyến tính, Xác suất thống kê

    Khoa học tự nhiên: Cơ học cổ điển

    Giáo trình: Understanding Quantum Information and Computation

    Khóa chính: Understanding Quantum Information and Computation · IBM Quantum

  5. Kinh tế học thuật toán

    Algorithmic Economics

    Nâng caokhoảng 33 giờ

    Cần học trước

    Trong nhóm: Thiết kế và phân tích thuật toán

    Toán học: Xác suất thống kê

    Giáo trình: Lecture Notes on Algorithmic Game Theory (CS364A, Stanford)

    Khóa chính: Algorithmic Game Theory · Stanford

  6. Thuật toán cho sinh học tính toán

    Algorithms for Computational Biology

    Nâng caokhoảng 35 giờ

    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

  7. Logic cho khoa học máy tính

    Logic for Computer Science

    Trung bìnhkhoảng 35 giờ

    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ử