Bài viết Về độ phức tạp tính toán của một bài toán liên quan đến tập rút gọn trên bảng quyết định trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. | Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 DOI: VỀ ĐỘ PHỨC TẠP TÍNH TOÁN CỦA MỘT BÀI TOÁN LIÊN QUAN ĐẾN TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH Nguyễn Ngọc Cương1, Vũ Đức Thi2 1 Khoa Toán-Tin - Học viện an ninh nhân dân Viện Công nghệ thông tin - Đại học quốc gia Hà Nội 2 TÓM TẮT - Trên thực tiễn, các vấn đề liên quan đến tập rút gọn trên bảng quyết định đã được nhiều tác giả đề cập và nghiên cứu. Trong bài báo này, chúng tôi trình bày một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định nhất quán DS với tập thuộc tính CU{d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. Tương tự chúng ta gọi A là tập tựa tối thiểu của thuộc tính d trên sơ đồ quan hệ s= nếu A chứa một tập tối thiểu của thuộc tính d. Gọi Q là tập tất cả các tập tựa rút gọn của bảng quyết định DS, P là tập tất cả các tập tựa tối thiểu của thuộc tính d trên s. Khi đó bài toán xác định Q có là tập con của P hay không là co-NP - đầy đủ. Việc tìm kiếm các tập rút gọn đóng vai trò quan trọng trong việc xử lí thông tin trên bảng quyết định. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cơ bản phục vụ cho việc xử lí thông tin. Về thực chất, việc rút gọn thuộc tính là tìm tập con nhỏ nhất của tập các thuộc tính để bảo toàn thông tin phân lớp trên bảng quyết định. Trong bài báo này chúng tôi chỉ đề cập tới các bảng quyết định nhất quán. Trên thực tiễn, tùy theo từng bài toán cụ thể, chúng 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. Bài báo này trình bày về một bài toán co-NP - đầy đủ liên quan đến các tập rút gọn trên bảng quyết định. Chúng ta gọi A là tập tựa rút gọn trên bảng quyết định DS với tập thuộc tính C U {d} và d là thuộc tính quyết định nếu A chứa một tập rút gọn nào đó. Tương tự chúng ta gọi A là tập tựa tối thiểu của
