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!
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc 1: Phần 2 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. 3.1- 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 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à chị ta muốn. Hãy chỉ ra lộ trình ngắn nhất mà chị ta có thể đi. Lời giải: Vì thành phố xuất phát đã đƣợc xác định. Do vậy thƣơng nhân có thể chọn tuỳ ý 7 thành phố còn lại để hành trình. Nhƣ vậy, tất cả số hành trình của thƣơng nhân có thể 45 đi qua là 7! = 5040 cách. 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. Có thể nói phƣơng pháp liệt kê là biện pháp cuối cùng nhƣng cũng là biện pháp phổ dụng nhất để giải quyết các bài toán tổ hợp. Khó khăn chính của phƣơng pháp này là sự bùng nổ tổ hợp. Để xây dựng chừng 1 tỷ cấu hình (con số này không phải là lớn đối với các bài toán tổ hợp nhƣ số mất thứ tự Dn, số phân bố Un, số hình vuông la tinh ln), ta giả sử cần 1 giây để liệt kê một cấu hình thì chúng ta cũng cần 31 năm mới giải quyết xong. Tuy nhiên với sự phát triển nhanh chóng của máy tính, bằng phƣơng pháp liệt kê, nhiều bài toán khó của lý thuyết tổ hợp đã đƣợc giải quyết và góp phần thúc đẩy sự phát triển của nhiều ngành toán học. 3.2. Thuật toán và độ phức tạp tính toán 3.2.1. Ví dụ và Định nghĩa Định nghĩa. Dãy hữ hạn các thao tác sơ cấp F=F1F2..Fn(Input)Output đƣợc gọi là một thuật toán trên tập thông tin vào Input để có đƣợc kết qua ra Output. Dãy các thao tác sơ cấp ở đây đƣợc hiểu là các phép toán số học, các phép toán logic, các phép toán so sánh. Một thuật toán cần thỏa mãn các tính chất dƣới đây: • Tính đơn định. Ở mỗi bƣớc của thuật toán, các thao tác sơ cấp phải hết sức rõ ràng, không gây nên sự lộn xộn, nhập nhằng, đa nghĩa. Thực hiện đúng các bƣớc của thuật toán trên tập dữ liệu vào, chỉ cho duy nhất một kết quả ra. • Tính dừng. Thuật toán không đƣợc rơi vào quá trình vô hạn. Phải dừng lại và cho kết quả sau một số hữu hạn các bƣớc. • Tính đúng. Sau khi thực hiện tất cả các bƣớc của thuật toán theo đúng qui trình đã định, ta phải nhận đƣợc kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó đƣợc kiểm chứng bằng yêu cầu của bài toán. • Tính phổ dụng. Thuật toán phải dễ sửa đổi để thích ứng đƣợc với bất kỳ bài toán nào trong lớp các bài toán cùng loại và có thể làm việc trên nhiều loại dữ liệu khác nhau. • Tính khả thi. Thuật toán phải dễ hiểu, dễ cài đặt, thực hiện đƣợc trên máy tính với thời gian cho phép. 3.2.2. Phƣơng pháp biểu diễn thuật toán: Thông thƣờng, để biểu diễn một thuật toán ta có thể sử dụng các phƣơng pháp sau: • Biểu diễn bằng ngôn ngữ tự ...