Biễu diễn tri thức và ứng dụng
MỤC LỤC
GVHD : PGS.TS Đỗ Văn Nhơn Trang 1
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
CHƯƠNG I.
KHÁI NIỆM VỀ TRI THỨC VÀ BIỂU
DIỄN TRI THỨC
1. Khái niệm về tri thức (knowledge)
• Tri thức không có được định nghĩa chính xác.
• Tri thức hay kiến thức có nhiều ý nghĩa tùy theo văn cảnh, nhưng lúc nào cũng
có liên quan với những khái niệm như hiểu biết, ý nghĩa, thông tin, giảng dạy,
giáo dục (quá trình giáo dục), giao tiếp, diễn tả, học hỏi, suy luận, nhận thức và
kích thích trí óc.
• Tri thức là các thông tin, các tài liệu, các cơ sở lý luận, các kỹ năng khác nhau,
đạt được bởi một tổ chức hay một cá nhân thông qua các trải nghiệm thực tế
hay thông qua sự giáo dục đào tạo; các hiểu biết về lý thuyết hay thực tế về
một đối tượng, một vấn đề, có thể lý giải được về nó.
• Tri thức là sự “hiểu biết” của người trong một phạm vi, lĩnh vực nào đó; được
xem xét theo các mục tiêu hay các vấn đề nhất định.
• Tri thức thường bao gồm các khái niệm, các loại sự kiện, các luật, …
• Ví dụ:
 Kiến thức về một lĩnh vực y học và khả năng chuẩn đoán bệnh là tri
thức.
 Biết một tam giác có các yếu tố nào cùng với các công thức liên hệ
giữa các yếu tố là tri thức.
GVHD : PGS.TS Đỗ Văn Nhơn Trang 2
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Biết các dạng cấu trúc dữ liệu thường dùng trong lập trình cùng
với các thuật toán xử lý cơ bản trên cấu trúc là tri thức.

 Một tập hợp các công thức liên hệ tính toán trên các yếu tố của tam
giác.
• Tập các biến trong tam giác gồm:
 a, b, c : 3 cạnh của tam giác.
 α, β, γ : 3 góc đối diện với 3 cạnh tương ứng trong tam giác.
 h
a
, h
b
, h
c
: 3 đường cao tương ứng với 3 cạnh của tam giác.
 S : diện tích tam giác.
 P : nửa chu vi của tam giác.
 R : bán kính đường tròn ngoại tiếp tam giác.
 v.v
• Tập công thức trong tam giác gồm:
 f1 : a + b + g = p (radian).
 f2 : a2 = b2 + c2 - 2.b.c.cos a
GVHD : PGS.TS Đỗ Văn Nhơn Trang 4
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 f3 : b2 = a2 + c2 - 2.a.c.cos b
 f4 : c2 = a2 + b2 - 2.a.b.cos g
 f5 : a / sin a = b / sin b
 v.v
4. Phân loại biểu diễn tri thức
• Phân loại theo các hệ thống tin học:
 Hệ thống thông tin, MIS, GIS, …
 Hệ CSTT, HCG, HTGQĐ.

 Hệ giải một số lớp bài toán Hóa học
 Phần mềm dạy học
 Phần mềm dạy học tiếng Anh.
 V.v…
GVHD : PGS.TS Đỗ Văn Nhơn Trang 6
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Hệ quản lý và hỗ trợ tìm kiếm các văn bản về CNTT
 Hệ quản lý kho tài nguyên học tập về CNTT (hoặc ngoại ngữ, vật,
hóa, …)
 Hệ quản lý văn bản cho một UBND cấp phường, quận, …
CHƯƠNG II.
CÁC PHƯƠNG PHÁP BIỄU DIỄN TRI
THỨC
1. Biểu diễn dựa trên logic hình thức
• Sử dụng các biểu thức logic hình thức trong một hệ thống logic để diễn đạt các
sự kiện và các luật trong cơ sở tri thức.
• Phép tính logic vị từ cấp 1 được sử dụng phổ biến nhất và có cả một ngôn ngữ
lập trình hỗ trợ cho phương phát này. Đó là ngôn ngữ PROLOG
• Trong ngôn ngữ PROLOG, chỉ cần khai báo các sự kiện và các luật. Hệ thống sẽ
thực hiện giải quyết vấn đề được yêu cầu trên tri thức được khai báo.
• Mô hình: : (Predicates, Clauses)
Predicates là tập gồm các vị từ, mỗi vị từ biểu diễn cho phát biểu nói về
một tính chất của đối tượng hay một quan hệ giữa các đối tượng. mỗi vị từ
xác định bởi tên vị từ và các kiểu tham biến.
Ví dụ: gioi(x:sinhvien), vg(v: vector, P: plane).
Clauses là tập gồm các biểu thức vị từ gồm 2 dạng fact và rule.
=> Nên dùng PROLOG, công cụ xử lý biểu diễn theo vị từ.
Predicates
GVHD : PGS.TS Đỗ Văn Nhơn Trang 7

