VỀ BÀI TOÁN XÂY DỰNG BẢNG QUYẾT ĐỊNH NHẤT QUÁN TRONG LÝ THUYẾT TẬP THÔ

Công Nghệ Thông Tin, it, phầm mềm, website, web, mobile app, trí tuệ nhân tạo, blockchain, AI, machine learning - Công Nghệ Thông Tin, it, phầm mềm, website, web, mobile app, trí tuệ nhân tạo, blockchain, AI, machine learning - Công nghệ thông tin Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9102020 DOI: 10.15625vap.2020.00230 VỀ BÀI TOÁN XÂY DỰNG BẢNG QUYẾT ĐỊNH NHẤ T QUÁN TRONG LÝ THUYẾT TẬP THÔ Vũ Đức Thi Đại học Quốc gia Hà Nội vdthivnu.edu.vn TÓM TẮT: Việc nghiên cứu các tập rút gọn trong lí thuyết tập thô 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 trên thế giới thực hiện. Đối với bảng quyết định nhất quán, chúng 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ũ. Chúng tôi 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. Có nghĩa là cho đến nay, việc tìm tậ p này là không khả thi trên hệ thống máy tính. Đặc biệt, người ta đã chứng minh được việc nghiên cứu các tập rút gọn trong bảng quyết đị nh nhất quán tương đương với việc nghiên cứu hệ Sperner. Đây là hệ tổ hợp đã được nhiều nhà khoa học trên thế giới nghiên cứ u và phát triển. Trong bài báo này, chúng tôi chứng minh bài toán xây dựng bảng quyết định nhất quán từ hệ Sperner K cho trướ c sao cho tập các rút gọn của nó chính là K có độ phức tạp hàm mũ. Từ khóa: Sperner system, reduct set, consistent decision table. 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. Mụ c tiêu chính của bài báo này là chứng minh xuất phát từ hệ Sperner K cho trước, bài toán xây dựng bảng quyết định nhấ t quán sao cho tập các rút gọn của nó chính là K có độ phức tạp hàm mũ. Trước hết chúng tôi trình bày một số các khái niệm cơ bản cần thiết cho việc trình bày các kết quả chính củ a bài báo 1. Những khái niệm cơ bản Mục này cung cấp một số khái niệm cơ bản được dùng trong bài báo. Các khái niệm này có thể xem trong 1, 3, 4, 6. Định nghĩa 1.1. Hệ thông tin là một bộ bốn S = ( U, A, V, f ) trong đó U là tập hữu hạn, khác rỗng các đối tượng; A là tập hữu hạn, khác rỗng các thuộc tính; a a A V V ∈ =  với aV là tập giá trị của thuộc tính a A∈ ; : af U A V× → là hàm thông tin, ,a A u U∀ ∈ ∈ ( ), ∈ af u a V . Với mọi ,u U a A∈ ∈ , ta ký hiệu giá trị thuộc tính a tại đối tượng u là ( )a u thay vì ( ),f u a . Nếu { }1 2, ,..., kB b b b A= ⊆ là một tập con các thuộc tính thì ta ký hiệu bộ các giá trị ( )ib u bởi ( )B u . Như vậy, nếu u và v là hai đối tượng, thì ta viết ( ) ( )B u B v= nếu ( ) ( )i ib u b v= với mọi 1,...,i k= . Định nghĩa 1.2. Bảng quyết định là một hệ thông tin S = (U, A, V, f) với A= C D và C D∩ = ∅ . Bả ng quyết định S được gọi là nhất quán nếu D phụ thuộc hàm vào C, tức là với mọi ( ) ( ), ,u v U C u C v∈ = kéo theo ( ) ( )D u D v= . Ngược lại thì gọi là không nhất quán hay mâu thuẫn. C được gọi là tập thuộc tính điều kiện và D là tập thuộ c tính quyết định Thông thường D = {d} chứa một thuộc tính. Định nghĩa 1.3. Cho bảng quyết định nhất quán ( ), , ,DS U C D V f= ∪ và tập thuộc tính R C⊆ . R được gọi là tậ p rút gọn nếu: - với mọi cặp đối tượng u, v thì R(u) = R(v) kéo theo D(u) = D(v); - với mọi E là tập con thực sự của R thì tồn tại cặp u, v để E(u) = E(v) không kéo theo. Vũ Đức Thi 691 D(u) = D(v) Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu ( )PRED C là họ tất cả các tập rút gọ n của C. Cho { }1 ,..., nR a a= là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính ia có miền giá trị là ( )iD a . Quan hệ r trên R là tập các bộ { }1 ,..., mh h với ( ): ,1 ∈ → ≤ ≤ i j i a R h R D a j m là một hàm sao cho ( ) ( )∈j i ih a D a . Cho { }1 ,..., mr h h= là một quan hệ trên tập thuộc tính { }1 ,..., nR a a= . 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 ( ) ( ) ( ) ( )( ) ( ) ( ) ( )( )( ),i j i j i jh h r a A h a h a b B h b h b∀ ∈ ∀ ∈ = ⇒ ∀ ∈ = . Đặt ( ){ }, : , ,rF A B A B R A B= ⊆ → là họ đầy đủ các PTH thỏa mãn quan hệ r. Ký hiệu ( )P R là tập các tập con của R. Cho ( ) ( )F P R P 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 R⊆ ( ) ( )1 , .A A F∈ ( ) ( ) ( ) ( )2 , , , , .A B F B C F A C F∈ ∈ ⇒ ∈ ( ) ( ) ( )3 , , , , .A B F A C D B C D F∈ ⊆ ⊆ ⇒ ∈ ( ) ( ) ( ) ( )4 , , , , .A B F C D F A C B D F∈ ∈ ⇒ ∪ ∪ ∈ Rõ ràng là F r là một họ f trên R. Nếu F là một họ f trên R thì có một quan hệ r trên R sao cho F r = F. Ký hiệu F + là tập tất cả các PTH được dẫn xuất từ F bằng việc áp dụng các quy tắc ( ) ( )1 4− . Sơ đồ quan hệ (SĐQH) s là một cặp ,R F< > với R là tập thuộc tính và F là tập các phụ thuộc hàm trên R . Ký hiệu { }{ }:A a A a F+ + = → ∈ , A+ được gọi là bao đóng của A trên s. Dễ thấy A B F + → ∈ khi và chỉ khi B A + ⊆ . Tương tự ký hiệu { }{ }:rA a A a F+ + = → ∈ , rA + được gọi là bao đóng của A trên quan hệ r. Cho ,s R F= < > là SĐQH trên R, a R∈ . Đặt { }: , s a A R A a= ⊆ → ∃  { }( ) ( ){ }:B B a B A→ ⊂ . Khi đó, s a  được gọi là họ các tập tối thiểu của thuộc tính a trên s. Tương tự, cho r là một quan hệ trên R và a R∈ . Đặt { }: , r a A R A a= ⊆ → ∃  { }( ) ( ){ }:B B a B A→ ⊂ . Khi đó, r a  được gọi là họ các tập tối thiểu của thuộ c tính a trên r. Gọi ( )P R⊆  là một hệ Sperner trên R nếu với mọi ,A B ∈  kéo theo A B⊄ . Dễ thấy K as , K ar là các hệ Sperner trên R. Với tập  là một hệ Sperner trên R, ta định nghĩa tập 1−  như sau: ( ) ( ){ }1 :A R B B A− = ⊂ ∈ ⇒ ⊄   và nếu ( ) ( )( )A C B B C⊂ ⇒ ∃ ∈ ⊆  Dễ thấy 1−  cũng là một hệ Sperner trên R. Nếu  là một hệ Sperner trên R đóng vai trò là tập các khóa tố i thiểu của quan hệ r (hoặc SĐQH s) thì 1−  là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là tậ p các phản khóa. Nếu  là một hệ Sperner trên R đóng vai trò là họ các tập tối thiểu của thuộc tính a trên r (hoặc trên s), hay r a=   (hoặc s a=   ), thì { } 1 1 r a − − =   (hoặc { } 1 1 s a − − =   ) là họ tất cả các tập lớn nhấ t không phải là tập tối thiểu của thuộc tính a, được định nghĩa như sau 1 : { } { } { }{ } 1 : , r a r rA R A a F A B B a F − + + = ⊆ → ∉ ⊂ ⇒ → ∈  , { } { } { }{ } 1 : , s a A R A a F A B B a F − + + = ⊆ → ∉ ⊂ ⇒ → ∈  . 692 VỀ BÀI TOÁN XÂY DỰNG BẢNG QUYẾT ĐỊNH NHẤT QUÁN TRONG LÝ THUYẾT TẬP THÔ Chúng ta có thể thấy khái niệm tập tối thiểu của thuộc tính trên quan hệ r tương đương khái niệm tập rút gọ n trong bảng quyết định nhất quán. 2. Kết quả Trong phần này, chúng tôi trình bày các kết quả của bài báo. Đầu tiên, chúng tôi trình bày một bổ đề cần thiết sau. Bổ đề 2.1. 5 Cho bảng quyết định nhất quán { }( ), , ,DS U C d V f= ∪ với { }1 2, ,..., nC c c c= , { }1 2, ,...,= mU u u u . Xét quan hệ { }1 2, ,...,= mr u u u trên tập thuộc tính { }R C d= ∪ . Đặt { }ij :1r E i j m= ≤ < ≤  với ( ) ( ){ }ij : i jE a R a u a u= ∈ = Đặt : ,d rA d A= ∈ ∉ ∃  { }: ,rB d B A B∈ ∉ ⊂  . Thì ( ) 1 r d d − =   . Ở đây r d  là họ các tập tối thiểu của thuộc tính { }d trên quan hệ r. Định lí 2.2. 2 Cho trước bảng quyết định DS = (U, C ∪ {d}, V, f) thì (K dr ) -1 là hệ Sperner trên C. Ngược lạ i nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) để K= (Kdr ) -1 . Trên cơ sở Định lí 2.2, nếu K là hệ Sperner trên C. Giả sử K = { A1,…,A m }. Chúng ta xây dựng bảng quyết định DS = (U, C∪{d}, V, f) như sau: U = {u0 , u1,…, u m} với mọi c ∈ C : c(u0) = 0 và d(u0) = 0. Với mọi i, i = 1,…m và c là phần tử của C. Chúng ta đặt c(ui) = 0 nếu c ∈ Ai. Ngược lại c(ui) = i. Đặt d(ui) = i. Với R = C ∪ {d}. Có thể thấy K= (Kdr ) -1 . Sau đây, chúng tôi đưa ra một thuật toán từ một hệ Sperner bất kỳ tìm tập phản khóa của nó. Thuật toán 2.3 8 (Tìm tập phản khóa) Vào:

