Luận án tiến sỹ toán học " Xây dựng hệ tính toán thông minh xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động "

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

271
lượt xem 80
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo luận văn - đề án 'luận án tiến sỹ toán học " xây dựng hệ tính toán thông minh xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động "', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sỹ toán học " Xây dựng hệ tính toán thông minh xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động "

BAI HQC QUOC GIA THANH PHO HO CHI MINH. TRUdNG BAI HQC KHOA HQC TV NHIEN -------------------- BO VAN NHcJN XA Y D{jNG HI:: TINH TOAN THONG MINH XAY DVNG & PHAT TRlftN cAe M6 HINH BlftU DlitN TRI TIHJ'CClIO CAC Ht GIAI TOAN TV DONG Chuyen nganh: Dam baa toao hQc cho may Hnh Va cac h~ tho'ng Hnh toaD Mii so': 1.01.10 TOM TAT LUh-N AN TIEN SI TO AN HQC Thanh pho' H6 Chi Minh - 2001
PHAN Md DAD Tri tu~ Nhan t
Tren cac ma hlnh bi6u di€n tri thUc nay, mQt s6 thu~t giai duQc xay dt!ng d6 co th6 cai o~t cac thu t\1cgiai bai loan dt!a tren cac kie'n thlic trong co so tri thlic. Cac ma hlnh tren se ouQCsa d\1ng trong thie't ke' va cai o~t mQt s6 chuang trlnh giai tt! dQng mQt s6 lOp bai loan vS cac tam giac, cac tli giac, cac bai loan hlnh hQc ph~ng, cac bai loan hlnh hQCgiai tich va mQt s6 bai loan tren cac phan ling hoa hQc. Lu~n an g6m 5"chuang. Chuang lla phfin t6ng quail v~ bi6u di€n tri thlic va h~ giai loan dt!a tren tri thlic. Chuang 2 d~ xua't mQt ma hlnh bi6u di€n tri thlic, duQc gQi la m;;tng suy di€n-tinh loan. Chuang 3 lieu leD mOt ma hlnh cho mOt lOp tri thUc, duQc gQi la ma hlnh tri thlic cac d6i tuQng t1nh' loan (C~Objcct). Chuang 4 trlnh bay mOt ma hlnh co th6 dung bi6u di€n cho d;;tng bai loan t6ng quat tren ma hlnh tri thlic vS cac C-Object: ma hlnh m;;tng cac C-Object. Chuang 5 trlnh bay cac ling d\1l1gva L " $C\IJ'heb la phan ket lu~n. Chu'o'ng 1. BIJ'fUDIEN TRI TRUC vA Rt GIAI TOAN D{jA TREN TRI TRUC Chuang n~y trlnh bay t6ng quan v~ cac phuong phap bi6u di€n tri thUc va cac cang trlnh lieu bi6u vS cac chuang trlnh giai cac bai loan dt!a tren tri thUc. Cac ke't qua nghien cliu oa co n~y cling ouQc nh?n d~nh va oanh gia. 1.1 Cae va'n d~ cd ban trong thie't ke' m{)t h~ giai b~li toan dQ.'a tren tri thue 1.1.1 Ca'u true eua m{)t h~ giai b~li to:1n dQ.'atren tri thue Ca'u truc co ban cua M th6ng bao g6m cac thanh ph~n ouQc chi ra tren blah 1.1 bell dUai. 2
Giao N gu'~l 511'dllng di
Phuong phap h
t6t d~ co th~ xiiy dl!ng m(>tco s0 tri thuG va m(>tligon ngG' khai bao bai loan mOt cach tl! nhien. 1.2.4 Phu'dng phIlp Wu Phuong phap Wu la mN phuong phap chung minh dinh 1:9 hlnh hQc theo cach liSp c~n d~i so'. Phuong phap nffy cho ta mOt bi~u dii;n kha dyp v~ m~t 1:9thuySt loan hQC.Tuy nhien no cling co nhi~u h~n chS nhu cac phuong pha p "di~n tich" va ':f'ull angle" trong nhu du xiiy dl!ng mOt M giiii bai loan dl!a tren tri thuG. 1.2.5 Cac phtidng philp chung minh hinh hQc biing may Hnh T(ing kG! cae nghicn Call VOcl~((ng l1linh t\( dOng cae bid loan hlnh hQC, S.C. Chou va cac d6ng lac giii oil li suy dii;n va cac M th6ng. thanh pMn khac cila 1.2.6 MQt s(f nghien CUllxfiy d1;ingh~ ghii toan hinh hQc M(>t so' nghien CUllxiiy dl!ng h~ giiii loan hlnh hQc GOng du
Chuang 2. M~NG SUY DIEN - TINH TOA.N 2.1 D§n nh1j.p: GiOi thi~u v~ ma hlnh va each tie'p c~n Kay d\!ng ma hlnh. 2.2 M~ng suy di~n va cae va-n M cd ban 2.2.1 Quan h~ va lu1j.tsuy di~n Cho M = {XI,X2,...,Xm} mQt t~p hcjp cae bie'n c6 th~ la'y gia la tri trong cae mi6n xae dint tuong ung D],D2,...,Dm. MQt quaD h~ R(x],x2,"',Xm) xac dinh mOt (hay mOt s6) anh X~lfR.u,v:Du---*Dv hay v~n t~t la f: u ---*v, trong d6 u ~ x, v~ x; Du va Dv la tkh eua cae mi6n xae dint tuong ung eua cae bie'n trong u va trong v. Quan h~ nhu the' ducjc gQi la quan h~ suy ddn. MQt quaD M ducjc n6i Hi deli xllng e6 hX2,...,Xn} t~p hcjp cae thuQe tinh hay cae ye'u to' la la'y gia trj trong cae mi6n xae dinh nao d6. (2) F= {f],f2,...,fm} la t~p hQp cae lu~t suy di€\n c6 d~ng f:u(f)---*v(f), trong d6 u(f) va v(f) la cae t~p hQp con khae = 0. r6ng cua M sao eho u(f) n v(f) D6i vdi m6i f E F, ta kg hi~u M(f) la t~p cae bie'n e6 lien M = u(f) trong quaD h~ f, nghla la M(f) u v(f). 2.2.3 Cae va-n d~ eo' ban tren m~ng suy di~n 6
Tren m(;lngsuy di6n (M,F) gici sa c6 mQt t~p bie'n A ~ M da du
M~nh d~ 2.3: neu 1en di~u ki~n dn va du d~ mQt day quail M ap dl)ng du'Qctren mQt t~p hQp A ~ M. Dinh Iv 2.2 Tren mQt m~ng suy di~n (M,F), gici Stl A, B 1a hai t~p con cua M. Ta co cac di~u sau day 1a tu'dng du'dng: A. (1) B ~ (2) Co mQt day D = {fl, f2, ..., fk} ~ F thoa cac di~u ki~n D ap dl)ng du'Qctren A va D(A);2 B. Thu~H toaD 2.1: TIm bao d6ng cua t~p A ~ M. 2.3.2 LOi giai cua b8i toaD M~nh d~ 2.4: Day quail M D 1iimQt Wi gicii cUa bai loan A~ B khi va chi khi D ap d\mg OltQCtren A va D(A) ;;2B. Thu~it toaD 2.2 TIm mQt Wi gicii cho b~liloan A ~ B. . Dinh I:V chung minh cd sa loan hQCch6 thu~t loan 2.3. 2.3 Thu~it toaD 2.3 TIm mQt Wi gicii t6t tu mQt loi gicii da bi~t. 2.3.3 Dinh Iy v~ st!-phan tich qua trinh gi:H Dinh Iv 2.4 Cho {fl, f2, ..., fm}1a mQt Wi gicii t6t cho biii loan A ~ B tren mQt m~ng suy di~n (M, F). f)~t: Ao = A, Ai = {fl, f2, ..., fi}(A), voi mQi i=I,...,m. Khi d6 c6 mQt day {Bo,B\, ..., Bm-I,Bm}, thOa cac di~u ki~n: (1) = B, Bi ~ Ai , voi mQi i=O,I,...,m, vii (3) Voi mQi Bm (2) ! i=I,...,m, {fi} 1a Wi gicii cua bai loan Bi-I ~ Bi nhu'ng khOng phcii 1a Wi gicii cua bai loan G ~ Bi , trong d6 G 1iimQt t~p con y cua tMt s1/ tily Bi-I. 2.4 M~ng soy di~n co trQng s6 va lOigiai t6i u'u 2.4.1 Dinh nghia va ky hi~u Dinh nghia 2.5: MQt mg.ngsuy ddn co trQngsr/, vie't t~t bdi MSDT, 1iimQtmo hlnh (A, D, w) bao g6m: (1) mQtt~p hQpcac thuQctinh A, (2) mQtt~p hQpcac 1u~tsuy di~n D, vii
(3) mQt ham trQng s6 du'dng w: D ~ R+ M6i lu~t dfin r thuQc D co d~ng r: U=:>v, vdi U va vIa cac t~p hQp con khac r6ng va roi nhau cua A. Bioh oghia 2.6: Neu len khai ni~m v~ Wi giiii t6i u'u d1!a tren cac trQng s6. 2.4.2 L G. (2) D(>diU cua m(>l 1(>lrlnh S lrcn
Thu~H tmin 2.6: TIm m(}t t~p h
Thui,H toaD 2.8: Cho m
M suy di~n do tIm nhung s\1'lien giua cac ySu t5 nao d6 ma ta quan Him se cho ta mQt phuong phap d€ t\1'dQng tIm ra them nhung lu~t suy di~n va nhung cong thuc tinh loan lien quan dSn cac ySu t5. E>i~un~y c6 y nghia nhu mOt ky thu~t kMm pM tri thuc. Chu'dng 3. MO HINH TRI THUC cAc DOl Tu'
3.2 M6 hlnh tri thuc cae d6i tu'qng tinh toan Ma hlnh tri thue cae C-objeet co th~ dung bi~u dien eho mQt d~ng co sO tri thue bao g6m cae khai ni~m v~ cae d6i tu'
4. Mot tap hop Ops d.c loan tu. Cac loan tu cho ta mQt s6 phep loan tren cac bie'n th1.fccling nhu tren cac d6i tuQng. 5. Mot tap hop Rules g6m cac luat duoc phan lOp. M6i lu~t cho ta mQt qui t~c suy lu~n M di de'n cac s1.fkil$n moi tu cac s1.f kil$n naG do, va v~ m~t ca'u truc m6i lu~t r co th6 duQc mo hInh duoi d~ng: r: {skI, skz, ..., skn} => { skI, skz, ..., skm } Dinh nghia 3.2: (Cac lo~i s1.f kil$n) (1) S1.fki~n thong tin v~ lo~i cua mQt d6i tU
[1] T~p tin "Objeets.txt" lu'u tru cae dinh danh eho cae lo
. giup de dang thiet ke cae m6dun Cau truc tl1CJngminh . truy c~p co so tri thuG. Ti$n IQicho thiet ke cac m6 dun gdli toan tlj dQng. .. Thich hQp cho vi$c djnh ra mQt ng6n ngu khai baa bai toan va di;lcta bai toan mQtcach tlj nhien. 3.4 GhH toan C-object Cae va'n dS eelban du KL. . Va'n d~ 3: Thl}c hi~n tinh loan cac thuQe tinh trong t~p h bai KL giai du
Thu(H giai 3.2: TIm mQt Wi giai cho bfd tocln GT ~ KL. . Giai doan 1: TIm mQt loi giai (neu c6) cho bai loan. . Giai doan 2: Tht/c hi~n lo~i bo cac bo'oc do' thlta trong Wi ghli (nSu c6) Om do'Qc d giai do~n 1 bhg cach troy ngo'Qc . theo Wi giai, ung voi m6i bo'oc giai ma st/ ki~n moi do'Qc sinh ra nho'ng kh6ng dn thiet thllo~i boo Vi du 3.3: Giai bai toclnGT ~ KL tren d6i to'Qng"TAM_GIAC" voi GT = {a, b=5, GocA = m*(b+c), GocA = 2*GocB, a"2=b"2+c"2}, KL = { GocB, GocC }. Thu~t giai 3.2 se cho ta m9t Wi giai nho'sau: 1. Soy ra {GaeE '= ~ GaeA } tlt {GocA = 2 GocR} 2 = ';2 + C2} 2. Soy ra {GocA '= ~ 1t} tlt {a2 3. Soy ra {GoeB '= ~ 1t} tlt {GoeE '= ~ GoeA ,GoeA = ~ 1t} , 4. Soy ra {GocB} lU' {CoeE = ~ 1t } 1 1 1 5. Soy ra {CaeC == 41t} tlt {CacA =2:1t, GacB=~rt} L1t } 6. Soy ra {GoeC } tlt {GoeC '= 4 3.4.3 Giai quye't vfi'n d~ cd ban 3 Thu~t giai 3.3: cho ta m9t thii tt,1ctht/c hi~n tinh loan cac thu9c Hnh trong t~p hQp KL tlt cac st/ ki~n trong GT trong tru'ong hQp bai loan GT~KL giai do'Qc. Vi du 3.5: Tren m9t d6i to'Qng "TAM_GIAC", cho bai loan {o, b = 1, GacA = ~ 1t} ~ {R, S, c} . Thu~t giiii 3.3 tren se OmWigiai r6i tht/c hi~n tinh loan va cho ta ket qua tinh loan nho'san: 17
{c:=~, S:= f~-~-~~1~7~2:=1=)(~=;-=J~2:i)(~-=;~7~2':i)(~~.1-=J~2':1)-, ~ 1 R:=-a} 2 3.4.4 Giai quye't va'n d~ cd ban 4 Thu;\it giai 3.4: Khcio sat tinh xac dinh cua mQt d6i tu'Qngtu mQt t~p s1,1' ki~n GT. Chu'o'ng 41 M~NG cAc DOl TU
3. TIm mQt Wi giai t6t nha't (hay Wi giai t6i u'u) eua b~d roan tinh roan B tu gia thie'tA? . B~d roan xae djnh B tU A tren m~ng (0, M, F) dU