BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TPHCM
LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
HỆ SUY DẪN VÀ ỨNG DỤNG
Giáo viên hướng dẫn:
PGS TSKH Nguyễn Xuân Huy
Học viên thực hiện:
Nguyễn Sơn Minh
Nhiệm vụ:
- Nhiệm vụ của em tìm hiểu hệ suy dẫn để áp
dụng vào các bài toán trong thực tiễn.
- Hoạt động đóng góp của em chưa nhiều, cụ
thể chỉ là:
+ Tìm hiểu thế nào là 1 hệ suy dẫn
+ Kiến trúc 1 hệ suy dẫn ra sao
+ Cơ chế suy dẫn hoạt động như thế nào
+ Cài đặt cơ chế suy dẫn và xây dựng một vài
ứng dụng nhỏ minh họa hệ suy dẫn
1
NỘI DUNG
1. Định nghĩa hệ suy dẫn
2. Các quy tắc hệ suy dẫn
3. Ứng dụng giải bài toán dạng 1
4. Ứng dụng giải bài toán dạng 2
5. Kết luận và hướng phát triển
6. Tài liệu tham khảo
2
1. Định nghĩa hệ suy dẫn
Hệ suy dẫn là một cặp = (U, F) trong
đó U một tập nền (tập các sự kiện), F là
tập các luật dẫn dạng L R; L, R U.
3
1. Định nghĩa hệ suy dẫn (tt)
Ví dụ:
Hệ suy dẫn =(U,F)
U=tam giác cân, tam giác đều, 2 cạnh bằng nhau, 2
góc bằng nhau, 3 cạnh bằng nhau, 3 góc bằng nhau
F=f1,f2
f1 = Tam giác cân 2 cạnh bằng nhau và 2 góc bằng nhau.
f2 = Tam giác đều 3 cạnh bằng nhau, 3 góc bằng nhau.
4
2. Các quy tắc suy dẫn
Cho = (U, F) là một hệ suy dẫn. Các quy tắc suy dẫn
theo hệ tiên đề Armstrong:
L, R, V U:
(F1) Phản xạ: L R L R,
(F2) Gia tăng: L R LV RV,
(F3) Bắc cầu: L R R V L V
5
3. Dạng toán 1
Cho = (U,F) và mệnh đề h: X Y. Cho biết tính
đúng của mệnh đề h ?
theo nghĩa: h là đúng khi và chỉ khi xuất phát từ tập
luật F sau hữu hạn bước vận dụng các quy tắc suy
dẫn F1 - F3 thì thu được h.
Mệnh đề h: XY là đúng khi và chỉ khi Y f(X), f là
ánh xạ cảm sinh của .
Câu hỏi dạng toán 1: XY?
Yêu cầu bài toán: Y f(X)?
6
Ví dụ dạng toán 1:
f1: Hình thang, 2 cạnh bên song song hình bình hành
F
f2: Hình bình hành, 1 góc vuông hình chữ nhật
g = hình thang, 2 cạnh bên song song, 1 góc vuônghình
chữ nhật
F g ?
((hình thang, 2 cạnh bên song song, 1 góc vuông))+ =
hình thang, 1 góc vuông, 2 cạnh bên song song, hình bình
hành, hình chữ nhật
7
Dạng toán 1(tt)
Các bước thực hiện giải dạng toán này
Bước 1 : Tính M = f(X).
Bước 2: Kiểm tra Y M ?
Nếu Y M: Đúng.
Nếu Y M: Sai.
Bước 3 : Kết luận bài toán dựa vào bước 2
8
4. Dạng toán 2
Cho = (U, F) và hai tập sự kiện X, Y. Hãy cho biết từ các sự
kiện X có thể suy ra những sự kiện nào trong số các sự kiện Y.
Từ các sự kiện X có thể suy ra các sự kiện nào ?
Câu hỏi dạng toán 2: X ?
Yêu cầu bài toán: f(X) \X = ?
9
Ví dụ dạng toán 2:
U = (csdl, hqtcsdl, ktlt, ctdl>,lthđt, ltwindowns )
F= { f1: csdl hqtcsdl, f2: ktlt ctdl>,
f3 : ktlt lthđt, f4 : lthđt ltwindowns }
Học X=(csdl & ktlt) thì học tiếp được những môn nào
Tính :
f(X) = csdl,ktlt, hqtcsdl, ctdl>, lthđt, ltwindowns
f(X) \X = { hqtcsdl, ctdl>, lthđt, ltwindowns}
Kết luận : học csdl và ktlt thì học tiếp được các môn:
hqtcsdl, ctdl>, lthđt, ltwindowns
10
4. Dạng toán 2(tt)
Các bước thực hiện giải dạng toán này
Bước 1 : Tính M = f(X).
Bước 2: Tìm tập phần tử f(X) \ X
Bước 3 : Kết luận bài toán dựa vào bước 2
11
5. Kết luận và phướng phát triển
Những nội dung chính đã được giải quyết trong luận văn
1. Lý thuyết:
Tìm hiểu hệ suy dẫn và cơ chế hệ suy dẫn
Ứng dụng hệ suy dẫn giải hai dạng toán.
2. Thực nghiệm :
Xây dựng các thí dụ để minh họa
Cài đặt chương trình để kiểm thử và đánh giá các
kết quả được trình bày trong luận văn.
12
5. Kết luận và phướng phát triển (tt)
Dạng toán thứ 3: Cho hệ sinh ánh xạ đóng . Hãy cho biết
từ ít nhất những sự kiện nào có thể suy ra được toàn bộ
những sự kiện còn lại.
Ví dụ:
Hãy cho biết để học tất cả các môn thì cần học ít
nhất những môn nào trước?
13
6-Tài liệu tham khảo
[1] Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ
sở dữ liệu, Viện Khoa học và Công nghệ Việt Nam, NXB
Thống kê, Hà Nội, 2006.
[5] Bùi Đức Minh, Lương Nguyễn Hoàng Hoa, Cao Tùng Anh,
Nguyễn Gia Như, Nguyễn Xuân Huy (2011), Biểu diễn cơ sở của
hệ sinh ánh xạ đóng, Kỷ yếu Hội thảo Quốc gia lần thứ XIII “Một
số vấn đề chọn lọc của Công nghệ thông tin và Truyền thông”,
Hưng Yên, 19-20/8/2010, NXB KHKT Hà Nội, tr. 51-58.
14
Xin trân trọng cảm ơn!
15
- Xem thêm -