tailieunhanh - Về một vấn đề thuật toán liên quan đến tập rút gọn trong bảng quyết định nhất quán

Bài viết đưa ra khái niệm tập tựa rút gọn (tập thuộc tính chứa một tập rút gọn nào đó) trong bảng quyết định nhất quán. Tác giả trình bày một bài toán NP- đầy đủ liên quan đến lực lượng của các tập tựa rút gọn. | Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR Hà Nội ngày 09-10 8 2018 DOI VỀ MỘT VẤN ĐỀ THUẬT TOÁN LIÊN QUAN ĐẾN TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH NHẤT QUÁN Vũ Đức Thi Đại học Quốc gia Hà Nội Email vdthi@ TÓM TẮT Việc nghiên cứu về các tập rút gọn nói chung và các tập rút gọn trong bảng quyết định nhất quán nói riêng được nhiều nhà khoa học thực hiện. Đối với bảng quyết định nhất quán ta đã có một thuật toán có độ phức tạp thời gian tính đa thức tìm một tập rút gọn bất kỳ. Đồng thời việc tìm các thuộc tính dư thừa thuộc tính không tham gia một tập rút gọn nào cũng được thực hiện bởi một thuật toán thời gian tính đa thức. Tuy vậy việc tìm tất cả các tập rút gọn trong bảng quyết định nhất quán là bài toán có độ phức tạp thời gian tính hàm mũ. Trong bài báo này tác giả đưa ra khái niệm tập tựa rút gọn tập thuộc tính chứa một tập rút gọn nào đó trong bảng quyết định nhất quán. Tác giả trình bày một bài toán NP- đầy đủ liên quan đến lực lượng của các tập tựa rút gọn. Trên cơ sở kết quả này tác giả chỉ ra rằng việc tìm tập rút gọn có lực lượng bé nhất không thể thực hiện được bằng một thuật toán có thời gian tính đa thức. Có nghĩa là cho đến nay việc tìm tập này là không khả thi trên hệ thống máy tính. Keywords I. CÁC KHÁI NIỆM CƠ BẢN Trong các bài toán thực tế bảng quyết định thường chứa các đối tượng không nhất quán là các đối tượng bằng nhau trên tập thuộc tính điều kiện nhưng khác nhau trên tập thuộc tính quyết định gọi là bảng quyết định không nhất quán. Tuy nhiên tùy thuộc vào lớp bài toán cần giải quyết mà ta có thể chuyển bảng quyết định không nhất quán về bảng quyết định nhất quán qua bước tiền xử lý số liệu bằng cách loại bỏ các đối tượng không nhất quán. Có thể thấy rằng trong một bảng quyết định DS bất kỳ nếu ta không cho phép có hai hàng giá trị giống nhau thì việc kiểm tra DS có là bảng quyết định nhất quán hay không có thể thực hiện bằng một thuật toán có độ phức tạp .

• Cơ sở dữ liệu
• 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ệ
• Lí thuyết tập thô
• Thuật toán tìm tập rút gọn
• Bảng quyết định không đầy đủ
• 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
• Ma trận phân biệt được
• Hệ thông tin
• Tập rút gọn
• Quan hệ tương đương
• Thuật toán tìm lõi Core (B)
• Lý thuyết tập thô
• Rút gọn thuộc tính
• Thuật toán gia tăng
• Phương pháp rút gọn thuộc tính
• Miền trị thuộc tính
• Tập thô mờ
• Thuật toán tìm tập phản khoá
• Thuật toán tìm tập khoá tối thiểu
• Tạo chí tin học
• Bảng quyết định
• Thuật toán tìm tất cả
• Thuật toán rút gọn
• Rút gọn tập luật mờ trích xuất
• Máy học Véc tơ
• Tích hợp thuật toán phân cụm k Means
• Mô hình mờ TSK
• Mô hình mờ hướng dữ liệu
• Luận văn Thạc sĩ
• Luận văn Thạc sĩ Máy tính
• Thuật toán filter wrappe
• Ứng dụng phát hiện tàu thuyền
• Phụ thuộc hàm
• Phụ thuộc xấp xỉ
• Cơ sở toán học cho tin học
• Hệ thống thông tin
• Luận án tiến sĩ
• Máy tính và công nghệ thông tin
• Lý thuyết tập thô mờ
• Thuật toán filter wrapper
• Phương pháp lai ghép trong rút gọn
• Tóm tắt luận văn Tiến sĩ
• Tóm tắt luận án Tiến sĩ Toán học
• Hiệu năng tập luật quyết định
• Phép xấp xỉ trên
• Mô hình phủ tập thô
• thuật toán xây dựng
• khoa học điều khiển
• hệ thống kỹ thuật
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• luận văn
• lý thuyết tập thô do Z
• Pawlak
• phụ thuộc đa trị
• Quan hệ tương đương mờ
• Khoảng cách mờ
• Khoảng cách mờ giữa hai phân hoạch mờ
• Xây dựng thuật toán Heuristic