Xem mẫu
- 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
nguon tai.lieu . vn