V Ề BÀI TOÁN XÂY DỰNG BẢNG QUYẾT ĐỊNH NHẤT QUÁN

TRONG LÝ THUY ẾT TẬP THÔ

Vũ Đức Thi

Đại học Quốc gia Hà Nội

vdthi@vnu.edu.vn

TÓM T ẮT: Việc nghiên cứu các tập rút gọn trong lí thuyết tập thô 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 trên thế giới thực hiện Đối với bảng quyết định nhất quán, chúng 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ũ Chúng tôi 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 Có nghĩa là cho đến nay, việc tìm tập này là không khả thi trên hệ thống máy tính Đặc biệt, người ta đã chứng minh được việc nghiên cứu các tập rút gọn trong bảng quyết định

nh ất quán tương đương với việc nghiên cứu hệ Sperner Đây là hệ tổ hợp đã được nhiều nhà khoa học trên thế giới nghiên cứu và phát triển

Trong bài báo này, chúng tôi ch ứng minh bài toán xây dựng bảng quyết định nhất quán từ hệ Sperner K cho trước sao cho tập các rút gọn của nó chính là K có độ phức tạp hàm mũ

T ừ khóa: Sperner system, reduct set, consistent decision table

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 Mục tiêu chính của bài báo này là chứng minh xuất phát từ hệ Sperner K cho trước, bài toán xây dựng bảng quyết định nhất quán sao cho tập các rút gọn của nó chính là K có độ phức tạp hàm mũ

