Bỏ qua tới nội dung chính
Toán học

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

Lý thuyết tính toán

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

Ôtômat, văn phạm, máy Turing, tính quyết định được và các lớp độ phức tạp P, NP, PSPACE.

Bắt đầu học

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

  • Thiết kế DFA, NFA, biểu thức chính quy cho một ngôn ngữ và 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 hoặc không phi ngữ cảnh
  • Thiết kế văn phạm phi ngữ cảnh và ôtômat đẩy xuống, chứng minh sự tương đương của hai mô hình
  • Mô tả máy Turing và các biến thể, giải thích luận đề Church–Turing
  • Chứng minh một bài toán không quyết định được bằng đường chéo hoặc 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
  • Giải thích định lý Cook–Levin, định lý Savitch và các định lý phân cấp ở mức ý tưởng chứng minh

Nên học trước

Giới thiệu

Lý thuyết tính toán nghiên cứu toán học của chính khái niệm "thuật toán". Môn học trả lời ba câu hỏi lớn: các mô hình máy tính khác nhau nhận diện được những ngôn ngữ nào (lý thuyết ôtômat), có những bài toán nào mà không thuật toán nào giải được (lý thuyết tính quyết định được), và trong số các bài toán giải được, bài toán nào giải được nhanh (lý thuyết độ phức tạp). Ở MIT đây là môn 18.404J của khoa Toán, do chính Michael Sipser — tác giả giáo trình chuẩn của môn — giảng dạy; OpenER có khóa học "Lý thuyết tính toán" bám sát toàn bộ 26 buổi giảng đó.

Ôtômat và ngôn ngữ

Mô hình đơn giản nhất là ôtômat hữu hạn (DFA, NFA): máy chỉ có một số hữu hạn trạng thái, không có bộ nhớ ngoài. Chúng nhận diện đúng lớp ngôn ngữ chính quy — cũng là lớp mô tả được bằng biểu thức chính quy. Bổ đề bơm cho thấy giới hạn của mô hình này: ngôn ngữ {0ⁿ1ⁿ} không chính quy. Thêm một ngăn xếp ta được ôtômat đẩy xuống, tương đương với văn phạm phi ngữ cảnh — mô hình của cú pháp ngôn ngữ lập trình.

Máy Turing và giới hạn của tính toán

Máy Turing — thêm một băng nhớ vô hạn đọc/ghi được — là mô hình tổng quát của mọi thuật toán; luận đề Church–Turing khẳng định mọi khái niệm "tính được bằng thuật toán" hợp lý đều tương đương với máy Turing. Từ đó chứng minh được những giới hạn tuyệt đối: bài toán dừng không quyết định được (bằng lập luận đường chéo, họ hàng của lập luận Cantor), và kỹ thuật quy dẫn lan truyền tính không quyết định được sang vô số bài toán khác. Định lý đệ quy — máy Turing có thể "biết mã nguồn của chính nó" — nối trực tiếp với định lý bất toàn của Gödel trong logic toán.

Độ phức tạp: P, NP và hơn thế

Trong số các bài toán giải được, lớp P gồm các bài toán giải được trong thời gian đa thức, lớp NP gồm các bài toán mà lời giải kiểm tra được trong thời gian đa thức. Định lý Cook–Levin chứng minh SAT là NP-đầy đủ, và qua quy dẫn đa thức, hàng nghìn bài toán thực tế (lập lịch, tô màu đồ thị, người du lịch) cũng vậy. Câu hỏi P = NP? là bài toán mở nổi tiếng nhất của tin học. Môn học còn đi tới độ phức tạp không gian (PSPACE, định lý Savitch, L và NL), các định lý phân cấp, tính toán xác suất (lớp BPP) và hệ chứng minh tương tác.

Vì sao là một môn toán?

Lý thuyết tính toán gần như không có lập trình: mọi kết quả đều là định lý với chứng minh chặt chẽ, dùng các kỹ thuật của toán rời rạc — quy nạp, đường chéo, đếm, xây dựng tường minh. Vì thế nó nằm trong nhóm Toán rời rạc và logic, và cần Toán rời rạc làm điều kiện trước.

Cách học hiệu quả

  • Học theo khóa "Lý thuyết tính toán" trên OpenER: mỗi buổi có video bài giảng MIT, bài giảng tiếng Việt và lecture notes; làm các problem set sau mỗi phần.
  • Với mỗi định lý, tự vẽ ví dụ nhỏ trước khi đọc chứng minh: một DFA ba trạng thái, một văn phạm cho biểu thức có ngoặc, một máy Turing cộng hai số nhị phân.
  • Luyện quy dẫn theo mẫu: quy dẫn từ bài toán dừng để chứng minh không quyết định được, quy dẫn đa thức từ 3-SAT để chứng minh NP-đầy đủ — hai kỹ thuật dùng chung một cách tư duy.
  • Tự kiểm tra bằng đề thi giữa kỳ và cuối kỳ mẫu của MIT 18.404J có trên trang.

Sau môn này

