Giáo trình Nhập môn trí tuệ nhân tạo - ĐH Đà Lạt

Giáo trình “Nhập môn Trí tuệ nhân tạo” được viết dành cho sinh viên ngành Toán – Tin, Tin học và Công nghệ thông tin. Để đọc giáo trình này, sinh viên cần có kiến thức cơ bản về lôgic, cấu trúc dữ liệu và thuật toán. Nội dung giáo trình này gồm 4 chương: Chương 1: Khái niệm về trí tuệ nhân tạo Chương 2: Các phương pháp giải quyết vấn đề Chương 3: Biểu diễn và xử lý tri thức Chương 4: Lập trình lôgic Chương 1 giới thiệu tóm tắt lịch sử hình thành và phát triển...
Nội dung trích xuất từ tài liệu:
Giáo trình Nhập môn trí tuệ nhân tạo - ĐH Đà Lạt Giáo trình Nhập môn trí tuệ nhân tạo TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA TOÁN –TIN Trương Chí Tín GIÁO TRÌNH NHẬP MÔN TRÍ TUỆ NHÂN TẠO Đà Lạt, 04 - 2009 LỜI MỞ ĐẦU Giáo trình “Nhập môn Trí tuệ nhân tạo” được viết dành cho sinh viên ngành Toán – Tin, Tin học và Công nghệ thông tin. Để đọc giáo trình này, sinh viên cần có kiến thức cơ bản về lôgic, cấu trúc dữ liệu và thuật toán. Nội dung giáo trình này gồm 4 chương: Chương 1: Khái niệm về trí tuệ nhân tạo Chương 2: Các phương pháp giải quyết vấn đề Chương 3: Biểu diễn và xử lý tri thức Chương 4: Lập trình lôgic Chương 1 giới thiệu tóm tắt lịch sử hình thành và phát triển cũng như các khái niệm chung nhất, các lĩnh vực nghiên cứu và ứng dụng chính của trí tuệ nhân tạo. Chương 2 trình bày các phương pháp biểu diễn và giải quyết vấn đề cơ bản: biểu diễn vấn đề trong không gian trạng thái bằng đồ thị thông thường, đồ thị VÀ/HOẶC, các phương pháp xác định trực tiếp lời giải, các phương pháp thử – sai (trong đó trình bày các phương pháp tìm kiếm theo chiều rộng, chiều sâu, theo hướng cực tiểu giá thành trên cây và đồ thị, thuật giải di truyền, phương pháp GPS, …) và các kỹ thuật heuristic. Chương 3 đề cập đến các phương pháp biểu diễn tri thức bằng: lôgic, luật sinh, mạng ngữ nghĩa, khung và các phương pháp xử lý tri thức bằng suy diễn dựa trên lôgic tất định và bất định. Chương 4 giới thiệu kỹ thuật lập trình lôgic thông qua ngôn ngữ lập tình Prolog. Cuối mỗi chương có phần bài tập nhằm củng cố chắc hơn kiến thức lý thuyết và rèn luyện kỹ năng thực hành cho học viên. Các phần được in chữ nhỏ dành cho học viên đọc thêm. Chắc chắn tài liệu này không tránh khỏi sơ suất, tác giả rất mong nhận được và chân thành biết ơn các ý kiến đóng góp quí báu của các bạn đồng nghiệp và độc giả nhằm làm cho giáo trình hoàn chỉnh hơn trong lần tái bản sau. Đà lạt, 04 - 2009 Tác giả MỤC LỤC Lời mở đầu CHƯƠNG I. KHÁI NIỆM VỀ TRÍ TUỆ NHÂN TẠO I.1. Lược sử hình thành và phát triển 1 I.2. Những lĩnh vực nghiên cứu của trí tuệ nhân tạo (TTNT) 3 I.3. Những ứng dụng của TTNT 6 CHƯƠNG II. CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ II.1. Các phương pháp xác định trực tiếp lời giải 8 II.1.1. Phương pháp giải chính xác 8 II.1.2. Phương pháp giải gần đúng 8 II.1.3. Phương pháp giải không tường minh, đệ qui 8 II.1.4. Phương pháp qui hoạch động 11 II.2. Các phương pháp thử – sai 13 II.2.1. Phương pháp vét cạn, nguyên lý mắt lưới, phương pháp sinh và thử, phương pháp nhánh cận 13 a. Phương pháp vét cạn 13 b. Nguyên lý mắt lưới 14 c. Phương pháp sinh và thử 15 d. Phương pháp nhánh cận 16 II.2.2. Phương pháp ngẫu nhiên 17 a. Phương pháp Monte - Carlo 17 b. Thuật giải di truyền GA 18 II.2.3. Nguyên lý mê cung 20 II.2.4. Các phương pháp biểu diễn và giải quyết vấn đề trong không gian trạng thái bằng cây và đồ thị 22 a. Biểu diễn vấn đề trong không gian trạng thái 22 b. Phương pháp tìm kiếm lời giải 27 c. Các dạng đặc biệt thường gặp: tìm kiếm theo chiều rộng, chiều sâu, sâu dần, cực tiểu AT 28 II.2.5. Quy bài toán về bài toán con và các chiến lược tìm kiếm trên đồ thị VÀ / HOẶC 32 a. Quy bài toán về bài toán con 32 b. Biểu diễn bài toán dưới dạng đồ thị VÀ / HOẶC 33 c. Các phương pháp tìm kiếm trên cây VÀ / HOẶC: tìm kiếm theo chiều rộng, chiều sâu, cực tiểu 34 II.2.6. Phương pháp GPS 40 II.3. Kỹ thuật Heuristic 42 II.3.1. Các thuật giải tìm kiếm tối ưu trên cây và đồ thị với tri thức heuristic 44 a. Thuật giải AKT 44 b. Thuật giải A* 44 c. Các ví dụ 45 II.3.2. Nguyên lý t ...