ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH

TÌM HIỂU MẠNG TÍNH TOÁN
VÀ CÁC ĐỐI TƯỢNG TÍNH TOÁN
XÂY DỰNG ỨNG DỤNG DEMO
Bộ môn : Biểu Diễn Tri Thức
GVHD : TS. Đỗ Văn Nhơn
Thực hiện : Nguyễn Chí Toàn
CH1301065
Thành phố Hồ Chí Minh - Tháng 3 Năm 2014
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN MỤC LỤC
Phần I: Biểu Diễn Tri Thức
I. Khái niệm tri thức 1
II. Các phương pháp biểu diễn tri thức 1
1. Bộ ba đối tượng – Thuộc tính – Giá trị 2
2. Logic mệnh đề 2
3. Logic vị từ 2
4. Mạng ngữ nghĩa 3
5. Frame 3

Tri thức sự kiện: là các khẳng định về một sự kiện, khái niệm nào đó (trong phạm vi xác đ.
Các định luật vật lý, toán học … thường được xếp vào loại này. Ví dụ: mặt trời mọc ở đằng
đông, tam giác đều có ba góc 60
0…
)
Tri thức thủ tục: thường dùng để diển tả phương pháp, các bước cần tiến hành, trình tự
hay ngắn gọn là các giải quyết một vấn đề. Thuật toán hay thuật giải là một dạng của tri thức
thủ tục
Tri thức mô tả: cho biết một đối tượng, sự kiện, vấn đề, khái niệm… được thấy, cảm nhận,
cấu tạo như thế nào ( một cái bàn thường có bốn chân, con người có hai tay, hai mắt …)
Tri thức heuristic: là một dạng tri thức cảm tính. Các tri thức thuộc loại này thường có
dạng ước lượng, phỏng đoán, và được hình thành thông qua kinh nghiệm
Tri thức có câu trúc: mô tả tri thức theo cấu trúc. Loại tri thức này mô tả mô hình tổng
quan hệ thống theo quan điểm của chuyên gia, bao gồm khái niệm, khái niệm con, và các đối
tượng: diễn tả chức năng và mối liên hệ giữa các tri thức dựa theo câu trúc xác định.
II. Các phương pháp biểu diễn tri thức
Các phương pháp diễn tả và tổ chức tri thức trong máy tính cho các hệ thông tin có tính
chất trí tuệ để máy có thể tiến hành các phép lập luận tự động. Trong trí tuệ nhân tạo, các
phương pháp BDTT thường được sử dụng như lôgic tân từ, mạng ngữ nghĩa, biểu diễn khung,
luật dẫn.
1. Bộ ba đối tượng - Thuộc tính – giá trị
Trang 4
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
Cơ chế tổ chức nhận thức của con người thường được xây dựng dựa trên các sự kiện
(fact), xem như các đơn vị cơ bản nhất. Một sự kiện là một dạng tri thức khai báo. Nó
cung cấp một số hiểu biết về một biến cố hay một vấn đề nào đó.
Một sự kiện có thể được dùng để xác nhận giá trị của một thuộc tính xác định của
một vài đối tượng. Ví dụ mệnh đề “quả bóng màu đỏ“ xác nhận “đỏ” là giá trị thuộc
tính “màu” của đối tượng “quả bóng”. Kiểu sự kiện này được gọi là bộ ba Đối tượng -

