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

Hướng dẫn học chủ đề

Lý thuyết tính toán

Theory of Computation

Trung bìnhkhoảng 40 giờ6 bước

Lý thuyết tính toán: automat, văn phạm hình thức và giới hạn của những gì máy tính có thể giải quyết được.

Bắt đầu học

Bạn sẽ học được gì

  • Xây dựng và chứng minh tính đúng đắn của ô-tô-mát hữu hạn (DFA/NFA) cho một ngôn ngữ chính quy cho trước
  • Chuyển đổi qua lại giữa biểu thức chính quy, NFA và DFA; dùng bổ đề bơm để chứng minh một ngôn ngữ không chính quy
  • Thiết kế văn phạm phi ngữ cảnh và ô-tô-mát đẩy xuống cho một ngôn ngữ lập trình đơn giản
  • Giải thích luận đề Church-Turing và mô phỏng máy Turing cho các bài toán tính toán cơ bản
  • Chứng minh một bài toán không khả quyết bằng quy dẫn từ Bài toán dừng
  • Phân loại bài toán vào P, NP, PSPACE và chứng minh NP-đầy đủ bằng quy dẫn đa thức

Nên học trước

Giới thiệu

Lý thuyết tính toán trả lời ba câu hỏi lớn: một máy tính lý tưởng tính được gì (automata, văn phạm), giới hạn tuyệt đối của tính toán ở đâu (khả quyết/bất khả quyết), và trong giới hạn đó, bài toán nào thực tế giải nhanh được (độ phức tạp). Đây là môn trừu tượng nhất trong khoa học máy tính, nhưng mọi khái niệm đều có mô hình cụ thể để vẽ ra giấy.

Ba mô hình máy tính, từ yếu đến mạnh

Ô-tô-mát hữu hạn (bộ nhớ cố định) → ô-tô-mát đẩy xuống (thêm một ngăn xếp) → máy Turing (thêm băng đọc/ghi vô hạn). Mỗi mô hình mạnh hơn nhận diện được lớp ngôn ngữ lớn hơn: chính quy ⊂ phi ngữ cảnh ⊂ khả quyết đệ quy. Luôn tự hỏi: mô hình này không làm được gì — chính giới hạn đó (bổ đề bơm, tính không khả quyết) mới là nội dung sâu sắc nhất.

Từ "tính được" đến "tính nhanh"

Máy Turing xác định cái gì tính được; độ phức tạp thời gian hỏi tính nhanh cỡ nào. Kỹ thuật quy dẫn xuất hiện ở cả hai tầng: quy dẫn từ Bài toán dừng để chứng minh bất khả quyết, quy dẫn đa thức từ 3-SAT để chứng minh NP-đầy đủ. Nắm vững một kiểu quy dẫn sẽ giúp hiểu kiểu còn lại rất nhanh.

Học chủ động, đừng chỉ học định nghĩa

Với mỗi định lý, tự vẽ ví dụ nhỏ trước khi đọc chứng minh: một DFA 3 trạng thái, một máy Turing mô phỏng phép cộng. Các bài giảng và bộ đề MIT 18.404 đi kèm lộ trình này rất giàu ví dụ — nên làm bài tập ngay sau mỗi buổi thay vì dồn lại.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

CC BY-NC-NDTrung bìnhTiếng Anh

Vì sao chọn: Sách mở, miễn phí toàn văn (CC BY-NC-ND), trình bày lý thuyết tính toán theo hướng hiện đại và trực quan, có thêm chương về mật mã học và tính toán lượng tử. Chọn làm sách chính vì bám sát đúng lộ trình automata → khả quyết → độ phức tạp của môn học này và không tốn chi phí.

Nên đọc: Automata and Regular Expressions; Defining Computation; Equivalent Models of Computation; Universality and Uncomputability; NP, NP-Completeness and the Cook-Levin Theorem; Space Bounded Computation

Introduction to the Theory of Computation

Michael Sipser · 2013 · Bản thứ 3

Có phíTrung bìnhTiếng Anh458 trang

Sách giáo khoa kinh điển nhất của môn; các bài giảng MIT 18.404J trong lộ trình này bám theo đúng cấu trúc chương của sách. Nên đọc song song để có thêm bài tập và cách trình bày chứng minh cô đọng, chuẩn mực; bản tiếng Anh, không có bản đọc miễn phí hợp pháp.

