Bài giảng Biểu diễn tri thức và giải toán tự động: Phần 2 - Đỗ văn Nhơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST

Báo xấu

46
lượt xem 6
download

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

Bài giảng "Biểu diễn tri thức và giải toán tự động: Phần 2 Mạng suy diễn - tính toán" có nội dung trình bày về một mô hình biểu diễn tri thức được gọi là Mạng suy diễn - tính toán. Các thuật giải cho các vấn đề cơ bản trên mô hình được thiết kế và áp dụng trong một số chương trình cụ thể. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Biểu diễn tri thức và giải toán tự động: Phần 2 - Đỗ văn Nhơn

MAÏNG SUY DIEÃN - TÍNH TOAÙN Ñoã Vaên Nhôn Ñaïi Hoïc Quoác Gia TPHCM Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
GIÔÙI THIEÄU „ Nghieân cöùu caùc phöông phaùp bieåu dieãn vaø xöû lyù tri thöùc laø coát loõi cho vieäc xaây döïng nhöõng chöông trình “thoâng minh”, ñaëc bieät laø caùc heä chuyeân gia vaø caùc heä giaûi toaùn döïa treân tri thöùc. „ Phaàn naøy seõ neâu leân moät moâ hình bieåu dieãn tri thöùc ñöôïc goïi laø Maïng Suy dieãn - Tính toaùn. Caùc thuaät giaûi cho caùc vaán ñeà cô baûn treân moâ hình ñöôïc thieát keá vaø aùp duïng trong moät soá chöông trình cuï theå. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
NOÄI DUNG I. Daãn nhaäp II. Moâ hình Maïng suy dieãn vaø vaán ñeà III. Tìm lôøi giaûi IV. Lôøi giaûi toái öu V. Taäp hôïp sinh VI. Maïng Suy dieãn - Tính toaùn Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
I. Daãn Nhaäp 1.1 Söï caàn thieát cuûa vieäc nghieân cöùu xaây döïng vaø phaùt trieån caùc moâ hình bieåu dieãn tri thöùc cho caùc chöông trình giaûi toaùn thoâng minh. 1.2 Caùc ví duï daãn tôùi söï ñeà xuaát moâ hình Maïng Suy dieãn - Tính toaùn vaø caùc vaán ñeà cô baûn treân moâ hình. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1.1 VAÁN ÑEÀ BIEÅU DIEÃN TRI THÖÙC ° Trong caáu truùc cuûa moät heä giaûi toaùn döïa treân tri thöùc, 2 thaønh phaàn trung taâm laø cô sôû tri thöùc vaø boä suy dieãn döïa treân tri thöùc. ° Ñaõ coù nhieàu phöông phaùp bieåu dieãn tri thöùc vaø suy dieãn ñaõ ñöôïc nghieân cöùu vaø ñeà xuaát. Tuy nhieân moãi phöông phaùp ñeàu chæ theå hieän ñöôïc moät khía caïnh naøo ñoù cuûa tri thöùc vaø coù nhöõng nhöôïc ñieåm nhaát ñònh. Caàn xaây döïng vaø phaùt trieån caùc moâ hình bieåu dieãn tri thöùc giuùp thieát keá vaø caøi ñaët phaàn tri thöùc cuõng nhö phaàn suy dieãn cuûa caùc heä giaûi toaùn döïa treân tri thöùc. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
1.2 CAÙC VÍ DUÏ DAÃN TÔÙI MOÂ HÌNH Trong nhieàu chuû ñeà giaûi toaùn thöôøng gaëp nhöõng vaán ñeà ñaët ra döôùi daïng nhö sau: ° Caàn phaûi thöïc hieän nhöõng tính toaùn hay suy dieãn ra nhöõng yeáu toá caàn thieát naøo ñoù töø moät soá yeáu toá ñaõ ñöôïc bieát tröôùc. ° Ñeå giaûi quyeát vaán ñeà ngöôøi ta phaûi vaän duïng moät soá hieåu bieát (tri thöùc) naøo ñoù veà nhöõng lieân heä giöõa caùc yeáu toá ñang ñöôïc xem xeùt. Nhöõng lieân heä cho pheùp ta coù theå suy ra ñöôïc moät soá yeáu toá töø giaû thieát ñaõ bieát moät soá yeáu toá khaùc. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví duï 1. „ Giaû söû chuùng ta ñang quan taâm ñeán moät soá yeáu toá trong moät tam giaùc, chaúng haïn : 3 caïnh a, b, c; 3 goùc töông öùng vôùi 3 caïnh : , , ; 3 ñöôøng cao töông öùng : ha, hb, hc; dieän tích S cuûa tam giaùc; nöûa chu vi p cuûa tam giaùc; baùn kính ñöôøng troøn noäi tieáp r cuûa tam giaùc. „ Giöõa 12 yeáu toá treân coù caùc coâng thöùc theå hieän nhöõng moái quan heä giuùp ta coù theå giaûi quyeát ñöôïc moät soá vaán ñeà tính toaùn ñaët ra nhö: Tính moät yeáu toá töø moät soá yeáu toá ñöôïc cho tröôùc. Chaúng haïn, tính S khi bieát a, b vaø p. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trong tam giaùc chuùng ta coù theå keå ra moät soá quan heä döôùi daïng coâng thöùc sau ñaây: „ Lieân heä giöõa 3 goùc : + + = „ Ñònh lyù cosin : a2 = b2 + c2 - 2.b.c.cos b2 = a2 + c2 - 2.a.c.cos c2 = a2 + b2 - 2.a.b.cos „ Ñònh lyù Sin: a b c sin sin sin Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
„ Lieân heä giöõa nöûa chu vi vaø 3 caïnh : „ 2.p = a + b + c „ Moät soá coâng thöùc tính dieän tích: „ S = a.ha/2; S = b.hb/2; S = c.hc/2; S = p.r „ Coâng thöùc tính dieän tích theo 3 caïnh (coâng thöùc Heron): S = p(p a)(p b)(p c) Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví duï 2. „ Moät vaät theå coù khoái löôïng m chuyeån ñoäng thaúng vôùi gia toác khoâng thay ñoåi laø a trong moät khoaûng thôøi gian tính töø thôøi ñieåm t1 ñeán thôøi ñieåm t2. Vaän toáùc ban ñaàu cuûa vaät theå laø v1, vaän toác ôû thôøi ñieåm cuoái laø v2, vaø vaän toác trung bình laø v. Khoaûng caùch giöõa ñieåm ñaàu vaø ñieåm cuoái laø s. Löïc taùc ñoäng cuûa chuyeån ñoäng laø f. Ñoä bieán thieân vaän toác giöõa 2 thôøi ñieåm laø v, vaø ñoä bieán thieân thôøi gian laø t. Ngoaøi ra coøn coù moät soá yeáu toá khaùc nöõa cuûa chuyeån ñoäng vaät theå coù theå ñöôïc quan taâm. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ñeå giaûi nhöõng baøi toaùn veà chuyeån ñoäng naày chuùng ta phaûi söû duïng moät soá coâng thöùc lieân heä giöõa caùc yeáu toá cuûa chuyeån ñoäng, chaúng haïn nhö: „ f = m * a; „ v = a* t; „ s = v* t; „ 2*v = v1 + v2; „ v = v2 - v1; „ t = t2 - t1; Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví duï 3. „ Trong hoùa hoïc chuùng ta thöôøng phaûi söû duïng caùc phaûn öùng hoùa hoïc ñeå ñieàu cheá caùc chaát naày töø caùc chaát khaùc. Loaïi vaán ñeà naày cuõng cho ta moät daïng töông töï nhö trong 2 ví duï treân : Cho tröôùc moät soá chaát hoùa hoïc, haõy tìm caùch ñieàu cheá ra moät hay moät soá chaát naøo ñoù. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
II. Moâ hình Maïng Suy dieãn 2.1 Moâ hình. „ ª Giôùi thieäu ª Ñònh nghóa ª Ví duï 2.2 Caùc vaán ñeà cô baûn. „ ª Tính giaûi ñöôïc ª Lôøi giaûi ª Söï boå sung giaû thieát 2.3 Moät soá khaùi nieäm vaø kyù hieäu Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
2.1 Moâ hình ª Giôùi thieäu: „ Nhaän thaáy coù nhieàu vaán ñeà trong caùc lónh vöïc khaùc nhau ñaët ra döôùi daïng moät “maïng” caùc yeáu toá, trong ñoù giöõa caùc yeáu toá coù nhöõng moái lieân heä (hay quan heä) cho pheùp ta coù theå suy ra ñöôïc moät soá yeáu toá naày töø moät soá yeáu toá khaùc. „ Moâ hình maïng suy dieãn - tính toaùn laø moät söï khaùi quaùt daïng tri thöùc treân, vaø coù theå duøng bieåu dieãn tri thöùc vaø thieát keá caùc chöông trình giaûi toaùn töï ñoäng. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
ª Ñònh nghóa ° Quan heä suy dieãn: Cho M = x1,x2,...,xm laø moät taäp hôïp caùc bieán coù theå laáy giaù trò trong caùc mieàn xaùc ñònh D1, D2, ...,Dm. Moãi quan heä suy dieãn R treân M ñöôïc xaùc ñònh bôûi moät (hay moät soá) aùnh xaï coù daïng: „ fR,u,v : Du D v, „ trong ñoù u,v laø caùc boä bieán ñöôïc phaân chia töø boä bieán x = ; Du vaø Dv laø tích cuûa caùc mieàn xaùc ñònh töông öùng cuûa caùc bieán trong u vaø trong v. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
„ Quan heä suy dieãn R(x) coù theå ñöôïc bieåu dieãn bôûi moät (hay moät soá) aùnh xaï fR,u,v vaø ta vieát vaén taét laø: „ f:u v. „ Caùch kyù hieäu treân bao haøm yù nghóa nhö moät luaät suy dieãn: ta coù theå xaùc ñònh hay suy ra ñöôïc caùc bieán thuoäc v khi bieát caùc bieán thuoäc u. „ Quan heä laø ñoái xöùng vaø coù haïng k khi quan heä ñoù giuùp ta coù theå tính ñöôïc k bieán baát kyø töø m-k bieán kia (ôû ñaây x laø boä goàm m bieán < x1,x2,...,xm >). Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví du 1ï: „ Quan heä f giöõa 3 goùc A, B, C trong tam giaùc ABC cho bôûi heä thöùc: A+B+C = . „ Quan heä f giöõa 3 goùc trong moät tam giaùc laø moät quan heä ñoái xöùng coù haïng 1. Quan heä naày bao haøm 3 luaät suy dieãn: „ A, B C „ A, C B „ C, B A Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ví du 2ï: „ Quan heä f giöõ a nöûa chu vi p vôùi caùc ñoä daøi cuûa 3 caïnh a, b, c: 2*p = a + b + c „ cho ta moät quan heä ñoái xöùng haïng 1 treân caùc bieán p, a, b, c. Ví du 3ï: „ Quan heä f giöõ a n bieán x1, x2, ..., xn ñöôïc cho döôùi daïng moät heä phöông trình tuyeán tính coù nghieäm. Trong tröôøng hôïp naày f laø moät quan heä ñoái xöùng coù haïng k baèng haïng cuûa ma traän heä soá cuûa heä phöông trình. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
ª Ñònh nghóa ° Maïng suy dieãn, vieát taét laø MSD, laø moät caáu truùc (M,F) goàm 2 taäp hôïp: ˜ M = x1,x2,...,xn , laø taäp hôïp caùc thuoäc tính hay caùc bieán laáy giaù trò trong caùc mieàn xaùc ñònh naøo ñoù. ˜ F = f1,f2,...,fm , laø taäp hôïp caùc luaät suy dieãn coù daïng: ˜ f : u(f) v(f) trong ñoù u(f) vaø v(f) laø caùc taäp hôïp con khaùc roãng cuûa M sao cho u(f) v(f) = .ø ˜ Kyù hieäu: M(f) = u(f) v(f). Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt
ª Ví duï: Maïng suy dieãn cho moät hình chöõ nhaät. „ Vieäc tính toaùn treân moät hình chöõ nhaät lieân quan ñeán moät soá giaù trò cuûa hình chöõ nhaät nhö sau : „ b1, b2 : hai caïnh cuûa hình chöõ nhaät; „ d : ñöôøng cheùo cuûa hình chöõ nhaät; „ S : dieän tích cuûa hình chöõ nhaät; „ p : chu vi cuûa hình chöõ nhaät; „ trong ñoù moãi bieán ñeàu coù giaù trò laø thuoäc taäp caùc soá thöïc döông. Ñaïi Hoïc Quoá c Gia TP.HCM, 2001 CuuDuongThanCong.com https://fb.com/tailieudientucntt