Tài liệu Hệ suy dẫn và ứng dụng

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: XY 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: XY? 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ônghì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