tailieunhanh - Bài giảng Toán rời rạc: Chương 5 - Dr. Ngô Hữu Phúc

Bài giảng Toán rời rạc: Chương 5 Bài toán liệt kê, cung cấp cho người đọc những kiến thức như: Giới thiệu bài toán; Nhắc lại kiến thức đệ quy; Sinh hoán vị - Sinh tổ hợp; Thuật toán quay lui. Bài toán xếp hậu. Mời các bạn cùng tham khảo! | TOÁN RỜI RẠC CHƯƠNG 5 BÀI TOÁN LIỆT KÊ Lecturer PhD. Ngo Huu Phuc Tel 0438 326 077 Mob 098 5696 580 Email ngohuuphuc76@ 1 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University NỘI DUNG CHƯƠNG 5 . Giới thiệu bài toán. . Nhắc lại kiến thức đệ quy. . Sinh hoán vị - Sinh tổ hợp. . Thuật toán quay lui. Bài toán xếp hậu. . Bài tập chương 5. 2 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 1 3 Cần có giải thuật để lần lượt xây dựng được tất cả các cấu hình đang quan tâm BÀI TOÁN LIỆT KÊ. Đối với bài toán liệt kê cần đảm bảo 2 nguyên tắc Không được lặp lại một cấu hình. Không được bỏ sót một cấu hình. Khó khăn chính của phương pháp này là sự bùng nổ tổ hợp 3 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 2 3 Ví dụ 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. Giải ví dụ . Số các tập con k phần tử của tập gồm n phần tử là C n k . Cần 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. Để thực hiện được bài toán cần liệt kê các cấu hình. 4 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Giới thiệu bài toán 3 3 Ví dụ Một người bán hàng tại 8 thành phố. Người này có thể bắt đầu hành trình của mình tại một thành phố nào đó nhưng phải qua 7 thành phố kia theo bất kỳ thứ tự nào mà người đó muốn. Hãy chỉ ra lộ trình ngắn nhất mà người đó có thể đi. Giải ví dụ . Có tất cả 7 5040 cách đi của người bán hàng. Tuy nhiên trong 5040 cách chúng ta phải duyệt toàn bộ để chỉ ra một hành trình là ngắn nhất. 5 @Copyrights by Dr. Ngo Huu Phuc Le Quy Don Technical University . Nhắc lại kiến thức đệ quy 1 9 . Định nghĩa bằng đệ quy 1 4 Trong thực tế nhiều đối tượng mà khó có thể định nghĩa nó một cách tường minh nhưng lại dễ dàng định nghĩa đối tượng qua chính nó. Kỹ thuật định nghĩa đối tượng qua .