1
DANH MỤC HÌNH VẼ .................................................................................................. 4
BẢNG KÝ HIỆU VIẾT TẮT .......................................................................................... 5
CHƢƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO ............................................... 6
1.1. Lịch sử phát triển của TTNT ................................................................................ 6
1.1.1. Lịch sử hình thành và phát triển .................................................................... 6
1.1.2. Đối tƣợng và mục tiêu nghiên cứu của TTNT .............................................. 8
1.1.3. Những tiền đề cơ bản của TTNT ................................................................... 8
1.2. Khái niệm về TTNT ............................................................................................. 9
1.2.1. Trí tuệ của con ngƣời ..................................................................................... 9
1.2.2. Trí tuệ nhân tạo ............................................................................................ 10
1.3. Vai trò của TTNT trong công nghệ thông tin ..................................................... 11
1.4. Các kỹ thuật TTNT ............................................................................................. 11
1.5. Các thành phần trong hệ thống TTNT ................................................................ 12
1.6. Các lĩnh vực nghiên cứu và ứng dụng cơ bản của TTNT .................................. 13
1.6.1. Trò chơi ....................................................................................................... 13
1.6.2. Suy luận và chứng minh định lý tự động .................................................... 14
1.6.3. Các hệ chuyên gia ........................................................................................ 15
1.6.4. Hiểu và mô hình hoá ngữ nghĩa ngôn ngữ tự nhiên .................................... 17
1.6.5. Mô hình hoá hoạt động của con ngƣời ........................................................ 18
1.6.6. Lập kế hoạch và robotics ............................................................................. 19
1.6.7. Các ngôn ngữ và môi trƣờng dùng cho TTNT ............................................ 20
1.6.8. Máy học ....................................................................................................... 21
1.6.9. Xử lý phân tán song song ............................................................................ 22
1.7. Những thách thức đối với TTNT ........................................................................ 23
CÂU HỎI CHƢƠNG 1 ................................................................................................. 25
CHƢƠNG 2: CÁC CHIẾN LƢỢC TÌM KIẾM ........................................................... 26
2.1. Biểu diễn vấn đề trong không gian trạng thái .................................................... 26
2.1.1. Không gian trạng thái của bài toán .............................................................. 26
2.1.2. Các ví dụ ...................................................................................................... 27
2.2. Giới thiệu các chiến lƣợc tìm kiếm .................................................................... 32
2.2.1. Các chiến lƣợc tìm kiếm mù........................................................................ 32
2.2.2. Các chiến lƣợc tìm kiếm kinh nghiệm (tìm kiếm heuristic) ........................ 33
2.3. Cây tìm kiếm ...................................................................................................... 33
2.4. Các chiến lƣợc tìm kiếm mù ............................................................................... 34
2.4.1. Tìm kiếm theo bề rộng ................................................................................ 34
2.4.2. Tìm kiếm theo chiều sâu.............................................................................. 38
2.4.3. Các trạng thái lặp ......................................................................................... 43
2.4.4. Tìm kiếm sâu lặp ......................................................................................... 43
2.4.5.Tìm kiếm trên đồ thị và/hoặc........................................................................ 47
2.5. Các chiến lƣợc tìm kiếm kinh nghiệm ................................................................ 56
2.5.1. Hàm đánh giá và tìm kiếm kinh nghiệm ..................................................... 56
2.5.2 Tìm kiếm tốt nhất đầu tiên............................................................................ 58
2.5.3. Tìm kiếm leo đồi ......................................................................................... 61
2.6. Các chiến lƣợc tìm kiếm tối ƣu .......................................................................... 64
2.6.1. Thuật toán A* .............................................................................................. 66
2.6.2. Thuật toán nhánh_cận.................................................................................. 70
2.7. Các giải thuật tìm kiếm lời giải cho trò chơi ...................................................... 74
2.7.1. Cây trò chơi đầy đủ ..................................................................................... 74
2
2.7.2. Giải thuật Minimax ...................................................................................... 76
2.7.3. Giải thuật Minimax với độ sâu hạn chế ....................................................... 78
2.7.4. Giải thuật Minimax với cắt tỉa Alpha-Beta ................................................. 80
CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 .......................................................................... 83
CHƢƠNG 3. LOGIC MỆNH ĐỀ ................................................................................. 95
3.1. Biểu diễn tri thức ................................................................................................ 95
3.2. Cú pháp và ngữ nghĩa của logic mệnh đề........................................................... 96
3.2.1. Các ký hiệu .................................................................................................. 96
3.2.2. Các quy tắc xây dựng các công thức ........................................................... 97
3.2.2. Ngữ nghĩa .................................................................................................... 97
3.3. Dạng chuẩn tắc ................................................................................................... 99
3.3.1. Sự tƣơng đƣơng của các công thức ............................................................. 99
3.3.2. Dạng chuẩn tắc .......................................................................................... 100
3.3.3. Các câu Horn ............................................................................................. 101
3.4. Luật suy diễn .................................................................................................... 102
3.4. Luật phân giải. Thủ tục chứng minh bác bỏ bằng luật phân giải ..................... 105
CÂU HỎI VÀ BÀI TẬP CHƢƠNG 3 ........................................................................ 113
CHƢƠNG 4: LOGIC VỊ TỪ ....................................................................................... 119
4.1. Cú pháp và ngữ nghĩa của logic vị từ ............................................................... 119
4.1.1. Cú pháp ...................................................................................................... 119
4.1.2. Ngữ nghĩa .................................................................................................. 121
4.2. Các công thức tƣơng đƣơng ............................................................................. 123
4.3. Chuẩn hóa các công thức .................................................................................. 124
4.4. Các luật suy diễn .............................................................................................. 126
4.4.1. Luật thay thế phổ dụng .............................................................................. 126
4.4.2. Hợp nhất .................................................................................................... 126
4.4.3. Luật Modus Ponens tổng quát ................................................................... 127
4.4.4. Luật phân giải tổng quát ............................................................................ 128
4.5. Thuật toán hợp nhất .......................................................................................... 129
4.6. Chứng minh bằng luật phân giải ...................................................................... 131
4.7. Các chiến lƣợc phân giải .................................................................................. 137
4.7.1. Chiến lƣợc phân giải theo bề rộng ............................................................ 139
4.7.2. Chiến lƣợc phân giải sử dụng tập hỗ trợ ................................................... 139
4.7.3. Chiến lƣợc tuyến tính ................................................................................ 141
4.8. Xây dựng CSTT ................................................................................................ 141
CÂU HỎI VÀ BÀI TẬP CHƢƠNG 4 ........................................................................ 144
CHƢƠNG 5. BIỂU DIỄN TRI THỨC ....................................................................... 148
5.1. Các dạng mô tả tri thức..................................................................................... 148
5.1.1. Biểu diễn tri thức bằng logic ..................................................................... 148
5.1.2. Biểu diễn tri thức bằng mạng ngữ nghĩa ................................................... 148
5.1.3. Biểu diễn tri thức bằng khung (Frame) ..................................................... 149
5.1.4. Biểu diễn tri thức bằng các luật nếu - thì .................................................. 149
5.2. Lập luận tiến ..................................................................................................... 151
5.2.1. Khái niệm .................................................................................................. 151
5.2.2. Thủ tục lập luận tiến .................................................................................. 153
5.3. Lập luận lùi ....................................................................................................... 158
5.3.1. Khái niệm lập luận lùi ............................................................................... 158
5.3.2. Thủ tục lập luận lùi .................................................................................... 160
3
5.4. Lập trình Prolog ................................................................................................ 166
5.4.1. Giới thiệu ngôn ngữ Prolog ....................................................................... 166
5.4.2. Cú pháp Prolog .......................................................................................... 167
5.4.3. Các kiểu dữ liệu sơ cấp của Prolog ........................................................... 169
5.4.4. Sự kiện và luật trong Prolog ...................................................................... 170
5.4.5. Kiểu dữ liệu cấu trúc của Prolog ............................................................... 182
5.4.6. Ngữ nghĩa của chƣơng trình Prolog .......................................................... 184
5.4.7. Các phép toán ............................................................................................ 190
CÂU HỎI VÀ BÀI TẬP CHƢƠNG 5 ........................................................................ 203
HƢỚNG DẪN GIẢI BÀI TẬP ................................................................................... 205
1. Bài tập Chƣơng 2 ................................................................................................. 205
2. Bài tập Chƣơng 3 ................................................................................................. 238
3. Bài tập Chƣơng 4 ................................................................................................. 248
4. Bài tập Chƣơng 5 ................................................................................................. 256
TÀI LIỆU THAM KHẢO ........................................................................................... 259
4
DANH MỤC HÌNH VẼ
Hình 1.1. Những tiền đề cơ bản của TTNT ..................................................................... 9
Hình 2.1. Mô tả không gian trạng thái bằng đồ thị định hƣớng .................................... 27
Hình 2.2. Trò chơi 8 số .................................................................................................. 28
Hình 2.3. Đồ thị biểu diễn cách rót nƣớc ...................................................................... 30
Hình 2.4. Biểu diễn không gian trạng của bài toán Tháp Hà Nội. ................................ 31
Hình 2.5. Một phần không gian trạng thái của bài toán với n=3 ................................... 32
Hình 2.6. Đồ thị không gian trạng thái và cây tìm kiếm tƣơng ứng ............................. 34
Hình 2.7. Đồ thị không gian trạng thái .......................................................................... 36
Hình 2.8. Đồ thị không gian trạng thái .......................................................................... 40
Hình 2.9. Đồ thị không gian trạng thái ví dụ 2.13 ......................................................... 45
Hình 2.10. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.13 ....................................... 46
Hình 2.11. Đồ thị không gian trạng thái ví dụ 2.14 ....................................................... 46
Hình 2.12. Các mức tìm kiếm trong cây tìm kiếm ví dụ 2.14 ....................................... 47
Hình 2.13. Quy một tích phân về các tích phân cơ bản ................................................. 48
Hình 2.14. Bản đồ nối các thành phố ............................................................................ 48
Hình 2.15. Đồ thị và/hoặc và vấn đề tìm đƣờng đi ....................................................... 49
Hình 2.16. Đồ thị và hoặc biểu diễn toán tử a b, c, d ............................................... 49
Hình 2.17. Minh họa đồ thị và/hoặc .............................................................................. 50
Hình 2.18. Cây nghiệm .................................................................................................. 51
Hình 2.19. Đồ thị và/ hoặc trong Ví dụ 2.16 ................................................................. 54
Hình 2.20. Cây nghiệm trong ví dụ 2.16 ....................................................................... 55
Hình 2.21. Cây nghiệm trong ví dụ 2.17 ....................................................................... 56
Hình 2.22. Hai hàm đánh giá trạng thái u...................................................................... 57
Hình 2.23. Đồ thị không gian trạng thái ........................................................................ 58
Hình 2.24. Cây tìm kiếm tốt nhất – đầu tiên ................................................................. 59
Hình 2.25. Đồ thị không gian trạng thái ........................................................................ 60
Hình 2.26. Một phần đồ thị không gian trạng thái của ví dụ 2.22................................. 61
Hình 2.27. Đồ thị không gian trạng thái ........................................................................ 63
Hình 2.28. Đồ thị không gian trạng thái ........................................................................ 64
Hình 2.29. Đồ thị không gian trạng thái với hàm đánh giá ........................................... 66
Hình 2.30. Cây tìm kiếm theo thuật toán A* ................................................................. 67
Hình 2.31. Đồ thị không gian trạng thái ........................................................................ 69
Hình 2.32. Cây tìm kiếm nhánh _cận ............................................................................ 72
Hình 2.33. Đồ thị không gian trạng thái ........................................................................ 73
5
Hình 4.1. Đồ thị phân giải ........................................................................................... 138
Hình 4.2. Một cây chứng minh từ đồ thị phân giải trong Hình 4.2 ............................. 139
Hình 4.3. Một cây chứng minh tìm đƣợc theo chiến lƣợc bề rộng ............................. 139
Hình 4.4. Đồ thị phân giải theo chiến lƣợc sử dụng tập hỗ trợ ................................... 140
Hình 5.1. Biểu diễn tri thức bằng mạng ngữ nghĩa. .................................................... 148
Hình 5.2. Các kiểu dữ liệu trong Prolog ...................................................................... 168
Hình 5.3. Cây gia hệ .................................................................................................... 170
Hình 5.4. Định nghĩa quan hệ chị em gái .................................................................... 176
Hình 5.5. (a) X là tổ tiên trực tiếp của Z, (b) X là tổ tiên gián tiếp của Z ................... 179
Hình 5.6. Các cặp tổ tiên hậu duệ gián tiếp ở các mức khác nhau .............................. 180
Hình 5.7. Ngày tháng là một đối tƣợng có cấu trúc .................................................... 182
Hình 5.8. Mô hình vào/ra của một thủ tục thực hiện một danh sách các đích ............ 189
BẢNG KÝ HIỆU VIẾT TẮT
STT
Ký hiệu
Ý nghĩa
1
TTNT
Trí tuệ nhân tạo
2
CSTT
Cơ sở tri thức
3
NSD
Ngƣời sử dụng