ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA: KHOA HỌC MÁY TÍNH
BÁO CÁO MÔN HỌC
BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG
ỨNG DỤNG MẠNG TÍNH TOÁN XÂY DỰNG
CHƯƠNG TRÌNH GIẢI TOÁN TỰ ĐỘNG
PGS. TS. ĐỖ VĂN NHƠN
NGUYỄN KHẮC MẪN _ CH1101102
: CH06
: 2012-2013
TP. Hồ Chí Minh, tháng 1 năm 2013
LỜI CẢM ƠN
!"#$#%&'()" *"
Trước tiên, tôi xin gởi lời cảm ơn chân thành đến Thầy hướng dẫn của
tôi, PGS.TS Đỗ Văn Nhơn. Trong suốt quá trình làm báo cáo, Thầy đã giúp tôi
đặt vấn đề, tìm hiểu vấn đề và giải quyết các vấn đề một cách khoa học.
Tôi xin gởi lời cảm ơn chân thành đến quí thầy cô của khoa Khoa học
Máy tính, cũng như tất cả quý thầy cô của trường Đại Học Công Nghệ Thông
Tin đã tận tình giảng dạy và truyền đạt kiến thức cho tôi trong suốt quá trình
học tập.
TP. Hồ Chí Minh, tháng 1 năm 2013
Nguyễn Khắc Mẫn
"+,-./0%1121123 4563
!"#$#%&'()" *"
NHẬN XÉT
(Của giảng viên hướng dẫn)
777777777777777777777777777777777777777777
77777777777777777778
777787777777
Mục Lục
BÁO CÁO BIỂU DIỄN TRI THỨC VÀ ÚNG DỤNG
Nguyễn Khắc Mẫn
#:;<=%>?"#?#@55%>/,#A
%2BC/%'%1121123
Tóm tắt/?DE=AFGF5:5HIE1JJKLM<N'I"O8
<P,QHERE?DLS+-:TFSU+,VWFXFR8
#:LHLH,Y5Z[DES+XE?DE=AHERZ\
+]U+,VWFX:E=A8=F^Y5_Z[
`6E`aU+5ERZ\Tbc5E=A:V8+\d:
LHLH,Z[F5:5]`aH:SEM:RE=A
8
I. MẠNG TÍNH TOÁN
HFe:5:]LVfHg^ER+]HFS
DEQ;LHf@hi?j
P+:Q;QH^<\=LH:5^SdE?DE=
AFSLS+-H`kQl:Tdm+]Z+,-FSDE
Q;8
"+,-./0%1121123 456n
!"#$#%&'()" *"
1. Mạng tính toán là gì ?
/=AQHER=LS+-:T^SdLS+-:
TXWFXAHFGbER^+U+FSU+,V
ERZ\=LH8/NE=AQHERE=mo5T5LV
HmU+5^SHFeHZkbFGA8^S^
:pE=AQHERZqU+c5iS+mQ+:r+G^i
I`P,HEdqGHO:D8
1.1. Các quan hệ
/st`
E
uHil+QH
$y`
1
u`
3
u888u`
E
z5,..QH$y`zyil+`dFS{LRLV|`
1
u`
3
u888u`
E
hz8}+5
$y`z`FwERy5,ERZ\z`=f
R,u,v
: D
u
→ D
v.
:F^+uQHLR
LVH+⊆`u⊆`~
+
H
QHAc5EX`FwOTc5LV
:+H:8
#5^SW,:pU+5$y`z^SFGLS+-LMER`=•
$u+u
2
, ,xn}
F = { f
1
,f
2
, ,fm}
<\EN• ∈„u5il+/y•zQH]LV^Q:U+5•8 o
/y•zQHER]c5//y•z⊆/8"V+V•=•+y•z →y•zD
5^/y•zs+y•z∪y•z8
Ví dụ 1 : Mạng tính toán về vật lý cơ học
Việc tính toán trong lĩnh vực vật lý cơ học sẽ liện quan đến các giá trị sau:
P: Trọng lực
F
hd
: Lực hấp dẫn
"+,-./0%1121123 456B
!"#$#%&'()" *"
G: Hằng số lực hấp dẫn
m: Khối lượng của vật
g: Gia tốc trọng trường
k: Độ cứng của lò xo
∆l: độ biến dạng lò xo
….
trong đó mỗi biến đều có giá trị là thuộc tập các số thực dương. Giữa các biến ta đã
biết có các quan hệ sau đây:
f
1
: P = m.g
f
"+,-./0%1121123 456…
!"#$#%&'()" *"
Các vấn đề đặt ra là:
1. Có thể xác định được tập B từ tập A nhờ các quan hệ trong F hay không?
Nói cách khác, ta có thể tính được giá trị của các biến thuộc B với giả thiết đã
biết giá trị của các biến thuộc A hay không?
2. Nếu có thể xác định được B từ A thì quá trình tính toán giá trị của các biến
thuộc B như thế nào?
3. Trong trường hợp không thể xác định được B, thì cần cho thêm điều kiện
gì để có thể xác định được B.
Bài toán xác định B từ A trên mạng tính toán ( M,F ) được viết dưới dạng:
A → B
trong đó A được gọi là giả thiết, B được gọi là mục tiêu tính toán (hay tập biến cần
tính) của vấn đề. Trường hợp tập B chỉ gồm có một phần tử b, ta viết vắn tắt bài toán
trên là A → b.
Định nghĩa 1:
Hf→ FG>QH giải đượci^SAFG:w
LV+R`+WrVf8#5^:pERƒ,U+5t•
1
u•
3
u888u•
i
v
⊆„QHERlời giảic5LHf→V+5QxQGbU+5†
ys1u888uiz`+WrVfDZ[AFGLV+R8;{ •
1
u
•
3
0
∪ M(f
1
), . . . , Ak = Ak
-1
∪ M(fk), và ký hiệu Ak là D(A), thì ta có D là một lời giải của bài toán A → D(A).
Trong trường hợp D là một dãy quan hệ bất kỳ (không nhất thiết là áp dụng được
trên A), ta vẫn ký hiệu D(A) là tập biến đạt được khi lần lượt áp dụng các quan hệ
trong dãy D (nếu được). Chúng ta có thể nói rằng D(A) là sự mở rộng của tập A nhờ
áp dụng dãy quan hệ D.
Thuật toán tính D(A) :
"]/=Ay/u„z
f⊆/
ƒ,U+5 st•
1
u•
3
u888u•Ev8
ˆ+W yfz8
#+]
18f‰ ←f~
38•:s1E
•†bFG:f‰6
f‰← f‰∪ /y†z~
98 yfz←f‰8
"+,-./0%1121123 456J
!"#$#%&'()" *"
3. Giải quyết vấn đề
3.1. Tính giải được của bài toán
#:Ebx,Y5+QERiE^QU+5FVA
"]/=Ay/u„zu
f ⊆ /8
ˆ+WŠ
#+]
18 ← f~
38 Repeat
1←~
for •∈ „do
if y•F\`Tand 5:y/y•z‹z≤ :y•zz ory•i?F\
`Tand/y•z‹⊆ y•zzthen
begin
←∪/y•z~
„ ← „‹t•v~ŒŒQ=•igQx`6E`aZ5+
end;
Untils1~
98 Š ← ~
"+,-./0%1121123 45611
!"#$#%&'()" *"
3.2. Lời giải của bài toán
•:5Fƒ+Q`FwAFGc5LH8#V6u5Z[
:DLH,DE:5Q;LHf→ :E=Ay/u„z8
Mệnh đề : Dãy quan hệ D là một lời giải của bài toán A → B khi và chỉ khi D áp
dụng được trên A và D(A) ⊇ B.
EFX:uFSDEERQ;5^SQHEZ5+ˆ+Wr
Vfu5kbU+5FSEM:Rx]LV^:wFG
`Fw~HU+:Dx,=:5ERZQ5:+,XA`Fw:]LV
FViF=FV]LV8 FP,QH+]DEERQ;LH
f→:E=Ay/u„z8
Thuật toán tìm một lời giải cho bài toán A → B:
"]/=Ay/u„zu
UntilQ+0•+oryfsfQz~
"+,-./0%1121123 45619
!"#$#%&'()" *"
n8if notQ+0•+then
Hi?^Q;~
else
Q+QHERQ;~
Ghi chú :
1. Về sau, khi cần trình bày quá trình giải (hay bài giải) ta có thể xuất phát từ lời giải
tìm được dưới dạng một dãy các quan hệ để xây dựng bài giải.
2. Lời giải (nếu có) tìm được trong thuật toán trên chưa chắc là một lời giải tốt. Ta có
thể bổ sung thêm cho thuật toán ở trên thuật toán để tìm một lời giải tốt từ một lời
giải đã biết nhưng chưa chắc là tốt. Thuật toán sẽ dựa trên định lý được trình bày tiếp
theo đây.
Định lý . Cho D={ f
1
, f
2
, , fm} là một lời giải của bài toán A → B. Ưùng với mỗi
i=1, ,m đặt Di = { f
1
, f
2
, , fi} , D
0
= ∅ . Ta xây dựng một họ các dãy con Sm, Sm
-1
,
, S
2
2
⊆ S
1
.
(2) Di
-1
∪ Si là một lời giải của bài toán A → B với mọi i=m, , 2, 1.
"+,-./0%1121123 4561n
!"#$#%&'()" *"
(3) Nếu S’
i
là một dãy con thật sự của Si thì Di
-1
∪ S’
i
không phải là một lời
giải của bài toán A → B với mọi i.
(4) S
1
là một lời giải tốt của bài toán A → B.
Từ định lý trên ta có một thuật toán tìm lời giải tốt từ một lời giải đã biết sau đây:
Thuật toán tìm một lời giải tốt từ một lời giải đã biết.
"]/=Ay/u„zu
Q;t•1u•3u888u•Evc5LHf→8
ˆ+WQ;\LHf→
#+]
18 ← t•1u•3u888u•Ev~
38forsEdownto1do
if ‹t†vQHERQ;then
← ‹t†v~
học đơn giản.
Để tìm ra lời giải cho bài toán trước hết ta xét mạng tính toán của các bài toán cơ
học. Mạng tính toán nầy gồm :
1. Tập biến M = { P, m, g,F
hd
, G, F
dh
, k, ∆l, F
ms
, μ, N, F
ht
, v, R, A, α, s, P, W
d
,
W
t
, h, W, H, A
ci
, A
tp
}
2. Các quan hệ:
Trọng lực: f1: P=mg
Lực hấp dẫn : f2:
2
m2*m1
r
GF
hd
=
=mgh
Cơ năng: f11: W=W
t+
W
d
Hiệu suất: f12:
tp
A
H
ci
A
=
Ví dụ : Một lò xo có chiều dài l
0
=10cm, độ cứng k=100N/m. Treo một vật có khối
lượng 5kg vào lò xò ở độ cao 1m, làm lò xo có chiều dài l=20cm. Tính trọng lực P
tác dụng vào vật, thế năng của vật và lực đàn hồi của lò xo. Cho g=10m/s
2
.
Giải:
Theo đề bài ta có tập giả thuyết : A={l
0
, k, m, l, h,g} và tập biến cần tính B={P,W
t
,
F
dh
}.
Áp dụng thuật toán tìm lời giải từ A cho đến khi tìm ra B:
{l
dh
,W
t
}
Ta có lời giài là: {f
1
,f
4
,f
3
,f
9
}
"+,-./0%1121123 4561…
!"#$#%&'()" *"
3.3. Định lý về sự phân tích quá trình giải
ˆaLHf→ :E=Ay/u„z8#:Eb:Y5
Fƒ:DLH,ERZ\OFS`FwAFGc5LHuDE:5
ERQ;\LH8
#:Ebx,5+QER`P,U+:DrERQ;Fƒ
LV8<\ERQ;u:W^iIERU+5HF^A
ERZ\LVr5uTQHLVA:5EHi?^ZkbL
AA5Z5+8 F^uY5x`6E`aU+:DbU+5:Q;
H{ALV]ZxVU+:D6Q;8<w
QlZ5+FP,5ERZPA]LVFG`Fw6Q;H:
OZMF^^S`P,U+:DALVFSU+,VLH8
Định lý Cho { f
1
, f
2
0
(áp dụng f
1
).
bước 2: tính các biến trong tập B
2
\ B
1
(áp dụng f
2
).
"+,-./0%1121123 4561‡
!"#$#%&'()" *"
v.v
bước m: tính các biến trong tập Bm \ Bm
-1
(áp dụng fm).
(2) Từ chứng minh của định lý trên, ta có thể ghi ra một thuật toán để xây dựng dãy
các tập biến { B
1
’, , Bm
-1
’, Bm’} rời nhau cần lần lượt tính toán trong quá trình giải
bài toán (Bi’ = Bi \ Bi
-1
) gồm các bước chính như sau:
Xác định các tập A
0
, A
1
!"#$#%&'()" *"
2.2. Các hàm trong package
• $65L•6‘y†Q65E6z
- TIQ5†Q6OZM:TF\GA8
- <\Z\
o †Q65E6F;FV†Q6T5?XEROZM:
TF\GAyQ+lW+:Y†Q6OZM:T
FY 6 U+ Fw y5E i †Q6
’#f/0f0#%"8`“:EbO:D6E
FSLVW+:Y†Q6zz8
- :w:X
5ZX:TF\GAuENERF\GQH
ER5Z•E
o #F\GA8
o #]+RAc5F\GA8
o #]U+5c5F\GA8
o #]+Nd:5T+XL•6H+RA
• 5‘y„Z6ufZ6z
- TIDEL5F^c5]f
- <\Z\
o „]GU+5
o f]GxkxFGAL5F^8
- :w:X
o #]GxkFGZ+,rfuTQHL5F^c5f
• f}+56y QZufZ6z
- TIDE]G+RAFGZ+,:5rfib
QxQGU+5:
- <\Z\
o 5ZU+5
o f]Gxk
E5Q68
- kbQwith (MangDoiTuongTinhToan;)FSQ55i56
- kbHE:5i56HEc5E5Q68
Cách 2:
- kbQlibname := libname, “đường dẫn đến thư mục chứa
package trên máy”; FS { Fw F; FV 5i56
/5 #+##58Ec5Y58
- kbQwith (MangDoiTuongTinhToan;)FSQ55i56
- kbHE:5i56HEc5E5Q68
9
- kb? m” iV \6/5Q6FSO
5i56Zk+5i56:O:D/5Q68
"+,-./0%1121123 45631
!"#$#%&'()" *"
3. OpenMaple
6/5Q6QHER]HEaQ]:D^S:+,]
HE_W+:YmQ+c5/5Q6:?mQ]:D
”uu•55888
<S^SZkb6/5Q6L:O:DL=x=Q5ZZ
Z5+yH,H?mQ]:D”z
- /5Q6–68Z
- 6/5Q68Z
ŒŒy„Q6Z+:66^S5Ei=EbZ+:66:Oi—E
6LH,z
5+iFƒ5†Q6:H:•6L={xiM=F\G
rQ5ZZ6/5Q6H5yZkF\GFG=^
QH6/z
- =, ER Q c5 6/5Q6 d HE 6/8$+y“ :
E5Q6“z~
- W,iVU+:X6/5Q68E,$6Z+Q~
„+#]HEV:?m”8
5;d5V:V;d?U+5
„:Eu+888
"+,-./0%1121123 45639
!"#$#%&'()" *"
4.3. Hướng dẫn sử dụng chương trình
O:DFGVHHLp?m”85O:D
=/ F^;Zkb^S5dQYX+WFX:d
ER58
4.3.1. Giao diên chương trình
%D15O:D
4.3.2. Hướng dẫn sử dụng
˜o5i6,‘:
- #,6=
YType := Type.TamGiac.TamGiacThuong;
- 4:LQ6E]FXLH=Z:
YProblem := " [chuỗi đề bài] ";
Ví dụ: Problem := "Cho tam giac ABC co cac canh a =3, b= 4, goc A = 60. Tinh
dien tich tam giac ";
"+,-./0%1121123 4563n
!"#$#%&'()" *"
- 6„+iM=WFX
YBeginFunction~
- –„+iVY]Q+
YEndFunction
- %,6ZZ+,VLH
Y Hypothesis := {[các giả thuyết cách nhau bởi
dấu ,]};
'AbHypothesis := {a,b,A};
- 5QEb+xDE
Copyright: Tài liệu đại học ©