if A, B then C;
if B, C then A;
if A, C then B;
if a, A then R;
v.v …
• Nhận xét: mô hình hệ luật dẫn trên khó áp dụng trực tiếp vì quan niệm sự kiện
khá đơn giản.
3. Mạng ngữ nghĩa
• Mạng ngữ nghĩa (semantic network) có dạng một đồ thị các nút và các cung:
 Các nút thể hiện các khái niệm, các đối tượng.
 Các cung thể hiện các quan hệ giữa các đối tượng.
• Dựa trên mạng ngữ nghĩa ta nhận biết tri thứ một cách trực quan giúp thiết
kế các xử lý như: thêm/ bớt các khái niệm hay các đối tượng, tìm kiếm thông
tin.
• Mô hình tri thức dạng đồ thị: (Nodes, Arcs)
 Nodes gồm các yếu tố hay các bộ phận cấu thành tri thức. Các node có
thể là khái niệm, đối tượng, sự kiện, cấu trúc trừu tượng, …
 Arcs gồm các liên kết biểu diễn cho các quan hệ giữa các nodes. Các
quan hệ có thể là: IS_A, HAS_A, …
 Tổ chức lưu trữ: Dựa trên các kỹ thuật biểu diễn và tổ chức lưu trữ xử
lý đồ thị.
GVHD : PGS.TS Đỗ Văn Nhơn Trang 9
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Ví dụ: Biểu diễn ma trận, biểu diễn dạng danh sách kề hay danh sách
cạnh, …
• Ví dụ: “Mạng tính toán trên tam giác”.
Tamgiac.txt:
Begin_variables
a : cạnh a của tam giác.

thành chương trình máy tính
• Các kỹ thuật cơ bản:
 Suy diễn tiến.
 Suy diễn lùi.
