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áchGiáo trình chính
Introduction to the Theory of Computation
Michael Sipser · 2013 · Bản thứ 3
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
Giáo trình mở, miễn phí toàn văn của Boaz Barak (Harvard), trình bày lý thuyết tính toán theo hướng hiện đại: bắt đầu từ mạch logic, có thêm mật mã học và tính toán lượng tử. Lựa chọn miễn phí để đọc song song hoặc thay thế Sipser.
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
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.
- Đọc: Chương 1, mục 1.1–1.4 — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Introduction, Finite Automata, Regular Expressions (MIT 18.404J, Lecture 1)VideoÔ-tô-mát hữu hạn và biểu thức chính quyTài liệu
Video: Nondeterminism, Closure Properties, Regex → Finite Automata (MIT 18.404J, Lecture 2)VideoKhông đơn định, tính đóng kín và tương đương NFA–DFATài liệu
Video: Regular Pumping Lemma, FA → Regex, CFGs (MIT 18.404J, Lecture 3)VideoBổ đề bơm cho ngôn ngữ chính quyTài liệuProblem Set 1 (MIT 18.404J)Tài liệuBướ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.
- Đọc: Chương 2, mục 2.1–2.3 — Introduction to the Theory of Computation
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.
- Đọc: Chương 3, mục 3.1–3.3 — Introduction to the Theory of Computation
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.
- Đọc: Chương 4, mục 4.1–4.2; Chương 5, mục 5.1–5.2; Chương 6, mục 6.1–6.2 — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Decision Problems for Automata and Grammars (MIT 18.404J, Lecture 7)VideoBài toán quyết định trên Automata và Văn phạmTài liệu
Video: Undecidability (MIT 18.404J, Lecture 8)VideoTính khả quyết và Bài toán dừngTài liệu
Video: Reducibility (MIT 18.404J, Lecture 9)VideoQuy dẫn (Reducibility)Tài liệu
Video: Computation History Method (MIT 18.404J, Lecture 10)VideoPhương pháp lịch sử tính toánTài liệu
Video: Recursion Theorem and Logic (MIT 18.404J, Lecture 11)VideoĐịnh lý đệ quy và LogicTài liệuProblem Set 3 (MIT 18.404J)Tài liệuBướ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.
- Đọc: Chương 7, mục 7.1–7.5 — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Time Complexity (MIT 18.404J, Lecture 12)VideoĐộ phức tạp thời gianTài liệu
Video: P and NP, SAT, Poly-Time Reducibility (MIT 18.404J, Lecture 14)VideoĐộ phức tạp thời gian: lớp P và NPTài liệu
Video: NP-Completeness (MIT 18.404J, Lecture 15)VideoNP-đầy đủTài liệu
Video: Cook-Levin Theorem (MIT 18.404J, Lecture 16)VideoĐịnh lý Cook-LevinTài liệuProblem Set 4 (MIT 18.404J)Tài liệuĐề thi giữa kỳ mẫu (MIT 18.404J, Fall 2006)Tài liệuBướ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.
- Đọc: Chương 8, mục 8.1–8.4; Chương 9, mục 9.1–9.2; Chương 10, mục 10.2 và 10.4 — Introduction to the Theory of Computation
Lý thuyết tính toánKhóa học
Video: Space Complexity, PSPACE, Savitch's Theorem (MIT 18.404J, Lecture 17)VideoĐộ phức tạp không gian, PSPACE và Định lý SavitchTài liệu
Video: PSPACE-Completeness (MIT 18.404J, Lecture 18)VideoPSPACE-đầy đủTài liệu
Video: Games, Generalized Geography (MIT 18.404J, Lecture 19)VideoTrò chơi và Generalized GeographyTài liệu
Video: L and NL, NL = coNL (MIT 18.404J, Lecture 20)VideoLớp L, NL và Định lý NL = coNLTài liệu
Video: Hierarchy Theorems (MIT 18.404J, Lecture 21)VideoCác định lý phân cấpTài liệu
Video: Provably Intractable Problems, Oracles (MIT 18.404J, Lecture 22)VideoBài toán khó chứng minh được và OracleTài liệu
Video: Probabilistic Computation, BPP (MIT 18.404J, Lecture 23)VideoTính toán xác suất và lớp BPPTài liệu
Video: Interactive Proof Systems, IP (MIT 18.404J, Lecture 25)VideoHệ thống chứng minh tương tác (IP)Tài liệuProblem Set 5 (MIT 18.404J)Tài liệuProblem Set 6 (MIT 18.404J)Tài liệuĐề thi cuối kỳ mẫu (MIT 18.404J, Fall 2006)Tài liệuLời giải đề thi cuối kỳ mẫu (MIT 18.404J, Fall 2006)Tài liệu
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.



