. Attribute reduction is one of the most important issues in rough set theory. There have been many scientific papers that suppose algorithms on attribute reduction. However, these algorithms are all heuristic which find the best attribute reduction based on a kind of heuristic information. In this paper, we present a new algorithm for finding all attribute reductions of a decision and we show that the time complexity of the algorithm is exponential in the number of attributes. We also show that this complexity is polynomial in many special cases. | T¤p ch½ Tin håc v i·u khiºn håc, , (2011), 199 205 THU T TO N T M T T C C C RÓT GÅN TRONG B NG QUY T ÀNH∗ NGUY N LONG GIANG, VÔ ÙC THI Vi»n Cæng ngh» thæng tin, Vi»n Khoa håc v Cæng ngh» Vi»t Nam Rót gån thuëc t½nh l b i to¡n quan trång trong lþ thuy¸t tªp thæ. Cho ¸n nay, nhi·u b i b¡o khoa håc v· c¡c thuªt to¡n rót gån thuëc t½nh ¢ ÷ñc · xu§t. Tuy nhi¶n, c¡c thuªt to¡n n y ·u t¼m mët tªp rót gån tèt nh§t theo mët ti¶u ch½ ¡nh gi¡ n o â. B i b¡o · xu§t mët thuªt to¡n mîi t¼m t§t c£ c¡c tªp rót gån trong b£ng quy¸t ành v ¡nh gi¡ thuªt to¡n n y câ ë phùc t¤p thíi gian l h m mô. Tuy vªy, trong nhi·u tr÷íng hñp cö thº, thuªt to¡n n y câ ë phùc t¤p l a thùc. Abstract. Attribute reduction is one of the most important issues in rough set theory. There have been many scientific papers that suppose algorithms on attribute reduction. However, these algorithms are all heuristic which find the best attribute reduction based on a kind of heuristic information. In this paper, we present a new algorithm for finding all attribute reductions of a decision and we show that the time complexity of the algorithm is exponential in the number of attributes. We also show that this complexity is polynomial in many special cases. Tóm t t. 1. MÐ U Rót gån thuëc t½nh trong b£ng quy¸t ành l qu¡ tr¼nh lo¤i bä c¡c thuëc t½nh d÷ thøa trong tªp thuëc t½nh i·u ki»n m khæng £nh h÷ðng ¸n vi»c ph¥n lîp c¡c èi t÷ñng. Düa v o tªp rót gån thu ÷ñc, vi»c sinh luªt v ph¥n lîp ¤t hi»u qu£ cao nh§t. Cho ¸n nay, câ r§t nhi·u cæng tr¼nh nghi¶n cùu v· c¡c thuªt to¡n rót gån thuëc t½nh trong lþ thuy¸t tªp thæ. Tuy nhi¶n, c¡c thuªt to¡n n y ·u t¼m ÷ñc mët tªp rót gån tèt nh§t theo mët ti¶u ch½ ¡nh gi¡ n o â vîi ë phùc t¤p a thùc (c¡c thuªt to¡n theo h÷îng ti¸p cªn heuristic) m ch÷a gi£i quy¸t b i to¡n t¼m t§t c£ c¡c tªp rót gån. Vîi b£ng quy¸t ành nh§t qu¡n DT = (U, C ∪ d, V, f ) trong lþ thuy¸t tªp thæ, theo ành ngh¾a cõa Pawlak n¸u B ⊆ C l mët rót gån cõa C
