tailieunhanh - Về vấn đề tìm tất cả các rút gọn trong bảng quyết định không đầy đủ

Bài viết trình bày việc giải quyết bài toán tìm tất cả các rút gọn trong bảng quyết định không đầy đủ theo hướng tiếp cận cơ sở dữ liệu quan hệ. Chúng tôi đề xuất thuật toán tìm tất cả các rút gọn của bảng quyết định không đầy đủ. Thuật toán này có độ phức tạp tồi nhất là hàm mũ. Tuy nhiên, trong nhiều trường hợp với các dữ liệu khác nhau thì thuật toán có độ phức tạp thời gian là đa thức. | Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR TP. HCM ngày 23-24 12 2021 DOI VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ Vũ Đức Thi1 Nguyễn Long Giang2 Nguyễn Ngọc Cương3 Phạm Việt Anh4 Viện Công nghệ thông tin Đại học Quốc gia Hà Nội 1 2 Viện Công nghệ thông tin Viện Hàn lâm Khoa học và Công nghệ Việt Nam 3 Cục An ninh mạng và Phòng chống tội phạm sử dụng công nghệ cao - Bộ Công an 4 Viện Công nghệ HaUI Trường Đại học Công nghiệp Hà Nội TÓM TẮT Các vấn đề liên quan đến bài toán rút gọn thuộc tính là những vấn đề quan trọng trong lý thuyết tập thô 13 . Hiện nay nhiều nhà khoa học trên thế giới quan tâm và phát triển những vấn đề này. 12 đã đưa ra khái niệm quan hệ tương đối tolerance relation để nghiên cứu những vấn đề về các bảng quyết định không đầy đủ. Trong bài báo này chúng tôi giải quyết bài toán tìm tất cả các rút gọn trong bảng quyết định không đầy đủ theo hướng tiếp cận cơ sở dữ liệu quan hệ. Chúng tôi đề xuất thuật toán tìm tất cả các rút gọn của bảng quyết định không đầy đủ. Thuật toán này có độ phức tạp tồi nhất là hàm mũ. Tuy nhiên trong nhiều trường hợp với các dữ liệu khác nhau thì thuật toán có độ phức tạp thời gian là đa thức. Từ khóa Tập rút gọn lí thuyết tập thô quan hệ tương đối bảng quyết định không đầy đủ. I. MỞ ĐẦU Rút gọn thuộc tính trong bảng quyết định là quá trình loại bỏ các thuộc tính dư thừa trong tập thuộc tính điều kiện mà không ảnh hưởng đến việc phân lớp các đối tượng. Dựa vào tập rút gọn thu được việc sinh luật và phân lớp đạt hiệu quả cao nhất. Cho đến nay có rất nhiều công trình nghiên cứu về các thuật toán rút gọn thuộc tính trong lý thuyết tập thô. Tuy nhiên các thuật toán này đều tìm được một tập rút gọn tốt nhất theo một tiêu chí đánh giá nào đó với độ phức tạp đa thức các thuật toán theo hướng tiếp cận heuristic mà chưa giải quyết bài toán tìm tất cả các tập rút gọn trong bảng quyết định không đầy đủ. Trong 7