Trước hết chúng tôi trình bày một số các khái niệm cơ bản cần thiết cho việc trình bày các kết quả chính của bài báo

1 Nh ững khái niệm cơ bản

Mục này cung cấp một số khái niệm cơ bản được dùng trong bài báo Các khái niệm này có thể xem trong [ 1, 3,

4, 6]

Định nghĩa 1.1 Hệ thông tin là một bộ bốn S = ( U, A, V, f ) trong đó U là tập hữu hạn, khác rỗng các đối

tượng; A là tập hữu hạn, khác rỗng các thuộc tính; a

a A

V V

∈

=  với Va là tập giá trị của thuộc tính a ∈ A;

f U × → A V là hàm thông tin, ∀ ∈ a A u , ∈ U f u a ( ) , ∈ Va

Với mọi u ∈ U a , ∈ A, ta ký hiệu giá trị thuộc tính a tại đối tượng u là a u ( ) thay vì f u a ( ) , Nếu

{ 1, 2, , k}

B = b b b ⊆ A là một tập con các thuộc tính thì ta ký hiệu bộ các giá trị b ui( ) bởi B u ( ) Như vậy, nếu u

và v là hai đối tượng, thì ta viết B u ( ) = B v ( ) nếu b ui( ) = b vi( ) với mọi i = 1, , k

