Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
TIỂU LUẬN MÔN HỌC
LẬP TRÌNH SYMBOLIC VÀ TRÍ TUỆ NHÂN TẠO
ĐỀ TÀI:
Ứng dụng Maple cài đặt thuật toán tìm
đường đi ngắn nhất Dijkstra
GVHD: TS. Đỗ Văn Nhơn
Người thực hiện: Phạm Vĩnh Thành
Mã số: CH1101035
Lớp: Cao học khóa 6 đợt 2
TP.HCM – 2013
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
MỤC LỤC

SV: Phạm Vĩnh Thành Trang: 2
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo

Chúng em xin chân thành cảm ơn Thầy Đỗ Văn Nhơn đã truyền đạt
những kiến thức quý báu từ những kinh nghiệm sống đến những vấn đề khoa học
mới nhất trong bộ môn Biểu diễn tri thức và ứng dụng.
Trong bài tiểu luận này, em xin trình bày cách cài đặt thuật toán tìm đường
đi ngắn nhất Dijkstra bằng cách sử dụng các công cụ giải toán mạnh mẽ của
Maple 16.
Tuy đã có nhiều cố gắng nhưng do hạn chế về kiến thức, thời gian và
nguồn tài liệu tham khảo nên các vấn đề nghiên cứu trong tiểu luận chắc chắn
còn nhiều thiếu sót.
Chân thành cám ơn!
Phạm Vĩnh Thành
SV: Phạm Vĩnh Thành Trang: 3
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo

nhau;
- Tính toán trên các biểu thức đại số;
- Có thể thực hiệc được hầu hết các phép toán cơ bản trong chương
trình toán đại học và sau đại học;
- Ngôn ngữ lập trình đơn giản và mạnh mẽ, có khả năng tương tác với
các ngôn ngữ lập trình khác;
- Một công cụ biên soạn giáo án và bài giảng điện tử, thích hợp với các
lớp học tương tác trực tiếp;
- Một công cụ hữu ích cho học sinh và sinh viên trong việc tự học;
- Tăng thêm 270 chức năng so với phiên bản trước đó
- …
III.Kiến trúc
Phần lớn chức năng toán học của Maple được viết bằng ngôn ngữ Maple,
và được thông dịch bởi nhân Maple. Nhân Maple được viết bằng C. Maple chạy
trên tất cả các hệ điều hành chính.
Ngôn ngữ lập trình Maple là một ngôn ngữ kiểu động. Cũng giống như
các hệ thống đại số máy tính, các biểu thức hình thức được lưu trữ trong bộ nhớ
theo đồ thị không chu trình có hướng (DAG). Ngôn ngữ cho phép các biến có
phạm vi nhất định (lexical scoping). Ngôn ngữ có hình thức lập trình hàm, nhưng
cũng có hỗ trợ đầy đủ cho lập trình truyền thống, theo kiểu mệnh lệnh.
Một điều lạ đối với chương trình thương mại, đa số mã nguồn đều có thể
xem tự do.
SV: Phạm Vĩnh Thành Trang: 5
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
Phần 2: Cài đặt giải thuật Dijkstra
I. Phân tích yêu cầu
- Đầu vào:
Đồ thị:
o Tập hợp các đỉnh
o Tập hợp các cạnh

error "Khong co duong giua 2 dinh %1 to %2.", u, v
end if;
if u = v then
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
> result1 := dijkstra(graph1, 2):
> listpath(result1, 2, 5);
[2, 3, 5]
SV: Phạm Vĩnh Thành Trang: 7
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
- Dữ liệu mẫu ngẫu nhiên 2
> result2 := dijkstra(graph2, 1):
> listpath(result2, 1, 5);
[1, 3, 5]
SV: Phạm Vĩnh Thành Trang: 8
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
KẾT LUẬN

Báo cáo này đã làm nổi bật vai trò của Maple trong việc hỗ trợ người
dùng lập trình các thuật toán phức tạp như Dijkstra đơn giản hơn bằng các kiểu
cấu trúc dữ liệu được định nghĩa sẵn cho đồ thị. Với công cụ mô phỏng vẽ đồ thị,
người dùng được cái nhìn trực quan hơn về bài toán. Điểm hạn chế trong việc vẽ
đồ thị là chưa hiển thị đồ thị có trọng số được.
Một lần nữa, em xin cám ơn Thầy Đỗ Văn Nhơn đã giảng dạy cho chúng
em kiến thức nền tảng, những bài giảng bổ ích của Thầy đã giúp em hoàn thành
được bài tiểu luận này.
SV: Phạm Vĩnh Thành Trang: 9
Tiểu luận: Lập trình Symbolic và trí tuệ nhân tạo
TÀI LIỆU THAM KHẢO

[1] Bài giảng của Thầy Đỗ Văn Nhơn.