Thuận toán nhanh tính toán lập thuộc tính lõi của bảng quyết định đưa vào vùng dương

Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 41 - 46<br /> <br /> 4 - 2009<br /> <br /> THUẬT TOÁN NHANH TÍNH TOÁN TẬP THUỘC TÍNH LÕI<br /> CỦA BẢNG QUYẾT ĐỊNH DỰA VÀO VÙNG DƢƠNG<br /> –<br /> )<br /> Phạm Quang Dũng (Trường Cao đẳng Giao thông vận tải)<br /> <br /> Tóm tắt<br /> Tính toán tập (thuộc tính) lõi của bảng quyết định là một nội dung nghiên cứu quan trọng của lý<br /> thuyết tập thô. Một số học giả đã xây dựng thuật toán tính toán tập lõi dựa vào vùng dương và sử dụng ma<br /> trận phân biệt. Độ phức tạp của thuật toán này là<br /> <br /> O C U<br /> <br /> 2<br /> <br /> . Bài báo này nhằm trình bày một thuật toán<br /> <br /> mới cho phép làm giảm độ phức tạp của thuật toán. Dựa vào vùng dương, chúng tôi định nghĩa ma trận phân<br /> biệt đơn giản hóa và tập lõi tương ứng. Chúng tôi chứng minh rằng tập lõi này tương đương với tập lõi xác<br /> định thông qua ma trận phân biệt nguyên thủy. Vì việc xác định phân hoạch U/C là chìa khóa để tính toán<br /> ma trận phân biệt đơn giản hóa, một thuật toán nhanh tính U/C được thiết kế sử dụng thuật sắp thứ tự theo<br /> cơ số. Độ phức tạp của thuật toán là O C U . Sử dụng thuật toán nhanh xác định U/C và ma trận phân<br /> biệt đơn giản hóa, một thuật toán mới xác định tập lõi dựa vào vùng dương được xây dựng. Độ phức tạp của<br /> thuật toán mới này được giảm thiểu và là<br /> <br /> max O C U p' os U / C , O C U<br /> <br /> .<br /> <br /> Từ khóa: Tập thô, Vùng dương, Ma trận phân biệt đơn giản hóa, Tập lõi, Độ phức tạp.<br /> <br /> Mở đầu<br /> Lý thuyết tập thô [1], do Pawlak đề xuất năm<br /> 1982, là một công cụ toán học mới để xử lý thông<br /> tin không chính xác, không chắc chắn hay tri thức<br /> mờ. Đến nay, lý thuyết tập thô đã và đang được<br /> ứng dụng rộng rãi trong nhiều lĩnh vực: trí tuệ<br /> nhân tạo, nhận dạng mẫu, khai phá tri thức và<br /> khám phá thông minh các luật quyết định.<br /> Tính toán tập (thuộc tính) lõi của bảng quyết<br /> định là một nội dung nghiên cứu quan trọng của lý<br /> thuyết tập thô. Cho đến nay, nhiều tác giả đã<br /> nghiên cứu đưa ra các thuật toán khác nhau tính<br /> toán tập lõi, trong đó có các thuật toán dựa vào<br /> vùng dương và sử dụng ma trận phân biệt. Trong<br /> [3], Hu đã đề xuất một thuật toán tính toán tập lõi<br /> dựa vào ma trận phân biệt với độ phức tạp là<br /> 2<br /> O C U .<br /> Trong bài này, để giảm thiểu độ phức tạp của<br /> thuật toán tính toán tập lõi, trước tiên chúng tôi<br /> đưa ra định nghĩa về ma trận phân biệt đơn giản<br /> hóa và định nghĩa tập lõi tương ứng. Chúng tôi<br /> chứng minh rằng tập lõi này tương đương với tập<br /> lõi xác định thông qua ma trận phân biệt nguyên<br /> thủy. Vì việc xác định phân hoạch U/C là bước<br /> chính trong quá trình tính toán ma trận phân biệt<br /> <br /> đơn giản hóa, một thuật toán nhanh tính U/C được<br /> thiết kế sử dụng thuật sắp thứ tự theo cơ số. Độ<br /> phức tạp của thuật toán là O C U . Sử dụng<br /> thuật toán nhanh xác định U/C, ma trận phân biệt<br /> đơn giản hóa, một thuật toán mới xác định tập lõi<br /> dựa vào vùng dương được xây dựng. Độ phức tạp<br /> của thuật toán mới này được giảm xuống là<br /> max O C U p' os U / C , O C U ,<br /> '<br /> trong đó U pos là tập các đại diện của các lớp<br /> tương đương sinh bởi phân hoạch U/C.<br /> I.Ma trận phân biệt đơn giản hóa dựa vào vùng<br /> dƣơng.<br /> Định nghĩa 2.1. [1]. Bảng quyết định là một bộ tứ<br /> S U , C , D,V , f , trong đó U<br /> x1 , x2 ,..., xn<br /> c1 , c2 ,..., cr là tập các<br /> là tập các đối tượng, C<br /> thuộc tính điều kiện, D là tập các thuộc tính quyết<br /> Va , trong đó Va là<br /> định, C D<br /> ; V<br /> a C D thuộc<br /> miền<br /> giá<br /> trị<br /> của<br /> tính<br /> a;<br /> f : U (C D) V là hàm thông tin cho biết<br /> giá trị của mỗi thuộc tính tại mỗi đối tượng, nghĩa<br /> là a C D, x U , f x, a Va .<br /> C D xác định<br /> Mỗi tập con thuộc tính P<br /> một quan hệ nhị phân, gọi là quan hệ không phân<br /> biệt IND P :<br /> IND P<br /> x, y U U | a P, f x, a f y, a (1)<br /> <br /> <br /> <br /> 1<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 41 - 46<br /> <br /> Dễ thấy, IND P là quan hệ tương đương. Ta<br /> <br /> 4 - 2009<br /> <br /> '<br /> U ' U p' os . Khi đó<br /> U p' os<br /> xi'1 , xi'2 ,..., xi't , U neg<br /> S ' U ' , C , D,V , f được gọi là bảng quyết định<br /> <br /> ký hiệu phân hoạch của U sinh bởi IND P là<br /> <br /> đơn<br /> <br /> U / IND P hoặc ngắn gọn hơn là U / P . Mỗi<br /> <br /> U /C<br /> x1' , x2' ,..., xm'<br /> c<br /> c<br /> '<br /> '<br /> U<br /> x1 , x2' ,..., xm' và<br /> <br /> tập con<br /> <br /> x<br /> <br /> y U| a<br /> <br /> p<br /> <br /> P, f x , a<br /> <br /> f y, a<br /> <br /> trong U / P là một lớp tương đương.<br /> Định nghĩa 2.2. [1]. Cho bảng quyết định<br /> S U , C , D,V , f , X U và tập con thuộc<br /> tính<br /> Tập<br /> R C D.<br /> R_ X<br /> Ri | Ri U / R, Ri X được gọi<br /> là xấp xỉ dưới của X theo R.<br /> <br /> <br /> <br /> Định nghĩa 2.3. [1]. Cho bảng quyết định<br /> S U , C , D, V , f<br /> Giả<br /> sử<br /> U / D D1 , D2 ,..., Dk ,<br /> U / C C1 , C2 ,..., Cm . Tập POSc D xác<br /> định theo công thức POSc D<br /> C _ Di<br /> <br /> <br /> <br /> Di U / D<br /> <br /> được gọi là vùng dương của D theo C. Nếu<br /> POSC D U thì S được gọi là bảng quyết định<br /> nhất quán, trường hợp ngược lại là không nhất quán.<br /> Định<br /> <br /> lý<br /> <br /> 2.1.<br /> <br /> Cho<br /> <br /> SPOSCU ,D<br /> C , D,V , f,<br /> X U /C<br /> <br /> X<br /> <br /> bảng<br /> <br /> quyết<br /> ta<br /> <br /> định<br /> có<br /> <br /> X /D 1<br /> <br /> .<br /> Chứng minh: Suy ra trực tiếp từ Định nghĩa 2.3.<br /> Định nghĩa 2.4. Cho bảng quyết định<br /> S U , C , D, V , f .<br /> Giả<br /> sử<br /> '<br /> '<br /> '<br /> POSC D<br /> xi1  xi2  ...  xit<br /> (theo<br /> c<br /> c'<br /> '<br /> ' c<br /> U ' và<br /> Định lý 2.1),trong đó xi1 , xi2 ,..., xit<br /> s 1, 2,..., t .<br /> Ký<br /> hiệu<br /> xi's / D 1<br /> <br /> giản<br /> <br /> hóa.<br /> c<br /> <br /> ,<br /> <br /> Định nghĩa 2.5. [4]. Cho bảng quyết định<br /> S U , C , D,V , f . Với thuộc tính c C , nếu<br /> POSC D POSC c D thì c được gọi là<br /> không cần thiết trong S, ngược lại c là cần thiết.<br /> Tập tất cả các thuộc tính cần thiết trong S được gọi<br /> là tập lõi, ký hiệu là Core(C) .<br /> Định nghĩa 2.6. [4]. Cho bảng quyết định<br /> S U , C , D,V , f và tập thuộc tính P C .<br /> Nếu mọi c P là cần thiết trong S thì P được<br /> gọi là độc lập.<br /> Định nghĩa 2.7. [4]. Cho bảng quyết định<br /> S U , C , D,V , f . Tập thuộc tính R C được<br /> gọi là một rút gọn của tập thuộc tính điều kiện C<br /> nếu R là độc lập và POS R ( D ) POSC ( D ) . Nói<br /> cách khác, R là rút gọn nếu nó là tập tối tiểu thỏa<br /> mãn POS R ( D ) POSC ( D ) .<br /> Định lý 2.2. [4]. Cho bảng quyết định<br /> S U , C , D,V , f . Gọi Red C là tập tất cả<br /> các rút gọn của C, ta có Core C<br /> B.<br /> B Red ( C )<br /> Định nghĩa 2.8. Cho bảng quyết định<br /> S U , C , D , V , f . S ' U ' , C , D, V , f<br /> là<br /> bảng quyết định đơn giản hóa từ S. Ma trận<br /> M '2 mi' j' với các phần tử mi j xác định bởi:<br /> (2)<br /> được gọi là ma trận phân biệt đơn giản hóa dựa<br /> vào vùng dương.<br /> <br /> <br /> <br /> C<br /> <br /> a/a<br /> mi' j '<br /> <br /> f x j , a nÕu vµ chØ nÕu x i hoÆc x j thuéc U 'pos ;<br /> <br /> C, f xi , a<br /> <br /> f xi ' , a<br /> <br /> f x j ' , a , f x i' , D<br /> <br /> f x j' , D<br /> <br /> nÕu xi' vµ x j ' thuéc U 'pos<br /> <br /> (2)<br /> <br /> trong tr­êng hîp ng­îc l¹i<br /> Định<br /> <br /> S<br /> <br /> nghĩa<br /> <br /> 2.9.<br /> <br /> U , C , D, V , f<br /> <br /> Cho bảng quyết định<br /> và ma trận phân biệt được<br /> <br /> đơn giản hóa dựa vào vùng dương M<br /> <br /> '<br /> 2<br /> <br /> mi' j'<br /> <br /> Khi đó, SDCore C được gọi là tập lõi của M 2' ,<br /> trong<br /> <br /> đó<br /> <br /> SDCore C<br /> <br /> '<br /> 2<br /> <br /> a | a C,<br /> <br /> mi' j'<br /> <br /> a , mi' j'<br /> <br /> M<br /> <br /> 2<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 41 - 46<br /> <br /> Định<br /> <br /> S<br /> <br /> lý<br /> <br /> 2.2.<br /> <br /> Cho<br /> U , C , D, V , f ,<br /> <br /> SDCore C<br /> <br /> bảng quyết<br /> ta<br /> <br /> định<br /> có:<br /> <br /> f xi' , a<br /> đó<br /> <br /> Core C .<br /> <br /> Chứng minh: Với bất kỳ a<br /> <br /> SDCore C tồn tại<br /> <br /> xi' và x 'j sao cho mi' j '<br /> <br /> a . Theo định nghĩa<br /> <br /> '<br /> 2.8, cả xi' và x 'j đều thuộc U pos , hoặc một trong<br /> <br /> x<br /> <br /> '<br /> j<br /> <br /> 4 - 2009<br /> <br /> f x 'j , a . Lại vì x 'j<br /> <br /> f xi' , b<br /> <br /> U<br /> <br /> '<br /> neg<br /> <br /> f x 'j , b<br /> <br /> x 'j<br /> <br /> C<br /> <br /> b C- a .<br /> <br /> , theo Định nghĩa 2.7, ta có mi' j '<br /> <br /> Còn nếu x 'j<br /> <br /> '<br /> U pos<br /> , thì vì f xi' , D<br /> <br /> theo Định nghĩa 2.7, ta có mi' j '<br /> <br /> a<br /> <br /> , do<br /> Nếu<br /> <br /> a .<br /> <br /> f x 'j , D ,<br /> <br /> a . Do đó,<br /> <br /> '<br /> các phần tử này thuộc U pos còn phần kia thuộc<br /> <br /> a SDCore C . Vì a được lựa chọn tùy ý, suy<br /> <br /> '<br /> '<br /> U neg<br /> . Nếu cả xi' và x 'j đều thuộc U pos thì<br /> <br /> ra SDCore C<br /> <br /> xi'<br /> <br />  x 'j<br /> <br /> C<br /> <br /> xi'<br /> <br /> C<br /> <br /> C<br /> <br /> xi'<br /> <br /> ( do<br /> <br /> a<br /> <br /> x 'j<br /> <br /> và<br /> <br /> C<br /> <br /> C<br /> <br /> là không thể phân biệt được trừ phi sử dụng thuộc<br /> f x 'j , D , do đó<br /> tính a.), trong khi f xi' , D<br /> <br /> xi'<br /> xi'<br /> <br /> C<br /> <br />  xi'<br /> <br /> C<br /> <br />  xi'<br /> <br /> C<br /> <br /> POSC<br /> <br /> D . Mặt khác do<br /> <br /> a<br /> <br /> POSC D ,<br /> <br /> C<br /> <br /> ta<br /> <br /> có<br /> <br /> POSC D , nên theo Bổ đề 2.1,<br /> <br /> D<br /> <br /> a<br /> <br /> POSC<br /> <br /> a Core C . Nếu một trong xi' và x 'j thuộc<br /> '<br /> U p' os , thì phần tử còn lại sẽ thuộc U neg<br /> . Giả sử<br /> '<br /> xi' U pos<br /> <br /> xi'<br /> <br /> xi'<br /> <br /> C<br /> <br />  x 'j<br /> <br /> C<br /> <br /> '<br /> x 'j U neg<br /> ,<br /> <br /> và<br /> <br /> xi'<br /> <br /> C<br /> <br />  xi'<br /> <br /> C<br /> <br /> a<br /> <br /> POSC<br /> <br /> C<br /> <br /> D ,<br /> <br /> xi'<br /> <br /> C<br /> <br /> POSC<br /> <br /> '<br /> i<br /> <br /> C<br /> <br /> POSC D nên POSC<br /> <br /> x<br /> <br /> a<br /> <br /> D .<br /> <br /> Mặt<br /> <br /> Theo Bổ đề 2.1, ta có a<br /> <br /> POSC D<br /> x<br /> <br /> '<br /> i<br /> <br /> U<br /> <br /> '<br /> pos<br /> <br /> nên<br /> <br /> do<br /> <br /> đó<br /> <br /> khác,<br /> <br /> vì<br /> <br /> POSC D .<br /> <br /> a<br /> <br /> Core C . Vì a được<br /> <br /> lựa chọn bất kỳ, ta có SDCore C<br /> Với bất kỳ a<br /> <br /> có<br /> <br /> '<br /> x 'j U neg<br /> <br /> . Vì<br /> a<br /> <br /> ta<br /> <br /> Core C .<br /> <br /> Core C , theo Bổ đề 2.1, đều có<br /> <br /> POSC<br /> <br /> D . Do vậy, tồn tại<br /> <br /> a<br /> <br /> xi'<br /> <br /> sao cho<br /> <br /> C<br /> <br /> a<br /> <br /> POSC<br /> <br /> a<br /> <br /> D .<br /> <br /> Suy ra, sẽ có ít nhất một đối tượng x 'i thỏa mãn<br /> <br /> xi'<br /> <br /> xi'<br /> <br /> f xi' , D<br /> <br /> C<br /> <br /> a<br /> <br /> x 'j<br /> <br /> xi'<br /> <br /> C<br /> <br /> , x 'j<br /> <br /> U'<br /> <br /> x 'j<br /> <br /> xi'<br /> <br /> f x 'j , D . Vì<br /> <br /> và<br /> C<br /> <br /> , ta có<br /> <br /> Core C .<br /> <br /> II.Thuật toán nhanh tính bảng quyết định đơn<br /> giản hóa.<br /> Chìa khóa để lập được bảng quyết định đơn giản<br /> hóa là việc xác định phân hoạch U/C. Độ phức tạp<br /> của thuật toán thông thường xác định U/C là<br /> <br /> O C U<br /> <br /> 2<br /> <br /> . Để làm giảm thiểu hơn nữa độ phức<br /> <br /> tạp, trong bài báo này, chúng tôi sử dụng ý tưởng<br /> của thuật sắp xếp theo cơ số. Bằng cách này, độ<br /> phức tạp của thuật toán xác định U/C được giảm<br /> xuống là O C U .<br /> 1. Thuật toán 1: Tính bảng quyết định đơn giản<br /> hóa<br /> Đầu vào: Bảng quyết định S U , C , D,V , f ,<br /> <br /> U<br /> <br /> x1 , x2 ,..., xn , C<br /> <br /> c1 , c2 ,..., cr<br /> <br /> '<br /> '<br /> Đầu ra: U pos , U neg .<br /> <br /> Bước 1: Tìm giá trị cực đại M i và giá trị cực tiểu<br /> <br /> mi của hàm f x j , ci<br /> <br /> j 1, 2,..., n<br /> <br /> với mỗi<br /> <br /> ci i 1, 2,..., r .<br /> Bước 2: Lưu lần lượt các đối tượng x1 , x2 ,..., xn<br /> theo thứ tự tĩnh ban đầu và tạo con trỏ đầu bảng<br /> trỏ đến x1 .Bước 3: for (i =1, i < r+1, i ++)3.1.<br /> “Sắp xếp” lần thứ i: xây dựng M i<br /> <br /> mi 1 hàng<br /> <br /> đợi<br /> <br /> rỗng.<br /> <br /> và<br /> <br /> k<br /> <br /> 0,1,..., M i<br /> <br /> Đặt<br /> <br /> frontk<br /> <br /> end k<br /> <br /> mi tương ứng là con trỏ đầu và<br /> <br /> con trỏ cuối của hàng đợi thứ k. Theo thứ tự, phân<br /> bổ mỗi đối tượng x U của dãy tĩnh ban đầu vào<br /> hàng đợi thứ f x, ci mi .<br /> 2. “Gom lớp” lần thứ i: Cho con trỏ đầu trỏ đến<br /> con trỏ đầu của hàng đợi khác rỗng đầu tiên, chỉnh<br /> <br /> 3<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 41 - 46<br /> <br /> sửa lại con trỏ cuối của mỗi hàng đợi khác rỗng<br /> sao cho nó trỏ đến đối tượng đầu tiên của hàng đợi<br /> khác rỗng tiếp theo.<br /> Bước 4: Giả sử dãy thu được sau bước 3 là<br /> x1' , x2' ,..., xn' ;<br /> <br /> for j<br /> <br /> 2, j<br /> <br /> if (flag > 1) break;<br /> }<br /> if (flag = = 1)<br /> core(C) = core(C)  B ;<br /> <br /> f x , ci , ci<br /> <br /> i t s x1,'j i;<br /> C i 1, 2,..., r for iBt 1, B<br /> j<br /> <br /> for<br /> <br /> else t=t+1;Bt<br /> '<br /> Bước 5: U pos<br /> <br /> x<br /> <br /> '<br /> j<br /> <br /> '<br /> ; U neg<br /> <br /> { B<br /> <br /> ;<br /> <br /> f ( x, D)<br /> <br /> k 1, k<br /> <br /> x, yi<br /> <br /> B lấy<br /> <br /> {B<br /> <br /> '<br /> đối tượng đầu tiên của Bi nhập vào U pos ;<br /> <br /> else<br /> vào U<br /> <br /> '<br /> neg<br /> <br /> lấy đối tượng đầu tiên của Bi nhập<br /> <br /> ;<br /> <br /> x1 , x2 ,..., xn , C<br /> <br /> c1 , c2 ,..., cr<br /> <br /> Đầu ra: Core(C)<br /> Sử dụng Thuật toán 1 tính bảng quyết định đơn<br /> giản hóa, thu được:<br /> <br /> U<br /> <br /> y1 , y2 ,..., ys ;U<br /> <br /> Cho core(C)<br /> for<br /> <br /> f z j , ck<br /> <br /> B  ck ; flag<br /> <br /> }<br /> <br /> core(C) core(C)  B;<br /> <br /> III.Thuật toán Nhanh tính toán tập lõi<br /> Theo Định nghĩa 2.7., Định nghĩa 2.8., Định lý<br /> 2.2. và Thuật toán 1, ta có thể thiết kế một thuật<br /> toán sau đây cho việc tính toán tập lõi dựa vào<br /> vùng dương.<br /> 1.Thuật toán 2: Thuật toán cho việc tính toán<br /> tập lõi<br /> Đầu vào: Bảng quyết định S U , C , D,V , f ,<br /> <br /> '<br /> pos<br /> <br /> f yi , ck<br /> <br /> if (flag >1) break ;<br /> }<br /> if ( flag==1)<br /> <br /> Độ phức tạp của thuật toán 1 là: O C U .<br /> <br /> U<br /> <br /> r 1, k<br /> <br /> { if<br /> <br /> f ( y, D)<br /> <br /> t 1, j<br /> <br /> ; flag 0;<br /> <br /> for<br /> <br /> ;<br /> <br /> i 1, j<br /> <br /> for (i=1, i < t+1, i++)<br /> if<br /> <br /> ; }<br /> <br /> }<br /> '<br /> j -1<br /> <br /> if f x , ci<br /> <br /> f y j , ck<br /> <br /> B  ck ; flag<br /> <br /> { B<br /> <br /> n 1, j<br /> <br /> '<br /> j<br /> <br /> f yi , ck<br /> <br /> { if<br /> <br /> x1' ;<br /> <br /> t 1; Bt<br /> <br /> 4 - 2009<br /> <br /> i 1, i<br /> <br /> '<br /> neg<br /> <br /> z1 , z2 ,..., zs ;<br /> <br /> ;<br /> s, i<br /> <br /> for j<br /> if<br /> { B<br /> for k<br /> <br /> 1, j<br /> <br /> s 1, j<br /> <br /> f yi , D<br /> <br /> f yj, D<br /> <br /> ; flag 0;<br /> 1, k<br /> <br /> r 1, k<br /> <br /> }<br /> Độ phức tạp của thuật toán 2 là: O U .<br /> IV.Ví dụ<br /> Trong mục này, ta minh họa tính hiệu quả của<br /> thuật toán mới thông qua một ví dụ. Xét bảng<br /> quyết định sau đây (Bảng 1):<br /> a<br /> <br /> b<br /> <br /> c<br /> <br /> d<br /> <br /> D<br /> <br /> X1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 0<br /> <br /> X2<br /> <br /> 2<br /> <br /> 2<br /> <br /> 2<br /> <br /> 1<br /> <br /> 1<br /> <br /> X3<br /> <br /> 2<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 0<br /> <br /> X4<br /> <br /> 2<br /> <br /> 3<br /> <br /> 2<br /> <br /> 3<br /> <br /> 0<br /> <br /> X5<br /> <br /> 2<br /> <br /> 2<br /> <br /> 2<br /> <br /> 1<br /> <br /> 1<br /> <br /> X6<br /> <br /> 3<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 0<br /> <br /> X7<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 2<br /> <br /> 2<br /> <br /> X8<br /> <br /> 4<br /> <br /> 3<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> X9<br /> <br /> 3<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 1<br /> <br /> X10<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 2<br /> <br /> 2<br /> <br /> X11<br /> <br /> 3<br /> <br /> 1<br /> <br /> 2<br /> <br /> 1<br /> <br /> 1<br /> <br /> X12<br /> <br /> 4<br /> <br /> 3<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> X13<br /> <br /> 4<br /> <br /> 3<br /> <br /> 4<br /> <br /> 2<br /> <br /> 1<br /> <br /> X14<br /> <br /> 1<br /> <br /> 2<br /> <br /> 3<br /> <br /> 2<br /> <br /> 3<br /> <br /> X15<br /> <br /> 4<br /> <br /> 3<br /> <br /> 4<br /> <br /> 2<br /> <br /> 2<br /> <br /> 4<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 52(4): 41 - 46<br /> <br /> 4 - 2009<br /> <br /> Bảng 1: Bảng quyết định 1<br /> Với 15 đối tượng của U, phân hoạch U/{a,b,c,d} được tính toán theo thuật toán 1.<br /> Tiến trình xử lý như sau:<br /> 1. Đặt c1 a, c2 b, c3 c, c4 d . Sau bước 1 của thuật toán 1 ta có:<br /> <br /> M1<br /> <br /> 4, m1 1; M 2<br /> <br /> 3, m2<br /> <br /> 1; M 3<br /> <br /> 4, m3 1; M 4<br /> <br /> 3, m4<br /> <br /> 1;<br /> <br /> 2. Sau theo bước 2 của Thuật Toán 1( Tính toán bảng quyết định đơn giản hoá) thu được:<br /> <br /> X1<br /> <br /> X2<br /> <br /> X3<br /> <br /> X4<br /> <br /> X5<br /> <br /> X6<br /> <br /> X7<br /> <br /> X8<br /> <br /> X9<br /> <br /> X 10<br /> <br /> X 11 ;<br /> <br /> X 12<br /> <br /> X 13<br /> <br /> X 14<br /> <br /> X 15 ;<br /> <br /> 3. Kết quả “sắp xếp” lần thứ 1 là:<br /> <br /> front 0<br /> <br /> X7<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> end 0 ; front 1<br /> <br /> X1<br /> <br /> X2<br /> <br /> X3<br /> <br /> front 2<br /> <br /> X6<br /> <br /> X9<br /> <br /> X 11<br /> <br /> end 2 ; front 3<br /> <br /> X8<br /> <br /> X 12<br /> <br /> X 13<br /> <br /> X4<br /> <br /> X5<br /> <br /> X 14<br /> <br /> end 1 ;<br /> <br /> end 3 ;<br /> <br /> 4. Kết<br /> <br /> quả “gom lớp” lần thứ 1 là:<br /> <br /> X7<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> X1<br /> <br /> X2<br /> <br /> X 3;<br /> <br /> X4<br /> <br /> X5<br /> <br /> X6<br /> <br /> X 11<br /> <br /> end 0 ; front 1<br /> <br /> X9<br /> <br /> X 11<br /> <br /> X8;<br /> <br /> X 12<br /> <br /> X 13<br /> <br /> X 15 ;<br /> <br /> 5. Kết quả “sắp xếp” lần thứ 2 là:<br /> <br /> front 0<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X9<br /> <br /> front 2<br /> <br /> X4<br /> <br /> X8<br /> <br /> X 12<br /> <br /> X 13<br /> <br /> X 15<br /> <br /> X7<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> X2<br /> <br /> X5<br /> <br /> end 1 ;<br /> <br /> end 2 ;<br /> <br /> 6. Kết quả “gom lớp” lần thứ 2 là:<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X9<br /> <br /> X 11<br /> <br /> X7;<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> X2<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X5<br /> <br /> X4<br /> <br /> X8;<br /> <br /> X 12<br /> <br /> X 13<br /> <br /> X 15 ;<br /> <br /> 7. Kết quả “sắp xếp” lần thứ 3 là:<br /> <br /> front 0<br /> <br /> X8<br /> <br /> X 12<br /> <br /> end 0 ; front 1<br /> <br /> front 2<br /> <br /> X7<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> end 2 ; front 3<br /> <br /> X 13<br /> <br /> X9<br /> <br /> X 15<br /> <br /> X 11<br /> <br /> X2<br /> <br /> X5<br /> <br /> X4<br /> <br /> end 1 ;<br /> <br /> end 3 ;<br /> <br /> 8. Kết quả “gom lớp” lần thứ 3 là:<br /> <br /> X8<br /> <br /> X 12<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X9;<br /> <br /> X 11<br /> <br /> X2<br /> <br /> X5<br /> <br /> X4<br /> <br /> X7<br /> <br /> X 10 ;<br /> <br /> X 14<br /> <br /> X 13<br /> <br /> X 15 ;<br /> <br /> 9. Kết quả “sắp xếp” lần thứ 4 là:<br /> <br /> front 0<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X9<br /> <br /> front 1<br /> <br /> X8<br /> <br /> X 12<br /> <br /> X7<br /> <br /> X 10<br /> <br /> X 11<br /> <br /> X2<br /> <br /> X 14<br /> <br /> X 13<br /> <br /> X5<br /> <br /> X8<br /> <br /> X5<br /> <br /> end 0 ;<br /> <br /> X 15<br /> <br /> end 1 ; front 2<br /> <br /> X4<br /> <br /> end 2 ;<br /> <br /> 10. Kết quả “gom lớp” lần thứ 4 là:<br /> <br /> X1<br /> <br /> X3<br /> <br /> X6<br /> <br /> X9<br /> <br /> X 11 ;<br /> <br /> X2<br /> <br /> X 12<br /> <br /> X7;<br /> <br /> X 10<br /> <br /> X 14<br /> <br /> X 13<br /> <br /> X 15<br /> <br /> X 4;<br /> <br /> 11. Kết quả thu được sau bước 4 của thuật toán 1 là:<br /> <br /> X 1 , X 3 , X 6 , X 9 , X 11 , X 2 , X 5 , X 8 , X 12 , X 7 , X 10 , X 14 , X 13 , X 15 , X 4 ;<br /> '<br /> <br /> 12. Kết quả sau bước 5 của thuật toán 1 là: U pos<br /> <br /> '<br /> X 1 , X 2 , X 8 , X 4 ;U neg<br /> <br /> 13. Kết quả sau bước 2 của thuật toán 2 là: core C<br /> <br /> b ;<br /> <br /> 14. Kết quả sau bước 3 của thuật toán 2 là: core C<br /> <br /> b, a, c ;<br /> <br /> X 6 , X 7 , X 13 ;<br /> <br /> V.Kết luận<br /> <br /> 5<br /> <br />