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

Lý thuyết tính toán

Theory of Computation

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.

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

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

Trung bìnhkhoảng 40 giờ6 bước
  • 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áo trình: Introduction to Theoretical Computer Science +1 sách khác

Đọc hướng dẫn đầy đủ
Thuộc nhóm Thuật toán và lý thuyết tính toán · Algorithms and Computation7 chủ đề · khoảng 265 giờPhần lý thuyết của khoa học máy tính: thiết kế và phân tích thuật toán, lý thuyết tính toán, logic, và các hướng mới như tính toán lượng tử, kinh tế thuật toán, sinh học tính toán.Xem nhóm
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.

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): ô-tô-mát, văn phạm, máy Turing, tính khả quyết và độ phức tạp; kèm video, ghi chú, bài tập và đề thi gốc từ MIT OCW. Đọc song song sách Sipser, sách tham khảo của lộ trình.

  • 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: Video ngắn chia theo tuần, nhiều ví dụ dựng DFA, NFA và máy Turing; hợp để xem lại phần ô-tô-mát khi thấy bài giảng chính quá nhanh.

    • Dễ bắt đầu

  • 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: Nhìn tính khả tính từ góc khác: máy thanh ghi, hàm đệ quy và phép tính lambda, gọn trong 12 buổi với ghi chú rõ ràng.

  • MIT · 18.405J · Xuân 2016

    Advanced Complexity Theory (mở trong tab mới)

    Lý thuyết độ phức tạp nâng cao

    Dana Moshkovitz

    Nâng caoChỉ tài liệuLiên kết ngoàiCấp độ: Nâng cao

    Vì sao chọn: Dành cho người đã xong 18.404J và muốn đi tiếp vào các kết quả độ phức tạp hiện đại.

    • Chuyên sâu

Bài viết

Bài đọc mở đầu

Lý thuyết tính toán: máy tính làm được gì — và không bao giờ làm được gì

Từ máy trạng thái hữu hạn tới máy Turing, từ biểu thức chính quy tới bài toán dừng: lý thuyết tính toán vẽ ra giới hạn của mọi máy tính.

16 phút đọc · Cập nhật 09/11/2026
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
Số mục mỗi trang
1–12 trên 85