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...
Saved in:
Main Author: | |
---|---|
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 |