Bạn có thể học tiếp độ phức tạp tính toán nâng cao, mật mã học lý thuyết, thiết kế thuật toán, logic toán và lý thuyết tính toán được, hoặc ứng dụng vào trình biên dịch và kiểm chứng hình thức.

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

Xem tất cả trong tab Sách

Giáo trình chính

Introduction to the Theory of Computation

Michael Sipser · 2013 · Bản thứ 3

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

Vì sao chọn: Giáo trình chuẩn của môn (Cengage, trả phí), do chính Michael Sipser viết và dùng trong MIT 18.404J; các buổi giảng của khóa học trên OpenER đi theo đúng các mục của sách. Văn phong rõ ràng, mỗi chứng minh có phần “ý tưởng” trước phần chi tiết — rất hợp để tự học.

Nên đọc: Chương 1, Chương 2 (trừ 2.4), Chương 3–5, mục 6.1–6.2, Chương 7–8, mục 9.1–9.2, 10.2 và 10.4 — phạm vi của MIT 18.404J

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ômat hữu hạn và ngôn ngữ chính quy

    khoảng 7 giờ

    Ôtômat hữu hạn đơn định và không đơn định, tính đóng của ngôn ngữ chính quy, biểu thức chính quy và sự tương đương với ôtômat, bổ đề bơm cho ngôn ngữ chính quy (buổi 1–3 của MIT 18.404J). Luyện tập: xây DFA nhận các xâu nhị phân biểu diễn số chia hết cho 3; chuyển một NFA sang DFA bằng cấu trúc tập con; chứng minh {0ⁿ1ⁿ} không chính quy; làm Problem Set 1.

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

    khoảng 6 giờ

    Văn phạm phi ngữ cảnh, ôtômat đẩy xuống và sự tương đương giữa hai mô hình, bổ đề bơm cho ngôn ngữ phi ngữ cảnh (buổi 3–5). Luyện tập: viết văn phạm cho biểu thức số học có ngoặc và chuyển sang ôtômat đẩy xuống; chứng minh {aⁿbⁿcⁿ} không phi ngữ cảnh.

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

    khoảng 5 giờ

    Định nghĩa máy Turing, các biến thể (nhiều băng, không đơn định, máy liệt kê) và sự tương đương, luận đề Church–Turing (buổi 5–6). Luyện tập: mô phỏng tay một máy Turing nhận {w#w}; giải thích vì sao máy nhiều băng mô phỏng được bằng máy một băng; làm Problem Set 2.

  4. Bước 4: Tính quyết định được, quy dẫn và định lý đệ quy

    khoảng 8 giờ

    Các bài toán quyết định được về ôtômat và văn phạm, bài toán dừng và lập luận đường chéo, quy dẫn ánh xạ, phương pháp lịch sử tính toán, định lý đệ quy và ứng dụng vào logic (buổi 7–11). Luyện tập: chứng minh bài toán “máy Turing có nhận xâu rỗng không” không quyết định được bằng quy dẫn từ bài toán dừng; làm Problem Set 3.

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

    khoảng 8 giờ

    Đo độ phức tạp thời gian, lớp P và lớp NP, quy dẫn thời gian đa thức, NP-đầy đủ và định lý Cook–Levin (buổi 12–16). Luyện tập: chứng minh CLIQUE và VERTEX-COVER là NP-đầy đủ bằng quy dẫn từ 3-SAT; làm Problem Set 4, rồi tự làm một đề thi giữa kỳ mẫu có trên trang.

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

    khoảng 16 giờ

    Độ phức tạp không gian, PSPACE và định lý Savitch, PSPACE-đầy đủ và trò chơi, lớp L và NL, NL = coNL, các định lý phân cấp, các bài toán được chứng minh là không giải được hiệu quả (provably intractable) và máy tiên tri (oracle), tính toán xác suất và lớp BPP, hệ chứng minh tương tác (buổi 17–26). Luyện tập: chứng minh bài toán Generalized Geography thuộc PSPACE; làm Problem Set 5 và 6, rồi tự làm đề thi cuối kỳ mẫu và đối chiếu với lời giải.

Khái niệm chính

Ôtômat hữu hạn (DFA, NFA)
Máy có hữu hạn trạng thái đọc xâu vào từng ký hiệu một; NFA cho phép nhiều lựa chọn chuyển trạng thái nhưng nhận diện đúng cùng lớp ngôn ngữ với DFA.
Ngôn ngữ chính quy và biểu thức chính quy
Lớp ngôn ngữ được nhận diện bởi ôtômat hữu hạn, trùng với lớp mô tả được bằng biểu thức chính quy; đóng với hợp, ghép nối và phép sao Kleene.
Bổ đề bơm
Mọi xâu đủ dài trong một ngôn ngữ chính quy đều có một đoạn “bơm” được (lặp lại tùy ý) mà xâu vẫn thuộc ngôn ngữ; với ngôn ngữ phi ngữ cảnh, hai đoạn được bơm đồng thời; dùng theo lối phản chứng để chứng minh một ngôn ngữ không thuộc lớp đó.
Văn phạm phi ngữ cảnh và ôtômat đẩy xuống
Văn phạm sinh xâu bằng các luật thay thế một biến; ôtômat đẩy xuống là ôtômat hữu hạn có thêm ngăn xếp; hai mô hình tương đương nhau.
Máy Turing
Mô hình tính toán với băng nhớ vô hạn đọc và ghi được; các biến thể (nhiều băng, không đơn định) đều tương đương về sức mạnh.
Luận đề Church–Turing
Khẳng định rằng khái niệm trực giác “thuật toán” trùng với khái niệm máy Turing; không phải định lý mà là một luận đề không chứng minh được (vì “thuật toán” không có định nghĩa hình thức), được chấp nhận rộng rãi.
Tính quyết định được và bài toán dừng
Một ngôn ngữ quyết định được nếu có máy Turing luôn dừng và trả lời đúng; bài toán dừng — máy M có dừng trên đầu vào w không — là không quyết định được.
Quy dẫn
Chuyển bài toán A về bài toán B; nếu A quy dẫn về B và B quyết định được thì A quyết định được, nên A không quyết định được kéo theo B không quyết định được.
Định lý đệ quy
Mọi máy Turing có thể thu được mô tả của chính nó trong lúc chạy; dùng để chứng minh gọn nhiều kết quả không quyết định được và liên hệ với định lý bất toàn.
Lớp P và lớp NP
P gồm các bài toán giải được trong thời gian đa thức; NP gồm các bài toán mà một lời giải đề xuất kiểm tra được trong thời gian đa thức.
NP-đầy đủ và định lý Cook–Levin
Bài toán NP-đầy đủ thuộc NP và mọi bài toán NP quy dẫn đa thức về nó; định lý Cook–Levin chứng minh SAT là NP-đầy đủ.
PSPACE và định lý Savitch
PSPACE gồm các bài toán giải được với bộ nhớ đa thức; định lý Savitch cho thấy không đơn định chỉ tiết kiệm được nhiều nhất một lũy thừa bậc hai về bộ nhớ.
Định lý phân cấp
Cho thêm đủ thời gian hoặc bộ nhớ thì giải được bài toán mới; ví dụ tồn tại bài toán giải được trong thời gian mũ nhưng không giải được trong thời gian đa thức.

Học xong để làm gì

  • Trình biên dịch: bộ phân tích từ vựng dùng ôtômat hữu hạn, bộ phân tích cú pháp dùng văn phạm phi ngữ cảnh
  • Biểu thức chính quy trong tìm kiếm văn bản, kiểm tra dữ liệu đầu vào và xử lý log
  • Kiểm chứng phần mềm: hiểu vì sao không công cụ nào kiểm tra được mọi tính chất của mọi chương trình (định lý Rice)
  • Mật mã học: độ an toàn của các hệ mã dựa trên giả định về độ khó tính toán
  • Thiết kế thuật toán: nhận ra bài toán NP-đầy đủ để chuyển sang thuật toán xấp xỉ, heuristic hoặc giới hạn đầu vào
  • Logic và nền móng toán học: liên hệ giữa bài toán dừng và định lý bất toàn của Gödel

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

Chủ đề này khác gì Lý thuyết tính toán trong lộ trình Khoa học máy tính?

Nội dung và nguồn học (MIT 18.404J, sách của Sipser) gần như giống nhau và dùng chung khóa học trên OpenER. Ở lộ trình Toán học, chủ đề nhấn mạnh hơn vào chứng minh và mối liên hệ với logic toán (định lý đệ quy, định lý bất toàn), và điều kiện trước là Toán rời rạc thay vì cấu trúc dữ liệu.

Có cần biết lập trình không?

Không bắt buộc. Môn học gần như hoàn toàn là chứng minh; biết lập trình chỉ giúp bạn có trực giác tốt hơn về thuật toán và máy Turing.

Sách của Sipser có miễn phí không?

Không, đó là sách trả phí (Cengage). Bạn vẫn có thể học trọn môn miễn phí bằng khóa học trên OpenER (video, bài giảng tiếng Việt, lecture notes, problem set) cùng giáo trình mở Introduction to Theoretical Computer Science của Boaz Barak.

Làm sao để giỏi các chứng minh bằng quy dẫn?

Bắt đầu bằng các quy dẫn mẫu trong sách và bài giảng, nhận ra khuôn chung (xây dựng một máy hoặc một phép biến đổi, rồi chứng minh hai chiều đúng), sau đó tự làm các bài trong problem set trước khi xem lời giải.

Mất bao lâu để học xong?

Khoảng 50 giờ cho lượt học đầu, tương đương 8–9 tuần với 6 giờ mỗi tuần. Đây là thời lượng tối thiểu: 18.404J là môn 12 đơn vị của MIT, tức khoảng 170 giờ trong một học kỳ kể cả làm problem set và ôn thi.

Chọn nguồn tự học

Bài giảng MIT 18.404J của Michael Sipser là nguồn chuẩn; hãy tự dựng ôtômat và máy Turing cho các ngôn ngữ nhỏ thay vì chỉ đọc chứng minh.