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
Thanh pho' H6 Chi Minh - 2001
TOM TAT LUh-N AN TIEN SI TO AN HQC
PHAN Md DAD
Tri tu~ Nhan t<;lOla mQt lInh vlfe eua khoa hge may tinh
nh~m nghien CUllphat tri6n cae h~ th6ng ngay cang thong mint hon h6 trel tcJt hon cho h()~\t dOng xlt ly thong tin va XL(ly tri
thue, tint loan va diSH khi6n, v.v... Trong qua trlnh philo tich va
thiSt kS cae M th6ng Tri tu~ Nhan t<;lO,d~e bi~t la cae M
ehuyen gia va cae h~ giai loan thong minh, nguoi ta ph~Uquan tam uSn 2 va'n dS co ban nha't la:
(I) Bi6u diGn tri thae, va
(2) Phlwng phap va ky thuOt t1mk16m hay SHYdiOn,
Ngl1i<3nel(U vi\ pl1~llridll de l1\t\1111111bidu di~n lri lhac vi\ suy
di€:n tlf dQng tren tri thue gilt mOt dia vi ra't quan tr9ng trang khoa 11(.)Cmay linh cOng nlu( lrong 'I'd lll\; Nhan l<.lo.
M~le lieu ct'1adS tai Iii xfiy d\1'ng,phat tri6n mOt sO'mo hint
bi6u di~n tri thue va cae thu~ t giai d6 giai tlf dOng cae d<;lngbEd
loan khae nhau dlfa tren tri thue.
Cach ti6p c~n duQc slt d\1ng Iii kC't hQp cae phuong phap
bi6u di~n tri thUe da e6 vdi nhung phat lri6n nha't dint d6 t<;lOra
mQt sO'mo hint bi6u di€:n tri thue mdi th6 hi~n duQe nhiSu d<;lng
kiC'n thue da d<;lngbon. Tli d6 cae ma hint nay e6 th6 duQe slt
d\1ng nhu la co s0 va Iii eong e\1eho vi~e thiSt kS co sa tri thUe,
bQ pMn SHYlu~n giai loan cling nhu thiSt kS ph§n giao di~n eua
chuang trlnh.
Lu~n an da xfiy d~tng cae mo hinh bi6u diGn tri thae sau:
1. M6 hint m<;lngSHYdi0n va tinh loan.
/'c
2. Mo hint mOt d6i tuQng tinh loan (C-Objeet).
3. Mo hint tri thue vS cae C-Objeet, vii ma hint ma
C-Objeet.
rf:JH. ~ H.Tt/ N~iE iJ THU V;rN .,
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
thlic cac d6i gQi la ma hlnh tri 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
L
"
$C\IJ'heb la phan ket
lu~n.
hlnh m;;tng cac C-Object. Chuang 5 trlnh bay cac ling d\1l1gva
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.'atren 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<$n
moh 1.1 Cffu true eua mQt h~ giiii loan thong minh
C6 th~ n6i rAng trai tim eua h~ th6ng la phh co sd tri thue,
loan.
trong d6 ehua cae kie'n thue dn thie't eho vi~e giiii cae bai loan.
BQ soy di1;n (con gQi 1£1mo-tel soy di1;n) se ap d\;lng kie'n thUc trong co sd tri thue M tlm Wi giiii eho bai 1.1.2 Va-o d~ Bi~u di~o Tri thuG
Bi~u di1;n tri thue d6ng vai tro rfft quail tn;mg trong thie't ke'
va xfiy dlfng mQt M giai bai loan thong minh. George F. Luger
([26]) va Gerhard Lakemeyer ([41]) oa t6ng ke't cae phuong
phap bi6u diGn tri thue khae nhau va philn lam 4 lo~i: bi6u diGn
dlfa tren logic hlnh thue, bi~u di1;n tri thue thu tl,1e,bi~u di~n
d[~ng \11l,1ng,va hiGHdiGn CrIlltruc. MOi phuong phap chI biGu
di1;n ou<;leffiQt khia e~nh eua kie'n thue trong khi tri thue dn
du<;lebi~u di€n trong cae Mung dl,1ngrfft da d~ng.
1.1.3 Va-n d~ Soy di~n Tt! dQng
Soy di1;n tlf dQng d~ giiii quye't cae bai loan dlfa tren tri thue
eilng 1a mQt vffn d~ quail trQng. Cae phuong phap soy di1;n tlf
dQng v~n dl,1ngkie'n thUe oa bie't d~ soy lu~n giiii quye't vffn d~
trong d6 quail tn;mg nhfft la. cae ehie'n lU<;ledi~u khi~n giup phat
sinh nhil'ng slf ki9n mdi tU cae slf ki~n da e6. Cae ky thu~t soy
di€n tlf dQng da du<;lecae nha nghien CUllkhiio sat kha d~y du d
mue dQ tuong d6i khai quat bao g6m:
3
Phuong phap h<;Jpgi<'titrong bi&u di~n tri tMc dudi d<;lnglogic vi
tu. Phuong phap suy di~n tie'n (forward chaining). Phuong phap
suy di~n llii (Backward chaining). Ke't h<;Jpsuy di~n tie'n va suy di~n llii.
1.2 Phfin tich, danh gill mQt s6 cong trlnh da co
Trong ph§n nay se ban lu~n v6 mQt s6 cong trlnh 19 thuye't
cling nhu ling d\lng da co lien quail de'n m\lc lieu cua d~ tai tu
do neu len cac m\lc lieu c\l th& du<;JCt~p trung nghien CUll,gii'd
quye't.
1.2.1 Cae phu'dng phIlp bi~u di~n tri thuc
Cac phuong phap bi&u di~n tri tMc chung da bie't du<;Jctrlnh
bay trong cac tai lic$ud~u co nhung u'u di6m nha't djnh;trong vi~c tUng d:;lng tri thU'c. Tuy nhien cac phuong phap nay bi&u dih
d~u co mQt nhu<;Jcdi&m chung la chi bi&u di~n du<;JcmQt khia
qnh cua tri thuc rift da d1;lngva chua hudng Wi mQt mo hlnh tri thuc baa ham nhi6u d<;lngthong tin va nhi6u d~ng 51/ki<$nkhac nhau.
1.2.2 MQt s6ly thuye't v~ chung minh va suy di~n ttf dQng
Trong cach tie'p c~n theo phuong phap hlnh thuc cac ke't qua
1:9 thuye't kha truu tu<;Jnglien rift kho ap d\lng trong cac h~
chuyen gia va cac M giai loan d1/a tren tri thuc trong th1/Cte' VI
cac hc$n§y doi hOi phai co mQt co sa tri thuc d1/a tren d.c mo
hlnh bi&u di~n tri thuc co Hnh tfl/Cquail , tinh mo dun hoa cao va
cMa d1!ng nhi~u thanh ph§n tri tMc da d<;lng.
1.2.3 MQt s6 phu'dng phIlp chung minh dinh ly hlnh hQc
Nhi~u phuong pha p chung minh djnh 19 hlnh hQc da dlt<;JCd~
xufft nhu phuong phap di~n tich va phuong phap "full angle".
Cac phuong phap nay chua cho ta mQt mo hlnh bi6u di~n tri thuc
4
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<$tke cae
phuong phap khac nhau co th6 sa dl,mg 06 chung minh cac bili
loan hlnh hQc b~ng may tinh. H~n chS ldn nha't cua cac phuopg phap nffy la chUng khong cho ta nhG'ng mo hlnh bi~u dii;n tri
thUGt6t giup xiiy dl!ng mOt co s0 tri thuG, b(> suy dii;n va cac thanh pMn khac cila M th6ng.
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<;icd~ c~p dSn va GOngco nhG'ng h~n chS tuong tl! nhu cac
phuong pha p da c1u<;iclieU d tren.
1.2.7 MQt s(f san phii'm phftn m~m giai toan
Trong m1,1cnffy u~ c~p uSn mOt so' phffm m~m Cl,lth~ co lien
quail uSn tri thuG va giai loan g5m: Cac chuong trlnh tinh loan
hlnh hQC trong bO phfin m~m Engineering 2000, Chuong trlnh
StudyWorks Chuong trlnh StudyWorks Chuong trlnh
StudyWorks Chuong trlnh StudyWorks, Chuong trlnh Math
Express!, Phffn m~m loan hQc MAPLE, MATHEMATICA, MATHCAD, REDUCE, v.v...
5
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}la mQt t~p hcjp cae bie'n c6 th~ la'y gia
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 h<;tng(rank) k khi quaD M d6 giup ta e6
th€ tint aucje k bie'n ba't ky tU m-k bie'n kia. D6i vdi cae quaD h~
khOng d6i Kung ta c6 th~ giii sti' quaD M xae djnh mQt lu~t d~n f
vdi t~p bie'n vao la u(f) va t~p bie'n ra la v(f).
2.2.2 M~ng suy di~n
Dinh nghia 2.1: Ta gQi mQt nu;mg suy ddn, vie't t~t la MSD, li'l
mQt du true (M,F) g6m 2 t~p hcjp:
(1) M = {Xl>X2,...,Xn}la t~p hcjp cae thuQe tinh hay cae ye'u to'
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 r6ng cua M sao eho u(f) n v(f) = 0.
f E F, ta kg hi~u M(f) la t~p cae bie'n e6 lien M
6
D6i vdi m6i trong quaD h~ f, nghla la M(f) =u(f) u v(f). 2.2.3 Cae va-n d~ eo' ban tren m~ng suy di~n
Tren m(;lngsuy di6n (M,F) gici sa c6 mQt t~p bie'n A ~ M da
du<;Jcxac dinh vft B 1ftmQt t~p bie'n ba't ky trong M.
nho cac quail M trong F hay khong?
. Va'n d~ 1: C6 th€ xac dinh du<;Jc(hay suy fa) t~p B tU t~p A . Va'n d~ 2: Ne'u c6 tItS suy ra du<;JcB tU A thl qua trlnh suy
di6n nhu the' nfta? Cach suy di6n khac nhau thl cach suy di0n nao la t6t nhflt'l
Va'n d~ 3: Trang truong h<;Jpkhong tItS xac dinh du<;JcB, 'thl
.
dn cho them di~u ki~n gl M c6 th~ xac dinh du'<;JcB.
Biii loan xac djnh B tU A tren m(;l~gsuy di6n (M,F) du<;Jcvie't dlfdi d~ng A -t B. Dinh nghia 2.2: Cho D = {1'" 1'2,..., 1'd c F va A eM. Ky hi<$u D(A) 1fts1,1'ma rQng clia A nho ap dl,lllgday quail h~ D. Dinh nghia 2.3: D = {fl, f2, ..., fd c F 1ft mQt liJi giai cua bfti loan A -t B khi D(A) ::) B. Bfti loan A -t B du<;JcgQi 1ftgidi du(/c khi n6 c6 mQtWigicii.Loi gicii{f10f2o..., fd 1ftliJi gidi t6't
ne'u khong tItS bo bot mQt s6 quail h~ trong Wi gicii.
2.3 TIm lui giai
Xet bfti loan A -t B tren m(;lng suy di6n (M,F). Trang m1,1c
n~y ta khao sat tinh ghli dtiQc cua b~1iloan suy di~n, tlm mQt loi
gicii t6t cho bfti loan suy di6n vft phan tkh qua trlnh suy di6n.
2.3.1 nnh giai duQc
Dinh nghia 2.4: Cho m(;lng suy di6n (M,F), vft A 1ftmQt t~p con
cua M. Bao dong cua A 1ftt~p B lOn nha't ~ M sao cho bfti loan
A-tB la gicii du<;Jc.Ky hi~u baa d6ng cua A la A.
M~nh d~ 2.1 lieU len mQt s6 Hnh cha't cua baa d6ng.
M~nh d~ 2.2 lieU len mQt s6 Hnh cha't cua Wi giai.
Dinh Iv 2.1: Trcn mQt m(;lngsuy di6n (M,F), b~d loan A -t B la
gicii du<;Jckhi va chi khi B ~ A .
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:
(1) B ~ A. (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:V2.3 chung minh cd sa loan hQCch6 thu~t loan 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.
(2)
(3) Voi mQi
, voi mQi
i=O,I,...,m,
! Bi ~ Ai
vii
(1)
Khi d6 c6 mQt day {Bo,B\, ..., Bm-I,Bm}, thOa cac di~u ki~n: Bm = B, i=I,...,m, {fi} 1a Wi gicii cua bai loan Bi-I ~ Bi nhu'ng khOng
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
phcii 1a Wi gicii cua bai loan G ~ Bi , trong d6 G 1iimQt t~p con tMt s1/ tily y cua Bi-I.
(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<1igiai va dQ phuc t~p cua qua trinh Hm loi giai
toaD 2.4: TIm mQt Wi giiii cho bai loan H ~ G tren mQt Thu~t MSDT (A, D, w).
t~p la O(IAI.IDl.min(IAI,IDI).
Meoh d~ 2.5 Thu~t loan 2.4 cho Wi giiii la dung va co dQ phuc
2.4.3 Tim liYigiiii t6i lill
vein d~ tlm Wi giiU lo'i u'u cho btd loan H~G lren MSDT (A,
D, w) du'Qcgiiii quye't d1!atren thu~t giiii A. b~ng cach xay d1!ng
d6 thj co trQng so' Grapgh(H~G). Meoh d~ 2.6:
(1) MQt day S g6m cac lu~t la mQt loi giiii cua H~G khi va chi
khi S la mQt 1(>trlnh tren Graph(H~G) n6i tU H de'n S(H) va
S(H) =:>G.
(2) D(>diU cua m(>l 1(>lrlnh S lrcn <16lhj Graph(H~G) Hi w(S),
trQng s6 cua danh sach lu~t S tren MSDT (A, D, w).
Thu~t toaD 2.5: TIm Wi giiii t6i u'u cho bfli tmin H~G.
t~p 1ft O(IAI2.IDI2).
2.5 TS)phqp sinh va vit:CKi~m djnh, bOsung gia thie't
2.5.1 Khai ni~m t~p hqp sinh Bioh oghia 2.7: Cho (A, D) la mQtm~ngsuy di~n. M9t t~p thu9C tinh SeA du'QcgQila m(>ttgp h(!psinh cua m~ng suy di~n khi ta co S =A.
2.5.2 Tim t~p hqp sinh
9
Meoh d~ 2.7 Thu~t loan 2.5 cho Wi giiii la dung va co dQ phuc
Thu~H tmin 2.6: TIm m(}t t~p h<;Jpsinh Strong MSD (A,D) b~ng
phu'dng phap thlt dfin.
Dinh nghla 2.8: xily dvng d6 thi Graph(A,D) tu'dng ung cua
m<,tngsoy di~n (A,D), va d6 thi tho g9n GraphD(A).
Dinh nghia 2.9: neu leu kh::lini~m biiu dc'Jphfln cap va muc cua dlnh.
M~nh d~ 2.8: Cho m<,tng(A, D). Giii slt d6 thi Graph(A, D) co d6
thi tho g9n Graphf)(A). Khi fly, ne'u Graphf)(A) la m(>td6 thi philo dtp thl t~p h<;JpS =Levelo g6m tilt ca cae dlnh mue 0 se eho ta m(}t t~p h<;Jpsinh eua m<,tngsoy di~n. Hdn nITatrong tru'ong h<;Jp
nfiy ta eon eo:
(1) S la t~p h<;Jpsinh nha nhflt ireD m~lllgsoy di6n.
(2) D la t~p h<;Jplu~t t6i thiSu M Levelo sinh ra A.
Dinh tv2.5: Cho m<,tngsoy di~n (A, D). ta eo: (1) SeA la m(}tt~p h<;Jpsinh ireD m<,tngsoy diSn khi va chi khi
co D' cD sao cho Graph(A, D') la m(}t d6 thi philo cflp va S
chua t~p h<;Jpeac dlnh muc 0 ctia d6 thi nfiy.
(2) T6n t<,tim(>tt~p lu~t D' cD sao cho Graph(A, D') la m(}t d6
thi philo cflp. Thu(lt toaD 2.7: TIm m(}tt~p h<;Jpsinh Strong m<,tngsoy di~n (A,
D) b~ng each xily dl/ng m(}tm<,tngcon (A', D') vdi A' = A va co
Graph(A', D') la m(>tbiSu d6 philo dtp.
2.5.3 nO' sung gia thic't cho bai toaD suy di~n
xet vit$c b6 sung gi:i thie't cho bai loan H ~ G tn~n m(}t
m<,tngsoy diSn (A, D) trong tru'ong h<;Jpbai loan khong gi:ii du'<;Jc. Y tu'ong chinh a dily la tie'n hanh m(}tqua trlnh xily dl/ng m(}t biSu d6 philo dtp vdi t~p h<;Jpdinh ehua G va u'u lien cho vi~c
10
d~t cae ph5n tlt cua H a muc O.
Thui,H toaD 2.8: Cho m<;lngsuy di~n (A, D) va bai loan H --+ G khong gilli dU<;1C(khong co Wi gilli). TIm H' sao cho H n H' =0 va bai loan (H u H') --+G la gilli dU<;1c.
Menh d~ 2.9: Thui,lt loan 2.8 d~ tlm s1,1'b5 sung gill thi~t cho bai
suy di~n la dung va co dQ phuc t~p la O(IAI.IDI).
2.6 M~ng Suy di~n - Tinh toaD 2.6.1 Mo hlnh
Dinh nghia 2.10: MQt m~ng suy di~n-tinh loan g6m:
(1) T~p h<;1pA g6m cac thuQc tinh.
(2) T~p h<;1pD g6m cac lu~t suy dit;n (hay cac quan h9 suy
di~n) In~ncite Ihll0c Ifnh.
(3) T~p h<;1pF gOm cac Gong thuG Hnh loan hay cac lhii ll,lc ~inh
loan tu'dng ung vdi cae lu~t suy di~n. S1,1'tu'dng ung nfly lhS hi<$nboi mQt anh x<;lf: D --+ F.
(4) T~p h<;1pR g6m mQt s6 qui t~c hay di@ukic$nrang buQc tren cac thuQc tinh.
M~ng suy di~n Hnh loan du<;1cky hic$uboi bQ b6n (A, D, F, R).
Theo dinh nghla, ta co (A, D) la mQt m<;lngsuy di€n va Wi gilli
cho bai loan H --+ G tren m~ng suy di€n n§y se xac dinh cac
Gong thuG hay cac thii t,=,cHnh loan cac ph§n ta thuQC G ti't cac
phh ta thuQc H.
2.6.2 Giai bili toaD tren m~ng guy di~n-tinh toaD
Ta co th€ gilli quy~t cac bai loan suy dit;n Hnh loan va tlm
Wi gilli t6i u'u d1,1'atren cac thu~t gilli dii trlnh bay a tren. Ngoai
fa, con tlm ra du<;1ccae Gong thuG Luong minh qua cac buGCgilli
bai loan va rUt gQn cae Gong thuG du'oi d~ng ky hil$u. Nhu lhe'
tren m~ng suy di€n-Hnh loan ta eo th~ chi ra mQt cach t1,1'dQng
cac Gong thUGLuong minh d~ Hnh mQt s6 y~u t6 n§y ti't mQt s6
y€u t6 khac (n€u b~1iloan co Wi giail ~~t. R 11 t THU'V!~N
I
, l
!
. do tIm nhung s\1'lien M suy di~n giua cac ySu t5 nao d6 ma ta
t\1'dQng tIm ra them
quan Him se cho ta mQt phuong phap d€ Chu'dng 3. MO HINH TRI THUC cAc DOl Tu'<;1NGTINH ToAN 3.1 Khai ni~m v~ d6i tu'Q'ngHnh toaD va mo hlnh Dinh ni!hia 3.1: MQt d5i tu9ng tinh loan (C-object) li\ mQtc15i . 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. tu9ng 0 c6 ca'u truc g6m: (1) MOt danh sach cac thuQc tinh Attr(O) = {XI,X2,...,xn}va giua cac thuQc tinh c6 lien h~ qua cac s\1'ki~n, cac lu~t suy di~n hay cac cong thuc tinh loan. (2) Cac h~lnh vi lien quan de'n s\1'suy di~n va tinh loan tren cac thuQc tinh cua d5i tuc;fngnhu: .
.
. Xem xet tinh xac dinh cua d5i tU<;1ng.
MOt C-Object c6 th~ dU9Cma hlnh h6a bdi mQt b9: d~ng A ~ B vdi A c Attr(O) va B c Attr(O).
Th\1'chi~n cac tinh loan.
Th\1'Chi~n g<;1iyb5 sung giii thiSt cho bi\i loan (Attrs, F, Facts, Rules) trong d6: Attrs la t~p thu9c tinh cua d5i tu9ng, F la t~p cac quan M suy di~n tinh loan, Facts la t~p h9P cac tinh cha't v5n c6 cua tU<;1ng,va Rules la t~p h9P cae lu~t suy di~n tren cac s\1' d5i
ki~n. 12 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'<;1ngco diu true cling voi cae lo~i quan h~ va cae eang thue Hnh loan lien quan.
3.2.1 M6 hlnh tri thuc Ta gQi mQt ma hlnh tri thue cae C-Objeet , vie't t1{tla mQt ma hlnh COKB (Computational Objects Knowledge Base), la mi)t h9 th6ng (C, H, R, Ops, Rules) g6m: 1. Mot tap hop C cae khai niem v~ cae C-Obieet. M5i khai ni9m la mQt lOp C-Objee't co du true bell trong nhu'
san: Ki~u d6i tu'<;1ng.
Danh saeh cae thuQe Hnh.
Quan h9 tren du true thie't l~p.
T~p h<;1pcae di~u ki9n rang buQe tren eae thuQe Hnh.
T~p h<;1peae tinh eha't nQi t~i tren cae thuQe Hnh.
T~p h<;1peae quan h~ soy dien - Hnh loan.
T~p h<;1peae lu~t soy dien eo d~ng: {cae SIfki~n giil thie't}:::>{caes11ki9n ke't lu~n} Cung voi du true tren, d6i tu'<;1ngeon du'<;1etrang bi eae Mnh vi trong vige giili quye't eae bai loan soy di~n va Hnh loan. 2. Mot tap H eae quan he phan dp giua cae loai d6i tu'ong. Tren t~p C ta eo mQt quan h~ phan dp theo do eo th~ eo mQt so' khai ni9m la st;l d~e bi9t hoa eua eae khai ni9m khae. C6 th~ n6i rhng H 11\mOt bi~u d6 Hasse khi xem quan M phan dp tren la mQt quan M thU t11tren C. 3. Mot tap R eae loai quan he tren cae C-Obieet. M6i quan h~ du'<;1exae dinh boi d6i tu'<;1ngclia quan h~, va quan M co th~ eo mQt so' Hnh eha't nhfft djnh. 13 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.fkil$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.fkil$n) (1) S1.fki~n thong tin v~ lo~i cua mQt d6i tU<;ing. (2) S1.fki~n v~ tinh xac dinh cua mQt d6i tuQng (cac thuQc tinh coi nhu da bie't) hay cila mQt thuQc Hnh. (3) S1.fki~n v~ s1.fxac dinh cua mQt thuQc Hnh haymQt d6i tuQng thong qua mQt bi6u thuc hiing. (4) S1.fki~n v~ s1.fbiing nhau giua mQt d6i tuQng hay mQt thuQc tinh voi mQt d6i tU<;inghay mQt thuQc Hnh khac. (5) S1.fki~n v~ s1.fphI,! thuQc cua mQt d6i tuQng hay cua mQt thuQc Hnh theo nhUng d6i tuQng hay cac thuQc tinh khac thong qua mQt cong thUc Hnh loan. : (6) S1.fki~n v~ mQt quail h~ tren cac d6i tuQng hay trcn cac thuQc Hnh cua cac d6i tuQng. .. Tri thlic v~ cac tam giac va tu giac trong hInh hQc ph~ng co
th<5dU<;icbi<5udiGn theo mo hInh COKB. MQt phan 10n kie'n thlic v~ hInh hQc giii tich 3 chi~u hay kie'n thlic v~ cac phin ling hoa hQc cling co th<5dU<;iCbi6u diGn theo ma hInh nay. 3.3 T6' chuc cd sd tri thuc COKB Co so tri thUc COKB co th6 duQc t6 chlic boi mQt M th6ng 14 t~p tin van ban co ca'u truc nhu sail: [1] T~p tin "Objeets.txt" lu'u tru cae dinh danh eho cae lo<;ti d6i tU<;1ngC-Objeet. cae lo<;ti [2] T~p tin "RELATIONS.txt" lu'u tru thong tin v€
quan h~ khae nhau tren cae lo<;tiC-Objeet. [3] T~p tin "Hierarehy.txt" lu'u l<;ticae bi~u d6 Hasse th~ hi~n quan h~ phan ea'p tren cae khai ni~m. [4] Cae t~p tin voi ten t~p tin d~ lu'u tru ea'u true eua lo<;ti d6i tu<;1ng. [5] T~p tin "Operators.txt" lu'u tru cae thOng tin v~ cae roan t\i' tren cae d6i tu<;1ng. lu'u tru thOng tin v~ cae lo<;tisl! [6] T~p tin "FACTS.txt"
ki~n khae nhau. [7] T~p tin "RULES.txt" lu'u h~ lu~t cua cd sa tri thUG. cofu truc 661 tu'
Cifu tnJc 661 tu'
M6i lien h~ v€ ca'u truc thong tin trong cd sa tri thUGc6 th~ ou<;1c
minh hQa trcn so d0 sau day: mnh 3.3 Bi~u 06 lien M giua cac thanh phgn trong COKB Cach tes chuG cci so tri thUG cho ta mQt cau truc tri thuG ro rang va tach bc;tChvoi day du cac thong tin clIng voi cac . Thfch hQp cho vi~c thie't ke' ml;Jt cd sa trl thuc vdl cae lien h$ khac nhau rat da dc;lng.Mo hlnh COKB dLiQCxay
dljng co cac Liudi§m sau day: 15 khai ni$m co th§ dLiQCbi§u dien bai cac C-Object. . 3.4 GhH toan C-object Cau truc tl1CJngminh giup de dang thiet ke cae m6dun
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. loan mOt d6i Cae va'n dS eelban du<;jed~t ra eho vi~egiai tu<;jngC-Objeet nhu sau: d6 GT va KL la cae t~p h<;jpnhung Sl}ki~n tren cae thuOe tinh cua d6i tu<;jng.
, Va'n d~ 3: Thl}c hi~n tinh loan cac thuQe tinh trong t~p h
KL ta cae sl} kil$n trong GT trong truong h<;jpbai loan GT => KL giai du<;1e. Va'n 08 4: X6t tinh xac dinh eua d6i tu<;jngdl}a tren mQt t~p . sl/ ki~n cho trude. 3.4.1 GhH quye't va'n d~ cd ban 1 Y Luong ehinh la thl/e hi~n mOt qua trinh suy di6n tie'n ke't h<;jpvdi mQt sO'qui t~e heuristic. Ta dn dinh nghIa mQt sO'khai ni~m lien quail bao g6m cae khai niQm: "Sf! hr;p nh(/t" eua cae sl/ kiQn, mQt "buC/cgidi", mQt "1i'Jigidi" va "sf! gidi dur;c". Cae khai niQm nay du<;jelieU len trong cae dinh nghIa 3.3, 3.4 va 3.5. Thu~t ghH 3.1: X6t tinh giai dU<;leeua bai loan GT => KL, trong d6 GT va KL la cae t~p h<;lpnhG'ng Sl}ki.9n lrcn cae lhuQc llnh eua mQt C-Objeet. 3.4.2 Giai quye't va'n d~ cd ban 2 D~ tlm mOt Wi giai eho bai loan GT => KL, ta e6 th~ thl/e hiQn mQt thu tl,1cg6m 2 giai do,!-nnhu dudi day. 16 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 Vi du 3.3: Giai bai toclnGT ~ KL tren d6i to'Qng"TAM_GIAC"
{a, b=5, GocA = m*(b+c), GocA = 2*GocB, sinh ra nho'ng kh6ng dn thiet thllo~i boo voi GT =
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. Soy ra {GocA '= ~ 1t} tlt {a2 = ';2 + C2} 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}
6. Soy ra {GoeC } tlt {GoeC '=L1t } 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 Thu~t giiii 3.3 tren se OmWigiai r6i tht/c hi~n tinh loan va cho
ta ket qua tinh loan nho'san: {o, b = 1, GacA = ~ 1t} ~ {R, S, c} . 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 Chu'o'ng 41 M~NG cAc DOl TU<)NGTlNH ToAN t~p s1,1'ki~n GT. 4.1 M~ng cae d6i ttNng Hnh toaD cd ban
4.1.1 Mo hlnh Dinh nghla 4.1: MQt m~ng cac d6i tu'Qngtinh toan cd ban la mQt bQ (0, M, F) g6m:
(1) 0 = {OJ, O2, ... , On} la t~p hQp cac C-Object cd ban voi ca'u truc g6m cac thuQc tinh va t~p cac quail M tinh toan. (2) M la t~p hQp cac thuQc tinh cua cac d6i tu'QngthuQc O. (3) F = {fl, f2, ... , fIll}la mQt t~p hQp cac quail M tinh toc'intren 4.1.2 Cae bai toaD tren m~ng (0, M, F) cac thuQc tinh thuQc M. Gia stYA ~ M da du'Qcxac dinh va B la mQt t~p bie'n bat ky trong M.
Cae va-n d~ cd ban du(fc diU fa la: 1. C6 th~ xac dinh du'Qct~p B tu t~p A nhO cac quail h~ trong F va cac d6i tu'QngthuQc 0 hay kh6ng? 2. NC'l1co lh6 xac ujnh ulf<;lcB tU A thl qua trlnh tinh toan gill tri cua cac bie'n thuQc B nhu' the' naG? 18 . tinh roan B tu gia thie'tA? 3. TIm mQt Wi giai t6t nha't (hay Wi giai t6i u'u) eua b~d roan B~d roan xae djnh B tU A tren m~ng (0, M, F) dU<;Ievie't duoi d~ng A~B. Dlnh nghia 4.2: neu khai ni~m Wi giai eua b~liroan A~B. 4.2 Cac thu~it giai 4.2.1 Tinh giai duQc cua bai tmin
Dlnh nghia 4.3: bao d6ng A cua A tren m(lng.
M~nh d~ 4.1 neu ten mQt tint ehfft eua bao d6ng. Dinh Iv 4.1: Tren mQt m~ng cae a6i tu<;lng(0, M, F), bai roan A
~ B Ia giai dlt<;lekhi va chi khi B ~A .
M~nh as 4.2 va 4.3 phat bitSu mOt tinh eha't lien quail de'n ky hi~u D(A) voi AS;;;;M, va day D = {tJ, t2, ..., tm}s;;;;F u O. Dinh I" 4.2. Cho mN m~ng cae d6i tu<;Ing(0, M, F), A va B la (2) C6 D S;;;; F u a sao eho D ap aU<;letren A va D(A) ~ B. hai t~p con eua M. Ta e6 cae di@usail day la tudng dUdng:
(1) B S;;;;A. Thuat toaD 4.1: tlm bao d6ng eua t~p AS;;;;M tren m~ng cae d6i tu<;lngtinh roan (0, M, F). 4.2.2 Tim IOigiai cua bai toaD Menh d~ 4.4: Day D c F u a la mQt Wi giai eua bai roan A~B khi va chi khi D ap dl,1ngdu<;letren A va D(A) ~ B. Thuat giai 4.2: tlm mi)t Wi giai eho bai roan A ~ B. 4.2.3 Dinh Iy v~ srf phan tich qua trinh giai Dinh IV 4.3. Cho {tl, t2, ..., tm} la mi)t Wi giai t6t eho bai roan A~B tren m~ng (0, M, F). f)~t : Ao =A, Ai = {tJ, t2, ..., t,}(A), voi mQi i=l,...,m. Khi d6 e6 mQt day {Bo,BJ, ..., Bm-I,Bm}cae t~p con eua M, thoa cae diSu ki~n sail day: 19 (1) Bm= B. (2) Bi ~ Ai, voi mQi i=O,l,...,m. (3) Voi mQi i=l,...,m, {td la Wi giai cua bai roan Bi-I ~ Bj nhu'ng thong phai la Wi giai cua bai roan G ~ Bj , trong d6
G la mQtt~p con th~t 51/tily Y cua Bi-I' 4.2.4 Uti giai t6i u'u Cac dint nghTa 4.4 va 4.5 neu len thai ni~m v~ Wi giai t5i u'u tren mc,tngc6 trQng 55 (O,M,F,c,c'), va m~nh d~ 4.5.cung cffp mQt each tlm Wi gii'ti t5i u'u cua bai roan A~B tren mc,tng. tang quat 4.3 M~ng cae C-object
4.3.1 Mo hlrth . Blnh nghla 4.6: Tren mQt mo hint COKE = (C, H, R, Ops,
Rules) mQt mc,tngcac C-Object, vie't v~n t~t bCiiCO-Net,
la mQt
bQ (0, F) voi: (1) a la t~p hc;Jpcac C-Object, m6i C-object thuQc mQt thai ni~m du'c;Jcbie't trong COKE. (2) F la mQt t~p hc;Jps1/ki~n, m6i 51/ki~n th~ hi~n mQt tinh chill hay mQt lien M nao d6 tren cac d5i tu'c;Jnghay tren cac thuQc tint cua cac d5i tu'c;Jng. Khi ta phai xem xet mQt t~p s1/ ki~n ml,1clieu G va mu5n khao sat nhting vffn d~ suy di~n va tint loan (hay giai loan) thl ta c6 mQt bai roan tren CO-Net, ky hi~u la (0, F) => G. 4.3.2 Phu'dng phap giai hI dQng Thui,HgiiH 4.3: mQt each tlm Wi giai d1/a tren vi~c xem xet tint hc;Jpnhilt cua cae sl! ki~n va sa dl,mg9 dc,tngsuy lu~n khac nhau. Thui;it giai 4.4: mQt qua trlnh suy di~n tlm Wi giai voi vi~c 5lt dl,1ngcac qui t~c heuristics. Cac heuristic giup ta c6 th6 tlm du'c;Jcloi giai nhanh ch6ng hon va cho mQt Wi giai rilt t1/ nhien nhu' s1/ suy fighTva cho Wi 20 giiii eua con ngu'oi. Du'oi day la mQt s6 heuristic e6 th~ du'<;1esU' dl,1ng: (HI) UU tieD sU' dl,1ng cae qui t~e xae djnh d6i tu'Qng va cae thuQe Hnh eua d6i tu'Qng. (H2) Chuy~n d6i d6i tu'Qng (nMn d~ng d6i tu'Qng thuQe khai ni~m mue eao hdn) sang khai ni~m mue eao hdn trong bi~u d6 phan ca'p cae khai ni~ljll. (H3) SU'dl,JOgcae qui t~e phat sinh d6i tu'<;1ngmoi d~ lien k€t cae y€u t6 tren mc;tngcae d6i tu'<;1ng. (H4) Khi phat sinh d6i tu'<;1ngthl u'u tieD t~o ra d6i tu'Qng e6 lien quail d6n cae d0i tlf<;lngdang e6 nhfllia lien quail d€n cae sl,[ki9n 1111,Ielicu. (H5) Uu tieD sU'dl,JOglu~t hay d<;\ngsoy lu~n d~ phcit sinh ra slf ki~n lien quail d€n cae slf ki~n ml,1etieu. (H6) N€u khong th~ phat sinh slf ki~n moi hay cae d6i tu'Qng moi ta e6 thS d~t tham bi€n va giiii cae phu'dng trinh hay h~ phu'dng trinh. . (H7) Luon luau e6 slf ki~n moi khi thi€t l~p d6i tu'Qngmoi. 4.4 TIl giac vUi Hnh Dang md rC)ng Trang ph~n n~y trlnh bay slf mC1rQng khii Dang giai tmin eua mQt C-Objeet thong qua vi~e b6 sung cae lu~t nQi bQ lien quail d€n cae d6i tu'<;1ngthi€t l~p tren daub saeh cae d6i tu'Qng n~n eua tU giae: 4 di~m CJ4 dinh eua tu giae. MQt m<;\ngd6i tu'<;1ngnQi bQ eGng du'<;1edu'a vao dS lien k€t cae thuQe Hnh eGng nhu' cae d6i tu'Qng lien quail lrang tu ghk Ky thu~t n~y lam eho d6i tu'Qng "tU giae" e6 khii Dang xU'ly va giiii quy€t nhi~u bai toaD hdn so voi phu'dng phap giiii C-Objeet dl1 du'Qe trinh bay tru'oe day trang ehu'dng 3. 21 Chu'dng5. cAc UNG D{}NG ChUeing fifty trlnh bay mQt s6 ling dl;mg eoa m(;lng suy di~n Hnh loan, ma hlnh COKE va ma hlnh m(;lng cae C-Objeet. Cae ling dl;mgfifty g6m cae ehUeingtrlnh: giai loan mQt C-Objeet, cae bai loan Hinh hQe phhg, giai cae bai loan Hinh hQe giai rich 3 ehi~u, va giai mQt s6 bai loan v~ cae phan ling hoa hQe. Ngoai ra, mQt pae~age v~ m(;lngsuy di~n Hnh loan t6ng qua t ding du'Qe cai d~t voi d5y do cae tho tl,1egiai quye't cae vin d~ eel ban dU<;Ie 5.1 Chu'ong trinh ghH tm!n C-object 5.1.1 So d6 ho~t dQng giai toaD eua ehu'ong trlnh HO(;ltdQnggiai loan C-Objeet eoa ehUeingtrlnh dlfa tren mQt eelsa tri thlie cae C-Objeetdu<;Iet6 ehUerhea ma hlnh COKE. I -, trlnh bay trong c1llfdng2. ~---7 ~
PHANTtCH"~ Giathi€tlA
K . I :; r 1 I I Tri thuc ~
~i g~ GIAIf)~ I moh 5.1 Seld6 ho(;ltdQng giai mQt d~ bai loan 5.1.2 Qui u'oc v~ d~ bai toaD parameters: ciu true eoa d~ bai loan co d(;lngnhu sau: begin_hypothesis 22 objects: tu<;ing> facts: end_hypothesis begin_goal 5.1.3 Mc)t s6 tho tl,lCchlnh Ml,1cn§y trlnh bay mOt sO'thu tl,1Cchinh du<;iCvie't trong moi truong MAPLE d~ giiii loan C-objcc~. 5.1.4 LOi ghH Ml,1cn~y trlnh bay mOt vi d~l v~ 101ghH cila bal loan uu<;ic tIm thffy bdi chuang trlnh. 5.2 Chu'dng trlnh ghli tmin hlnh hQc phiing Ph§n nfty trlnh bay v6 mOt ling dl,1ngcila mo hlnh COKB va mi,lng cac C-Objcct: package ghli cac bi'ii loan hlnh hQCphhg. Ky thu~ t thie't ke' cac thu~t giiii dil du<;ictrlnh bay trong chuang 3 va chuang 4. Phfln cai d~t cl,1th~ tuang tl! nhu phfln cai d~t backage giiii loan C-Object. Duai day se lieU len phftn ligon ngu begin_hypothesis
parameters:
objects: tu<;ing> facts: end_hypothesis 23 d~c ta cho bai loan va trlnh bay mQt sO'vi dl,1minh hQa.
5.2.1 Ngon ngii d~c tit bai tmln
Bid toan du<;ic khai bao theo diu truc sau day: begin_goal loan: 5.2.2 Cac VIdQ
Vi du 5.3: Cho tam giac din ABC, din t<;tiA, va cho bie't tru'dc
g6c dinh A b~ng cr, c<;tnhday a bAng m. Ben ngoai tam giac c6
hai hlnh vuong ABDE va ACFG. Tinh dQ dai EG. !
facts: 01.GOC[C,A,B] ; DOAN [B, C] ; 01.
01.A = pi - 02.A; end_hypothesis
begin_goal determine: 02.DOAN[E,G] end_goal begin_hypothesis
objects:
A,
01
02
03
04 B, C, D, E, F, G : DIEM;
: TAM_GIAC_CAN[A,B,C];
: TAM_GIAC[A,G,E];
: HINH_VUONG[A,E,D,B] i
: HINH_VUONG[A,C,F,G]; Bu'dc 1: determine 02.A, Wc la g6c A cua tam giac AGE.
Bu'dc 2: detem1ine 01.DOAN[A,B].
II trong d6i tu'<;1ng01
Bu'dc 3: determine 03.DOAN[A, B].
Bu'dc 4: determine 04.DOAN[A, C].
Bu'dc 5: determine 02.DOAN[A, E].
Bu'dc 6: detenlline 02.DOAN[A, G].
Bu'dc 7: determine 02. DOAN[E, G]. II trong 02 5.3 Chtidng tr'inh ghH toan h'inh hQc giai tich 3 chi~u Philn nily trlnh bay thie't ke' mQt chu'ang trlnh gieii toaD Hinh HQCGieii Tich 3 chi~u dt!a tren mo hlnh tri thUc COKB va m<;tng 24 cac C-Object. Chuang trlnh da duQc cai d~t thil' nghic$m dung
Visual C++. 5.3.1 Cftu true M th6ng eua ehlidng trlnh Chuang trlnh g6m 3 thanh phfin chinh: phfin giao dic$n,co so tri thilc va module giiii bai loan. Chuang trlnh c6 cac thlfc don cho nguoi dung thlfc hic$nvic$cchQn llfa chilc Dang, cho phep ta nh~p vao d~ bai loan. £>~bai loan se duQc nh~p vao duoi d~ng mQt van ban co cfiu truc dlfa tren mQt ngan ngG' khai bao bai loan Luong tlf nhu d6i voi chuang trlnh giai bai loan Hlnh hQC phhg a tren. Khi co yeti du giai bai loan chuang trlnh se tlm loi giiii va th6 hi9n loi giiii cling nhl!, hlnh ve trong cac cil'a s6
Iren IlInn h1nh. 5.3.2 Cd sd tri thuc cua chu'dng trlnh T6 chilc co so tri thilc cua chuang trlnh duQc thlfc hic$ntheo ma hInt COKE. Dlfa tren cach t6 chilc co so tri thilc nhu tren chung ta se d~ dang thlfc hic$nslf tlm kie'm va truy c~p vao co so tri thUc: cac khai nic$m,cac slf kic$nva cac lu~t co th~ duQc b6 sung, thay d6i, hay lo~i boo 5.3.3 Ky thu~t giai bai toan Ky thu~t giai bai loan duQC phat tri~n dlfa tren ma hInt m~ng cac d6i tuQng trong mQt COKE. D~ng t6ng quat cua bai
loan co th~ duQc ma hInt boi cac t~p hQp sail: a = {aI, O2, . . .,
On}, R = {rl, 1'2,. . ., rm},va F = {fl, f2,. . ., fp}.Trang do a la t~p
hQp cac d6i tuQng, R la t~p hQp cac slf kic$ncho ta cac quail hc$ v~ phuong dic$nhlnh hQc giG'a cac d6i tu<;lng,va F cling la t~p h<;lpcac s\t ki~n nhltng g6m cac cang thUe th~ hi~n cae quail h~ lint tatln tren cae dOi tu'<;Ingva cae thuOc lint eua chung. Phu'dng ph:ip soy di~n tie'n du<;lcsil' d\Jng cung voi cac heuristic d~ thie't ke' thu~t giiii tlm Wi giiii cho bai loan dlfa.tren tri thUc.
5.3.4 Ngon ngii' khai bao bai toan 25 £>6 yeu du chll'ong trlnh giai mQt bai toan ta chi dn khai bao cac d6i tll'<;Jngtrong bai toan, cac slf ki~n va m\1c tieu cua bai toan theo diu truc g6m 2 ph~n nhll'sau: (1) Khai bao ph~n gilt thie't baa g6m cac d6i tll'<;Jng,cac slf kil$n quail hI$, cac quail hl$ tinh toan (hay cac bi6u thlic), va cac ye'u to' dft dll'<;Jcxac dinh trll'oc (d6i tll'<;Jng,thuQc tinh hay
tham bie'n). (2) Khai baa ph~n m\ICtieu cua bai toan. Phh n~y trlnh bay vi~c ap dl,mgmo hlnh m~ng suy di~n
tinh toan trong suy di6n giai mQtsO'bfd toan tren cac phan ling ! h6a hQc. Lu~n an dft t~p trung nghien cliu va phat tri6n cac mo hlnh bi6u di~n tri thUc d6 lam co sd va 1a cong C\1cho vil$c thie't k€ co sd tri thlic, bQ suy 1u~n tlf dQng giai toan cling nhll' giao di~n cua cac hI$giiii toan thong minh. Cac hl$ th6ng nay c6 ho~t c1Qilg \ ' tll'duy giai toan tll'ong tlf nhll' ngll'oi va c6 kha nang cho cac Wi giai tll'ong minh, tlf nhien' va phuh<;Jp voi cach nghI va cach vi€t cua con ngll'oi. Lu~n an da d~t dll'<;JcmQt sO'ke't qua chinh nhll'
sail: V6 m~t 19 thuye't 1u~n an dft g6p ph~n trong vi~c phat tri6n cac mo hlnh biSu di6n tri thlic moi. Lu~n an phan tich va danh gia cac phll'ong phap bi6u di~n tri thUc dft bie't, khao sat nhung ke't qua nghien cliu v6 19 thuy€t cling nhll' thlfc hanh tU d6 xay dlfng dll'<;JcmQt sO'mo hlnh bi6u di~n tri thUc kha t6t c6 th6 sa 26 dl,mg trong thie't ke' cae h~ giai toan dtfa tren tri thue. Cae m6 hlnh nay g6m: . thu~t biSu di~n m~ng ngu nghla, biSu di~n d~ng lu~t d~n,
biSu di~n ca:u true d~e bi~t la biSu di~n tren cd sa cae d6i 1. M6 hlnh m~ng suy di~n Hnh toan trong do tich hc;ipcae ky tu'c;ingcling vai cae ky thu~t Hnh toan symbolic tren may
tinh. 2. M6 hlnh tri thue vS cae C-Objeet la mOt m6 hlnh biSu di~n tri thue theo caeh tie'p e~n hu'ang d6i tu'c;ing.M6 hlnh eho ta eho mOtlOr ki6n thac t6ng quM bao g6m mOth9 thong cae mOt thS hi~n tu'ong u6i d~y uu vai cae ca:u true tu'ong minh khlii ni9m v~ de C-Objcet, de qllun hO djnh tfnh eGng nhl\' dinh lu'c;ingtren cae kMi ni~m C-Objeet, cae lo~i s1,1'ki~n khae nhau lien quail de'n cae lo~i quail h~ cling vai cae d~ng lu~t kha phong phu. 3. M6 hlnh m~ng cae C-Objeet la mOt m6 hlnh thS hi~n du'c;ie cae d~ng bai toan t6ng quat trong tri thue vS cae C-Objeet. Tren cd sa cae m6 hlnh biSu di~n tri thue tren lu~n van eGng neu leu caeh t6 chIle cd so tri thue v~ cae C-Objeet va pMt tri~n cae thu~t giai as giai quye't cae va'n d~ co ban du'c;ied~t ra tren
m6 hlnh. D6i vdi mo hlnh m~ng suy di~n va tinh toan, cae va'n dS cd ban du'ge giai quye't baa g6m: 1. Khao sat tinh giai du'ge eua bai toan suy di~n. 2. TIm baa dong eua mOt t~p thuOe Hnh. 3. TIm Wi giai eho bai toan va th1,1'ehi~n cae tinh toan baa g6m tinh toan so' va tillh toan ky hi~u. 4. TIm Wi giai t6i u'u tren m~ng suy di~n tinh loan co tn,)fig so'. 27 5. TIm mQt t~p h<;1psinh tren m~ng suy di~n tinh loan va giai quye't va'n d~ b6 sung gia thie't cho bai loan. D6i voi mo hlnh tri thuG v~ cac C-Object ta co mQt t6 chuG cd sa tri thUGch~c eM va ti~n l<;1icho vi~c hi~u chinh, truy c~p tv dQng cac bai eling nhu' cho vi~c SU dl,lllg tri thuG trong giai
loan. D6i vdi mo hlnh m~ng cac C-Object, lu~n van cling lieU leu cac thu~ t gi<'tid~ giai quye't cac va'n d~ cd ban d6i voi bai loan tu'dng tv nhu' cac yell du cd ban d6i voi bai loan tren m~ng suy di~n tinh loan nhu'ng voi mUGdQ khai quat va ph~m vi ap dl,lllg rQng va sa u hdn. Cu6i clIng cac mo hlnh bi~u di~n tri thUGd~ ra trong lu~n van c1u'<;1Cchi ro u'u the' va l<;1iich cua chung trang vi<$cthie't ke' cae ehu'dng tdnh giai bai loan thOng minh dva tren tri thue thong qua vi<$cthie't ke' va dli d~t mQt so' chu'dng tdnh ung dl,1ngcl,1th~ g6m: 1. Chu'dng tdnh giai loan mQt C-Object t6ng quat. Chu'dng tdnh nay co kha nang giai cac bai loan tren mQt C-Object ba't ky co lrong cd sa tri thUGcua ehu'dng tdnh nhu': giai cae bai loan tren tam giac, tren tU giac. 2. Chu'dng tdnh giai cac bai loan hlnh hQc ph~ng trong d6 co th~ giai cac bai loan tinh loan tren ky hi~u cli nhu' giai cac bai loan suy di~n tren cae sv ki~n quail h~ hlnh hQc va cae bai loan suy di~n lien quail de'n ca tinh loan lh quail M. 3. Chu'dng tdnh giai bai loan hlnh hQCgiai rich 3 chi~u co kha nang thvc hi~n cac suy di~n va tinh loan d~ giai du'<;1cnhi~u d~ng bai loan khac nhau. 4. Chu'dng tdnh giai mQt so' bai loan suy di~n tren cac phan 28 ung h6a hQc. Huang phat tri~n cua lu~n van: 1. Tie'p t1,1Cphat tri~n va hoan thi~n mo blah tri thuc v~ cac C- Object tie'n Wi xfiy dlfng mi)t M cd sa tri thuc cho lOp cac kie'n thuc 101;lingy vai dgy du cac chuc nang nhu hi~u chinh, truy c~p, trao d6i tri thuc phan tan va giai loan tlf di)ng. 2. Ap dl,Ingcac mo blah dS phat tri~n cac san phffm phgn m~m giai loan hoan chinh nhu giiii cac bai loan v~ d1;lis6, giai tich, blah hQc, v~t ly, h6a hQc v.v... trong d6 cling dip nhi~u
chuc nang da d1;lngduQc phan lOp d~ c6 th~ dung trong tra CUllkie'n thuc, hQc kie'n thuc, hQc giili loan vdi nhi~u muc
dO khac nhau. 3. Phat tri~n cac ky thu~t hQc va kham pha tri thUc dlfa tren dc mo hint bi6u di6n tri thuc d6 t~ng cu(jng khi\ n~ng h9C CAC BAI BAO CO LIEN QUAN DEN LU~N AN va phat triSn tri thuc cua cac h~ giili bai loan thong mint. [1] Hoang Kie'm - D6 Van Nhdn, M(mR tinh toan va unR dl,lng,
tr. 10- T1;lpchi Tin hQc va di~u khi6n hQc, T.13, S.3 (1997),
20. [2] Hoang Kie'm-D6 Van Nhdn-Le Hoai B~c, A knowledgeable model: networks 'o.f C-objects, Asia-Pacific Symposium on and Telecommunication Information
Technologies
(APSITT'97), Hanoi - Vietnam (1997), pp. 15.5.1- 15.5.4.
[3] D6 Van Nhdn, A model o.f Knowledge of Analytic Geometry, Proceedings of the IT@EDU 98 Conference, Ho Chi Minh City (1998), pp. 3.5.1-3.5.6. [4] D6 van Nhdn, Model o.fproblems in Analytic Geometry and automatically solving, Proceedings of the IT@EDU 98 29 Conference, Ho Chi Minh City (1998), pp. 3.3.1 - 3.3.7. [5] D6 Van Nhon - Le Hoai B~c, Analytic Geometry Problem Solving System, HQi thao Qu6c gia v~ Tin hQc Ung d\lng,
Qui Nhon (1998), tr. 92-98. [6] D6 Van Nhc1n, Lc Hoai B~c, An algorithm on a relational knowledge model and its aplications, Journal Science & Technology Development, Vo1umn 2 - Number 2&3/1999, pp.81-85. [7] D6 van Nhon - Le Hoai B~c, Weighted Computational nets, Proceedings of the IT-EDU 2000 Conference, Ho Chi Minh
City (2000), tr. 92 - 98. [8] D6 Van Nhon, A system that supports studying knowledge and I solving' of analytic geometry problems, 16 th World
, Computer Congress 2000, Proceedings of Conference
Education Uses on
and Communication Information of Technologies, Beijjing, China, pp. 236-239. [9] D6 Van Nhon, A Program for studying and Solving problems in Plane Geometry, Proceedings of International Conference on Artificial Intelligence 2000, Las Vegas, USA, pp. 1441-1447, [10] D6 van Nhon - D~ng Van Hung, A Systematic Design Method f()/' Real-Time Systems using Duration calculus, 5th World Multiconference on SYSTEMICS, CYBERNETICS [11]Nguyh Huu Anh- D6 Van Nhc1n,UJi gidi t6'i uu va t(ip
sinh tren mc;mgsuy diln, T;;\p chi Phat tri€n Khoa hQc Cong AND INFORMATICS, Orlando, Florida, USA (2001), pp,
241-246. [12] Hoang Kie'm - D6 Van Nhon, M() hlnh Tri ngM DHQG TPHCM, 1&2 (2001), t~p 4, tr. 10-16, thuc cae E>6'i tullng Tinh roan, HQithao Khoa hQcky ni~m 25 nam thanh
l~p Vi~n Cong Ngh~ Thong Tin, Ha NQi (2001), tr. 379-388. 30 DE TAl NGHIEN cuu KHOA HQC
CO LIEN QUANDEN LU!N AN Ten d~ ad: M6 hlnh tri thuc C-Object va Ap dl,lllg. D~i H9C Qu6c Gia TP.HCM ~~Li!E ;;! Truong D~i h9C Khoa h9CT1,J'nhien, nam 2001. , '! ~;.:; I
\ i1
I a:: 31 I J --- t. Xac djnh bao d6ng cua mQt t~p thuOc tinh A.
. X6t tinh ghH oU<;1ccua bai loan suy di~n tinh loan c6
3.2.2 Vi dQ.v~ m{)t mo hinh tri thuc cae C-object
.
..
. Va'n dS 1: X6t tinh giai du<;jeeua bai loan GT => KL, trong
. Va'n dS 2: TIm mOt loi giili eho bai loan GT => KL.
r-::\
. E>~c tei bai
. Loi gieii:
5.4 Giui I11Qt so' bili toan v~ c~lc plu\11 ling h6a IH)c
KET LU!.N
r!J H. !-