MSHV: CH1301065
Như vậy để biểu diễn vị của các trái cây, các mệnh đề sẽ được viết lại thành :
Cam có vị Ngọt ⇒ Vị (Cam, Ngọt), Cam có màu Xanh ⇒ Màu (Cam, Xanh)
4. Mạng ngữ nghĩa
Phương pháp mạng ngữ nghĩa biểu diễn tri thức dưới dạng một đồ thị, trong đó đỉnh là các
đối tượng (khái niệm) còn các cung cho biết mối quan hệ giữa các đối tượng (khái niệm) này.
Tuy mạng ngữ nghĩa là một kiểu biểu diễn trực quan đối với con người nhưng khi đưa vào
máy tính, các đối tượng và mối liên hệ giữa chúng thường được biểu diễn dưới dạng những
phát biểu động từ (như vị từ). Hơn nữa, các thao tác tìm kiếm trên mạng ngữ nghĩa thường
khó khăn (đặc biệt đối với những mạng có kích thước lớn). Do đó, mô hình mạng ngữ nghĩa
được dùng chủ yếu để phân tích vấn đề. Sau đó, nó sẽ được chuyển đổi sang dạng luật hoặc
frame để thi hành hoặc mạng ngữ nghĩa sẽ được dùng kết hợp với một số phương pháp biểu
diễn khác.
5. Frame
Frame là một cấu trúc dữ liệu chứa đựng tất cả những tri thức liên quan đến một đối tượng
cụ thể nào đó. Frames có liên hệ chặt chẽ đến khái niệm hướng đối tượng. Ngược lại với các
phương pháp biểu diễn tri thức đã được đề cập đến, frame "đóng gói" toàn bộ một đối tượng,
tình huống hoặc cả một vấn đề phức tạp thành một thực thể duy nhất có cấu trúc. Một frame
bao hàm trong nó một khối lượng tương đối lớn tri thức về một đối tượng, sự kiện, vị trí, tình
huống hoặc những yếu tố khác. Do đó, frame có thể giúp ta mô tả khá chi tiết một đối tượng.
Frame thường được dùng để biểu diễn những tri thức "chuẩn" hoặc những tri thức được
xây dựng dựa trên những kinh nghiệm hoặc các đặc điểm đã được hiểu biết cặn kẽ. Bộ não
của con người chúng ta vẫn luôn "lưu trữ" rất nhiều các tri thức chung mà khi cần, chúng ta có
thể "lấy ra" để vận dụng nó trong những vấn đề cần phải giải quyết. Frame là một công cụ
thích hợp để biểu diễn những kiểu tri thức này.
6. Biểu diễn tri thức bằng luật dẫn
Đây là một kiểu biểu diễn tri thức có cấu trúc. Ý tưởng cơ bản là tri thức có thể được cấu
trúc bằng một cặp điều kiện & hành động : "NẾU điều kiện xảy ra THÌ hành động sẽ được thi
hành". Chẳng hạn : NẾU đèn giao thông là đỏ THÌ bạn không được đi thẳng, NẾU máy tính
đã mở mà không khởi động được THÌ kiểm tra nguồn điện, v.v…

R5 : E ∧ K  B { A, B, E, H, K }
R2 : B  D { A, B, D, E, H, K }
R6 : D ∧ E ∧ K  C { A, B, C, D, E, H, K }
Trang 7
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
Suy diễn lùi : là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu, ta tìm kiếm
các sự kiện đã "sinh" ra sự kiện này. Một ví dụ thường gặp trong thực tế là xuất phát từ các
tình trạng của máy tính, chẩn đoán xem máy tính đã bị hỏng hóc ở đâu. Ví dụ:
Tập các sự kiện :
Ổ cứng là "hỏng" hay "hoạt động bình thường"
Hỏng màn hình.
Lỏng cáp màn hình.
Tình trạng đèn ổ cứng là "tắt" hoặc "sáng"
Có âm thanh đọc ổ cứng.
Tình trạng đèn màn hình "xanh" hoặc "chớp đỏ"
Không sử dụng được máy tính.
Điện vào máy tính "có" hay "không".
Tập các luật :
R1. Nếu ( (ổ cứng "hỏng") hoặc (cáp màn hình "lỏng")) thì không sử dụng được máy
tính.
R2. Nếu (điện vào máy là "có") và ( (âm thanh đọc ổ cứng là "không") hoặc tình trạng
đèn ổ cứng là "tắt")) thì (ổ cứng "hỏng").
R3. Nếu (điện vào máy là "có") và (tình trạng đèn màn hình là "chớp đỏ") thì (cáp màn
hình "lỏng").
Để xác định được các nguyên nhân gây ra sự kiện "không sử dụng được máy tính", ta phải
xây dựng một cấu trúc đồ thị gọi là đồ thị AND/OR như sau :
Cơ chế suy diễn của suy diễn lùi
Như vậy là để xác định được nguyên nhân gây ra hỏng hóc là do ổ cứng hỏng hay cáp màn
hình lỏng, hệ thống phải lần lượt đi vào các nhánh để kiểm tra các điều kiện như điện vào máy

