Giáo trình Trí tuệ nhân tạo: Phần 1 - ĐH Huế

ĐẠI HỌC HUẾ<br /> TRƯỜNG ĐẠI HỌC KHOA HỌC<br /> <br /> Giáo trình<br /> <br /> TRÍ TUỆ NHÂN TẠO<br /> <br /> Huế, 2004<br /> <br /> Lời nói đầu<br /> Trong các năm qua, nhiều tài liệu của ngành công nghệ thông tin đã được giới<br /> thiệu nhiều cho các cán bộ nghiên cứu, ứng dụng và sinh viên ở bậc đại học.<br /> Tuy nhiên các giáo trình của ngành học này chưa đáp ứng dược nhu cầu của<br /> sinh viên các trường đại học, đặc biệt đối với sinh viên khu vực miền Trung.<br /> Vì vậy, chúng tôi biên soạn giáo trình “Trí tuệ nhân tạo”, một môn cơ sở<br /> chuyên ngành trong chương trình đào tạo Cử nhân Tin học, ngoài mục đích<br /> xây dựng nhiều giáo trình trên một khung chương trình đào tạo, mà còn giúp<br /> cho sinh viên có tài liệu học tập phù hợp với hoàn cảnh thực tế của Đại học<br /> Huế.<br /> Trong cuốn sách này, sinh viên được làm quen với một số kiến thức cơ bản<br /> nhất về các phương pháp tìm kiếm lời giải và các phương pháp xử lý tri thức.<br /> Ngoài ra, cuốn sách cũng giới thiệu một số chương trình cài đặt, nhằm giúp<br /> sinh viên có thể hiểu một cách tường tận các giải thuật, đồng thời tin tưởng<br /> rằng các giải thuật này có thể áp dung thực tế và cài đặt được trên máy tính<br /> một cách dễ dàng.<br /> Các nội dung trình bày trong cuốn sách đã từng được giảng cho sinh viên<br /> ngành Công nghệ Thông tin tại Đại học Huế trong những năm vừa qua.<br /> Cuốn sách ra đời dưới sự giúp đỡ về mặt vật chất cũng như tinh thần của Đại<br /> học Huế, Trường Đại học Khoa học và đặc biệt là Ban chủ nhiệm Khoa Công<br /> nghệ Thông tin và các đồng nghiệp thuộc Bộ môn Khoa học Máy tính. Chúng<br /> tôi xin gửi tới họ lòng biết ơn. Xin chân thành cám ơn các bạn bè đã cổ cũ và<br /> gíup cho cuốn sách sớm được hoàn thành.<br /> Mặc dù đã hết sức cố gắng, tuy nhiên cuốn sách cũng không tránh khỏi những<br /> thiếu sót. Chúng tôi rất mong được sự góp ý của các độc giả, đặc biệt đối với<br /> các đồng nghiệp và sinh viên để cuốn sách ngày càng hoàn thiện.<br /> Huế, tháng 7 năm 2004<br /> Tác giả<br /> <br /> Tài liệu tham khảo<br /> 1. Bạch Hưng Khang, Hoàng Kiếm<br /> Trí tuệ nhân tạo: Các phương pháp và ứng dụng. Nhà xuất bản Khoa học<br /> và Kỹ thuật, 1989.<br /> 2. Đinh Mạnh Tường<br /> Giáo trình Trí tuệ nhân tạo, Đại học Quốc gia Hà nội.<br /> 3. Nguyễn Thanh Thuỷ<br /> Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri<br /> thức. Nhà xuất bản Giáo dục, 1996.<br /> 4. N. Nilson<br /> Artificial Intelligence. Ed. McGrawhill, 1971<br /> 5. Patrick Henry Winston<br /> Artificial Intelligence. Ed. Addison Wesley, 1992.<br /> .<br /> <br /> Mục lục<br /> Chương 0. Mở đầu<br /> 1. Tổng quan về Khoa học Trí ruệ nhân tạo<br /> 2. Lịch sử phát triển của Trí tuệ nhân tạo<br /> 3. Một số vấn đề Trí tuệ nhân tạo quan tâm<br /> 4. Các khái niêm cơ bản<br /> <br /> 2<br /> 2<br /> 5<br /> 8<br /> 10<br /> <br /> Chương 1. Biểu diễn bài toán trong không gian trạng thái<br /> 1. Đặt vấn đề<br /> 2. Mô tả trạng thái<br /> 3. Toán tử chuyển trạng thái<br /> 4. Không gian trạng thái của bài toán<br /> 5. Biểu diễn không gian trạng thái dưới dạng đồ thị<br /> 6. Bài tập<br /> <br /> 12<br /> 12<br /> 12<br /> 14<br /> 17<br /> 18<br /> 21<br /> <br /> Chương 2.<br /> Các phương pháp tìm kiếm lời giải trong không gian trạng thái<br /> 1. Phương pháp tìm kiếm theo chiều rộng<br /> 2. Phương pháp tìm kiếm theo chiều sâu<br /> 3. Phương pháp tìm kiếm sâu dần<br /> 4. Phương pháp tìm kiếm tốt nhất đầu tiên<br /> 5. Tìm kiếm đường đi có giá thành cực tiểu - Thuật toán AT<br /> 6. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*<br /> 7. Phương pháp tìm kiếm leo đồi<br /> 8. Phương pháp sinh và thử<br /> 9. Phương pháp thoả mãn ràng buộc<br /> 10. Cài đặt một số giải thuật.<br /> 11. Bài tập<br /> <br /> 23<br /> 23<br /> 30<br /> 34<br /> 36<br /> 39<br /> 43<br /> 46<br /> 49<br /> 51<br /> 53<br /> 72<br /> <br /> Chương 3<br /> Phân rã bài toán – Tìm kiếm lời giải trên đồ thị Và/Hoặc<br /> 1. Đặt vấn đề<br /> 2. Đồ thị Và/Hoặc<br /> 3. Các phương pháp tìm kiếm lời giải trên đồ thị Và/Hoặc<br /> 4. Cây tìm kiếm và các đấu thủ<br /> <br /> 90<br /> 90<br /> 92<br /> 94<br /> 104<br /> <br /> Chương 4.<br /> Biểu diễn bài toán bằng logic và các phương pháp chứng minh<br /> <br /> 107<br /> <br /> 1. Biểu diễn vấn đề hờ logic hình thức<br /> 2. Một số giải thuật chứng minh<br /> 3. Ví dụ và bài tập<br /> <br /> 108<br /> 130<br /> 138<br /> <br /> Chương 5. Tri thức và các phương pháp suy diễn<br /> 1. Tri thức và dữ liệu<br /> 2. Các dạng mô tả tri thức<br /> 3. Suy diễn trên luật sản xuất<br /> <br /> 148<br /> 148<br /> 149<br /> 152<br /> <br /> Tài liệu tham khảo<br /> <br /> 163<br /> <br />