Lập trình trong Maple ứng dụng giải các bài toán phức tạp
MỤC LỤC
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
1
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
Phần 1: GIỚI THIỆU ĐỀ TÀI
1. Lý do chọn đề tài
Lập trình Symbolic cho Trí Tuệ Nhân Tạo là môn học đem lại nhiều sự sức thu húc
cho người học cũng như nghiên cứu. Môn học rèn luyện cho chúng ta sự tính toán một
cách nhanh chóng, hiệu quả. Nói đến toán học không chỉ đơn thuần là một môn khoa học
mà còn được ứng dụng vào hầu hết các lĩnh vực trong xã hội. Việc ra đời của chiếc máy
tính và ngôn ngữ lập trình phần nào giúp các nhà toán học giải quyết vấn đề một cách
nhanh chóng. Một bài toán nếu giải theo cách thông thường có thể mất không ít thời gian
và kết quả cũng chưa chắc đúng hoàn toàn, trong khi, nếu bài toán đó được giao cho máy
tính xử lý thì kết quả có độ chính xác cao hơn. Tuy nhiên, các ngôn ngữ lâu đời như C ,
Pascal … hay kể cả ngôn ngữ hiện đại như C#, Java …cũng rất khó khăn trong việc thực
hiện các dạng toán như giải tích sơ cấp, đại số tuyến tính ….Chúng không thể biểu diễn các
ký hiệu toán học đều này cũng gây nên cản trở cho các nhà toán học muốn áp dụng công
nghệ thông tin. Cần có một công cụ chuyên biệt có khả năng biểu diễn và giải các bài toán
theo ngôn ngữ toán học. Các công cụ Maple, Mathematica, Matlab ra đời nhằm mục đích
trên. Và đặc biệt hiện nay phần mềm Maple tích hợp rất nhiều tính năng để giải quyết bài
toán một cách nhanh chóng, cũng như đem lại cho người học CNTT sự thích thú, say mê
trong lập trình ứng dụng trên Maple.
2. Mục tiêu đề tài
- Tìm hiểu và làm rõ một số khái niệm, định nghĩa trong toán học
- Hiểu cách định nghĩa các hàm trong Maple
- Giải quyết bài toán một cách nhanh chóng và hiệu quả
- Ứng dụng phần mềm để giảng dạy hoặc nghiên cứu
- Lập trình viên có thể ứng dụng tạo ra một số hàm hay định nghĩa hàm phục vụ riêng khi
cần thiết.
- Tích hợp phát triển ứng dụng cao hơn.

