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Ề 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.
- 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.
- 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 tính toán đa thức với kích cỡ của bảng này..
- Việc nghiên cứu các tập rút gọn trên bảng quyết định nhất quán liên hệ khá chặt chẽ với lí thuyết cơ sở dữ liệu quan hệ.
- Trong phần này, chúng tôi đưa ra một vài khái niệm cơ bản cần dùng trong lí thuyết cơ sở dữ liệu quan hệ và lí thuyết tập thô.
- Định nghĩa 1.1.
- a n  là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính a i có miền giá trị là D a.
- Quan hệ r trên R là tập các bộ  h 1.
- h R D a j m là một hàm sao.
- h m  là một quan hệ trên tập thuộc tính R.
- Phụ thuộc hàm (PTH) trên R là một dãy ký tự có dạng A B với A, B  R.
- PTH A B thỏa mãn quan hệ r trên R nếu:.
- B  là họ đầy đủ các PTH thỏa mãn quan hệ r.
- là tập các tập con của R.
- Ta nói rằng F là một họ f trên R nếu với mọi A B C D.
- F  là tập tất c Sơ đồ q hiệu A.
- và v là hai đối Định n quyết định S đ.
- ính quyết định.
- Tập rút của C..
- g là F r là một cả các PTH đư quan hệ (SĐQH.
- à một quan hệ c gọi là họ các nghĩa 1.2.
- Bản được gọi là nh.
- mọi cặp đối tư mọi E là tập con.
- E là tập cung..
- N ược dẫn xuất từ H) s là một cặ.
- là một hệ Spe.
- là một hệ Spe ĐQH s) thì.
- A , ta ký h à một tập con viết B u.
- ng quyết định hất quán nếu D.
- thì gọi là khôn.
- o bảng quyết địn.
- Nếu F là một từ F bằng việc ặp  R F.
- ược gọi là bao.
- của thuộc tính một bộ bốn S ác thuộc tính.
- hiệu giá trị th các thuộc tính.
- h là một hệ thô D phụ thuộc ng nhất quán ha.
- Thông thườn nh nhất quán D.
- òn gọi là tập r.
- ột bài toán NP ạnh - vertex co là tập điểm ph kết quả cần thi.
- họ f trên R thì c áp dụng các q với R là tập th đóng của A trên ược gọi là bao đ u với mọi A , a định nghĩa tậ.
- Nếu  là mộ cả các tập khôn.
- với mọi i.
- U, A, V, f) vớ ức là với mọi C được gọi là tậ.
- F là tập các ph A.
- n quan hệ r..
- ó U là tập hữu à tập giá trị c.
- tập thuộc tính đ.
- ai trò là tập cá r (hoặc của s),.
- là tập các.
- ác khóa tối , gọi là tập.
- là tập thuộc.
- ọi là tập rút.
- tập rút gọn.
- [4] Cho bảng quyết định nhất quán.
- DS  U C  d V f với C.
- Xét quan hệ r.
- 2 u m  trên tập thuộc tính R C.
- Ở đây  d r là họ các tập tối thiểu của thuộc tính.
- d trên quan hệ r..
- CÁC KẾT QUẢ.
- Định nghĩa 2.1.
- Cho trước DS = (U, C ∪ {d}, V, f), tập B được gọi là tập tựa rút gọn của DS nếu tồn tại một tập rút gọn A của DS sao cho A ⊆ B..
- Trước tiên, tác giả đưa ra kết quả sau..
- Cho K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán:.
- Ta xây dựng bảng quyết định DS.
- u m } với mọi c C : c(u 0.
- Với mọi i, i = 1,…m và c là phần tử của C.
- Kết quả đã được chứng minh..
- Vấn đề sau là NP- đầy đủ.
- Việc xác định có tồn tại hay không một tập A ⊆ R sao cho.
- và xác định A không là tập con của mỗi tập B.
- Dễ thấy việc xác định này có thời gian tính đa thức với n và m (Ở đây.
- Chúng ta chọn vấn đề sau [1] là NP - đầy đủ (vấn đề lực lượng của tập điểm phủ cạnh -vertex cover problem)..
- Cho số k nguyên dương và đồ thị không định hướng G = <V,E>, với V là tập đỉnh và E là tập cung, xác định có một tập điểm phủ cạnh có lực lượng không lớn hơn k..
- Chúng ta chứng minh vấn đề này được chuyển về vấn đề của chúng ta bằng một phép biến đổi có thời gian đa thức..
- Dễ thấy P là một hệ Sperner trên R.
- 578 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 Nếu |A.
- đối với mọi (a , a.
- Do đó A là một tập điểm phủ cạnh của G.
- Ngược lại A là một tập điểm phủ cạnh của G thì từ định nghĩa của P và định nghĩa của tập điểm phủ cạnh, ta có A ⊈ B , với mọi i = 1,...,m.
- Do đó A ⊈ B (với mọi i = 1,...,m) khi và chỉ khi A là một tập điểm phủ cạnh của G..
- Kết quả được chứng minh..
- Trên cơ sở Bổ đề 2.1, chúng ta có thuật toán thời gian tính đa thức để tìm một bảng quyết định nhất quán từ một hệ Sperner cho trước K sao cho.
- cho nên với định lý trên chúng ta có kết quả sau..
- Vấn đề sau là NP - đầy đủ: Cho trước số nguyên dương k và một bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f).
- Việc xác định có tồn tại hay không một tập tựa rút gọn A của DS mà |A.
- Như chúng ta đã biết, nếu kí pháp lớp bài toán được nhận biết bởi máy Turing tiền định là P và lớp bài toán được nhận biết bởi máy Turing bất định là NP, thì bài toán NP = P hay không là bài toán chưa giải được.
- Từ kết quả trên, chúng ta có kết quả sau..
- Cho trước bảng quyết định DS = (U, C ∪ {d}, V, f.
- Khi đó việc tìm tập rút gọn có lực lượng nhỏ nhất của DS 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..
- “Thuật toán tìm tất cả các rút gọn trong bảng quyết định”

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt