tailieunhanh - Báo cáo khoa học: " RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH DỰA VÀO HỌ PHỦ TẬP THÔ"

Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung, và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP -khó. Lý do chính là do s tổ hợp các thuộc tính. ự Trong bài báo này, chúng tôi ề xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự đ phát triển các kết quả của Cheng Degang và cộng sự trong hệ quyết định. | TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG - SỐ 4 33 .2009 RÚT GỌN TẬP THUỘC TÍNH CỦA HỆ QUYẾT ĐỊNH DỰA VÀO HỌ PHỦ TẬP THÔ ON THE ATTRIBUTE REDUCTION OF DECISION SYSTEMS BASED ON A FAMILY OF COVERING ROUGH SETS Nguyễn Đức Thuần Trường Đại học Nha Trang Nguyễn Xuân Huy Viện Công nghệ thông tin Hà Nội TÓM TẮT Rút gọn thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán tìm rút gon tối thiểu của một hệ thống thông tin nói chung và bài toán rút gọn của một hệ thống thông tin không đầy đủ nói riêng là một bài toán NP-khó. Lý do chính là do sự tổ hợp các thuộc tính. Trong bài báo này chúng tôi ềí xuất một thuật toán rút gọn tập thuộc tính. Thuật toán là sự phát trển các kết quả của Cheng Degang và cộng sự trong hệ quyết định phủ nhất quán và không nhất quán. Độ phức tạp của giải thuật là O A U 2 . Trong phần cuối bài báo chúng tôi trình bày một ví dụ minh họa thể hiện hiệu năng của giải thuật. ABSTRACT Attribute reduction is an important issue in the rough set theory. It has been proved that finding the minimal reduction of an information system is a NP-hard problem so is finding the minimal reduction of an incomplete information system. The main reason for this problem is caused by a combination of attributes. In this paper we theoretically study an attribute reduction algorithm. This is based on the results given by Chen Degang and his colleages in the consistent and inconsistent covering decision system. The time complexity of this algorithm is O A U 2 . At the end of this paper an illustrative example is also provided to show the application potential of the algorithm. 1. Giới thiệu Bài toán rút gọn tập thuộc tính là một bài toán quan trọng trong lý thuyết tập thô. Bài toán này thuộc lớp NP-khó 3 .Vì vậy đôi khi nguời ta chỉ tìm một rút gọn nhằm thu gọn kích thuớc của hệ thống thông tin . Trong bài báo này chúng tôi đề xuất một thuật toán tìm một rút gọn tối thiểu tập thuộc tính ứng với một họ phủ quyết định tập thô. Độ phức tạp của thuật toán .