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

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ủ đề.

  1. Cơ bảnkhoảng 40 giờ

    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

  2. Trung bìnhkhoảng 42 giờ

    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

  3. Cần học trước

    Trong nhóm: Toán rời rạc

    Nền tảng: Nhập môn chứng minh toán học

    Giáo trình: A Friendly Introduction to Mathematical Logic

    Khóa chính: Mathematical Logic · IIT Madras

  4. Trung bìnhkhoảng 50 giờ

    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