như đáp ứng đầy đủ các giả thiết cần thiết.
Thuật toán đơn giản dễ cài đặt cho nên việc bảo
trì hệ thống tương đối đơn giản.
Có thể xây dựng hệ thống suy luận và giải thích
một cách rõ ràng và dễ hiểu.
Không giải được các tri thức
phức tạp, lưu trữ khó khăn
và nhập nhằng khi quản lý.
Đồng thời việc xây dựng lại
thuật toán là một việc tương
đối khó khăn  bảo trì lại
toàn bộ hệ thống.
Frame Có sức mạnh diễn đạt tốt, dễ cài đặt các thuộc
tính cho các slot cũng như các mối liên hệ, dễ
dàng tạo ra các thủ tục chuyên biệt hóa, dễ đưa
vào các thông tin mặc định và dễ thực hiện các
thao tác phát hiện các giá trị bị thiếu sót.
Khó lập trình, khó suy diễn,
thiếu phần mềm hỗ trợ.
PHẦN II: MẠNG TÍNH TOÁN VÀ CÁC ĐỐI TƯỢNG TÍNH TOÁN
I. Mạng tính toán
Trang 9
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
Mạng tính toán là một dạng biểu diễn tri thức có thể dùng biểu diễn các tri thức về các vấn
đề tính toán và được áp dụng một cách có hiệu quả để giải một số dạng bài toán. Mỗi mạng
tính toán là một mạng ngữ nghĩa chứa các biến và những quan hệ có thể cài đặt và sử dụng
được cho việc tính toán. Chúng ta xét một mạng tính toán gồm một tập hợp các biến cùng với
một tập các quan hệ (chẳng hạn các công thức) tính toán giữa các biến. Trong ứng dụng cụ thể
mỗi biến và giá trị của nó thường gắn liền với một khái niệm cụ thể về sự vật, mỗi quan hệ thể

hay không?
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?
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 của bài toán.
2. Mạng tính toán và các ký hiệu:
Như đã nói ở trên, ta sẽ xem xét các mạng tính toán bao gồm một tập hợp các biến M và
một tập hợp các quan hệ (tính toán) F trên các biến. Trong trường hợp tổng quát có thể viết:
M = {x
1
,x
2
, ,x
n
},
F = {f
1
,f
2
, ,f
m
}.
Đối với mỗi f ∈ F, ta ký hiệu M(f) là tập các biến có liên hệ trong quan hệ f. Dĩ nhiên M(f)
là một tập con của M: M(f) ⊆ M. Nếu viết f dưới dạng:
f : u(f) → v(f)
thì ta có M(f) = u(f) ∪ v(f).
Ví dụ 1: Cho tam giác ABC có cạnh a và 2 góc kề là β, γ được cho trước. Tính diện tích S
của tam giác.

f
3
:
c
sin
b
sin
γ β
=
f
4
:
a
sin
c
sin
α γ
=
f
5
: p = (a+b+c) /2 f
6
: S = a.h
a
/ 2
f
7
: S = b.h
b
/ 2 f

2
f
 →
{a, β, γ, α, b}
3
f
 →
{a, β, γ, α, b, c}
5
f
 →
{a, β, γ, α, b, c, p}
9
f
 →
{a, β, γ, α, b, c, p, S}.
Có thể nhận thấy rằng lời giải nầy không phải là lời giải tốt vì có bước tính toán thừa,
chẳng hạn là f
5
. Thuật toán tìm lời giải tốt nhất sẽ lọc ra từ lời giải trên một lời giải tốt là {f
1
,
f
2
, f
9
}:
{a, β, γ}
1
f