Định nghĩa 1.2 Bảng quyết định là một hệ thông tin S = (U, A, V, f) với A= C D và C ∩ = ∅ D Bảng quyết định S được gọi là nhất quán nếu D phụ thuộc hàm vào C, tức là với mọi u v , ∈ U C u , ( ) = C v ( ) kéo theo

D u = D v Ngược lại thì gọi là không nhất quán hay mâu thuẫn C được gọi là tập thuộc tính điều kiện và D là tập thuộc tính quyết định

Thông thường D = {d} chứa một thuộc tính

Định nghĩa 1.3 Cho bảng quyết định nhất quánDS = ( U C , ∪ D V f , , ) và tập thuộc tính R ⊆ C R được gọi là tập rút gọn nếu:

- với mọi cặp đối tượng u, v thì R(u) = R(v) kéo theo D(u) = D(v);

- với mọi E là tập con thực sự của R thì tồn tại cặp u, v để E(u) = E(v) không kéo theo

D(u) = D(v)

Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak Ký hiệu PRED C ( ) là họ tất cả các tập rút gọn

của C

Cho R = { a1, , an} là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính ai có miền giá trị là D a ( )i Quan hệ r trên R là tập các bộ { h1, , hm}với : ( ) ,1

∈

i

a R

h R D a j m là một hàm sao cho

( ) ∈ ( )

Cho r = { h1, , hm}là một quan hệ trên tập thuộc tính R = { a1, , an} 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

( ∀ h hi, j∈ r ) ( ( ∀ ∈ a A h a ) ( ) ( i = h aj( ) ) ⇒ ∀ ∈ ( b B h b ) ( ) ( i = h bj( ) ) ) Đặt Fr = { ( A B , ) : , A B ⊆ R A , → B } là

họ đầy đủ các PTH thỏa mãn quan hệ r Ký hiệu P R ( ) là tập các tập con của R Cho F = P R ( ) ( ) × P 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 , , , ⊆ R

( ) ( 1 A A , ) ∈ F

( ) ( 3 A B , ) ∈ F A , ⊆ C D , ⊆ ⇒ B ( C D , ) ∈ F

Rõ ràng là F r là một họ f trên R Nếu F là một họ f trên R thì có một quan hệ r trên R sao cho F r = F Ký hiệu

F+là tập tất cả các PTH được dẫn xuất từ F bằng việc áp dụng các quy tắc ( ) ( ) 1 − 4

Sơ đồ quan hệ (SĐQH) s là một cặp < R F , > với R là tập thuộc tính và F là tập các phụ thuộc hàm trên R Ký

hiệu A+ = { a A : → { } a ∈ F+}, A+ được gọi là bao đóng của A trên s Dễ thấy A → ∈ B F+ khi và chỉ khi B ⊆ A+

Tương tự ký hiệu Ar+ = { a A : → { } a ∈ F+}, Ar+ được gọi là bao đóng của A trên quan hệ r

Cho s = < R F , > là SĐQH trên R, a ∈ R Đặt a s= ⊆ { A R A : → { } a , ∃ B B : ( → { } a ) ( B ⊂ A ) } Khi đó, s

a



được gọi là họ các tập tối thiểu của thuộc tính a trên s Tương tự, cho r là một quan hệ trên R và a ∈ R Đặt

{ }

r

 { B : ( B → { } a ) ( B ⊂ A ) } Khi đó, r

a

 được gọi là họ các tập tối thiểu của thuộc

tính a trên r

Gọi  ⊆ P R ( ) là một hệ Sperner trên R nếu với mọi A B , ∈  kéo theo A ⊄ B Dễ thấy Ka, Kar là các

