Các ứng dụng trong mạng tính toán

CHÖÔNG II.- MAÏNG TÍNH TOAÙN (MTT)

I.- MAÏNG TÍNH TOAÙN :

Maïng tính toaùn laø moät daïng bieåu dieãn tri thöùc coù theå duøng bieåu dieãn caùc tri

thöùc veà caùc vaán ñeà tính toaùn vaø ñöôïc aùp duïng moät caùch coù hieäu quaû ñeå giaûi quyeát

caùc vaán ñeà naày. Moãi maïng tính toaùn laø moät maïng ngöõ nghóa chöùa caùc bieán vaø nhöõng

quan heä coù theå caøi ñaët vaø söû duïng ñöôïc cho vieäc tính toaùn. Coù theå noùi raèng maïng tính

toaùn laø moät söï toång quaùt hoaù cuûa kieåu döõ lieäu tröøu töôïng coù khaû naêng töï xaây döïng

caùc haøm duøng cho vieäc toång hôïp thaønh caùc chöông trình.

Trong chöông naày chuùng ta xeùt moät maïng tính toaùn goàm moät taäp hôïp caùc bieán

cuøng vôùi moät taäp caùc quan heä (chaúng haïn caùc coâng thöùc) tính toaùn giöõa caùc bieán.

Trong öùng duïng cuï theå moãi bieán vaø giaù trò cuûa noù thöôøng gaén lieàn vôùi moät khaùi nieäm

cuï theå veà söï vaät, moãi quan heä theå hieän moät söï tri thöùc veà söï vaät.

Trong chöông keá ta seõ xeùt moät maïng tính toaùn döôùi daïng moät maïng caùc “ñoái

töôïng tính toaùn”. Caùch bieåu dieãn tri thöùc tính toaùn döôùi daïng caùc ñoái töôïng naày raát töï

nhieân vaø gaàn guõi ñoái vôùi caùch nhìn vaø nghó cuûa con ngöôøi khi giaûi quyeát caùc vaán ñeà

tính toaùn lieân quan ñeán moät soá khaùi nieäm veà caùc ñoái töôïng, chaúng haïn nhö caùc tam

giaùc, töù giaùc, hình bình haønh, hình chöõ nhaät, v.v... .

1. Caùc quan heä:

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 töông öùng D1,D2,...,Dm. Ñoái vôùi moãi quan heä R ⊆ D1xD2x...xDm treân caùc taäp

hôïp D1,D2,...,Dm ta noùi raèng quan heä naày lieân keát caùc bieán x1,x2,...,xm, vaø kyù hieäu laø

R(x1,x2,...,xm) hay vaén taét laø R(x) (kyù hieäu x duøng ñeå chæ boä bieán < x1,x2,...,xm >).

Quan heä R(x) xaùc ñònh moät (hay moät soá) aùnh xaï :

fR,u,v : Du → Dv,

trong ñoù u,v laø caùc boä bieán vaø u ⊆ x, v⊆ 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.

6

Ta coù theå thaáy raèng quan heä R(x) coù theå ñöôïc bieåu dieãn bôûi moät aùnh xaï fR,u,v vôùi u ∪

v = x, vaø ta vieát :

fR,u,v : u → v,

hay vaén taét laø:

f : u → v.

Ñoái vôùi caùc quan heä duøng cho vieäc tính toaùn, caùch kyù hieäu treân bao haøm yù nghóa nhö

laø moät haøm: ta coù theå tính ñöôïc giaù trò cuûa caùc bieán thuoäc v khi bieát ñöôïc giaù trò cuûa

caùc bieán thuoäc u.

Trong phaàn sau ta xeùt caùc quan heä xaùc ñònh bôûi caùc haøm coù daïng:

f : u → v,

trong ñoù u ∩ v = ∅ (taäp roãng). Ñaëc bieät laø caùc quan heä ñoái xöùng coù haïng (rank) baèng

moät soá nguyeân döông k. Ñoù laø caùc quan heä maø 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 >). Ngoaøi ra, trong tröôøng hôïp

caàn noùi roõ ta vieát u(f) thay cho u, v(f) thay cho v. Ñoái vôùi caùc quan heä khoâng phaûi laø

ñoái xöùng coù haïng k, khoâng laøm maát tính toång quaùt, ta coù theå giaû söû quan heä xaùc ñònh

duy nhaát moät haøm f vôùi taäp bieán vaøo laø u(f) vaø taäp bieán ra laø v(f); ta goïi loaïi quan heä

naày laø quan heä khoâng ñoái xöùng xaùc ñònh moät haøm, hay goïi vaén taét laø quan heä khoâng

ñoái xöùng.

Ta coù theå veõ hình bieåu dieãn cho caùc quan heä ñoái xöùng vaø caùc quan heä khoâng ñoái

xöùng (xaùc ñònh moät haøm) nhö sau:

Hình 1.1. Quan heä ñoái xöùng coù haïng k

7