Toán rời rạc ứng dụng trong tin học

Cuốn sách này bao gồm bốn phần chính:

• Phần I: Kiến thức bổ trợ
  • Chương 1: Các khái niệm cơ bản của thuật toán và phương pháp đệ quy, bao gồm định nghĩa, đặc trưng, ngôn ngữ (liệt kê từng bước, sơ đồ khối, ngôn ngữ lập trình) và độ phức tạp thuật toán (O(n), O(logn), O(n^b), v.v.). Phần này cũng giới thiệu về phương pháp đệ quy và thuật toán quay lui với các ví dụ minh họa.
  • Chương 2: Các phương pháp đếm, bao gồm tập hợp và biểu diễn tập hợp trên máy tính, các phép toán trên tập hợp, lực lượng của tập hợp, tích Đề-các. Ngoài ra, chương này còn đề cập đến hoán vị, chỉnh hợp, tổ hợp và định lý nhị thức.
  • Chương 3: Quan hệ, bao gồm định nghĩa, biểu diễn, tính chất, cung và đường trong đồ thị của quan hệ, quan hệ ngược, quan hệ hợp thành, quan hệ tương đương và bao đóng bắc cầu của quan hệ.
• Phần II: Lôgic và ứng dụng
  • Chương 4: Lôgic mệnh đề, bao gồm các phép toán, công thức, điều kiện đồng nhất đúng/sai và các quy tắc suy diễn.
  • Chương 5: Lôgic vị từ, định nghĩa vị từ, khái niệm công thức đồng nhất bằng nhau/đúng/sai, ý nghĩa các vị từ theo lý thuyết tập hợp, dạng chuẩn tắc, vấn đề về tính giải được, nguyên lý quy nạp và quy tắc suy diễn.
  • Chương 6: Hệ toán mệnh đề, bao gồm xây dựng hệ toán mệnh đề, các định nghĩa, tính chất, định lý tương đương, quan hệ giữa Lôgic mệnh đề và hệ toán mệnh đề, tính phi mâu thuẫn, đầy đủ, độc lập.
• Phần III: Đồ thị và ứng dụng
  • Chương 7: Lý thuyết đồ thị, bao gồm định nghĩa, biểu diễn, một số dạng đồ thị thường gặp, thuật ngữ, tính chất, số ổn định trong/ngoài, sắc số, chu trình Euler và Hamilton, đường đi ngắn nhất.
  • Chương 8: Cây và ứng dụng của cây, bao gồm định nghĩa, các ví dụ về cây, rừng cây, cây có gốc, cây m-phân, cây nhị phân, tính chất, ứng dụng (cây tìm kiếm nhị phân, cây quyết định, mã tiền tố), các phương pháp duyệt cây và cây khung của đồ thị.
• Phần IV: Ngôn ngữ hình thức
  • Chương 9: Văn phạm và ngôn ngữ sinh bởi văn phạm, bao gồm khái niệm chung về ngôn ngữ, văn phạm và ngôn ngữ sinh bởi văn phạm, phân loại văn phạm của Chomsky.
  • Chương 10: Ôtômat hữu hạn và ngôn ngữ đoán nhận của nó, bao gồm định nghĩa ôtômat hữu hạn, phương pháp biểu diễn, ngôn ngữ chính quy và biểu thức chính quy.
  • Chương 11: Ôtômat đẩy xuống đoán nhận ngôn ngữ phi ngữ cảnh, bao gồm văn phạm phi ngữ cảnh, cây dẫn xuất, giản lược văn phạm phi ngữ cảnh, văn phạm chuẩn của Chomsky, ôtômat đẩy xuống.
  • Chương 12: Máy Turing không đơn định đàn hồi đoán nhận ngôn ngữ văn phạm, bao gồm máy Turing đơn định, máy Turing không đơn định đàn hồi và sự tương đương giữa máy Turing không đơn định đàn hồi và văn phạm Chomsky.

Sách cũng có phần phụ lục gồm một số đề thi tuyển sinh sau đại học và tài liệu tham khảo. Mục tiêu của sách là nâng cao chất lượng giảng dạy và học tập, giúp người học hiểu lý thuyết, rèn luyện tư duy khoa học, kỹ năng tính toán và khả năng vận dụng toán học vào giải quyết vấn đề trong lĩnh vực Công nghệ thông tin.