hệ Sperner trên R Với tập  là một hệ Sperner trên R, ta định nghĩa tập − 1 như sau:

1

:

  và nếu ( A ⊂ C ) ( ⇒ ∃ ∈ B  )( B ⊆ C )

Dễ thấy − 1 cũng là một hệ Sperner trên R Nếu  là một hệ Sperner trên R đóng vai trò là tập các khóa tối

thiểu của quan hệ r (hoặc SĐQH s) thì − 1 là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là tập

các phản khóa Nếu  là một hệ Sperner trên R đóng vai trò là họ các tập tối thiểu của thuộc tính a trên r (hoặc trên

s), hay   = a r (hoặc s

a

=

  ), thì 1 { }r 1

a

−

− =

a

−

− =

  ) là họ tất cả các tập lớn nhất không

phải là tập tối thiểu của thuộc tính a, được định nghĩa như sau [1] :

r

a − = A ⊆ R A → a ∉ Fr+ A ⊂ ⇒ → B B a ∈ Fr+

s

a − = A ⊆ R A → a ∉ F+ A ⊂ ⇒ → B B a ∈ F+

Chúng ta có thể thấy khái niệm tập tối thiểu của thuộc tính trên quan hệ r tương đương khái niệm tập rút gọn trong bảng quyết định nhất quán

2 Kết quả

Trong phần này, chúng tôi trình bày các kết quả của bài báo Đầu tiên, chúng tôi trình bày một bổ đề cần thiết sau

Bổ đề 2.1 [5] Cho bảng quyết định nhất quánDS = ( U C , ∪ { } d , , V f )với C = { c c1, 2, , cn},

{ 1, 2, , }

Xét quan hệ r = { u u1, 2, , um} trên t ập thuộc tính R = ∪ C { } d

Đặt r = { Eij:1 ≤ < ≤ i j m }với Eij= ∈ { a R a u : ( )i = a u ( )j }

Đặt d = { A ∈ r: d ∉ A , ∃ B ∈ r : d ∉ B A , ⊂ B }

−

=

d

 là họ các tập tối thiểu của thuộc tính { } d trên quan h ệ r

Định lí 2.2 [2] Cho trước bảng quyết định DS = (U, C ∪ {d}, V, f) thì (Kdr) -1 là hệ Sperner trên C Ngược lại

nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) để K= (Kdr) -1

Trên cơ sở Định lí 2.2, nếu K là hệ Sperner trên C Giả sử K = { A1,…,Am } Chúng ta xây dựng bảng quyết định DS = (U, C∪{d}, V, f) như sau:

U = {u0, u1,…, um} với mọi c ∈ C : c(u0) = 0 và d(u0) = 0 Với mọi i, i = 1,…m và c là phần tử của C Chúng ta đặt c(ui) = 0 nếu c ∈ Ai Ngược lại c(ui) = i Đặt d(ui) = i Với R = C ∪ {d}

Có thể thấy K= (Kd

r

) -1 Sau đây, chúng tôi đưa ra một thuật toán từ một hệ Sperner bất kỳ tìm tập phản khóa của nó

Thu ật toán 2.3 [8] (Tìm tập phản khóa)

Vào: 𝐾 = {𝐵1, … , 𝐵𝑛} là hệ Sperner trên R

Ra: 𝐾−1

Bước 1: Ta đặt 𝐾1= {𝑅 − {𝑎}: 𝑎 ∈ 𝐵1} Hiển nhiên 𝐾1= {𝐵1}−1

Bước q+1: (q < m) Ta giả thiết rằng 𝐾𝑞= 𝐹𝑞 ∪ �𝑋1, … , 𝑋𝑡𝑞�, ở đây 𝑋1, … , 𝑋𝑡𝑞 chứa 𝐵𝑞+1 và 𝐹𝑞=

�𝐴 ∈ 𝐾𝑞∶ 𝐵𝑞+1 ⊈ 𝐴� Đối với mỗi i (i = 1, , 𝑡𝑞) ta tìm các phản khóa của �𝐵𝑞+1� trên 𝑋𝑖tương tự như 𝐾1 Kí pháp chúng là 𝐴1𝑖, … , 𝐴𝑟𝑖𝑖 Đặt 𝐾𝑞+1= 𝐹𝑞 ∪ � 𝐴𝑖𝑝∶ 𝐴 ∈ 𝐹𝑞 𝑘é𝑜 𝑡ℎ𝑒𝑜 𝐴𝑝𝑖 ⊄ 𝐴 , 1 ≤ 𝑖 ≤ 𝑡𝑞 1 ≤ 𝑝 ≤ 𝑟𝑖� Cuối cùng ta đặt

