Xây dựng mô hình biểu diễn tri thức dạng hàm và áp dụng vào bài toán rút gọn biểu thức lượng giác

  • Số trang: 26 |
  • Loại file: PDF |
  • Lượt xem: 38 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27372 tài liệu

Mô tả:

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN BIỂU DIỄN TRI THỨC VÀ ỨNG DỤNG TIỂU LUẬN GVHD : PGS. TS. ĐỖ VĂN NHƠN Học viên: Vũ Đăng Khôi (CH1101017 – Cao học CNTT K6) Tháng 01/2013 LỜI CÁM ƠN Em xin chân thành cám ơn PGS. TS. Đỗ Văn Nhơn về những tri thức và những kinh nghiệm quý báu mà thầy đã truyền đạt lại cho lớp trong phạm vi môn học Biểu diễn tri thức và ứng dụng thuộc chương trình đào tạo cao học ngành Công nghệ thông tin tại trường Đại học Công nghệ thông tin – Đại học Quốc gia Thành phố Hồ Chí Minh. Tác giả cũng xin cám ơn các anh, chị và các bạn trong lớp cao học Công nghệ thông tin khóa 6/2011 về những ý kiến đóng góp trong quá trình học tập và trao đổi trên lớp và trên diễn đàn. Với khả năng và thời gian có hạn, tiểu luận chắc chắn còn có những thiếu sót nhất định, kính mong thầy và các anh chị góp ý để tác giả có điều kiện hoàn thiện hơn. TP. Hồ Chí Minh, 01/2013 Học viên thực hiện Vũ Đăng Khôi NHẬN XÉT CỦA GIẢNG VIÊN ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... ...................................................................................................................................... MỤC LỤC LỜI NÓI ĐẦU ................................................................................... i DANH MỤC CÁC HÌNH ẢNH ......................................................ii PHẦN I. DẪN NHẬP ....................................................................... 1 PHẦN II. NỘI DUNG ...................................................................... 3 1. TỔNG QUAN VỀ TRI THỨC VÀ BIỂU DIỄN TRI THỨC .................. 3 1.1. Tri thức ......................................................................................................... 3 1.2. Biểu diễn tri thức .......................................................................................... 4 1.2.1. Bộ ba Đối tượng – Thuộc tính – Giá trị (Object-Attribute-Value).................. 4 1.2.2. Các luật dẫn (Rules) ........................................................................................ 5 1.2.3. Mạng ngữ nghĩa (Semantic Networks) ............................................................ 5 1.2.4. Khung (Frames) ............................................................................................... 5 1.2.5. Logic ................................................................................................................ 6 1.2.6. Mô hình một đối tượng tính toán (C-Object) .................................................. 6 1.2.7. Mô hình cơ sở tri thức các đối tượng tính toán (COKB)................................. 7 2. MÔ HÌNH TRI THỨC DẠNG HÀM ....................................................... 8 3. ỨNG DỤNG MÔ HÌNH TRI THỨC DẠNG HÀM ĐỂ GIẢI BÀI TOÁN RÚT GỌN BIỂU THỨC LƯỢNG GIÁC ..................................................... 9 3.1. Phát biểu bài toán ......................................................................................... 9 3.2. Giải quyết bài toán ..................................................................................... 10 3.2.1. Chuẩn bị cơ sở tri thức .................................................................................. 10 3.2.2. Thuật giải suy diễn tiến ................................................................................. 10 3.2.3. Thuật giải suy diễn tiến với Heuristics .......................................................... 10 3.2.4. Xây dựng các thủ tục xử lý trên biểu thức..................................................... 15 3.3. Chương trình minh họa .............................................................................. 16 PHẦN III. KẾT LUẬN .................................................................. 19 TÀI LIỆU THAM KHẢO ............................................................. 20 Biểu diễn tri thức và ứng dụng -i- GVHD: PGS. TS. Đỗ Văn Nhơn LỜI NÓI ĐẦU Biểu diễn tri thức và ứng dụng là một môn học bắt buộc thuộc chương trình đào tạo cao học ngành Công nghệ thông tin tại trường Đại học Công nghệ thông tin – Đại học Quốc gia TP. HCM. Ngoài các buổi học được giảng viên truyền đạt trực tiếp trên lớp, các học viên được giao tìm hiểu các chủ đề liên quan đến môn học để thấu hiểu sâu sắc từng vấn đề đó và trình bày lại những hiểu biết thông qua một bài tiểu luận. Qua thời gian tìm hiểu, nghiên cứu tài liệu, em đã đúc kết lại những vấn đề cơ bản, quan trọng nhất của vấn đề nghiên cứu và trình bày lại trong bài tiểu luận này với chủ đề “Xây dựng mô hình biểu diễn tri thức dạng hàm và áp dụng vào bài toán rút gọn biểu thức lượng giác”. Tài liệu tham khảo chính của bài viết là tập tài liệu bài giảng môn Biểu diễn tri thức và ứng dụng của PGS. TS. Đỗ Văn Nhơn, giảng viên phụ trách môn học này. Ngoài ra, bài viết cũng tham khảo thêm một số tài liệu khác có liên quan đến chủ đề báo cáo được liệt kê ở phần tài liệu tham khảo. Học viên: Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng - ii - GVHD: PGS. TS. Đỗ Văn Nhơn DANH MỤC CÁC HÌNH ẢNH Hình 1. Biểu diễn tri thức bằng mạng ngữ nghĩa ....................................................................... 5 Hình 2. Biểu diễn tri thức bằng frame ........................................................................................ 5 Hình 3. Giao diện chương trình minh họa Rút gọn biểu thức lượng giác ................................ 17 Hình 4. Giao diện chương trình minh họa – Cập nhật cơ sở tri thức ....................................... 18 Học viên: Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -1- GVHD: PGS. TS. Đỗ Văn Nhơn PHẦN I. DẪN NHẬP Sự khác biệt giữa các hệ cơ sở tri thức và các chương trình truyền thống nằm ở cấu trúc. Trong các chương trình truyền thống, cách thức xử lý hay hành vi của chương trình đã được ấn định sẵn qua các dòng lệnh của chương trình dựa trên một thuật giải đã định sẵn. Trong các hệ cơ sở tri thức, có hai chức năng tách biệt nhau, trường hợp đơn giản có hai khối: khối tri thức hay còn được gọi là cơ sở tri thức và khối điều khiển hay còn được gọi là động cơ suy diễn. Với các hệ thống phức tạp, bản thân động cơ suy diễn cũng có thể là một hệ cơ sở tri thức chứa các siêu tri thức (tri thức về cách sử dụng tri thức khác). Việc tách biệt tri thức khỏi các cơ chế điều khiển giúp ta dễ dàng thêm vào các tri thức mới trong tiến trình phát triển một hệ thống. Đây là điểm tương tự của động cơ suy diễn trong một hệ cơ sở tri thức và não bộ con người (điều khiển xử lý), là không đổi cho dù hành vi của cá nhân có thay đổi theo kinh nghiệm và kiến thức mới nhận được. Giả sử một chuyên gia dùng các chương trình truyền thống để hỗ trợ công việc hàng ngày, sự thay đổi hành vi của chương trình yêu cầu họ phải biết cách cài đặt chương trình. Nói cách khác, chuyên gia phải là một lập trình viên chuyên nghiệp. Hạn chế này được giải quyết khi các chuyên gia tiếp cận sử dụng các hệ cơ sở tri thức. Trong các hệ cơ sở tri thức, tri thức được biểu diễn tường minh chứ không nằm ẩn như trong các chương trình truyền thống. Do vậy, có thể thay đổi các cơ sở tri thức, sau đó các động cơ suy diễn sẽ làm việc trên các tri thức mới được cập nhật nhằm thực hiện yêu cầu mới của chuyên gia. Đối với các hệ giải quyết vấn đề dựa trên tri thức như các hệ chuyên gia, các hệ giải toán tự động hay bán tự động thì việc biểu diễn tri thức và chiến lược tìm kiếm đóng vai trò quyết định trong quá trình xây dựng và cài đặt hệ thống. Như vậy, việc nghiên cứu và phát triển các mô hình biểu diễn tri thức và suy diễn tự động trên tri thức giữ một vị trí rất quan trọng trong khoa học máy tính cũng như trong Trí tuệ Nhân tạo. Các kết quả nghiên cứu về biểu diễn tri thức và suy luận tự động dựa trên tri thức sẽ là cơ sở và là công cụ cho việc xây dựng các hệ chuyên gia, các hệ giải toán dựa trên tri thức và các hệ cơ sở tri thức. Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -2- GVHD: PGS. TS. Đỗ Văn Nhơn Tri thức dạng hàm và tính toán hàm là những tri thức khá phổ biến, đặc biệt là trong toán học. Tri thức dạng hàm và tính toán hàm xuất hiện trong các bài toán tính toán phổ thông cũng như đại học. Tiểu luận sẽ đề xuất và phát triển một mô hình tri thức dạng hàm, các kỹ thuật suy luận tự động để giải các dạng bài toán tổng quát trên mô hình và áp dụng vào bài toán cụ thể là rút gọn biểu thức lượng giác. Cách tiếp cận để giải quyết mục tiêu đề ra là kết hợp có phát triển các phương pháp biểu diễn tri thức đã biết và tích hợp vào một số phần mềm toán học phổ biến (như Maple, Mathematica) và giao diện ứng dụng được thiết kế dựa trên môi trường web tương tác (sử dụng ngôn ngữ lập trình php. Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -3- GVHD: PGS. TS. Đỗ Văn Nhơn PHẦN II. NỘI DUNG 1. TỔNG QUAN VỀ TRI THỨC VÀ BIỂU DIỄN TRI THỨC 1.1. Tri thức Tri thức là sự hiểu biết về một lĩnh vực nào đó. Một số dạng tri thức được biết đến là: [4]  Tri thức thủ tục – procedured knowledge. Mô tả cách thức giải quyết một vấn đề. Loại tri thức này đưa ra giải pháp để thực hiện một công việc nào đó. Các dạng tri thức thủ tục tiêu biểu là các luật, chiến lược, lịch trình và thủ tục.  Tri thức khai báo – declared knowledge. Cho biết một vấn đề được thấy như thế nào. Loại tri thức này bao gồm các phát biểu đơn giản, dưới dạng các khẳng định logic đúng hoặc sai. Tri thức khai báo cũng có thể là một danh sách các khẳng định nhằm mô tả đầy đủ hơn về đối tượng hay một khái niệm nào đó.  Siêu tri thức - metaknowledge. Mô tả tri thức về tri thức. Loại tri thức này giúp lựa chọn tri thức thích hợp nhất trong số các tri thức khi giải quyết một vấn đề. Các chuyên gia sử dụng tri thức này để điều chỉnh hiệu quả giải quyết vấn đề bằng cách hướng các lập luận về miền tri thức có khả năng cao hơn.  Tri thức heuristic – heuristic knowledge. Mô tả các “mẹo” để dẫn dắt tiến trình lập luận. Tri thức heuristic còn gọi là tri thức nông cạn do không đảm bảo hoàn toàn chính xác về kết quả giải quyết vấn đề. Các chuyên gia thường dùng các tri thức khoa học như sự kiện, luật, … sau đó chuyển chúng thành các tri thức heuristic để thuận tiện hơn trong việc giải quyết một số bài toán.  Tri thức có cấu trúc – structured knowledge. Mô tả tri thức theo cấu trúc. Loại tri thức này mô tả mô hình tổng quan hệ thống theo quan điểm của chuyên gia, bao gồm khái niệm, khái niệm con và các đối tượng; diễn tả chức năng và mối liên hệ giữa các tri thức dựa theo cấu trúc xác định. Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -4- GVHD: PGS. TS. Đỗ Văn Nhơn Ngoài các dạng tri thức được đề cập ở trên, người ta còn phân tri thức thành 2 loại: • Tri thức tường minh – explicit knowledge. Diễn đạt bằng ngôn ngữ hình thức, dễ trao đổi giữa các cá nhân. Có thể biểu diễn bằng các công thức khoa học, các thủ tục tường minh, hoặc nhiều cách khác. Bao gồm thông tin, dữ liệu, sách báo, văn bản, tài liệu đã được hệ thống bằng nhiều phương tiện. Tri thức tường minh được đặc trưng bởi các cách tiếp cận lý thuyết, các cách giải quyết vấn đề, tài liệu, cơ sở dữ liệu, cơ sở tri thức. • Tri thức ngầm – tacit knowledge. Có được và ẩn chứa trong kinh nghiệm của từng cá nhân, mang tính chủ quan, bao gồm những hiểu biết riêng thấu đáo, trực giác, linh cảm, kỹ năng, ... Khó trao đổi hoặc chia sẻ với người khác. Chỉ có thể học được từ người khác nhờ quan hê gần gũi trong một khoảng thời gian nào đó. Tri thức ngầm liên quan đến nhận thức như niềm tin, quan niệm, trực giác, mô hình ẩn dụ, … và kỹ thuật như các ngón nghề (craft), các bí quyết (knowhow). 1.2. Biểu diễn tri thức Biểu diễn tri thức (Kowledge Representation) là phương pháp cho phép mã hóa tri thức trong cơ sở tri thức của hệ thống. Biểu diễn tri thức là một vấn đề được quan tâm trong cả khoa học nhận thức lẫn trí tuệ nhân tạo. Trong khoa học nhận thức, người ta quan tâm đến cách thức lưu trữ và xử lý thông tin. Còn trong trí tuệ nhân tạo, mục tiêu chính là lưu trữ tri thức sao cho các chương trình có thể xử lý chúng và đạt được sự thông minh như con người. Các nhà nghiên cứu trí tuệ nhân tạo đã mượn các lý thuyết về biểu diễn thông tin từ khoa học nhận thức. Một số kỹ thuật biểu diễn tri thức được biết đến là: [4] 1.2.1. Bộ ba Đối tượng – Thuộc tính – Giá trị (Object-Attribute-Value) Ví dụ: Ghế màu Nâu Đối tượng Thuộc tính Giá trị Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng GVHD: PGS. TS. Đỗ Văn Nhơn -5- 1.2.2. Các luật dẫn (Rules) Ví dụ: IF Bình điện hỏng THEN Xe sẽ không khởi động được IF Xe không khởi động được THEN Đi bộ IF Xe sẽ không khởi động được AND Hệ thống nhiên liệu tốt THEN Kiểm tra hệ thống điện 1.2.3. Mạng ngữ nghĩa (Semantic Networks) Ví dụ: cánh có Sẻ là Chim di chuyển bay Hình 1. Biểu diễn tri thức bằng mạng ngữ nghĩa 1.2.4. Khung (Frames) Ví dụ: PHIẾU ĐIỂM Họ tên: Lớp: Địa chỉ: Môn Toán Vật lý … Tên frame: Thuộc tính: Điểm Thuộc tính 1 Thuộc tính 2 … Thuộc tính n Giá trị 1 Giá trị 2 Giá trị n Hình 2. Biểu diễn tri thức bằng frame Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng GVHD: PGS. TS. Đỗ Văn Nhơn -6- 1.2.5. Logic Logic mệnh đề Logic vị từ Ví dụ: Ví dụ: A = “Xe không khởi động được” “Tôi ăn Cơm” Ăn(Tôi, Cơm) B = “Khoảng cách từ nhà đến cơ quan Trong đó “Tôi” và “Cơm” là hằng số, xa” “ăn” là vị từ. C = “Sẽ trễ giờ làm” A ^ B  C = “IF Xe không khởi động được AND Khoảng cách từ nhà đến cơ quan xa THEN Sẽ trễ giờ làm việc” Các phương pháp biểu diễn tri thức trên đây đều có những ưu và nhược điểm nhất định. Mỗi phương pháp chỉ biểu diễn được một khía cạnh của tri thức trong khi tri thức cần được biểu diễn trong các hệ ứng dụng rất đa dạng và thường bao gồm các khái niệm từ đơn giản đến có cấu trúc phức tạp, các hệ thức tính toán với những qui luật nhất định, các liên hệ đa dạng bao gồm cả định tính lẫn định lượng, các luật dẫn và các heuristic, v.v... Một cách tiếp cận khác được sử dụng là kết hợp các phương pháp biểu diễn tri thức đã có với những phát triển nhất định để tạo ra một số mô hình biểu diễn tri thức mới với phạm vi tri thức bao gồm nhiều dạng kiến thức đa dạng hơn, và như thế các mô hình biểu diễn tri thức này có thể được sử dụng như là cơ sở và là công cụ cho việc thiết kế cơ sở tri thức, bộ phận suy luận giải toán tự động cũng như thiết kế phần giao diện của chương trình. 1.2.6. Mô hình một đối tượng tính toán (C-Object) Mô hình này được đề xuất bởi Đỗ Văn Nhơn trong công trình luận án tiến sĩ toán học: “Xây dựng hệ tính toán thông minh: Xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động”. Một C-Object có thể được mô hình hóa bởi một bộ: (Attrs, F, Facts, Rules) Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -7- GVHD: PGS. TS. Đỗ Văn Nhơn trong đó: Attrs là tập hợp các thuộc tính của đối tượng, F là tập hợp các quan hệ suy diễn tính toán, Facts là tập hợp các tính chất hay các sự kiện vốn có của đối tượng, và Rules là tập hợp các luật suy diễn trên các sự kiện liên quan đến các thuộc tính cũng như liên quan đến bản thân đối tượng. Ví dụ: Đối tượng (C-Object) “TAM_GIAC” được biểu diễn theo mô hình trên gồm có: • Attrs = { GocA, GocB, GocC, a, b, c, ha, hb, hc, ma, mb, mc, pa, pb, pc, S, p, R, r, ra, rb, rc } • F = { GocA + GocB + GocC = Pi, a*sin(GocB) = b*sin(GocA),  a^2 = b^2 + c^2 - 2*b*c*cos(GocA), . . . } • Facts = {} • Rules = { {GocA = GocB}⇒ {a = b}, {a = b} ⇒ {GocA = GocB}, {a^2 = b^2+c^2}⇒{GocA=pi/2}, {GocA=pi/2} ⇒ {a^2 = b^2+c^2, b ⊥ c}, ...} Khảo sát các bài toán suy diễn và tính toán trên một C-Object và xây dựng các thuật giải thích hợp sẽ là cơ sở cho việc thiết kế các hệ hỗ trợ giải toán kết hợp với sự tra cứu kiến thức và học kiến thức. Tuy nhiên, mỗi loại C-Object khi xét riêng biệt chỉ thể hiện được một phần tri thức có tính chất cục bộ trong ứng dụng trong khi kiến thức của con người về một lĩnh vực hay một phạm vi kiến thức nào đó thường bao gồm các khái niệm và các loại đối tượng khác nhau với những mối quan hệ hữu cơ. 1.2.7. Mô hình cơ sở tri thức các đối tượng tính toán (COKB) Mô hình này được đề xuất bởi Đỗ Văn Nhơn trong công trình luận án tiến sĩ toán học: “Xây dựng hệ tính toán thông minh: Xây dựng và phát triển các mô hình biểu diễn tri thức cho các hệ giải toán tự động”. Trong mô hình này, ngoài những quan hệ tính toán còn có nhiều luật khác trên các loại sự kiện khác nhau. Ở đây không phải chỉ có các loại sự kiện tính toán được quan tâm khảo sát mà ta còn đề cập đến những sự kiện quan hệ khác trên các thuộc Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -8- GVHD: PGS. TS. Đỗ Văn Nhơn tính và trên các đối tượng. Mô hình mạng các C-Object tổng quát sẽ cho ta một phương pháp biểu diễn các dạng bài toán tổng quát trong hệ cơ sở tri thức các CObject, làm cơ sở cho việc thiết kế các môđun giải toán và trợ giúp giải toán trong các hệ giải toán thông minh. 2. MÔ HÌNH TRI THỨC DẠNG HÀM Một mô hình tri thức dạng hàm có thể được mô hình hóa bởi bộ: (Predicate, Facts, Rules) trong đó: −Predicate là tập hợp chứa các định nghĩa danh mục các hàm, gồm: o Tên hàm, o Các đối và kiểu đối của hàm, o Kiểu kết quả của hàm. −Facts là tập hợp các giá trị đặc biệt của các hàm đã được định nghĩa trong tập Predicate. −Rules là tập hợp các công thức biểu diễn mối quan hệ giữa các hàm đã được định nghĩa trong tập Predicate, Rules gồm các bộ công thức được phân loại theo toán tử hay tên hàm. Đặc biệt, nên phân loại như trong thực tế đã phân loại, ví dụ như các công thức lượng giác trong các sách giáo khoa phân thành các bộ công thức: hệ thức cơ bản, cung liên quan đặc biệt, công thức cộng, công thức nhân, công thức hạ bậc, công thức biến đổi tích sang tổng,… thì ta cũng sẽ phân loại như vậy. Ví dụ: Kiến thức về lượng giác có thể được biểu diễn như sau: Predicate = {sin[Real], cos[Real], tan[Real], cot[Real]} Facts = {cos[Pi/3] =1/2, sin[Pi/2] = 1, cos[0] = 1, … (liệt kê tất cả các giá trị đặc biệt của các hàm lượng giác )} Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng -9- GVHD: PGS. TS. Đỗ Văn Nhơn Rules = {{sin[x]2 + cos[x]2 = 1, cot[x]tan[x] = 1, tan[x] = sin[x]/cos[x], cot[x]=cos[x]/sin[x], …}, {}, … (liệt kê tất cả các công thức lượng giác) {(a+b)2 = a2 + 2ab + b2, a2 – b2 = (a+b)(a-b), (hằng đẳng thức)}}. 3. ỨNG DỤNG MÔ HÌNH TRI THỨC DẠNG HÀM ĐỂ GIẢI BÀI TOÁN RÚT GỌN BIỂU THỨC LƯỢNG GIÁC 3.1. Phát biểu bài toán Giả sử có biểu thức exp. Rút gọn biểu thức exp: Có thể biến đổi biểu thức exp thành một biểu thức expnew mà expnew gọn hơn exp không? Định nghĩa: Một biểu thức exp1 được gọi là gọn hơn biểu thức exp2 nếu độ dài của biểu thức exp1 nhỏ hơn độ dài của biểu thức exp2. Nếu độ dài bằng nhau, giữa các hàm là phép lũy thừa thì gọn hơn phép nhân, chia và phép, nhân chia lại gọn hơn phép cộng, trừ. Độ dài của biểu thức exp được định nghĩa như sau: Length[exp] = số lượng hàm xuất hiện trong exp Như vậy, biểu thức hằng có độ dài bằng 0. Ví dụ: exp = 9 (hay a, a+c) thì Length[exp] = 0 exp = sin[x]cos[x] + tan[x] có Length[exp] = 3 exp = cos[x-y] có Length[exp] = 1 exp = cos[x]cos[y] + sin[x]sin[y] có Length[exp] = 4. Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng - 10 - GVHD: PGS. TS. Đỗ Văn Nhơn 3.2. Giải quyết bài toán 3.2.1. Chuẩn bị cơ sở tri thức − Khai báo Predicate − Nhập giá trị đặc biệt cho các hàm Facts − Nhập tất cả các công thức Rules. Chia tập hợp Rules thành các bộ công thức, do người sử dụng chia theo trong thực tế, nếu không, chương trình chia tự động theo tên hàm hay toán hạng. 3.2.2. Thuật giải suy diễn tiến Bước 1: Xác định tất cả các công thức có thể dùng. Nếu exp không thể áp dụng được công thức nào thì thực hiện biến đổi cơ bản cho exp (các phép biến đổi cơ bản là quy đồng, khai triển, đặt thừa số chung, nhân lượng liên hợp) và lặp lại bước 1. Bước 2: Áp dụng các công thức đó vào biến đổi exp. Lặp lại hai bước trên cho đến khi exp được rút gọn. 3.2.3. Thuật giải suy diễn tiến với Heuristics Để tìm được lời giải một cách nhanh chóng, chúng ta có thể sử dụng một số luật heuristic vào phương pháp suy diễn tiến. Xem xét phương pháp con người giải các bài toán, ta dùng các luật heuristic trong thuật giải. Sau đây là một số luật được sử dụng: Chia tập hợp Rules các công thức ra thành nhiều bộ công thức khác nhau như con người đã từng làm trong thực tế. Với một biểu thức đã cho, chọn bộ công thức nào “thích hợp” nhất để rút gọn biểu thức đó. Sau khi đã chọn được một bộ công thức thích hợp, ta sử dụng các luật heuristic lại chọn một công thức “thích hợp” nhất để áp dụng vào biến đổi biểu thức. Nếu kết quả bước 2 chỉ có một công thức có thể áp dụng được thì chọn ngay công thức đó. Ngược lại, chọn một công thức để áp dụng theo các ưu tiên sau: Ưu tiên 1: Ưu tiên sử dụng công thức có kết quả là hằng số. Ví dụ: Nếu kết quả ở bước 2, có 3 công thức có thể áp dụng là: Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng - 11 - GVHD: PGS. TS. Đỗ Văn Nhơn sin[x]2 + cos[x]2 = 1 sin[x]2 = 1 − cos[2 x] 2 cos[x]2 = 1 + cos[2 x] 2 thì ta dùng ưu tiên này chọn công thức thứ nhất sin[x]2 + cos[x]2 = 1 để áp dụng. Ưu tiên 2: Ưu tiên sử dụng công thức phát sinh các hàm, các dạng đối liên quan đến kết quả. (ví dụ: kết quả có tan (cung 2x như tan[2x]) thì ưu tiên dùng các công thức biến đổi sang tan, (cung [2x]) …) Ví dụ: Giả sử sau bước giải 1, ta có: exp = − cos[ x]2 + cos[ x]2 sin[ x] 2 kết quả bài toán rút gọn này là: cos[x]2cot[x]2 và có 4 công thức có thể dùng là: sin[x]2 = 1 − cos[2 x] 2 cos[x]2 = 1 + cos[2 x] 2 cos[ x] = tan[ x] sin[ x] 1 = 1 + cot[ x] 2 sin[ x] 2 thì ta chọn công thức 1 = 1 + cot[ x] 2 để áp dụng. sin[ x] 2 Ưu tiên 3: Ưu tiên sử dụng công thức không sinh ra hàm mới, biến mới so với kết quả (để hy vọng đồng dạng, gom lại những hạng tử đồng dạng). Ví dụ như exp chỉ chứa cung x thì không nên dùng các công thức biến đổi sang cung 2x. (đến khi nào vẫn chưa ra kết quả thì mới dùng). Ví dụ: Rút gọn biểu thức: exp = cos[x]sin[x](1+tan[x])(1+cotan[x]) Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng GVHD: PGS. TS. Đỗ Văn Nhơn - 12 - Ta có, công thức có thể áp dụng là: cos[x]sin[x] = tan[x] = sin[2 x] 2 sin[ x] cos[ x] nhưng không chọn công thức thứ nhất vì sẽ ra kết quả chứa cung mới 2x, mà chọn công thức tan[x] = sin[ x] để biến đổi. cos[ x] Ưu tiên 4: Ưu tiên sử dụng công thức có vế trái dài nhất (để hy vọng biến đổi phần dài nhất đó thành phần ngắn hơn). Ví dụ: Rút gọn biểu thức exp với: exp = 1 + tan[a ] 2 1 − tan[a ] 2 thì bước giải đầu tiên ta có các công thức có thể dùng là: tan[a] = sin[a ] 1 và 1 + tan[a]2 = cos[a ] cos[a ]2 và vì cả hai công thức đều không rơi vào các ưu tiên từ 1 đến 3 nên khi áp dụng ưu tiên 4 ta chọn để áp dụng công thức 1 + tan[a]2 = 1 vì công thức này có vế cos[a ]2 trái là 1 + tan[a]2 dài hơn vế trái của công thức tan[a] = sin[a ] là tan[a]. cos[a ] Từ đó ta có thuật giải suy diễn tiến với heuristic để rút gọn biểu thức như sau: Bước 1: Xét exp “thích hợp” với bộ công thức nào nhất => chọn một bộ công thức “thích hợp” nhất (bộ công thức có nhiều công thức có vế trái xuất hiện trong exp nhất, nếu có nhiều bộ công thức như thế thì ta ưu tiên chọn bộ công thức ưu tiên dùng trong thực tế, chẳng hạn như đối với dạng lượng giác ta thường dùng các hệ thức cơ bản hơn là các công thức hạ bậc, điều này có thể được thể hiện bằng việc đánh trọng số cho từng bộ công thức) Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng - 13 - GVHD: PGS. TS. Đỗ Văn Nhơn Bước 2: Với bộ công thức chọn được ở bước 1, phát sinh tất cả các công thức có thể có (chỉ phát sinh công thức để tìm số hạng) và thêm các công thức này vào bộ công thức đó. Ví dụ: Với công thức: cos[x]2 +sin[x]2 = 1, ta phát sinh thêm các công thức: cos[x]2 = 1 – sin[x]2, sin[x]2 = 1 – cos[x]2 và các công thức theo chiều ngược lại: 1 = sin[x]2 + cos[x]2 (hằng số chuyển sang vế phải) Repeat Bước 3: Trên bộ công thức tìm được ở bước 2, xác định tất cả các công thức mà exp có thể dùng (là tất cả những công thức có vế trái xuất hiện trong exp). Nếu không có công thức nào mà exp áp dụng được thì thực hiện biến đổi cơ bản cho exp (các phép biến đổi cơ bản là quy đồng, khai triển, đặt thừa số chung, nhân lượng liên hợp) rồi lặp lại bước 3. Lưu ý chọn phép biến đổi cơ bản sao cho kết quả xuất hiện vế trái của một công thức nào đó trong bộ công thức đang được phép áp dụng (đó là bộ công thức xác định ở bước 2). Nếu không có phép biến đổi cơ bản nào cho kết quả như thế, ta sang bước 1 để chọn bộ công thức khác. Bước 4: Dùng các luật ưu tiên để chọn một công thức “thích hợp” nhất, nếu vẫn còn nhiều hơn một công thức “thích hợp” nhất thì chọn công thức đầu tiên. (vì thế nên xếp các công thức trong cơ sở tri thức theo thứ tự mức ưu tiên thường dùng giảm dần). Bước 5: Áp dụng công thức xác định được ở bước 4 vào biến đổi biểu thức exp. Ghi nhận lại sự kiện hay công thức được sử dụng và kết quả biến đổi. Until (với bộ công thức đang dùng, không thể áp dụng được công thức nào nữa) Lặp lại từ bước 1 đến bước 5 cho đến khi biểu thức exp được rút gọn. Ví dụ: Rút gọn biểu thức: exp = sin[x]cos[x](1+tan[x])(1+cot[x]) Bước 1: Ta có biểu thức exp “thích hợp” với bộ công thức fHệThứcCơBảnSangSinCos nhất, với: fHệThứcCơBảnSangSinCos = Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011 Biểu diễn tri thức và ứng dụng GVHD: PGS. TS. Đỗ Văn Nhơn - 14 - {cos[x]2 + sin[x]2 = 1, cot[x]tan[x] = 1, 1 + tan[x]2 = 1 , 1 + cot[x]2 = 2 cos[ x] 1 sin[ x] cos[ x] , tan[x] = , cot[x] = }; 2 cos[ x] sin[ x] sin[ x] vì có số công thức có vế trái xuất hiện trong exp là nhiều nhất (hai công thức): tan[x] = sin[ x] cos[ x] cot[x] = cos[ x] sin[ x] Bước 2: Phát sinh tất cả các công thức có thể có, ta được bộ công thức fHệThứcCơBảnSangSinCos trở thành: fHệThứcCơBảnSangSinCos = {cos[x]2 + sin[x]2 = 1, cot[x]tan[x] = 1, 1 + tan[x]2 = 1 , 1 + cot[x]2 = 2 cos[ x] 1 sin[ x] cos[ x] , tan[x] = , cot[x] = , cos[x]2 = 1 – sin[x]2, sin[x]2 = 1 – cos[x]2 , 2 cos[ x] sin[ x] sin[ x] 1 = sin[x]2+ cos[x]2 } Bước 3: Tất cả những công thức có thể dùng là: tan[x] = sin[ x] cos[ x] cot[x] = cos[ x] sin[ x] sin[ x] cos[ x] Bước 4: Chọn công thức tan[x] = Bước 5: exp = sin[x]cos[x](1 + sin[ x] )(1 + cot[x]) cos[ x] Bước 3: Công thức có thể dùng: cot[x] = cos[ x] sin[ x] Bước 4: Chọn ngay công thức này Học viên:Vũ Đăng Khôi Cao học CNTT khóa 6/2011
- Xem thêm -