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ê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 dịnh nhất q...

Full description

Saved in:
Bibliographic Details
Main Author: Vũ Đức Thi
Format: Book Book chapter Dataset
Published: ĐHQGHN 2016
Online Access:http://repository.vnu.edu.vn/handle/VNU_123/10835
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Vietnam National University, Hanoi
id oai:112.137.131.14:VNU_123-10835
record_format dspace
spelling oai:112.137.131.14:VNU_123-108352017-04-05T14:08:54Z 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 Vũ Đức Thi 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 dị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= < C U {d}, F> 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 đủ. 2016-05-26T07:31:02Z 2016-05-26T07:31:02Z 2015 Book Book chapter Dataset http://repository.vnu.edu.vn/handle/VNU_123/10835 application/pdf ĐHQGHN
institution Vietnam National University, Hanoi
building VNU Library & Information Center
country Vietnam
collection VNU Digital Repository
description 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 dị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= < C U {d}, F> 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 đủ.
format Book
Book chapter
Dataset
author Vũ Đức Thi
spellingShingle Vũ Đức Thi
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
author_facet Vũ Đức Thi
author_sort Vũ Đức Thi
title 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
title_short 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
title_full 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
title_fullStr 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
title_full_unstemmed 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
title_sort 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
publisher ĐHQGHN
publishDate 2016
url http://repository.vnu.edu.vn/handle/VNU_123/10835
_version_ 1680967926504488960