𝐾−1= 𝐾𝑚

Định lý 2.4 [8]

Với mọi q (1 ≤ 𝑞 ≤ 𝑚), 𝐾𝑞 = �𝐵1, … , 𝐵𝑞� −1có nghĩa là 𝐾𝑚= 𝐾−1

Rõ ràng, K và 𝐾−1là xác định duy nhất lẫn nhau và từ định nghĩa của 𝐾−1 có thể thấy thuật toán của chúng ta không phụ thuộc vào thứ tự của dãy 𝐵1, … , 𝐵𝑚 Đặt 𝐾𝑞= 𝐹𝑞 ∪ �𝑋1, … , 𝑋𝑡𝑞� và 𝑙𝑞 (1 ≤ 𝑞 ≤ 𝑚 − 1) là số các phần tử

𝐾𝑞

Trên cơ sở này ta có:

M ệnh đề 2.5

Độ phức tạp thời gian tồi nhất của Thuật toán 2.3 là Θ(|𝑅|2∑𝑚−1𝑡𝑞 𝑢𝑞)

𝑞−1

Ở đây: 𝑢𝑞= �𝑙1 , 𝑛ế𝑢 𝑙𝑞− 𝑡𝑞 , nếu 𝑙𝑞 > 𝑡𝑞

𝑞= 𝑡𝑞

Rõ ràng trong mỗi bước thuật toán ta có 𝐾𝑞 là hệ Sperner trên R Ta biết rằng ([8]) kích thước của hệ Sperner

bất kỳ trên R không vượt quá 𝐶𝑛[𝑛/2], ở đây n = |𝑅| Có thể thấy 𝐶𝑛[𝑛/2] xấp xỉ bằng 2𝑛+1/2/(𝛱 𝑛1/2) Từ đó độ phức tạp

thời gian tồi nhất của thuật toán trên không nhiều hơn hàm số mũ theo n Trong trường hợp mà 𝑙𝑞≤ 𝑙𝑚 (q = 1, , m-1),

dễ thấy rằng độ phức tạp thuật toán không lớn hơn Θ(|𝑅|2 |𝐾| |𝐾−1|2) Như vậy, trong các trường hợp này độ phức tạp

của Thuật toán 2.3 tìm 𝐾−1là đa thức theo |𝑅|, |𝐾|, 𝑣à |𝐾−1| Có thể thấy nếu số lượng các phần tử của K là nhỏ thì Thuật toán 2.3 rất hiệu quả, nó chỉ đòi hỏi thời gian đa thức theo |𝑅|

Định lí 2.6 [9] Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) thì PRED C ( ) (họ tất cả các tập rút gọn của C) là hệ Sperner trên C Ngược lại nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán

DS = (U, C ∪ {d}, V, f) để K= PRED (C)

Trên cơ sở Định lí 2.2, Thuật toán 2.3, Định lí 2.6, chúng ta có kết quả sau:

Thu ật toán 2.7 (Xây dựng bảng quyết định)

Vào: K = { A1,…,Ap } là một hệ Sperner trên C = {c1, , cn}

Ra: Bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) sao cho K= PRED (C)

Bước 1: Trên cơ sở thuật toán 2.3, từ K chúng ta xây dựng tập phản khóa K-1

Giả sử K-1

= { B1, ,Bm}

Bước 2: Chúng ta xây dựng bảng quyết định nhất quán DS = ( U, C∪{d}, V, f) như sau:

U = {u0, u1,…, um} với mọi c ∈ C : c(u0) = 0 và d(u0) = 0 Với mọi i, i = 1,… m và c là phần tử của C Chúng ta đặt c(ui) = 0 nếu c ∈ Bi Ngược lại c(ui) = i Đặt d(ui) = i

Có thể thấy, trên cơ sở Bổ đề 2.1 và Định lí 2.2, chúng ta có K-1

