Cài đặt mạng tính toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (52.04 KB, 6 trang )
CHƯƠNG V. CÀI ĐẶT MẠNG TÍNH TOÁN
Trong chương nầy sẽ nêu lên một cách cài đặt mạng tính toán và mạng các
đối tượng tính toán. Ngoài ra chúng ta cũng tiến hành cài đặt mạng tính toán cho một
ứng dụng cụ thể : chương trình giải tam giác, giải tứ giác, và giải một số bài toán
khác.
I.- CÀI ĐẶT MẠNG TÍNH TOÁN :
Chúng ta biết rằng mạng tính toán gồm một tập hợp các biến và tập hợp các
quan hệ. Mỗi quan hệ đối xứng được xác đònh bởi một tập hợp con của tập tất cả các
biến trong mạng tính toán và hạng của quan hệ; ở đây tập hợp con các biến chính là
tập hợp các biến có liên hệ trong quan hệ đang nói. Mỗi quan hệ không đối xứng
được xác đònh bởi tập hợp các biến có liên hệ và tập hợp các biến phụ thuộc, tức là
các biến sẽ tính ra được từ các biến kia. Như vậy để cài đặt mạng tính toán, trước hết
ta phải nêu lên cách cài đặt các tập hợp.
1. Cài đặt tập hợp :
Giả sử ta cần phải thực hiện các phép tính trên các tập hợp con của một tập
hợp X, chẳng hạn X là tập hợp các tên biến hoặc là tập hợp các mẫu tin. Việc cài đặt
lưu trữ các tập hợp và thực hiện các phép tính tập hợp có thể được làm như sau :
- Ghi nhận các phần tử X trong một danh sách. Như vậy mỗi phần tử x ∈ X có
một số thứ tự xác đònh (số thứ tự nầy có thể tính từ 0 hoặc tính từ 1 tùy vào sự thuận
tiện của ngôn ngữ lập trình sử dụng trong cài đặt).
- Mỗi tập hợp con A của X sẽ được biểu diễn bởi một dãy bit, mỗi bit ứng với
một số thứ tự hay ứng với một phần tử x ∈ X để ghi nhận thông tin cho biết phần tử
x có thuộc tập con A hay không. Ký hiệu bit tương ứng với số thứ tự i (ứng với một
phần tử x) trong dãy bit A là A(i), ta có thể qui ước rằng :
81
A(i)
1 khi x X
khi x X
=
∈
∉
0
Theo cách như thế, tập hợp rỗng sẽ được biểu bởi dãy bit 0, tập X được biểu bởi dãy
bit 1, tập hợp chỉ có phần tử đầu tiên được biểu diễn bởi dãy bit với bit đầu tiên là 1
và các bit còn lại là 0.
- Các phép tính tập hợp như giao, hội, hiệu, lấy phần bù sẽ tương ứng với các
thao tác trên các bit.
- Phép kiểm tra một phần tử có số thứ tự là i có thuộc một tập hợp A hay
không tương ứng với việc xác đònh xem bit i của dãy bit A là 1 hay là 0.
- Việc thêm hoặc bớt ra phần tử có số thứ tự i từ tập hợp A tương ứng với
việc gán cho bit i trong dãy bit A là 1 hoặc là 0.
Tóm lại theo cách trên chúng ta có thể dễ dàng cài đặt các phép tính tập hợp
sẽ được sử dụng trong việc cài đặt các thuật giải dùng trong mạng tính toán.
2. Cài đặt mạng tính toán :
Để cài đặt mạng tính toán chúng ta đưa ra cách để ghi nhận đầy đủ thông tin
cần cho việc xử lý về tập hợp các biến, tập hợp các quan hệ.
Đối với các biến của mạng tính toán, ta cần có một số biến trong cài đặt để
biểu diễn chúng :
n số biến trong mạng tính toán
s danh sách tên biến
x danh sách các biến ghi nhận giá trò của từng biến trong mạng tính toán
Đối với các quan hệ, ta cần có các biến trong cài đặt như sau :
m số quan hệ ;
pf danh sách ghi nhận tính đối xứng của các quan hệ
1: đối xứng; 0 : không đối xứng;
82
Mf danh sách các tập biến tương ứng của các quan hệ;
rf danh sách các hạng của các quan hệ đối xứng tương ứng
vf danh sách các tập biến phụ thuộc (tức là tập các biến được tính
theo các biến khác) của các quan hệ không đối xứng
expf danh sách các biểu thức của các quan hệ ;
namef danh sách các tên hay cách gọi của các quan hệ;
Tất cả những thông tin về các biến, tri thức về các quan hệ của mạng tính
toán có thể được lưu trữ trong một file TEXT theo một cấu trúc nào đó để chương
trình dễ dàng đọc hiểu được, cập nhật các thông tin và các tri thức khi cần thiết. Dưới
đây là một mẫu lưu trữ của mạng tính toán một tam giác :
object TAM_GIAC
variables
a : cạnh của tam giác; // <tên biến dạng ký hiệu> : chú giải
b : cạnh của tam giác;
c : cạnh của tam giác;
alpha : góc của tam giác;
v.v . . .
// chương trình đọc các biến và tự đếm số biến.
end variables;
relation
<tên gọi hay lời giải thích về relation>;
// ví dụ : công thức Sin;
<thông tin cho biết về tính đối xứng của relation>; // 1 hoặc 0
<danh sách biến liên quan của relation>;
// ví dụ : M = a,b,c,p;
<hạng (trường hợp đối xứng)>; // ví dụ : r = 1;
<tập biến phụ thuộc của quan hệ (trường hợp không đối xứng)>;
// ví dụ : v = p;
<biểu thức của quan hệ>;
// ví dụ : a+b+c - p = 0
// ví dụ : S = ...
end relation;
relation
. . .
end relation;
v.v . . .
83
end object;
Ngoài ra, đối với mạng tính toán chúng ta còn cài đặt một số hàm (function)
cần thiết cho việc giải quyết bài toán trên mạng tính toán, chẳng hạn như :
- Tìm bao đóng của một tập hợp biến.
- Tìm sự mở rộng tối đa của một tập biến giao với một tập biến cho trước.
- xác đònh tính giải được của một bài toán
- cho lời giải của một bài toán
- cho gợi ý bổ sung giả thiết cho một bài toán nếu được.
II.- CÀI ĐẶT CHƯƠNG TRÌNH GIẢI TAM GIÁC :
Chương trình giải tam giác sẽ nhận một đề ghi trong một file text có một cấu
trúc khá đơn giản : trong đề cho biết những yếu tố đã biết và những yếu tố yêu cầu
phải tính. Dưới đây là một mẫu ví dụ về một đề giải tam giác :
problem <lời ghi chú hay giải thích >;
Input :
a=5;
b = 3;
c = 4;
Output :
S, p;
end.
Từ đề nhận được chương trình sẽ tiến hành việc dò tìm trong tri thức đã biết về tam
giác để tìm lời giải cho đề và ghi lời giải (nếu có) trong một file dưới một dạng qui
đònh nào đó, chẳng hạn như :
Input :
...
Output :
...
84
Solution :
1. . . .
2. . . .
3. . . .
v.v . . .
// Ở mỗi bước chương trình cho biết :
// - tính biến nào
// - áp dụng quan hệ (relation) nào
Kết luận (hay kết quả):
. . .
// phần nầy chỉ ghi lại kết quả của các biến cần tính của bài toán.
Trong trường hợp bài toán không có lời giải thì chương trình cho thông báo và gợi ý
cách điều chỉnh giả thiết nếu có thể.
Như vậy, tổ chức hoạt động của chượng trình giải tam giác có thể được diển
đạt bởi sơ đồ sau đây :
Ghi chú : Trong phần phụ lục có liệt kê một phần của chương trình giải tam giác
viết bằng ngôn ngữ C.
85