thời việc xây dựng lại thuật toán là một việc tương đối khó khăn  phải bảo trì lại toàn
bộ hệ thống.
• Đối với các bài toán mà sử dụng nhiều các đối tượng tính toán bài toán trở nên phức tạp,
việc giải quyết bài toán bằng mạng tính toán trở nên khó khăn cho người lập trình.
Trang 12
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
II. Mạng các đối tượng tính toán
Cấu trúc của mạng tính toán bao gồm một tập các biến M và một tập các quan hệ F thể hiện
tri thức về sự liên hệ tính toán giữa các biến trong mạng. Bây giờ nếu ta xét một bài toán gồm
có hai tam giác có một số liên hệ với nhau, chẳng hạn cạnh a của tam giác nầy bằng cạnh b
của tam giác kia, thì ta có một mạng tính toán bao gồm 2 “đối tượng” có cùng loại (đều là tam
giác). Mỗi đối tượng trong trường hợp nầy có thể được thay thế bởi một mạng tính toán tương
ứng, và từ đó ta được một mạng tính toán trong đó có 2 bộ phận (hay 2 mạng con) có cùng
loại.
Hình 1.1. Mạng tính toán gồm 2 tam giác.
Hình 1.2. Mạng tính toán gồm 2 bộ phận,
mỗi bộ phận là mạng tính toán của 1 tam giác.
1. Mạng con, đối tượng tính toán
Một mạng tính toán (M,F) được gọi là một mạng con của mạng tính toán (M’,F’) nếu thỏa
các điều kiện sau đây :
Trang 13
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
(1) M ⊆ M’,
(2) F ⊆ F’,
(3) M(f) ⊆ M’(f), với mọi f∈ F.
Trong trường hợp nầy, ta còn nói (M,F) là một sự thu hẹp của mạng (M’,F’) hay (M’,F’) là
một sự mở rộng của mạng (M,F); ký hiệu : (M,F) ≤ (M’,F’).
Liên quan đến việc mở rộng và thu hẹp mạng tính toán, ta có một số tính chất được ghi

MSHV: CH1301065
Một mạng tính toán còn được xem là một đối tượng tính toán. Theo quan niệm nầy, từ
bên ngoài phạm vi của mạng tính toán ta xem nó như một tổng thể bao gồm một số yếu tố ta
quan tâm và các yếu tố khác (xem như phần nội bộ bên trong của đối tượng) mà ta ít quan tâm
hơn. Trong hình 1.1 TAM GIAC 1 là một đối tượng tính toán mà trong mạng gồm 2 tam giác
ta đặc biệt quan tâm đến cạnh a của nó, còn các yếu tố khác của TAM GIAC 1 như cạnh b,
cạnh c, diện tích S, nửa chu vi p, v.v tạm thời chưa được quan tâm.
Như vậy đối với mỗi đối tượng tính toán O, có một tập biến và một tập các quan hệ tương
ứng. Tập các biến và tập các quan hệ của đối tượng O lần lượt được ký hiệu là M(O), F(O).
Từ đó ta có thể viết :
O = ( M(O),F(O) ).
Hình vẽ dưới đây biểu diễn cho một đối tượng O, trong đó tập {x
1
, , x
k
} ⊆ M(O) là một tập
biến đang được quan tâm xem xét của đối tượng O.
Hình 1.3. Đối tượng tính toán O.
Ngoài ra đối tượng tính toán, giả sử là O, còn có khả năng đáp ứng lại một số thông điệp yêu
cầu từ bên ngoài. Trong các khả năng đó của đối tượng tính toán ta có thể kể đến những điểm
sau đây :
(1) Xác định bao đóng (trong đối tượng O) của một tập A ⊆ M(O).
(2) Xác định tính giải được của một bài toán A → B,
trong đó A ⊆ M(O), B ⊆ M(O).
(3) Tìm một lời giải tốt cho bài toán A → B trên mạng (M(O),F(O)),
trong đó A ⊆ M(O), B ⊆ M(O).
2. Mạng các đối tượng tính toán :
Trong mục nầy trình bày một số khái niệm về mạng các đối tượng tính toán. Trong đó có
khái niệm về quan hệ giữa các đối tượng. Ta gọi một quan hệ f giữa các biến của các đối
Trang 15