= (Kdr) -1 Trên cơ sở này và dựa trên định nghĩa của hệ Sperner, tập phản khóa và định nghĩa các tập rút gọn của bảng quyết định nhất quán, chúng ta có K = PRED (C)

Từ Mệnh đề 2.5, do phải xây dựng tập K-1 từ K, chúng ta thấy độ phức tạp tồi nhất của thuật toán này là hàm

mũ với lực lượng của C

Từ Bổ đề 2.1, Định lí 2.2, Định lí 2.6, chúng ta có kết quả sau:

Mệnh đề 2.8 Cho bảng quyết định nhất quánDS = ( U C , ∪ { } d , , V f )với C = { c c1, 2, , cn},

{ 1, 2, , }

Xét quan hệ r = { u u1, 2, , um} trên t ập thuộc tính R = ∪ C { } d

Đặt r = { Eij:1 ≤ < ≤ i j m }với Eij= ∈ { a R a u : ( )i = a u ( )j }

Đặt d = { A ∈ r: d ∉ A , ∃ B ∈ r : d ∉ B A , ⊂ B }

K = { A1,…,Ap } là một hệ Sperner trên C và K = PRED (C) thì K-1

= Md

Nh ận xét 2.9 Cho bảng quyết định nhất quánDS = ( U C , ∪ { } d , , V f )với C = { c c1, 2, , cn},

{ 1, 2, , }

Xét quan hệ r = { u u1, 2, , um} trên t ập thuộc tính R = ∪ C { } d

Đặt r = { Eij:1 ≤ < ≤ i j m }với Eij= ∈ { a R a u : ( )i = a u ( )j }

Đặt d = { A ∈ r: d ∉ A , ∃ B ∈ r : d ∉ B A , ⊂ B }

Cho K là một hệ Sperner trên C và K = PRED (C)

1 Có thể thấy, theo định nghĩa của Er , chúng ta có |Er | = m (m -1)/2 Theo định nghĩa của Md, chúng ta có

|Md | < m(m-1)/2 Theo Mệnh đề 2.8 ta có | K-1|< m(m-1)/2

2 Nếu chúng ta đặt t = min { m: | U | = m, ở đây DS = < U, C {d}, V, f > có K = PRED (C) } Khi đó | K-1

|< t(t-1)/2 Từ đó (2 | K-1| ) ½ < t

B ổ đề 2.10: Cho trước R = {a1,a2,…,an} là tập thuộc tính Khi đó luôn tồn tại một hệ Sperner K trên R sao cho

lực lượng của K là tuyến tính đối với n và lực lượng của K-1 là hàm mũ với n

Chứng minh:

Phân đoạn R thành mỗi nhóm có 3 phần tử Như vậy:

R = X1 X2 … Xm W trong đó: |Xi| = 3, Xi∩ Xj = ∅, m = [ n/3], |W| = 0, hoặc |W| = 1, hoặc |W| = 2

Xét K = {A : |A| = 2, A là tập con thực sự của Xi với một i nào đó } nếu |W| = 0

K = {A : |A| = 2, A là tập con thực sự của Xi với một i nào đó với 1 < i < m-1 hoặc A là tập con thực sự của Xi

W} nếu |W| = 1

K = {A : |A| = 2, A là tập con thực sự của Xi với một i nào đó với 1 < i < m-1 hoặc A = W là tập con thực sự

của Xi W} nếu |W| = 2

Chúng ta có thể thấy n-1 < |K| < n+2 Có nghĩa là |K| tuyến tính với n

Mặt khác, chúng ta có thể thấy:

K-1 = {B : |B ∩ Xi | = 1 với mọi i} nếu |W| = 0

K-1 = {B : |B ∩ Xi| = 1 với 1 < i < m-1 và | B ∩ (Xm W)| = 1} nếu |W| = 1

K-1 = {B : |B ∩ Xi| = 1 với 1 < i < m và | B ∩ W| = 1} nếu |W| = 2

Chúng ta có thể thấy |K-1| > 3 [n/4] Như vậy |K-1| là hàm mũ với n

Kết quả đã được chứng minh

Định lí 2.11 Bài toán cho trước một hệ Sperner K trên C = { c c1, 2, , cn}, bài toán tìm bảng quyết định nhất quán DS = (U, A = C {d}, V, f) sao cho K = PRED(C) có độ phức tạp tính toán là hàm mũ theo lực lượng của C