B0: khai báo biến a,b,c,vt,m1,x1,x2,isConst=false;
B1: khởi tạo biến pt:= phương trình theo tham số m;
B2: p:=vế trái phương trình theo tham số m.
B3: gán cho biến a,b,c lần lượt là hệ số của x
2
,x
1
,x
0
B4: Delta=b*b-4*a*c;
B5: Kiểm tra kiểu dữ liệu của Delta, nếu hợp lệ thì isConst=true.
B6: Nếu isConst:=true thì
B6.1: Delta>0 thì pt có 2 nghiệm phân biệt: x1=(-b+sqrt(Delta))/2*a;
X2=(-b-sqrt(Delta))/2*a;
B6.2: Delta=0 thì pt có nghiệm kép x1=x2=-b/2*a;
B6.3: Delta<0 thì pt vô nghiệm.
B7: nếu isConst:=false thì return;
B8: TH Delta=0
B8.1 giải pt delta=0 theo m: m1=solve(Delta=0,bienm)
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
4
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
B8.2 nếu m1<>Null phương trình có nghiệm kép
X1=subs(bienm=m1[1],-b/2*a;
X2=subs(bienm=m1[2],-b/2*a;
B9: TH Delta>0
B9.1 giải bất phương trình Delta>0 tham số m: m1=solve(Delta>0,bienm)
B9.2 nếu m1<>Null pt có 2 nghiệm phân biệt
X1=(-b+sqrt(Delta,symbolic)/2*a;
X2=(-b-sqrt(Delta,symbolic)/2*a;

Known:Lưu lại tập sự kiện đã biết
B1: Khởi tạo biến: Sol:=[];
Known:=H;
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
7
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
B2: while (chưa đạt được mục tiêu G) do
2.1: Tìm luật r thuộc R có thể áp dụng trên Known
2.2: If (không tìm được r) then
Dừng: không tìm được lời giải
2.3: Thêm r vào Sol; them kl(r) vào Known
End do;
B3: Cho kết quả tìm được lời giải Solution
2.4 Thủ tục:
Giả sử đã có (F,R), biến toàn cục
2.5 Dữ liệu mẫu:
GT={a,b}
Rules={a->c;b->d;a->e; a,d->e;b,c->f; e,f->g}
Sol={g};
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
8
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
3. Tìm chu trình Euler
3.1 Phân tích yêu cầu:
- Đường Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần.
- Chu trình Euler của đa đồ thị là đường đi qua mỗi cạnh của đồ thị đúng một lần.
- Đa đồ thị G có chu trình vô hướng Euler khi và chỉ khi mọi đỉnh đều có bậc
chẵn.
- Đa đồ thị G có đường đi Euler vô hướng khi và chỉ khi số đỉnh bậc lẻ bằng 2.
 Phác họa lời giải:

end:
- H=duplicate(G): sao chép đồ thị G vào H
- V:=vertices(G): lấy tập các đỉnh vào V
- E:=edges(G); lấy tập các cạnh vào E
- Convert: chuyển đổi từ dạng danh sách sang tập hợp
3.3 Thuật giải
B1: Khởi tạo:
- V: Tập các đỉnh của đồ thị G
- E: Tập các cạnh/cung của đồ thị G
- H chứa đồ thị G(V,E)
- Đỉnh xuất phát là đỉnh 1:Vstart:= V[1];
- Chu trình bằng rỗng: ECycle=[];
B2: Thực hiện vòng lặp: trong khi E khác rỗng:
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
11
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
B2.1: cho i:=Vstart, C=[i]; CycleFound=false;
B2.2: Thực hiện vòng lặp: Trong khi Not CycleFound:
B2.2.1: Tìm đỉnh j kế cận đỉnh i, nếu đỉnh j=Vstart thì tìm được một chu trình.
B2.2.2: thêm đỉnh j vào C rồi xóa cạnh i,j
B2.2.3: Nếu j=Vstart thì cập nhật CycleFound=true; i=j;
B2.2.4: Nếu tìm được một chu trình C thì thêm vào ECycle
B2.2.5: Tìm đỉnh Vstart kế tiếp nếu còn chu trình
End do;
End do;
B3: In ra kết quả các chu trình đã tìm được.
3.4 Thủ tục
Thủ tục khởi tạo ban đầu, sử dụng các package cần thiết :
> Init:=proc()
restart;

if cycleFound then
#Them chu trinh C vao ECycle tai vi tri vStart
if ECycle=[] then ECycle:=C;
else
i:=1;
while ECycle[i]<>vStart do i:=i+1; od;
GVHD: PGS.TS Đỗ Văn Nhơn HVTH: Lê Nhựt Trường – CH1101150
13
Lập trình trong Maple ứng dụng giải các bài toán phức tạp
ECycle:=[op(1 i-
1,ECycle),op(C),op(i nops(ECycle),ECycle)];
fi:
#Tim dinh vStart ke tiep neu con chu trinh
if E<>{} then
V:={};
for i in E do V:=V union ends(i,H) od;
V:=V intersect convert(ECycle,set);
vStart:=V[1];
fi;
fi;
od;
od;
ECycle:=[op(ECycle),ECycle[1]];
return ECycle;
end:
3.5 Dữ liệu mẫu
> V:={1,2,3,4,5,6,7,8,9,10}:
E:=[{1,2},{1,4},{3,2},{3,4},{3,5},{3,6},{7,5},{7,6},{5,8},
{5,10},{8,9},{9,10}]:
H:=graph(V,E):