2
Bây giờ ta xét một bài toán mà việc tính toán có liên quan đến một số đối tượng tính toán
và giữa các đối tượng nầy có những quan hệ nhất định. Việc giải bài toán sẽ dựa trên một
mạng các đối tượng tính toán. Mạng các đối tượng tính toán bao gồm một tập hợp các đối
tượng tính toán :
O = {O
1
,O
2
, , O
n
}
và một tập hợp các quan hệ giữa các đối tượng :
F = {f
1
,f
2
, , f
m
}.
Đặt :
M(f
i
) = tập hợp các biến có liên quan với nhau bởi quan hệ f
i.
M(F) =
M(f
i
i 1
m

các đối tượng tính toán. Ngoài ra ta còn có :
M(O
i
i 1
n
)
=

⊇ M ⊇
M(f
i
i 1
m
)
=

,
hay M(O) ⊇ M ⊇ M(F).
Ví dụ sau đây sẽ minh họa cho các ký hiệu ở trên.
Ví dụ 2 : Cho tam giác cân ABC, cân tại A, và cho biết trước góc đỉnh α, cạnh đáy a.
Bên ngoài tam giác có hai hình vuông ABDE và ACFG. Tính độ dài EG.
Bài toán có dạng một mạng các đối tượng tính toán bao gồm :
1. Bốn đối tượng :
O
1
: tam giác cân ABC,
O
2
: tam giác AEG,
O

.a // cạnh b của tam giác ABC = cạnh của hình vuông ACFG
f
3
: O
2
.b = O
4
.a // cạnh b của tam giác AEG = cạnh của hình vuông ACFG
f
4
: O
2
.c = O
3
.a // cạnh c của tam giác AEG = cạnh của hình vuông ABDE
f
5
: O
1
.α + O
2
.α = 180
Trong ví dụ nầy ta có :
M(f
1
) = { O
1
.c , O
3
.a },

.b, O
1
.c, O
1
.α, O
2
.b, O
2
.c, O
2
.α, O
3
.a, O
4
.a, O
2
.a}.
Lưu ý rằng O
2
.a (cạnh EG của tam giác AEG) là biến cần tính.
Trang 18
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
PHẦN III. CÀI ĐẶT ỨNG DỤNG DEMO
I. Giới thiệu ứng dụng:
Dựa trên những kiến thức về mạng tính toán và đối tượng tính toán đã nêu trên, để cài đặt
ứng dụng giải bài toán hình học về hình chữ nhật.
Về mặt tính toán, chúng ta có thể xem hình chữ nhật là một mạng tính toán (hay một đối
tượng tính toán) bao gồm các biến ghi nhận giá trị của các yếu tố trong hình chữ nhật, và các
quan hệ là các công thức thể hiện mối liên hệ tính toán giữa các yếu tố đó.

}, hệ thống luật dẫn của mạng tính toán
• Name: tên của mạng tính toán
Các phương thức của mạng tính toán:
• Phương thức đọc file tri thức Rules.txt, đưa tri thức tam giác vào đối tượng
MangTinhToan
• Thuật giải suy diễn tiến để suy diễn các luật trong F, tìm ra lời giải từ những giả thiết
cho trước
Thiết kế class MangCacDoiTuongTinhToan gồm các thành phần sau:
• O = {O
1
,O
2
, ,O
n
}, các đối tượng tính của mạng các đối tượng tính toán
• R = {f
1
,f
2
, ,f
m
}, hệ thống luật dẫn của mạng các đối tính toán
• M = {O
1
.a,O
2
.b, ,O
n
.e}, các thành phần quan hệ với nhau của các đối tượng tính toán
Trang 19