2. Hợp giải trong tri thức dạng logic
• Phương pháp: thực hiện quá trình phát sinh sự kiện mới bằng cách sử dụng
các luật suy diễn cơ bản trên các biểu thức logic như: Modus Ponens, Modus
Tollens, tam đoạn luận
• Trong logic vị từ: quá trình hợp giải có thể được cài đặt dựa trên kỹ thuật
hợp nhất (unification) và quay lui (backtracking.
• PROLOG là một ngôn ngữ lập trình được thiết kế với chức năng suy diễn theo
phương pháp này.
GVHD : PGS.TS Đỗ Văn Nhơn Trang 11
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
3. Suy diễn tiến
• Phương pháp: suy dẫn từ giả thiết đi đến kết luận. Chiến lược này được bắt
đầu bằng tập sự kiện đã biết, rút ra các sự kiện mới nhờ dùng các luật mà
phần giả thiết khớp với sự kiện đã biết, và tiếp tục quá trình này cho đến khi
thấy trạng thái đích, hoặc cho đến khi không còn luật nào khớp được các sự
kiện đã biết hay được sự kiện suy luận.
• Trong áp dụng cụ thể phương pháp thường sử dụng kết hợp với các qui tắc
heuristic trong việc chọn luật.
4. Suy diễn lùi
• Phương pháp: truy ngược từ kết luận trở về giả thiết, phương pháp này được
tiến hành bằng cách truy ngược từ mục tiêu cần đạt trở về phần giả thiết của
bài toán bằng cách áp dụng các luật trong cơ sở tri thức.
• Quá trình suy diễn lùi này sẽ phát sinh một sơ đồ cây mục tiêu kèm theo một
cơ chế quay lui và lời giải sẽ được tìm thấy khi tất cả các mục tiêu ở các nút lá
của cây mục tiêu đều thuộc về những sự kiện đã biết.

Biễu diễn tri thức và ứng dụng
 Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn
cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục
bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
 Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự
hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải
tốt.
2. Hàm Heuristic
• Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm
Heuristic. Đó là các hàm đánh già thô, giá trị của hàm phụ thuộc vào trạng thái
hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được
cách hành động tương đối hợp lý trong từng bước của thuật giải.
• Bài toán hành trình ngắn nhất – ứng dụng nguyên lý Greedy
Bài toán: Hãy tìm một hành trình cho một người giao hàng đi qua
n điểm khác nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao
cho tổng chiều dài đoạn đường cần đi là ngắn nhất. Giả sử rằng có con
đường nối trực tiếp từ giữa hai điểm bất kỳ.
 Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường
có thể đi, tính chiều dài của mỗi con đường đó rồi tìm con đường có
chiều dài ngắn nhất. Tuy nhiên, cách giải này lại có độ phức tạp 0(n!)
(một hành trình là một hoán vị của n điểm, do đó, tổng số hành trình là
số lượng hoán vị của một tập n phần tử là n!). Do đó, khi số đại lý tăng
thì số con đường phải xét sẽ tăng lên rất nhanh.
 Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là
dùng một thuật giải Heuristic ứng dụng nguyên lý Greedy. Tư tưởng của
thuật giải như sau:
GVHD : PGS.TS Đỗ Văn Nhơn Trang 14
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho

GVHD : PGS.TS Đỗ Văn Nhơn Trang 16
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công
việc với thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. ta có một phương
án phân công (L) như hình sau:
 Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên
máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn
thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy
P1 và P2 vẫn đang thực hiện công việc đầu tiên mình … Sơ đồ phân việc
theo hình ở trên được gọi là lược đồ GANTT. Theo lược đồ này, ta thấy
thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách
cảm tính ta thấy rằng phương án (L) vừa thực hiện là một phương án
không tốt. Các máy P1 và P2 có quá nhiều thời gian rãnh.
 Thuật toán tìm phương án tối ưu Lo cho bài toán này theo kiểu vét cạn có
độ phức tạp cỡ O(mn) (với m là số máy và n là số công việc). Bây giờ ta
xét đến một thuật giải Heuristic rất đơn giản (độ phức tạp O(n)) để giải
bài toán này.
 Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.
 Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian
nhất.
 Với tư tưởng như vậy, ta sẽ có một phương án L* như sau:
GVHD : PGS.TS Đỗ Văn Nhơn Trang 17
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
 Rõ ràng phương án L* vừa thực hiện cũng chính là phương án tối ưu của
trường hợp này vì thời gian hoàn thành là 8, đúng bằng thời gian của
công việc J3. Ta hy vọng rằng một giải Heuristic đơn giản như vậy sẽ là
một thuật giải tối ưu. Nhưng tiếc thay, ta dễ dàng đưa ra được một
trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối ưu.

GVHD : PGS.TS Đỗ Văn Nhơn Trang 22
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
CHƯƠNG VI.
KẾT QUẢ ĐẠT ĐƯỢC
Do thời gian có hạn nên chương trình còn khá đơn giản và hạn chế. Tuy nhiên đã cơ
bản cài đặt được thuật toán HEURISTIC trên máy tính để giải toán nguyên hàm.
Tiếp tục hoàn thiện chương trình áp dụng cho việc xử lý và giải toán tích phân.
GVHD : PGS.TS Đỗ Văn Nhơn Trang 23
HVTH : Mã Tuấn Huy
Biễu diễn tri thức và ứng dụng
CHƯƠNG VII.
TÀI LIỆU THAM KHẢO
1. Tài liệu
• PGS.TS Đỗ Văn Nhơn – Biểu diễn tri thức và Ứng dụng – 2012-2013
• PGS.TS. Đỗ Văn Nhơn – TS. Đỗ Phúc – “Giáo trình Các Hệ Cơ Sở Tri Thức, Đại học
Quốc gia Tp.HCM, 2002”.
• Mai Trung Thành – “Khóa luận tốt nghiệp – Xây dụng Website giải toán 9”
Tp.HCM tháng 7 năm 2012.
• Đỗ Tấn Nhàn – “Khóa luận – Một mô hình Ontology và ứng dụng” Tp.HCM năm
2005
• Bài thu hoạch các khóa trước.
• http://www.voer.edu.vn/bai-viet/toan-va-thong-ke/thuat-giai-heuristic.html
• http://www.voer.edu.vn/bai-viet/toan-va-thong-ke/bieu-dien-tri-thuc-bang-
script.html
• http://www.voer.edu.vn/bai-viet/toan-va-thong-ke/cac-phuong-phap-bieu-dien-tri-
thuc-tren-may-tinh.html
• http://www.voer.edu.vn/bai-viet/toan-va-thong-ke/phoi-hop-nhieu-cach-bieu-dien-
tri-thuc.html
• http://tailieu.vn/upgrade.html?emsg=SQLSTATE[HY000]%20[1040]%20Too