Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1 Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2 Chương 3 BÀI TOÁN LIỆT KÊ Toán rời rạc 3 NỘI DUNG 1. Giới thiệu bài toán 2. Thuật toán và độ phức tạp 3. Phương pháp sinh 4. Thuật toán quay lui Toán rời rạc 4 Giíi thiÖu bµi to¸n ⚫ Bài toán đưa ra danh sách tất cả cấu hình tổ hợp thoả mãn một số tính chất cho trước được gọi là bài toán liệt kê tổ hợp. ⚫ Do số lượng cấu hình tổ hợp cần liệt kê thường là rất lớn ngay cả khi kích thước cấu hình chưa lớn: Số hoán vị của n phần tử là n! Số tập con m phần tử của n phần tử là n!/(m!(nm)! ⚫ Do đó ần có quan niệm thế nào là giải bài toán liệt kê tổ hợp 5 Giíi thiÖu bµi to¸n ⚫ Bài toán liệt kê tổ hợp là giải được nếu như ta có thể xác định một thuật toán để theo đó có thể lần lượt xây dựng được 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 2 yêu cầu cơ bản: 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. 6 Chương 3. Bài toán liệt kê 1. Giới thiệu bài toán 2. Thuật toán và độ phức tạp 3. Phương pháp sinh 4. Thuật toán quay lui Toán rời rạc 7 Khái niệm bài toán tính toán ⚫ ⚫ ⚫ ⚫ ⚫ Định nghĩa. Bài toán tính toán F là ánh xạ từ tập các xâu nhị phân độ dài hữu hạn vào tập các xâu nhị phân độ dài hữu hạn: F : {0, 1}* → {0, 1}*. Ví dụ: Mỗi số nguyên x đều có thể biểu diễn dưới dạng xâu nhị phân là cách viết trong hệ đếm nhị phân của nó. Hệ phương trình tuyến tính Ax = b có thể biểu diễn dưới dạng xâu là ghép nối của các xâu biểu diễn nhị phân của các thành phần của ma trận A và vectơ b. Đa thức một biến: P(x) = a0 + a1 x + ... + an xn, hoàn toàn xác định bởi dãy số n, a0, a1, ..., an, mà để biểu diễn dãy số này chúng ta có thể sử dụng xâu nhị phân. 8 Khái niệm thuật toán ⚫ Định nghĩa. Ta hiểu thuật toán giải bài toán đặt ra là một thủ tục xác định bao gồm m