Giáo trình Toán rời rạc và lý thuyết đô thị

Giáo trình Toán rời rạc và lý thuyết đô thị gồm 11 chương, nội dung không đi sâu vào các vấn đề lý thuyết mà tập trung vào các vấn đề cơ bản của toán rời rạc và các giải thuật cũng như tính ứng dụng của môn học. Tiêu biểu là các nội dung về cơ sở logic, quan hệ hai ngôi, đại số bool - hàm bool, lý thuyết đô thị, biểu diễn đồ thị trên máy tính, tô màu đồ thị, luồng trong mạng,... Mời bạn tham khảo.

Nội dung trích xuất từ tài liệu:
Giáo trình Toán rời rạc và lý thuyết đô thị NGUYỄN THÀNH SƠN - ĐẶNG TRƯỜNG SƠN - LÊ VĂN VINH TRẦN CÔNG TÚ - NGUYỄN QUANG NGỌC - NGUYỄN PHƯƠNG GIÁO TRÌNH TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ Nguyễn Thành Sơn, Đặng Trường Sơn, Lê Văn Vinh, Trần Công Tú, Nguyễn Quang Ngọc, Nguyễn Phương Giáo trình TOÁN RỜI RẠC VÀ LÝ THUYẾT ĐỒ THỊ NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH - 2016 LỜI NÓI ĐẦU Toán rời rạc và Lý thuyết đồ thị là môn học tích hợp từ hai môn Toán rời rạc và môn Lý thuyết đồ thị. Đây là một trong những môn học căn bản và quan trọng trong lĩnh vực ứng dụng toán trong tin học. Nội dung “Toán rời rạc” trang bị cho người học những kiến thức cơ bản về logic mệnh đề, logic vị từ, suy diễn logic, quan hệ tương đương, quan hệ thứ tự, dàn, đại số Bool và cung cấp cho người học kiến thức và kỹ năng trong việc phân tích, nhìn nhận vấn đề, cũng như trong việc xác định công thức đa thức tối tiểu bằng phương pháp biểu đồ Karnaugh. Còn kiến thức về “Lý thuyết đồ thị” có ứng dụng đa dạng trong cuộc sống. Nó cung cấp các kiến thức về công cụ, phương pháp, thuật toán và hỗ trợ chúng ta xây dựng các mô hình nhằm giải quyết nhiều bài toán thực tiễn. Toán rời rạc và Lý thuyết đồ thị hiện là môn học bắt buộc trong chương trình đào tạo các ngành Công nghệ thông tin, Toán tin, Khoa học máy tính, … Sau khi học xong môn Toán rời rạc và Lý thuyết đồ thị, sinh viên sẽ có khả năng phân tích, giải thích, tư duy và lập luận giải quyết các vấn đề về toán rời rạc và lý thuyết đồ thị. Sinh viên sẽ được cung cấp kiến thức để hiểu và vận dụng được những quy trình, giải thuật trên đồ thị, có kỹ năng trong việc lập trình để giải quyết các bài toán trên đồ thị. Một năng lực quan trọng khác là khả năng phân tích, nhìn nhận vấn đề một cách khoa học, không phiến diện hay tư duy theo lối mòn. Ngoài ra, sinh viên sẽ biết cách sử dụng đồ thị như một công cụ mô hình hóa trong việc mô phỏng các vấn đề thực tế để chuyển thành các bài toán có thể giải được trên đồ thị. Nội dung giáo trình gồm có 11 chương, bao quát hầu hết các vấn đề cốt lõi của môn học. Giáo trình không đi sâu vào các vấn đề lý thuyết mà tập trung vào các vấn đề cơ bản của toán rời rạc và các giải thuật cũng như tính ứng dụng của môn học. Cuối mỗi chương đều có phần bài tập để sinh viên có thể tự kiểm tra kiến thức của mình. Các thuật toán trong giáo trình hầu hết được trình bày dưới dạng mã giả. Phần phụ lục có mã nguồn của một số thuật toán. Với kinh nghiệm nhiều năm giảng dạy môn Toán rời rạc và Lý thuyết đồ thị tại trường đại học, chúng tôi đã cố gắng đem những kiến thức và kinh nghiệm của mình để trình bày các vấn đề trong giáo trình một cách rõ ràng và đơn giản nhất. Tuy nhiên, những thiếu sót là điều không thể tránh khỏi. Trong quá trình biên soạn giáo trình này chúng tôi đã nhận được nhiều lời động viên và góp ý của các đồng nghiệp, xin chân 3 thành cám ơn và mong muốn tiếp tục nhận được ý kiến đóng góp của các giảng viên và các bạn sinh viên để giáo trình ngày càng hoàn thiện hơn. Các tác giả 4 MỤC LỤC LỜI NÓI ĐẦU .......................................................................................... 3 MỤC LỤC ................................................................................................ 5 Chương 1. CƠ SỞ LOGIC ...................................................................... 9 1.1 Phép tính mệnh đề ...................................................................... 9 1.2 Suy diễn logic ........................................................................... 19 1.3 Vị từ và lượng từ ...................................................................... 27 Bài tập chương 1 ............................................................................ 34 Chương 2. QUAN HỆ HAI NGÔI........................................................ 37 2.1 Khái niệm chung ..................................................................... 37 2.2 Quan hệ tương đương ............................................................... 39 2.3 Quan hệ thứ tự .......................................................................... 41 2.4 Dàn (Lattice) ............................................................................ 47 Bài tập chương 2 ............................................................................ 53 Chương 3. ĐẠI SỐ BOOL – HÀM BOOL .......................................... 55 3.1 Đại số Bool ............................................................................... 55 3.2 Hàm Bool ................................................................................. 59 3.3 Mạng các ...