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

Sách cho chủ đề

Lý thuyết tính toán

Theory of Computation

Giáo trình chính và sách tham khảo, kèm phần nên đọc. Ưu tiên sách có giấy phép mở hoặc đọc miễn phí; sách có phí chỉ dẫn tới nhà xuất bản. Xem sách của cả lĩnh vực

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)