có dạng p1˄p2˄….˄p
n
=> q sao cho p
j
∈T, ∀
J
= nghĩa là left(r
i
) ∈T thì T = T +
right(r
i
). Quá trình này lâp lại cho đến kkhi G ⊂ T hoặc không có luật nào sinh ra thêm sự kiện
mới
Giải thuật:
Input: -Tập luật Rule ={r1,r2,…,rm}
-GT, KL
Output: Thông báo “thành công” nếu GT->KL
Ngược lại thông báo không thành công”
Procedure suydientien;
Begin
T := F;
S := Loc(Rule,T); { S: là tập luật có dạng p1˄p2˄….˄p
n
=> q sao cho cho p
j

∈
T,
∀
J

mãn thi sự kiện nằm trong phần kết luận được xem là sự kiện được suy ra. Nếu sự kiện này là
sự kiện mới (không có trong bộ nhớ làm việc) thì nó được đưa vào bộ nhớ làm việc. Qúa trình
trên cứ lặp lại cho đên khi nào không có luật nào sinh ra sự kiện mới.
Trang 21
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
Qúa trình suy diễn tiến không định hướng tới giải quyết một vấn đề nào cả, không hướng
tới tìm câu trả lời cho một câu hỏi nào cả. Suy diễn tiến chỉ là quá trình suy ra các sự kiện mới
từ các sự kiện có trong bộ nhớ làm việc
2. Cài Thuật toán tìm một lời giải tốt từ một lời giải đã biết:
Nhập : Mạng cc đối tượng tính tốn (O,F),
lời giải
{
t
1
, t
2
, , t
m
}
của bi tốn A
→
B.
Xuất : lời giải tốt cho bi tốn A
→
B
Thuật tóan :
1. D
←


IV. Hình ảnh demo của chương trình
1. Giải bài toán tam giác sử dụng mạng tính toán
Quy tắc nhập số liệu để tính giải bài toán hình chữ nhật là:
nhập trực tiếp số liệu các cạnh a, b, dc, r
2.Xử lý và xuất ra kết quả
Khi đã nhập thông số,bước tiếp theo ta chọn thông số cần tính giả xử dc => click button Giải
Trang 23
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
V. Kết Luận
Biễu diển tri thức là một lĩnh vực quan trọng, làm cơ sở để xây dựng các hệ chuyên gia, hệ
hỗ trợ ra quyết định, hệ hỗ trợ chẩn đoán, mạng tính toán …
Chương trình demo trên là một minh họa đơn giản về mạng tính toán, sử dụng phương
pháp biểu diễn tri thức dưới dang text có định dạng để giải quyết vấn đề giải bài toán tam giác.
Tuy nhiên chương trình còn hạn chế ở khâu nhập đề bài, chương trình yêu câu phải nhập
đính khuôn dạng đã quy định trước thì mới có thể giải được.
Trang 24
GVHD: PGS.Ts Đỗ Văn Nhơn Họ và Tên: Nguyễn Chí Toàn
MSHV: CH1301065
Tài liệu tham khảo
Bài giảng Mạng Các Đối Tượng Tính Toán – TS. Đỗ Văn Nhơn
Bài giảng Biểu Diễn Tri Thức và Ứng Dụng – TS. Đỗ Văn Nhơn
Slide bài giảng Mạng Suy Diễn Tính Toán – TS. Đỗ Văn Nhơn
Ứng dụng Mạng Tính Toán Trong Một Số Bài Toán Hình Học – TS. Đỗ Văn Nhơn
Mạng Tính Toán Và Ứng Dụng – TS. Đỗ Văn Nhơn
Model for Knowledge Bases of Computational Objects – TS. Đỗ Văn Nhơn
A Knowledgeable Model - Network of C-Objects – TS. Đỗ Văn Nhơn
Demo tham khảo source code giải tam giác />bai-toan-tam-giac-bang-mo-hinh-he-luat-dan-dung-thuat-giai-suy-dien-tien-va-suy-dien-lui-
part-1/
Trang 25