Bài giảng Trí tuệ nhân tạo - Bài 11, 12, 13 : Lập trình logic Prolog

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

113
lượt xem 20
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong bài giảng này, chúng ta sẽ cùng tìm hiểu về lập trình logic Prolog. Trong chương này gồm có các nội dung chính sau: Biễu diễn cấu trúc danh sách, một số vị từ xử lí danh sách, các thao tác cơ bản trên danh sách,... Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Trí tuệ nhân tạo - Bài 11, 12, 13 : Lập trình logic Prolog

S ROLOG WI • Hiện nay đã có nhiều hệ lập trình logic ra đời mà tiêu biểu là Prolog. Prolog là viết tắt của cụm từ tiếng Pháp ”Programmation en Logique” • Hệ Prolog đầu tiên ra đời vào năm 1973 do Alain Colmerauer và nhóm trí tuệ nhân tạo thuộc Đại học tổng hợp Aix-Marseilie, Pháp xây dựng. • Mục đích ban đầu của hệ này là dịch các ngôn ngữ tự nhiên. 1
• Điều khác nhau căn bản của lập trình Prolog so với lập trình truyền thống là: • • Trong Prolog người lập trình mô tả vấn đề bằng các câu trong logic. • • Hệ sẽ sử dụng lập luận logic để tìm ra các câu trả lời cho vấn đề. 2
• Một chương trình Prolog gồm một dãy các luật có dạng: A :- B1, ..., Bm • trong đó, m ≥ 0, A và Bi (i = 1, ..., m) là các câu phân tử. Luật trên được đọc là “A nếu B1 và ... và • Bm”. Nó là cách viết trong Prolog của logic mênh đề sau: • A B B m ⇒ ∧ ∧… 1 • Trong luật trên, A được gọi là đầu, danh sách các câu Bi (B1, ..., Bm) được gọi là thân của luật. • Nếu m=0, ký hiệu “:-” sẽ được bỏ đi, khi đó ta có câu phân tử A và nó được gọi là một sự kiện. 3
Ví dụ. • Giả sử chúng ta biết các thông tin sau đây về An và Ba: • An yêu thích mọi môn thể thao mà cậu chơi. • Bóng đá là môn thể thao. • Bóng bàn là môn thể thao. • An chơi bóng đá. • Ba yêu thích mọi thứ mà An yêu thích. => Các câu trên được chuyển thành 1 chương trình Prolog sau : • likes(an, X) :- sport(X), plays(an, X) • sport(football). • sport(tennis). • plays(an, football). • likes(ba, Y) :- likes(an, Y). => Câu hỏi : “An yêu thích cái gì ?”: ? - likes(an, X). 4
5
S ROLOG WI Tiết 3: CẤU TRÚC DANH SÁCH Giáo sinh thực hiện: Đặng Thị Mỹ Bình 6
NỘI DUNG I Biễu diễn cấu trúc danh sách II Một số vị từ xử lí danh sách III Các thao tác cơ bản trên danh sách 4 7
I. Biễu diễn cấu trúc danh sách - Danh sách là kiểu dữ liệu có cấu trúc được sử dụng rộng rãi trong các ngôn ngữ lập trình phi số - Một danh sách (list) là một dãy các phần tử cùng kiểu Ví dụ: [ann, tennis, tom, skiing] là một list được viết ở Prolog - Chú ý rằng các list được diễn tả trong Prolog bằng các cây nhị phân 8
. - List rỗng được diễn tả bởi [ ] . ann - Một list khác rỗng gồm có Head hai thành phần: tennis . Tail tom .  Phần tử đầu tiên (head) skiing []  Phần đuôi của list (tail) - Các phần tử của 1 list có thể là bất kì loại đối tượng nào, kể cả 1 list. 9
• Prolog cung cấp ba cách viết danh sách – [Item1, Item2, ...] – [Head | Tail] – [Item1, Item2, ... | others] Prolog dùng dấu | (split) để tách biệt phần head và tail của list . L= [ann, tennis, tom, skiing] L= [ann | [tennis, tom, skiing]] ann . L= [ann, tennis, tom, skiing | []] tennis . HOẶC: tom . L= [ann | tennis | [tom, skiing]] skiing [] …. 10
II. Một số vị từ xử lí danh sách: có sẵn trong Prolog VỊ TỪ Ý NGHĨA VÍ DỤ Kiểm tra xem X có phải là 1 ?- member(a,[a,b,c]). 1. member(X,L). một phần tử của danh sách Yes L không. 2 ?- append([a,b,c],[1,2],L). 2. append(L1,L2,L). Ghép danh sách L1 và L2 L = [a, b, c, 1, 2] vào thành L Yes 3. nextto(X,Y,L). Kiểm tra xem Y có đứng 3 ?- nextto(b,a,[a,b,c]). ngay sau X trong L không. No Lấy X ra khỏi L để trả về 4 ?- select(3,[3,4,2],L). phần tử còn lại trong L1. 4. select(X,L,L1). - Có thể dùng để chèn thêm 1 L=[4,2] phần tử vào danh sách. Yes 11
VỊ TỪ Ý NGHĨA VÍ DỤ Kiểm tra xem phần tử thứ 5. nth0(Index,L,X). Index (tính từ 0) của L có 1 ?- nth0(1,[a,b,c],a). phải là X không. No Kiểm tra xem phần tử thứ 2 ?- nth1(1,[a,b,c],a). 6. nth1(Index,L,X). Index (tính từ 1) của L có Yes phải là X không. Kiểm tra xem X có đứng 3 ?- last([a,b,c,d],d). 7. last(L,X). cuối trong L không. Yes Nghịch đảo danh sách L1, 4 ?- reverse([a,b,c],L). 8. reverse(L1,L2). kết quả trả về L2. L=[c,b,a] 9.Permutation(L1,L2).Danh sách L2 là hoán vị của 5 ?- Permutation([a,b ,c], L) . danh sách L1 12
III. Các thao tác cơ bản trên danh sách 1. Kiểm tra một phần tử X có mặt trong danh sách L: dựng lại một số vị từ có sẵn. * Xây member (X , L). a . Ví dụ: . tử X thuộc danh sách L nếu: b 1 ?-Phần => member(a,[a,b,c,d]). c . 1. Yes X là đầu của L, hoặc nếu 2. 2 ?- X là một phần tử của]]). member(d,[a,b,[c,d đuôi của L d [] No  Xây dựng lại hai điều kiện trên thành hai mệnh đề: 3 ?- member([c,d],[a,b,[c,d]]). Sự kiện: member (X, [X | Tail]). Yes Luật: member (X, [Head | Tail]) :- member(X,Tail). 13
2. Ghép hai danh sách append (L1, L2, L). Xây dựng lại vị từ này: - Có- thể dùng append để phân tách danh sách đã cho thành danhXét -Ghép hai sách trường haimới hợp:L1 và L2, kết quả trả về L danh sách VíVídụ1. : :1Nếu dụ L1 =(L1, 1 ?- ?- append rỗng L2,thì append viếtb], ([a, [a,b,c] ).như [c,sau: append ([], L, L). d], L). 2. L1 Nếu= [] L1 L=≠[a, rỗng thìd]nó gồm một đầu và một đuôi b, c, như L2 = [a,sau: b, c];[X | L1] Yes L1 = [a] Kết quả phép ghép danh sách là: L2 = [b, c]; append ([X | L1], L2, [X | L3]) :- append (L1, L2, L3). L1 = [a, b]; … X L1 L2 L3 14
3. Nghịch đảo danh sách reverse (L1, L2). - Nghịch đảo danh sách L1, kết quả trả . về danh sách L2. . a - Ví dụ: . b 1 ?- reverse([a, b, c, d], L). c . L = [d, c, b, a] Yes d [] - Thủ tục nghịch đảo được viết như sau: Reverse ([], []). Reverse ([X | Tail], L) :- Reverse (Tail, L1), append (L1, [X], L). Trong đó: L1 là danh sách nghịch đảo trung gian. 15
4. Hoán vị danh sách permutation (L1, L2). - Danh sách L2 là hoán vị của danh sách L1. - Ví dụ: 1 ?- permutation([a, b, c], L) . L = [a,b,c] ; L = [a,c,b] ; L = [c,b,a] ; … - Thủ tục hoán vị được viết trong Prolog như sau: permutation ([], []). permutation ([X | L], P) :- permutation(L, L1), insert(X, L1, P). 16
H·y nhí! [Item 1, Item 2,… ]  Danh sách là một cấu trúc hoặc rỗng hoặc gồm hai phần: Head và Tail. [Head | Tail ]  Prolog quản lí danh sách theo cấu trúc cây nhị phân và có nhiều cách [Item 1, Item 2,… | Others ] biểu diễn DS  Các thao tác thường dùng với danh với Tail, Others là các danh sách sách là: kiểm tra xem một phần tử có thuộc DS không, nghịch đảo danh sách, hoán vị danh sách,… 17
Bài tập về nhà 1 Bổ sung một phần tử vào danh sách. 2 Loại bỏ một phần tử ra khỏi danh sách. 18