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

• Cơ sở dữ liệu
• Tập rút gọn
• Lí thuyết tập thô
• Bảng quyết định không đầy đủ
• Thuật toán tìm tập phản khoá
• Thuật toán tìm tập khoá tối thiểu
• Bài tập rút gọn biểu thức
• Bài tập Toán thi vào lớp 10
• Câu hỏi rút gọn biểu thức
• Luyện thi vào lớp 10
• Ôn tập rút gọn biểu thức
• Ôn tập môn Toán
• Rút gọn biểu thức số
• Bài tập biểu thức số
• Bài tập rút gọn
• Ôn tập vào lớp 10
• Rút gọn biểu thức chứa chữ
• Rút gọn biểu thức
• Bài tập biểu thức
• Thuật toán tìm tập rút gọn
• Tìm tập rút gọn
• Điều khiển học
• Rút gọn tri thức
• Thuật toán Heuristic
• Rút gọn thuộc tính trực tiếp trên bảng
• Tiếp cận tập thô mờ
• Bảng quyết định
• Quan hệ tương tự mờ
• Rút gọn thuộc tính
• Rút gọn biểu thức chứa căn
• Chuyên đề Rút gọn biểu thức chứa căn
• Biểu thức chứa căn
• Bài tập chứa căn thức
• Bài tập Toán lớp 8
• Chuyên đề Rút gọn biểu thức
• Rút gọn biểu thức chứa căn thức bậc hai
• Biểu thức chứa căn thức bậc hai
• Giải bài tập Đại số 6
• Giải bài tập SGK Đại số 6
• Chương phân số
• Rút gọn phân số
• Luyện tập rút gọn phân số
• Phân số tối giản
• Phân số cùng ước chung
• Lý thuyết tập thô
• Thuật toán gia tăng
• Ma trận phân biệt được
• Hệ thông tin
• Quan hệ tương đương
• Thuật toán tìm lõi Core (B)
• Độ phức tạp tính toán
• Tập rút gọn trên bảng quyết định
• Bài toán co NP
• Bảng quyết định DS
• Phương pháp xử lý giá trị
• Xử lý giá trị thiếu
• Bài tập Hóa lý cơ sở rút gọn
• Hóa lý cơ sở rút gọn
• Hóa lý cơ sở
• Cân bằng hóa học
• Cân bằng pha
• Cân bằng dung dịch
• Tập thô mờ
• Bảng quyết định mờ
• Phân hoạch mờ
• Miền dương mờ
• Phương pháp rút gọn thuộc tính
• Miền trị thuộc tính
• Rút gọn phân thức
• Chuyên đề Rút gọn phân thức
• Phương pháp phân tích đa thức thành nhân tử
• Tính chất cơ bản của phân thức
• Chứng minh đẳng thức
• Giáo án Đại số 8
• Giáo án điện tử lớp 8
• Bài tập Toán 8
• Phương pháp rút gọn phân thức
• Giải bài tập Toán 9
• Giải bài tập SGK Toán 9
• Căn bậc hai căn bậc ba
• Giải bài tập SGK Toán 9 trang 32
• Giải bài tập rút gọn biểu thức chứa căn bậc hai
• Giải bài tập Toán 8
• Giải bài tập SGK Toán 8
• Phân thức đại số
• Giải bài tập SGK Toán 8 trang 39
• Giải bài tập SGK Toán 8 trang 40
• Ước chung của phân số
• Khai phá dữ liệu
• Tập thô dung sa
• Hệ quyết định đa trị
• Bài tập Số học 6
• Số học 6
• Bài tập rút gọn phân số
• So sánh phân số
• Bài tập Toán lớp 6
• Khai phá tập dữ liệu
• Lí thuyết tập tin thô
• Tập rút gọn trong bảng quyết định
• Xử lý thông tin trên bảng quyết định
• Hệ tổ hợp Sperner
• Thuật toán tập rút gọn
• Bảng quyết định nhất quán
• Thời gian tính đa thức
• Lí thuyết cơ sở dữ liệu quan hệ