Nhóm chủ đề 3/8
Toán rời rạc và logic
Discrete Mathematics and Logic
Đế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.
4 chủ đềkhoảng 174 giờ17 khóa học11 sách
Theo cấp độ: 1 Cơ bản · 2 Trung bình · 1 Nâng cao
Giới thiệu
Nhóm Toán rời rạc và logic gồm bốn chủ đề: Toán rời rạc (logic, tập hợp, quy nạp, đếm, quan hệ truy hồi, số học modulo), Tổ hợp và lý thuyết đồ thị (hàm sinh, bao hàm – loại trừ, cây, tô màu, luồng, ghép cặp), Logic toán và lý thuyết tập hợp (logic vị từ, hệ tiên đề ZFC, bản số, định lý bất toàn Gödel) và Lý thuyết tính toán (ôtômat, máy Turing, tính quyết định được, P và NP).
Vì sao nhóm này quan trọng
Máy tính chỉ làm việc với đối tượng rời rạc, nên đây là phần toán mà lập trình viên và nhà khoa học máy tính dùng hằng ngày: đếm số trường hợp để phân tích thuật toán, mô hình hóa mạng bằng đồ thị, chứng minh chương trình đúng bằng quy nạp. Logic và lý thuyết tính toán trả lời những câu hỏi sâu hơn: điều gì chứng minh được, điều gì tính được.
Học thế nào
Học Toán rời rạc ngay sau khi quen viết chứng minh — không cần giải tích. Sau đó rẽ theo mối quan tâm: tổ hợp và đồ thị nếu thích giải bài, logic nếu thích nền móng của toán học, lý thuyết tính toán nếu thiên về tin học. Hãy tự viết chương trình nhỏ để kiểm tra một công thức đếm hoặc mô phỏng một ôtômat.
Nên học trước
Thứ tự học
Sắp theo mục "Nên học trước" trong hướng dẫn của từng chủ đề.
Cần học trước
Nền tảng: Nhập môn chứng minh toán học
Giáo trình: Discrete Mathematics: An Open Introduction
Khóa chính: Mathematics for Computer Science · MIT
Cần học trước
Trong nhóm: Toán rời rạc
Giáo trình: Applied Combinatorics
Khóa chính: Combinatorics · IIT Madras
Giáo trình: A Friendly Introduction to Mathematical Logic
Khóa chính: Mathematical Logic · IIT Madras
Cần học trước
Trong nhóm: Toán rời rạc
Giáo trình: Introduction to the Theory of Computation
Khóa chính: Lý thuyết tính toán · MIT
Kỹ năng đạt được
- Đếm bằng quy tắc cộng – nhân, hoán vị, tổ hợp, bao hàm – loại trừ và hàm sinh
- Giải quan hệ truy hồi và làm việc với số học modulo
- Mô hình hóa bài toán bằng đồ thị: cây, tô màu, luồng, ghép cặp
- Hiểu logic vị từ, hệ tiên đề và ý nghĩa của định lý bất toàn
- Xác định một bài toán có giải được bằng máy không và thuộc lớp độ phức tạp nào
Nghề nghiệp
- Nền cho kỹ sư phần mềm và nhà khoa học máy tính
- Thiết kế thuật toán, tối ưu tổ hợp và vận trù học
- Nghiên cứu logic, lý thuyết tính toán và mật mã
- Học tiếp nhóm Algorithms and Computation của lộ trình Khoa học máy tính