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

Nối tiếp phần 1, "Bài giảng Toán rời rạc 1: Phần 2" tiếp tục cung cấp cho học viên những kiến thức về bài toán liệt kê; thuật toán và độ phức tạp tính toán; thuật toán quay lui; bài toán tối ưu; kỹ thuật rút gọn giải quyết bài toán người du lịch; thuật toán nhánh cận giải bài toán người du lịch; bài toán tồn tại; phương pháp phản chứng; nguyên lý Dirichlet; . 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 CHƢƠNG 3. BÀI TOÁN LIỆT KÊ Nội dung bài toán đếm là đếm xem có bao nhiêu cấu hình tổ hợp thỏa mãn một số tính chất nào đó. Bài toán liệt không chỉ đếm đƣợc các cấu hình tổ hợp thỏa mãn các tính chất đặt ra mà còn xem xét từng cấu hình tổ hợp đó là gì. Đối với mỗi bài toán khi chƣa tìm đƣợc thuật giải thì liệt kê đƣợc xem là biện pháp cuối cùng để thực hiện với sự hỗ trợ của máy tính. Có thể nói liệt kê đƣợc xem là phƣơng pháp giải vạn năng một bài toán bằng máy tính. Nội dung chính của chƣơng này tập chung giải quyết những vấn đề cơ bản sau Giới thiệu bài toán liệt kê. Thuật toán và độ phức tạp tính toán. Giải quyết bài toán liệt kê bằng phƣơng pháp sinh. Giải quyết bài toán liệt kê bằng phƣơng pháp quay lui. Bạn đọc có thể tìm thấy cách giải nhiều bài toán liệt kê trong các tài liệu 1 và 2 trong tài liệu tham khảo. Giới thiệu bài toán Bài toán đƣa ra danh sách tất cả các cấu hình tổ hợp có thể có đƣợc gọi là bài toán liệt kê tổ hợp. Khác với bài toán đếm là tìm kiếm một công thức cho lời giải bài toán liệt kê lại cần xác định một thuật toán để theo đó có thể xây dựng đƣợc lần lƣợt tất cả các cấu hình cần quan tâm. Một thuật toán liệt kê phải đảm bảo hai nguyên tắc Không được lặp lại bất kỳ một cấu hình nào. Không được bỏ sót bất kỳ một cấu hình nào. Ví dụ 1. Cho tập hợp các số a1 a2 . an và số M. Hãy tìm tất cả các tập con k phần tử của dãy số an sao cho tổng số các phần tử trong tập con đó đúng bằng M. Lời giải Nhƣ chúng ta đã biết số các tập con k phần tử của tập gồm n phần tử là C n k . Nhƣ vậy chúng ta cần phải duyệt trong số C n k tập k phần tử để lấy ra những tập có tổng các phần tử đúng bằng M. Vì không thể xác định đƣợc có bao nhiêu tập k phần tử từ tập n phần tử có tổng các phần tử đúng bằng M nên chúng ta chỉ còn cách liệt kê các cấu hình thoả mãn điều kiện đã cho. Ví dụ 2. Một thƣơng nhân đi bán hàng tại tám thành phố. Chị ta

• Toán học
• Bài giảng Toán rời rạc 1
• Toán rời rạc 1
• Bài toán liệt kê
• Thuật toán quay lui
• Thuật toán nhánh
• Nguyên lý Dirichlet
• Toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Lý thuyết về toán rời rạc
• Nguyên lý toán rời rạc
• Cấu hình tổ hợp
• Cấu hình toán rời rạc
• bài tập Toán rời rạc
• đề cương Toán rời rạc
• tìm hiểu Toán rời rạc
• Bài toán tồn tại
• Bài toán tối ưu
• Toán rời rạc ứng dụng trong tin học
• Đại cương về đồ thị
• Biểu diễn đồ thị
• Đồ thị có hướng
• Biểu diễn quan hệ
• Quan hệ tương đương
• Quan hệ thứ tự
• toán cao cấp
• cơ sở dữ liệu
• hệ thống dữ liệu
• Tập hợp
• Vị từ
• Lượng từ
• Bài toán đếm
• Nguyên lý đếm
• Nguyên lý bù trừ
• Toán học rời rạc
• Cấu trúc rời rạc
• Tổ hợp căn bản
• Tổ hợp lặp
• Khai triển lũy thừa
• Khai triển đa thức
• Cơ sở logic
• Qui tắc suy diễn
• Qui nạp toán học
• Mệnh đề phức hợp
• Phép nối rời
• Cấu trúc dữ liệu và giải thuật
• Trí tuệ nhân tạo
• Mạch logic
• Logic vị từ
• Bảng chân trị
• Mệnh đề
• Qui tắc thay thế
• Qui tắc De Morgan
• Luật giao hoán
• Luật trung hòa
• Phép đếm
• Nguyên lý cộng
• Tổ hợp suy rộng
• Bài tập phép đếm
• Luật đối ngẫu De Morgan
• Hiệu đối xứng
• Tập hợp hữu hạn
• Xác định một tập hợp con
• Tính chất tập rỗng
• Quan hệ toàn phần
• Tính chất của quan hệ
• Đại số Bool
• Hàm bool
• Biểu đồ karnaugh
• Mạch rút gọn
• Tối tiểu hàm Bool
• Đa thức tối tiểu
• Công thức biểu diễn hàm Boole
• Toán thống kê
• Công thức toán học
• Công thức truy hồi
• Nguyên lý qui nạp toán học
• Mệnh đề toán học
• Thuật toán
• Biểu diễn thuật toán
• Cấu trúc cơ bản của thuật toán
• Một số thuật toán cơ bản
• Phép tính mệnh đề
• Dạng mệnh đề
• Quy tắc suy diễn
• Phương pháp quy nạp toán học
• Logic mệnh đề
• Mệnh đề logic phức hợp
• Toán tử logic
• Phép toán logic với các bit
• Logic toán học
• Mệnh đề tương đương