Bài giảng Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê tổ hợp

Bài giảng "Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê tổ hợp" cung cấp cho sinh viên các kiến thức: Giới thiệu bài toán, thuật toán và độ phức tạp, phương pháp sinh, thuật toán quay lui. Đây là một tài liệu hữu ích dành cho các bạn sinh viên dùng làm tài liệu học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Lý thuyết tổ hợp - Chương 3: Bài toán liệt kê tổ hợp Phần thứ nhấtLÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1 Nội dungChương 0. Mở đầuChương 1. Bài toán đếmChương 2. Bài toán tồn tạiChương 3. Bài toán liệt kê tổ hợpChương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2 Chương 3BÀI TOÁN LIỆT KÊ Toán rời rạc 3 NỘI DUNG1. Giới thiệu bài toán2. Thuật toán và độ phức tạp3. Phương pháp sinh4. 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!(n- m)! 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án2. Thuật toán và độ phức tạp3. Phương pháp sinh4. 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ột dãy hữu hạn các bước cần thực hiện để thu được đầu ra cho một đầu vào cho trước của bài toán. Thuật toán có các đặc trưng sau đây: • Đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào đó. • Đầu ra (Output): Với mỗi tập các dữ liệu đầu vào, thuật toán đưa ra các dữ liệu tương ứng với lời giải của bài toán. • Chính xác (Precision): Các bước của thuật toán được mô tả chính xác. 9 Khái niệm thuật toán• Hữu hạn (Finiteness): Thuật toán cần phải đưa được đầu ra sau một số hữu hạn (có thể rất lớn) bước với mọi đầu vào.• Đơn trị (Uniqueness): Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc vào đầu vào và các kết quả của các bước trước.• Tổng quát (Generality): Thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho. 10 Độ phức tạp của thuật toán Độ phức tạp tính toán của thuật toán được xác định như là lượng tài nguyên các loại mà thuật toán đòi hỏi sử dụng. Có hai loại tài nguyên quan trọng đó là thời gian và bộ nhớ. Việc tính chính xác được các loại tài nguyên mà thuật toán đòi hỏi là rất khó. Vì thế ta quan tâm đến việc đưa ra các đánh giá sát thực cho các đại lượng này. Trong giáo trình này ta đặc biệt quan tâm đến đánh giá thời gian cần thiết để thực hiện thuật toán mà ta sẽ gọi là thời gian tính của thuật toán. 11 Độ phức tạp của thuật toán Rõ ràng: Thời gian tính phụ thuộc vào dữ liệu vào. Ví dụ: Việc nhân hai số nguyên có 3 chữ số đòi hỏi thời gian khác hẳn so với việc nhân hai số nguyên có 3*109 chữ số! Định nghĩa. Ta gọi kích thước dữ liệu đầu vào (hay độ dài dữ liệu vào) là số bít cần thiết để biểu diễn nó. Ví dụ: Nếu x, y là đầu vào cho bài toán nhân 2 số nguyên, thì kích thước dữ liệu vào của bài toán là n = log |x| + log |y| . Ta sẽ tìm cách đánh giá thời gian tính của thuật toán bởi một hàm của độ dài dữ liệu vào. 12 Phép toán cơ bản Đo thời gian tính bằng đơn vị đo nào? Định nghĩa. Ta gọi phép toán cơ bản là phép toán có thể thực hiện với thời ...