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

Lý thuyết tính toán

Ô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.

5 khóa học đề xuất83 học liệu (25 video, 33 tài liệu, 23 slide, 2 sách)

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

Trung bìnhkhoảng 50 giờ6 bước
  • 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

Giáo trình: Introduction to the Theory of Computation +1 sách khác

Đọc hướng dẫn đầy đủ
Thuộc nhóm Toán rời rạc và logic · Discrete Mathematics and Logic4 chủ đề · khoảng 174 giờĐếm, đồ thị, logic hình thức và giới hạn của tính toán: phần toán của thế giới rời rạc, gắn chặt với tin học.Xem nhóm
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.

Khóa học đề xuất

Khóa trên OpenER và khóa mở của các trường, tuyển chọn cho chủ đề này.

Xem tất cả (5)

MIT · 18.404J · Thu 2020

Lý thuyết tính toán

Michael Sipser

Đề xuất chínhVideo + tài liệuTrên OpenERCấp độ: Trung bìnhCC BY-NC-SA 4.0 và giấy phép khác

Khóa học đầy đủ về tính khả tính và độ phức tạp tính toán, bám sát toàn bộ 26 buổi giảng thực tế của 18.404J Theory of Computation (MIT): ngôn ngữ chính quy/phi ngữ cảnh, máy Turing, tính khả quyết, quy dẫn, các lớp độ phức tạp P/NP/PSPACE/L/NL, định lý phân cấp, oracle, tính toán xác suất và hệ chứng minh tương tác. Bài giảng do OpenER biên soạn gốc; kèm link video, lecture notes, bài tập và đề thi thật từ MIT OpenCourseWare (CC BY-NC-SA 4.0).

Vì sao chọn: Bài giảng tiếng Việt đi theo các buổi của MIT 18.404J (Fall 2020) do chính Michael Sipser dạy, đúng mạch sách Sipser, sách chính của chủ đề: ôtômat, văn phạm, máy Turing, tính quyết định được và độ phức tạp; kèm video, bài tập và đề thi gốc từ MIT OCW.

  • Chuyên sâu
  • Có phụ đề Việt
  • Kinh điển

23 bài

  • IIT Kanpur · 106104148

    Theory of Computation (mở trong tab mới)

    Lý thuyết tính toán (NPTEL)

    Raghunath Tewari

    Thay thếVideo + tài liệuLiên kết ngoàiCấp độ: Trung bình

    Vì sao chọn: Giảng chậm với nhiều ví dụ dựng ôtômat và máy Turing cụ thể, hợp để luyện phần thiết kế máy song song khóa chính. Video công khai trên NPTEL.

  • IIT Guwahati · 111103016

    Formal Languages and Automata Theory (mở trong tab mới)

    Ngôn ngữ hình thức và lý thuyết ôtômat

    K. V. Krishna, Diganta Goswami

    Thay thếVideo + tài liệuLiên kết ngoàiCấp độ: Trung bình

    Vì sao chọn: Khóa từ khoa Toán IIT Guwahati, chú trọng chứng minh chặt các định lý về ngôn ngữ hình thức (Myhill–Nerode, bổ đề bơm, tính chất đóng) và đi tới P, NP, phân cấp Chomsky. Video công khai trên NPTEL.

  • Cambridge · 2025–26

    Computation Theory (mở trong tab mới)

    Lý thuyết tính toán (Cambridge)

    Anuj Dawar

    Thay thếChỉ tài liệuLiên kết ngoàiCấp độ: Trung bình

    Vì sao chọn: Góc nhìn khác về tính toán được: máy thanh ghi, hàm đệ quy và phép tính lambda bên cạnh máy Turing, hợp với người quan tâm logic và nền tảng toán học; có ghi chú và phiếu bài tập.

Khóa học

Lý thuyết tính toán

Massachusetts Institute of Technology · Michael Sipser • Fall 2020

Khóa học đầy đủ về tính khả tính và độ phức tạp tính toán, bám sát toàn bộ 26 buổi giảng thực tế của 18.404J Theory of Computation (MIT): ngôn ngữ chính quy/phi ngữ cảnh, máy Turing, tính khả quyết, quy dẫn, các lớp độ phức tạp P/NP/PSPACE/L/NL, định lý phân cấp, oracle, tính toán xác suất và hệ chứng minh tương tác. Bài giảng do OpenER biên soạn gốc; kèm link video, lecture notes, bài tập và đề thi thật từ MIT OpenCourseWare (CC BY-NC-SA 4.0).

Cập nhật 08/10/2026
Sách

Introduction to the Theory of Computation

Nhà xuất bản Cengage Learning

Giáo trình kinh điển và phổ biến nhất về automata, tính khả quyết và độ phức tạp; cấu trúc chương trùng với các bài giảng MIT 18.404J dùng trong lộ trình này.

Cập nhật 25/09/2026
Sách

Introduction to Theoretical Computer Science

Trang chính thức của tác giả (Boaz Barak, Harvard)

Giáo trình nhập môn khoa học máy tính lý thuyết hiện đại: mô hình tính toán, automata, khả quyết, độ phức tạp, có thêm chương về mật mã học và tính toán lượng tử; toàn văn miễn phí.

Cập nhật 25/09/2026
Video

Video: Regular Pumping Lemma, FA → Regex, CFGs (MIT 18.404J, Lecture 3)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: NP-Completeness (MIT 18.404J, Lecture 15)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: Provably Intractable Problems, Oracles (MIT 18.404J, Lecture 22)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: Recursion Theorem and Logic (MIT 18.404J, Lecture 11)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: Decision Problems for Automata and Grammars (MIT 18.404J, Lecture 7)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: Games, Generalized Geography (MIT 18.404J, Lecture 19)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: P and NP, SAT, Poly-Time Reducibility (MIT 18.404J, Lecture 14)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: PSPACE-Completeness (MIT 18.404J, Lecture 18)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Video

Video: Pushdown Automata, CFG ↔ PDA (MIT 18.404J, Lecture 4)

MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020)

Video bài giảng thật từ MIT OpenCourseWare — 18.404J Theory of Computation (Fall 2020).

Cập nhật 19/09/2026
Số mục mỗi trang
1–12 trên 84