CHƯƠNG III. MẠNG CÁC ĐỐI TƯNG TÍNH TOÁN
I.- MẠNG CÁC ĐỐI TƯNG TÍNH TOÁN :
Trong chương trước chúng ta xét một 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. Một ví dụ điển hình về một mạng tính toán đã nêu trong chương II
là mạng tính toán của một tam giác. 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.
26
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 :
(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 trong mệnh đề sau :
Mệnh đề 1.1.
(1) Cho (M,F) là một thu hẹp của mạng tính toán (M’,F’). Giả sử A → B là
một bài toán trên mạng (M’,F’), và A ⊆ M, B ⊆ M. Khi đó, ta có thể xem A → B
cũng là một bài toán trên mạng thu hẹp (M,F). Nếu bài toán là giải được trên mạng
thu hẹp (M,F) thì cũng giải được trên mạng ban đầu (M’,F’). Hơn nữa lời giải của bài
toán trên mạng thu hẹp cũng là lời giải trên mạng ban đầu.

(2) Cho mạng tính toán (M,F), M1 ⊆ M. Đặt :
F1 = {f ∈ F  M(f) ⊆ M}.
Ta có (M1,F1) là một thu hẹp của mạng (M,F).
(3) Cho mạng tính toán (M,F), F1 ⊆ F. Đặt :
M1 M(f)
f F1
=
∈

.
Ta có (M1,F1) là một thu hẹp của mạng (M,F).
(4) Cho mạng tính toán (M,F), B ⊆ M. Đặt :
F(B) = {f ∈ F  M(f) ∩ B ≠ ∅},
M(B) =
M(f)
f F(B)∈

Ta có (M(B),F(B)) là một thu hẹp của mạng (M,F).
Ghi chú : Lời giải tốt của một bài toán trên mạng thu hẹp không nhất thiết là tốt
trên mạng lớn hơn vì nó chỉ sử dụng “kiến thức” gồm một tập quan hệ ít hơn. Tuy
nhiên, có thể nói lời giải đó là tốt trong một phạm vi tri thức giới hạn.
27
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).
28
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 tượng tính toán là một quan hệ giữa các đối tượng đó. Quan hệ nầy
cho phép ta tính được một hay nhiều biến của các đối tượng từ một số biến khác.
Ví dụ 1: Giả sử có 2 đối tượng O
1
, O
2
. Trong các biến của đối tượng O
1

có một
biến, ký hiệu a, có liên hệ f với một biến của đối tượng O
2
, ký hiệu b, được xác đònh
bởi hệ thức :
a - b = 0.
Chính xác hơn, ta viết hệ thức trên là :
O
1
.a - O
2
.b = 0.
Như vậy f là một quan hệ giữa 2 đối tượng O
1
và O
2
. Đây là một quan hệ đối xứng có
hạng bằng 1.
Hình 1.4. f là một quan hệ giữa O
1
và O
2
Ví dụ 2: Giả sử có 3 đối tượng O
1
, O
2
, O
3
. Giữa biến a của O
1

, biến a và b của
O
2
, biến c của O
3
có một quan hệ f xác đònh bởi hệ thức:
O
3
.c = O
1
.a + O
2
.a - O
2
.b.
Ta có f là một quan hệ giữa các đối tượng O
1
, O
2
, O
3
.
29
Hình 1.5. f là một quan hệ giữa O
1
, O
2
, O
3
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
)
=


.
M(O) =
M(O
i
i 1
n
)
=

.
M là tập hợp những biến được xem xét trên mạng, kể cả các biến thuộc
các tập M(f
i
).
M
i
= M ∩ M(O
i
),i=1,2, ... , m.
Theo cách ký hiệu trên, M
i
là tập hợp những biến của đối tượng O
i
được xem xét
trên mạng 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
)
=

,
30
hay M(O) ⊇ M ⊇ M(F).
Ví dụ sau đây sẽ minh họa cho các ký hiệu ở trên.
Ví dụ 3 : 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
3
: hình vuông ABDE,
O
4

: hình vuông ACFG,
trong đó mỗi tam giác có các biến: a, b, c, α, β, γ, h
a
, h
b
, h
c
, S, p, R, r, ...,
mỗi hình vuông có các biến: a (cạnh), c (đường chéo), S (diện tích), ...
2. Các quan hệ giữa các đối tượng :
f
1
: O
1
.c = O
3
.a // cạnh c của tam giác ABC = cạnh của hình vuông ABDE
f
2
: O
1
.b = O
4
.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 },
M(f
2
) = { O
1
.b , O
4
.a },

M(f
3
) = { O
2
.b , O
4
.a },
M(f
4
) = { O
2
.c , O
3
.a },
M(f
5
) = { O
1
.α , O
2
.α },
31
M = { O
1
.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.
II.- VẤN ĐỀ TRÊN MẠNG CÁC ĐỐI TƯNG:
Cho một mạng các đối tượng tính toán (O,F), trong đó O là tập hợp các đối
tượng tính toán và F là tập hợp các quan hệ giữa các đối tượng. Xét một tập hợp biến
M trên mạng :
M(O) ⊇ M ⊇ M(F).
Giả sử có một tập biến A ⊆ M đã được xác đònh (tức là tập gồm các biến đã biết
trước giá trò), và B là một tập biến bất kỳ trong M.
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 và các đối tượng
thuộc O 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.
32

Tương tự như đối với một mạng tính toán, bài toán xác đònh B từ A trên mạng (O,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 bài toá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.
Chúng ta có thể nhận thấy rằng nếu gộp lại tất cả các biến của các đối tượng
O
i
(i=1,2,...,n) thành một tập biến lớn và gộp tất cả các quan hệ nội bộ của từng đối
tượng cùng với các quan hệ giữa các đối tượng thành một tập các quan hệ thì ta có
một mạng tính toán như đã xét trong chương II. Như vậy nếu đặt :
M (O,F) = M(O),
F (O,F) =
F(O F
i
i 1
n
)
=
 
,
thì (M, F ) là một mạng tính toán; mạng nầy được gọi là mạng tính toán tương
ứng của mạng các đối tượng tính toán (O,F).
Bài toán A → B trên mạng các đối tượng tính toán (O,F) được gọi là giải được
khi bài toán đó là giải được trên mạng tính toán tương ứng (M, F ) , hay nói
chung ta có thể tính toán được giá trò các biến thuộc B xuất phát từ giả thiết A. Tất
nhiên một lời giải của bài toán trên trên mạng (M, F ) cũng được xem là một lời
giải trên mạng các đối tượng. Tuy nhiên lời giải đó có thể có chứa các quan hệ nội
bộ bên trong của các đối tượng mà nhiều khi ta không cần quan tâm chi tiết. Do đó ta

gọi một lời giải như thế là một lời giải chi tiết của bài toán trên mạng các đối tượng
tính toán. Chẳng hạn như trong tình huống nêu trong ví dụ sau đây:
Ví dụ 1 : Giả sử đang xét bài toán A → B trên mạng các đối tượng (O,F), và
khi giải bài toán trên mạng tính toán (M, F ) tương ứng ta tìm được một lời giải
gồm 10 quan hệ (thuộc F ) là {f
1
, f
2
, ..., f
10
}, trong đó ta có:
{f
1
, f
4
, f
7
, f
8
, f
10
} ⊆ F,
33