Bài giảng Toán rời rạc 1 - Học viện Công nghệ Bưu chính Viễn thông

Bài giảng "Toán rời rạc 1" có cấu trúc gồm 5 chương trình bày các nội dung: Logic, tập hợp và ứng dụng; bài toán đếm; bài toán liệt kê; bài toán tối ưu; bài toán tồn tại. Cuối mỗi chương đều có các bài tập ôn tập giúp người học củng cố kiến thức. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc 1 - Học viện Công nghệ Bưu chính Viễn thôngHỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG -------------------- KHOA CÔNG NGHỆ THÔNG TIN 1 BÀI GIẢNG IT TOÁN RỜI RẠC 1PT Hà Nội 2013 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ạcdù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ácnhau. 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 xemlà 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ễnthô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ở kinhnghiệ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ảiquyế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àitoá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, địnhnghĩa, các thuật toán trên đồ thị, đồ thị Euler, đồ thị Hamilton. Một số bài toán có ứngdụ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 trongmạng. IT 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àobả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ỏinhữ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ả PTvà các bạn đồng nghiệp. Hà nội, tháng 10 năm 2013 2 MỤC LỤCCHƯƠNG 1. LOGIC, TẬP HỢP VÀ ỨNG DỤNG............................................ 5 1.1. Giới thiệu chung ................................................................................................... 5 1.2. Những kiến thức cơ bản về Logic mệnh đề ........................................................... 6 1.2.1. Định nghĩa & phép toán ................................................................................ 6 1.2.2. Sự tương đương giữa các mệnh đề ................................................................. 7 1.2.3. Dạng chuẩn tắc............................................................................................... 9 1.3. Vị từ và lượng từ................................................................................................. 10 1.4. Một số ứng dụng trên máy tính ........................................................................... 12 1.5. Những kiến thức cơ bản về lý thuyết tập hợp ...................................................... 15 1.5.1. Khái niệm & định nghĩa ............................................................................... 15 1.5.2. Các phép toán trên tập hợp ........................................................................... 16 1.5.3. Các hằng đẳng thức trên tập hợp .................................................................. 17 1.6. Biểu diễn tập hợp trên máy tính .......................................................................... 18 IT 1.7. Những nội dung cần ghi nhớ ............................................................................... 19BÀI TẬP CHƯƠNG 1...................................................................................... 19CHƯƠNG 2. BÀI TOÁN ĐẾM........................................................................ 21 2.1. Những nguyên lý đếm cơ bản.............................................................................. 21 PT 2.1.1. Nguyên lý cộng ............................................................................................ 21 2.1.2. Nguyên lý nhân ............................................................................................ 22 2.2. Nguyên lý bù trừ ................................................................................................. 24 2.3. Đếm các hoán vị và tổ hợp.................................................................................. 27 2.3.1. Chỉnh hợp lặp............................................................................................... 27 2.3.2. Chỉnh hợp không lặp .................................................................................... 27 2.3.3. Hoán vị ............................................................... ...