TL;DR

Giáo sư Boaz Barak (Harvard) phát hành miễn phí "Introduction to Theoretical Computer Science" - giáo trình chính thức của Harvard CS 121. 600 trang, 23 chương, bao phủ toàn bộ nền tảng lý thuyết từ Boolean circuits đến quantum computing. Tải PDF tại introtcs.org, hoàn toàn miễn phí theo Creative Commons BY-NC-ND 4.0.

Introduction to Theoretical Computer Science - Boaz Barak

Cuốn sách này là gì?

Introduction to Theoretical Computer Science là giáo trình đại học do Boaz Barak - giáo sư Khoa học Máy tính tại Harvard - biên soạn và liên tục cập nhật. Sách được dùng làm tài liệu chính thức cho:

  • Harvard CS 121 - Introduction to Theoretical Computer Science

  • UVa CS 3102 (University of Virginia)

  • UCLA CS 181

Không giống các giáo trình lý thuyết truyền thống, cuốn sách này tiếp cận theo hướng xây dựng dần từ những mô hình tính toán cơ bản nhất, kết nối chặt chẽ giữa lý thuyết và lập trình thực tế - bao gồm cả code Python minh họa và notebook Jupyter đi kèm.

Điểm khác biệt so với sách giáo khoa truyền thống

Điểm độc đáo nhất của cuốn sách: bắt đầu bằng Boolean circuits, không phải finite automata - khác hoàn toàn so với Sipser hay Hopcroft-Ullman. Barak lập luận rằng mô hình mạch số (circuits) phù hợp hơn với nền tảng học sinh đã có, đồng thời trực tiếp liên quan đến cryptography và quantum computing.

Tiêu chí

Barak (introtcs.org)

Sipser (truyền thống)

Mô hình mở đầu

Boolean circuits / NAND

Finite automata / DFA

Mô hình độ phức tạp

RAM machines

Multi-tape Turing machines

Phong cách chứng minh

Constructive, có Python code

Toán học truyền thống

Chủ đề nâng cao

Cryptography, quantum, randomized algorithms

Rất ít

Giá

Miễn phí (CC BY-NC-ND 4.0)

~$100+

Sách cũng dùng RAM model (thay vì Turing machines) cho time complexity - quen thuộc hơn với sinh viên đã học algorithms, giúp các ký hiệu Big-O có nghĩa thực tế hơn.

23 chương - Bạn sẽ học gì?

Sách chia làm 4 phần chính:

  • Phần I - Finite Computation (Ch. 0-5): Biểu diễn dữ liệu, Boolean circuits, cổng NAND, tính toán mọi hàm hữu hạn, tính phổ quát (universality), code-as-data

  • Phần II - Infinite Domains (Ch. 6-11): Automata, regular expressions, Turing machines, NAND-TM, RAM machines, lambda calculus, uncomputable problems (halting problem, Rice's theorem), Gödel incompleteness

  • Phần III - Efficiency (Ch. 12-17): Time complexity, P vs. NP, polynomial reductions, NP-completeness (Cook-Levin theorem), space complexity

  • Phần IV - Advanced Topics (Ch. 18-23): Probability, randomized algorithms, BPP, derandomization, cryptography, quantum computing (Shor's algorithm)

Đặc biệt, sách xây dựng hai ngôn ngữ lập trình sư phạm riêng - NAND-CIRC (cho straight-line computation) và NAND-TM (cho loop/Turing-machine computation) - rồi chứng minh chúng tương đương với RAM machines, lambda calculus và cellular automata. Đây là cách hiếm gặp để sinh viên thực sự "thấy" tại sao mọi mô hình tính toán đều tương đương.

Ai nên đọc cuốn sách này?

Cuốn sách phù hợp nhất với:

  • Sinh viên CS năm 2-3 đang hoặc sắp học một khóa lý thuyết tính toán

  • Lập trình viên tự học muốn lấp gap nền tảng lý thuyết - đặc biệt về P vs. NP, cryptography, quantum computing

  • Giảng viên muốn thiết kế khóa học lý thuyết hiện đại, bao phủ cả cryptography và quantum thay vì chỉ dừng ở automata

Yêu cầu: Không cần ngôn ngữ lập trình cụ thể, chỉ cần quen với lập trình cơ bản và toán học đại học (tập hợp, hàm số, chứng minh cơ bản - đã được ôn trong Ch. 1).

Tải xuống và bắt đầu học

Tất cả tài nguyên hoàn toàn miễn phí:

Sách được cập nhật liên tục (lần cuối: tháng 12/2023) và nhận đóng góp từ cộng đồng qua GitHub. Blog Windows on Theory của Barak giải thích chi tiết các quyết định sư phạm đằng sau từng lựa chọn thiết kế.

Nếu bạn đang tìm một nguồn tài liệu miễn phí, nghiêm túc, và hiện đại nhất để học lý thuyết tính toán - đây là lựa chọn đáng đọc nhất hiện tại.

Via: introtcs.org, Harvard CS 121, Windows on Theory.