Nên đọc: Chương 1–2 (Automata và ngôn ngữ), Chương 3–6 (Lý thuyết khả quyết), Chương 7–9 (Lý thuyết độ phức tạp)

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Ô-tô-mát hữu hạn và ngôn ngữ chính quy

    khoảng 6 giờ

    Học DFA, NFA, biểu thức chính quy và các phép chuyển đổi qua lại giữa chúng; dùng bổ đề bơm để chứng minh một ngôn ngữ không chính quy. Tự xây một DFA nhận diện chuỗi nhị phân chia hết cho 3, rồi chứng minh bằng bổ đề bơm rằng {0^n1^n} không chính quy.

  2. Bước 2: Văn phạm phi ngữ cảnh và ô-tô-mát đẩy xuống

    khoảng 6 giờ

    Học văn phạm phi ngữ cảnh, ô-tô-mát đẩy xuống và bổ đề bơm cho ngôn ngữ phi ngữ cảnh. Viết văn phạm phi ngữ cảnh cho biểu thức số học có ngoặc và chuyển nó thành một ô-tô-mát đẩy xuống.

  3. Bước 3: Máy Turing và luận đề Church-Turing

    khoảng 6 giờ

    Định nghĩa máy Turing, các biến thể tương đương (nhiều băng, không đơn định) và luận đề Church-Turing. Mô phỏng tay một máy Turing đơn giản thực hiện phép cộng nhị phân trên băng.

  4. Bước 4: Tính khả quyết và quy dẫn

    khoảng 7 giờ

    Học các bài toán khả quyết cho automata/văn phạm, Bài toán dừng và kỹ thuật quy dẫn để chứng minh bất khả quyết. Chứng minh bài toán 'một chương trình có bao giờ in ra chuỗi rỗng không' là không khả quyết bằng quy dẫn từ Bài toán dừng.

  5. Bước 5: Độ phức tạp thời gian: P, NP và NP-đầy đủ

    khoảng 8 giờ

    Học lớp P, NP, định nghĩa NP-đầy đủ và Định lý Cook-Levin. Tự quy dẫn đa thức từ 3-SAT sang một bài toán đồ thị quen thuộc (như Independent Set) để chứng minh nó NP-đầy đủ.

  6. Bước 6: Độ phức tạp không gian và các lớp nâng cao

    khoảng 7 giờ

    Học PSPACE, Định lý Savitch, các lớp L/NL và các chủ đề nâng cao (định lý phân cấp, tính toán xác suất). Chọn một bài toán trò chơi hai người (như Generalized Geography) và chứng minh nó thuộc PSPACE.

Khái niệm chính

Ô-tô-mát hữu hạn (DFA/NFA)
Mô hình tính toán với số trạng thái hữu hạn, không có bộ nhớ ngoài; nhận diện đúng lớp ngôn ngữ chính quy.
Bổ đề bơm (Pumping lemma)
Công cụ chứng minh một ngôn ngữ không thuộc một lớp (chính quy hoặc phi ngữ cảnh) bằng cách chỉ ra chuỗi đủ dài luôn 'bơm' được mà vẫn phải thuộc ngôn ngữ, dẫn đến mâu thuẫn.
Văn phạm phi ngữ cảnh & Ô-tô-mát đẩy xuống
Văn phạm sinh ra cấu trúc lồng nhau (ngoặc, cú pháp lập trình); ô-tô-mát đẩy xuống là automaton tương đương, thêm một ngăn xếp vào DFA.
Máy Turing & Luận đề Church–Turing
Mô hình tính toán tổng quát nhất được biết; luận đề Church-Turing cho rằng mọi khái niệm 'thuật toán' hợp lý đều tương đương về sức mạnh với máy Turing.
Tính khả quyết & Bài toán dừng
Một bài toán khả quyết nếu có thuật toán luôn dừng và trả lời đúng/sai; Bài toán dừng là ví dụ kinh điển không khả quyết, chứng minh bằng đường chéo hóa.
Quy dẫn (Reducibility)
Chuyển một bài toán A về bài toán B đã biết tính chất; nếu B khả quyết và A quy dẫn được về B thì A cũng khả quyết — dùng theo chiều ngược để chứng minh bất khả quyết hoặc NP-khó.
Lớp P, NP và NP-đầy đủ
P là các bài toán giải được trong thời gian đa thức; NP là các bài toán mà lời giải có thể kiểm tra trong thời gian đa thức; NP-đầy đủ là các bài toán khó nhất trong NP.

Học xong để làm gì

  • Trình biên dịch và bộ phân tích cú pháp: DFA cho từ vựng (lexer), văn phạm phi ngữ cảnh cho cú pháp (parser)
  • Biểu thức chính quy (regex) dùng trong tìm kiếm văn bản, xác thực dữ liệu, xử lý log
  • Kiểm chứng phần mềm và phần cứng: mô hình hóa hệ thống bằng automaton để chứng minh tính chất an toàn
  • Mật mã học: độ an toàn của nhiều hệ mật mã dựa trên giả định P ≠ NP, tức không có thuật toán đa thức phá được
  • Biết khi nào nên dừng tìm thuật toán tối ưu và chuyển sang heuristic — nhận diện bài toán NP-đầy đủ giúp tiết kiệm thời gian nghiên cứu

Câu hỏi thường gặp

Môn này có ứng dụng thực tế không hay chỉ là lý thuyết suông?

Regex, trình biên dịch, kiểm chứng phần mềm và cả việc biết khi nào nên ngừng tìm thuật toán tối ưu (vì bài toán NP-đầy đủ) đều dùng trực tiếp các khái niệm ở đây.

Sao phải học máy Turing khi không ai lập trình bằng nó?

Máy Turing không phải để lập trình — nó là công cụ toán học để chứng minh giới hạn của tính toán, tương tự dùng số thực trừu tượng để chứng minh định lý giải tích.

Làm sao để thành thạo các chứng minh bằng quy dẫn?

Làm nhiều bài tập quy dẫn theo mẫu có sẵn trước (ví dụ từ Bài toán dừng), nhận ra khuôn mẫu chung, rồi mới thử quy dẫn một bài toán mới hoàn toàn.

Cần thuộc lòng các chứng minh trong sách không?

Không cần thuộc lòng; quan trọng hơn là hiểu ý tưởng cốt lõi (đường chéo hóa, mô phỏng, đối số đếm) vì các bài tập mới thường tái dùng đúng những ý tưởng này.

Chọn nguồn tự học

Chủ đề khá trừu tượng — nên tìm nguồn có nhiều ví dụ minh họa cụ thể thay vì chỉ định nghĩa hình thức.