Đề thi kết thúc học phần
MÔN: TRÍ TUỆ NHÂN TẠO (L N 2) Thời gian: 90 phút
Câu 1: Cho bài toán sau:
Có hai can có dung tích lần lượt là 4 lít và 9 lít, một bể nước (giả thiết có đủ nước cho các thao
tác thực hiện trong bài toán này), và một thùng chứa tạm để đựng nước (giả thiết cũng đủ lớn để
chứa nước cho các thao tác thực hiện trong bài toán). Chúng ta cần lấy ra chính xác 6 lít nước
trong can 9 lít hoặc trong thùng chứa tạm. Các thao tác chúng ta có thể thực hiện như sau:
- Lấy đầy nước vào môt can từ bể nước
- Đổ hết nước của một can vào thùng chứa tạm hoặc đổ vào bể
- Đổ nước từ một can vào can khác đến khi hêt nước ở can thứ nhất hoặc đến khi can thứ hai đầy Yêu c u:
1. Biểu diễn trạng thái của bài toán, vẽ cây không gian trạng thái của bài toán, với gốc của cây là
trạng thái đầu tiên và độ sâu của cây là 3.
2. Hãy chỉ ra các phương pháp tìm kiếm mà Anh (Chị) đã biết có thể sử dụng được để tìm ra lời
giải của bài toán trên. Muốn tìm được lời giải có số thao tác thực hiện ít nhất thì áp dụng phương
pháp nào và lời giải đó là gì? (Các bạn có thể vẽ cây tìm kiếm bằng giấy nháp, không yêu cầu trình bày trong bài làm). Câu 2:
a/ Biểu diễn các thông tin cho bởi các câu sau sang thành các câu trong Logic cấp một:
- Mọi sinh viên đều học môn Cơ sở dữ liệu hoặc môn Mạng máy tính
- Tất cả sinh viên học môn Cơ sở dữ liệu đều biết SQL
- Tất cả sinh viên biết SQL đều không thích Excel
- An là sinh viên thích Excel
b/ Với các thông tin trong câu a (Cơ sở tri thức), hãy sử dụng các luật hợp giải (Resolution) để
chứng minh rằng An là sinh viên học môn Mạng máy tính (yêu cầu liệt kê các bước chứng minh).
Câu 3: Thế nào là câu dạng Horn trong Logic cấp 1, và các câu dạng Horn có ý nghĩa gì trong
việc xây dựng các giải thuật lập luận. ĐÁP ÁN Câu 1: (4 đ)
1. (2đ) Biểu diễn trạng thái của bài toán là: (x,y,z) với x, y, z là lượng nước có trong can 4
lít, 9 lít và thùng chứa. Cây không gian trạng thái của bài toán có độ sâu 3 và gốc là trạng thái đầu như sau (0,0,0) |---(4,0,0) | |----(4,9,0) | | |---- (0,9,4) | | |----(4,0,9) | |----(0,4,0) | | |----(4,4,0) | | |----(0,0,4) | |---(0,0,4) | |---(4,0,4) | |---(0,9,4) |---(0,9,0) |---(4,9,0) | |---(0,9,4) | |---(4,0,9) |---(4,5,0) | |---(0,5,4) | |---(4,0,5) |---(0,0,9) |---(4,0,9) |---(0,9,9)
2. Chiến lược tìm kiếm theo chiều rộng, tìm kiếm tiến, tìm kiếm lùi có thể áp dụng để giải
bài toán trên, tìm kiếm theo chiều rộng sẽ tìm được lời giải có số thao tác thực hiện là ít
nhất, lời giải đó là: (0,0,0) --- (0,9,0) --- (4,5,0) --- (4,0,5) --- (0,0,5) --- (0,9,5) --- (4,5,5)
--- (0,5,5) --- (4,1,5) --- (4,0,6) (Có thể có lời giải khác cũng có số thao tác như lời giải này) Câu 2 (5 đ) a/ (2đ) Cơ sở tri thức:
∀x HocCSDL(x) ∨ HocMangMT(x)
∀x HocCSDL(x) => BietSQL(x)
∀x BietSQL(x) => ¬ ThichExcel(x) ThichExcel(An)
b/ (3đ) Chứng minh câu truy vấn q từ cơ sở tri thức KB bằng các luật hợp giải là chứng minh
KB, ¬q => []. Để áp dụng luật hợp giải, chuyển cơ sở tri thức và phủ định của câu cần chứng
minh sang sạng chuẩn hội. Dạng chuẩn hội và các bước chứng minh như sau: HocCSDL(x) ∨ HocMangMT(x) (1) ¬ HocCSDL(x) ∨ BietSQL(x) (2)
¬ BietSQL(x) ∨ ¬ ThichExcel(x) (3) ThichExcel(An) (4) ¬ HocMangMT(An) (5)
Các bước chứng minh bằng hợp giải như sau:
(1), (5) {x=An} => HocCSDL(An) (6)
(6), (2) {x=An} => BietSQL(An) (7)
(7), (3) {x=An} => ¬ ThichExcel(An) (8) (8), (4) {x=An} => [] (9) Câu 3: (1đ)
- Câu dạng chuẩn Horn là câu dạng chuẩn hội, trong đó có nhiều nhất 1 literal dương
(không có ký hiêu phủ định phía trước)
- Giải thuật hợp giải tổng quát làm việc không hiệu quả. Nếu cơ sở tri thức và phủ định của
câu truy vấn biểu diễn dạng Horn thì sẽ có giải thuật hợp giải có độ phức tạp tuyến tính
đối với số câu có trong cơ sở tri thức.