tailieunhanh - Bài giảng Toán rời rạc 1: Phần 1

"Bài giảng Toán rời rạc 1: Phần 1" cung cấp cho học viên những kiến thức về logic, tập hợp và ứng dụng; vị từ và lượng từ; biểu diễn tập hợp trên máy tính; bài toán đếm; những nguyên lý đếm cơ bản; nguyên lý bù trừ; đếm các hoán vị và tổ hợp; hệ thức truy hồi; . Mời các bạn cùng tham khảo! | HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG - - KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG TOÁN RỜI RẠC 1 NGUYỄN DUY PHƯƠNG HàNội 2016 LỜI GIỚI THIỆU Toán rời rạc là lĩnh vực nghiên cứu và xử lý các đối tƣợng rời rạc. Toán rời rạc dùng để đếm quan sát và xử lý mối quan hệ giữa các đối tƣợng trong các tập hợp khác nhau. Bản chất tính toán trên máy tính là rời rạc. Chính vì vậy toán học rời rạc đƣợc xem là môn học kinh điển cho sinh viên các ngành Công nghệ thông tin và Điện tử Viễn thông. Tài liệu hƣớng dẫn môn học toán học rời rạc đƣợc xây dựng dựa trên cơ sở kinh nghiệm giảng dạy môn học và kế thừa những nội dung từ giáo trình Toán học rời rạc ứng dụng trong tin học của Kenneth Rossen. Tài liệu đƣợc trình bày thành hai phần Lý thuyết tổ hợp Toán rời rạc 1 và Lý thuyết đồ thị Toán rời rạc 2 . Phần I trình bày những kiến thức cơ bản về lý thuyết tổ hợp thông qua việc giải quyết bốn bài toán cơ bản đó là Bài toán đếm Bài toán tồn tại Bài toán liệt kê và Bài toán tối ƣu. Phần II trình bày những kiến thức cơ bản về Lý thuyết đồ thị khái niệm định nghĩa các thuật toán trên đồ thị đồ thị Euler đồ thị Hamilton. Một số bài toán có ứng dụng thực tiễn quan trọng khác của lý thuyết đồ thị cũng đƣợc chú trọng giải quyết đó là Bài toán tô màu đồ thị Bài toán tìm đƣờng đi ngắn nhất và Bài toán luồng cực đại trong mạng. Trong mỗi phần của tài liệu chúng tôi cố gắng trình bày ngắn gọn trực tiếp vào bản chất của vấn đề. Các thuật toán đƣợc trình bày và cài bằng ngôn ngữ lập trình C . Mặc dù đã rất cẩn trọng trong quá trình biên soạn tuy nhiên tài liệu không tránh khỏi những thiếu sót và hạn chế. Chúng tôi rất mong đƣợc sự góp ý quí báu của tất cả đọc giả và các bạn đồng nghiệp. Hà nội tháng 12 năm 2016 2 MỤC LỤC CHƢƠNG 1. LOGIC TẬP HỢP VÀ ỨNG DỤNG . 5 . Giới thiệu chung . 5 . Những kiến thức cơ bản về Logic mệnh đề . 6 . Định nghĩa amp phép toán . 6 . Sự tƣơng đƣơng giữa các mệnh đề . 7 . Dạng chuẩn tắc . 9 . Vị từ và lƣợng từ . 10 . Một số ứng dụng trên máy tính .