Ch ứng minh:

Ta chứng minh hai bước: Tồn tại một thuật toán hàm mũ tính ra tất cả các rút gọn và bài toán tìm tất cả các rút

gọn có độ phức tạp tính toán không nhỏ hơn hàm mũ theo lực lượng của C

1 Theo Thuật toán 2.7, từ K chúng ta xây dựng được bảng quyết định nhất quán DS = (U, A = C {d}, V, f) sao cho K = PRED(C) Thuật toán này có độ phức tạp tính toán là hàm mũ theo lực lượng của C

2 Ta chứng minh bài toán tìm bảng quyết định nhất quán từ một hệ Sperner K trên C cho trước có độ phức tạp tính toán không nhỏ hơn hàm mũ theo lực lượng của C

Giả sử C = {c1,c2,…,cn} Trên C ta phân đoạn C như trong Bổ đề 2.10 Chúng ta xây dựng K và K-1

như trong

Bổ đề 2.10 Có thể thấy |K-1| > 3 [n/4] , |n-1 < |K| < n+2

Theo Nhận xét 2.9, nếu chúng ta đặt t = min { m: | U | = m, ở đây DS = < U, C {d}, V, f > có K = PRED

(C)} Khi đó (2 | K-1| ) ½ < t Có nghĩa là từ cách phân đoạn trên chúng ta có t > 3 [n/8]

Như vậy, đối với tập thuộc tính C không rỗng bất kỳ ta luôn chỉ ra một hệ Sperner K trên C có lực lượng tuyến tính với n, thì mọi bảng quyết định nhất quán DS = (U, C {d}, V, f) sao cho PRED (C) = K có lực lượng của U luôn

là hàm mũ theo lực lượng của C

Kết quả đã được chứng minh

Lời cảm ơn: Chúng tôi xin cảm ơn sự tài trợ của đề tài” Nghiên cứu thiết kế xây dựng bức tường lửa chuyên

dụng tích hợp kỹ thuật mật mã của ngành Cơ yếu” mã số 01/2018/KCM

TÀI LIỆU THAM KHẢO

[1] Demetrovics J., Thi V D., Quang H M., Anh N V “An Method to reduce the size of consistent decision tables” Acta Cybernetica V 23, pp 1039- 1054, 2018

[2] Demetrovics J., Thi V D., Duong T H., Giang N L “On the time complexity of the problem related to reduct of consistent decision tables” SERDICA J of computing Bugarian Academy of Sciences Vol 9, No 2, pp

101-110, 2015

[3] Demetrovics J and Thi V.D., “Some remarks on generating Armstrong and inferring functional dependencies relation”, Acta Cybernetica 12, pp 167-180, 1995

[4] Nguyen Long Giang, Vu Duc Thi, “Some Problems Concerning Condition Attributes and Reducts in Decision Tables”, Proceeding of the Fifth National Symposium Fundamental and Applied Information Technology Research (FAIR), Bien Hoa, Dong Nai, pp 142-152, 2011

[5] Nguyễn Long Giang, Vũ Đức Thi, “Thuật toán tìm tất cả các rút gọn trong bảng quyết định”, Tạp chí Tin học và Điều khiển

học, T.27, S.3, tr 199-205, 2011

[6] Pawlak Z., “Rough sets: Theoretical Aspects of Reasoning About Data”, Kluwer Academic Publishers, 1991 [7] Vũ Đức Thi, “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” Kỷ yếu hội nghị

quốc gia về nghiên cứu cơ bản và ứng dụng công nghệ thông tin lần thứ XI, Hà Nội, tr 150-157, 2018

[8] Vu Duc Thi, “Minimal keys and antikeys”, Acta Cybernetica 7, 4, pp 361-371, 1986

[9] Vũ Đức Thi, “Về một vấn đề tương đương liên quan đến tập rút gọn trong bảng quyết định” Kỷ yếu hội nghị nghiên cứu cơ bản và ứng dụng công nghệ thông tin - FAIR 12, Đại học Huế, trang 534- 538, 2019

ON THE PROBLEM RELATED TO BULLD THE CONSISTENT DECISION TABLES

Vu Duc Thi

ABTRACT In this paper, we show the complication of the problem buiiding the consistent decision table from the Sperner –

system is exponential

Keywords: reduct set, consistent decision table, Sperner- system