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.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
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
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
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
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 |
Có thể bạn quan tâm!
-
Nhập môn trí tuệ nhân tạo - 2 -
Hiểu Và Mô Hình Hoá Ngữ Nghĩa Ngôn Ngữ Tự Nhiên -
Mô Tả Không Gian Trạng Thái Bằng Đồ Thị Định Hướng
Xem toàn bộ 272 trang tài liệu này.
CHƯƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO
1.1. Lịch sử phát triển của TTNT
1.1.1. Lịch sử hình thành và phát triển
Trong lĩnh vực Công nghệ thông tin, Trí tuệ nhân tạo (Artificial Intelligence) là một ngành mới, nhưng phát triển rất mạnh mẽ và đem lại nhiều kết quả to lớn.
Lịch sử của TTNT cho thấy ngành khoa học này có nhiều kết quả đáng ghi nhận. Theo các mốc phát triển, người ta thấy TTNT được sinh ra từ những năm 50 của thế kỷ 20 với các sự kiện sau:
Turing được coi là người khai sinh ngành TTNT bởi phát hiện của ông về máy tính có thể lưu trữ chương trình và dữ liệu. Phép thử Turing là một cách để trả lời câu hỏi
„máy tính có biết nghĩ không?‟, được phát biểu dưới dạng một trò chơi. Hình dung có ba người tham gia trò chơi, một người đàn ông (A), một người đàn bà (B) và một người chơi (C). Người chơi ngồi ở một phòng tách biệt với A và B, không biết gì về A và B (như hai đối tượng ẩn X và Y) và chỉ đặt các câu hỏi cũng như nhận trả lời từ A và B qua một màn hình máy tính. Người chơi cần kết luận trong X và Y ai là đàn ông ai là đàn bà. Trong phép thử này, A luôn tìm cách làm cho C bị nhầm lẫn và B luôn tìm cách giúp C tìm được câu trả lời đúng. Phép thử Turing thay A bằng một máy tính, và bài toán trở thành liệu C có thể phân biệt được trong X và Y đâu là máy tính đâu là người đàn bà. Phép thử Turing cho rằng máy tính là thông minh (qua được phép thử) nếu như biết cách làm sao cho C không thể chắc chắn kết luận của mình là đúng. Tuy phép thử Turing đến nay vẫn được xem có tầm quan trọng lịch sử và triết học hơn là giá trị thực tế (vì con người vẫn chưa làm được máy hiểu ngôn ngữ và biết lập luận như vậy), ý nghĩa rất lớn của nó nằm ở chỗ đã nhấn mạnh rằng khả năng giao tiếp thành công của máy với con người trong một cuộc đối thoại tự do và không hạn chế là một biểu hiện chính yếu của trí thông minh nhân tạo.
Tháng 8/1956 J.Mc Carthy, M. Minsky, A. Newell, Shannon. Simon… đưa ra khái niêm"Trí tuệ nhân tạo”.
Vào khoảng năm 1960 tại Đại học MIT (Massachussets Institure of Technology) ngôn ngữ LISP ra đời, phù hợp với các nhu cầu xử lý đặc trưng của TTNT - đó là ngôn ngữ lập trình đầu tiên dùng cho TTNT.
Thuật ngữ TTNT được dùng đầu tiên vào năm 1961 cũng tại MIT.
Những năm 60 là giai đoạn lạc quan cao độ về khả năng làm cho máy tính biết suy nghĩ. Trong giai đoạn này người ta đã được chứng kiến máy chơi cờ đầu tiên và các chương trình chứng minh định lý tự động. Cụ thể:
- 1961: Chương trình tính tích phân bất định
- 1963: Các chương trình Heuristics: Chương trình chứng minh các định lý hình học không gian có tên là"tương tự”, chương trình chơi cờ của Samuel.
- 1964: Chương trình giải phương trình đại số sơ cấp, chương trình trợ giúp ELIZA (có khả năng làm việc giống như một chuyên gia phân tich tâm lý).
- 1966: Chương trình phân tích và tổng hợp tiếng nói.
Tuy nhiên, do giới hạn khả năng của các thiết bị, bộ nhớ và đặc biệt là yếu tố thời gian thực hiện nên có sự khó khăn trong việc tổng quát hoá các kết quả cụ thể vào trong một chương trình mềm dẻo thông minh.
Vào những năm 70, máy tính với bộ nhớ lớn và tốc độ tính toán nhanh nhưng các phương pháp tiếp cận TTNT cũ vẫn thất bại (do sự bùng nổ tổ hợp trong quá trình tìm kiếm lời giải các bài toán đặt ra). Vào cuối những năm 70 một vài kết quả như xử lý ngôn ngữ tự nhiên, biểu diễn tri thức và giải quyết vấn đề. Những kết quả đó đã tạo điều kiện cho sản phẩm thương mại đầu tiên của TTNT ra đời đó là Hệ chuyên gia, được đem áp dụng trong các lĩnh vực khác nhau (Hệ chuyên gia là một phần mềm máy tính chứa các thông tin và tri thức về một lĩnh vực cụ thể nào đó, có khả năng giải quyết những yêu cầu của người sử dụng trong một mức độ nào đó, ở một trình độ như một chuyên gia con người có kinh nghiệm khá lâu năm). Một sự kiện quan trọng vào những năm 70 là sự ra đời ngôn ngữ Prolog, tương tự LISP nhưng nó có cơ sở dữ liệu đi kèm.
Vào những năm 80, thị trường các sản phẩm dân dụng đã có khá nhiều sản phẩm ở trình độ cao như: máy giặt, máy ảnh... sử dụng TTNT. Các hệ thống nhận dạng và xử lý ảnh, tiếng nói.
Những năm 90, các nghiên cứu nhằm vào cài đặt thành phần thông minh trong các hệ thống thông tin, gọi chung là cài đặt TTNT, làm rò hơn các ngành của khoa học TTNT và tiến hành các nghiên cứu mới, đặc biệt là nghiên cứu về cơ chế suy lý, về TTNT phân tạo, về các mô hình tương tác.
Hiện nay, nhiều lĩnh vực mới của TTNT đã ra đời và tiến triển sôi động theo sự thay đổi của môi trường tính toán và tiến bộ khoa học. Chẳng hạn sự xuất hiện của những hệ dữ liệu lớn với quan hệ phức tạp như dữ liệu Web, dữ liệu sinh học, thư viện điện tử… đã là động lực ra đời các ngành khai phá dữ liệu, Web ngữ nghĩa, tìm kiếm thông tin trên Web. Thêm nữa, TTNT đã thâm nhập từ các khoa học vi mô như góp phần giải các bài toán của sinh học phân tử (tin-sinh học) đến các khoa học vĩ mô như nghiên cứu vũ trụ, rồi cả khoa học xã hội và kinh tế như phát hiện các cộng đồng mạng trong xã hội hay phân tích các nhóm hành vi. Trong các thành công của TTNT giai đoạn này có sự kiện máy tính thông minh tranh tài với các kỳ thủ cờ vua, và đặc biệt máy tính
Deep Blue của IBM với trí tuệ nhân tạo đã đánh bại nhà vô địch cờ vua thế giới Garry Kasparov vào năm 1997, và cuối năm 2006 máy tính Deep Fritz lại đánh bại nhà vô địch Kramnik.
Một lĩnh vực tiêu biểu của TTNT trong giai đoạn này là các tác nhân thông minh. Tác nhân (agent), theo nghĩa chung nhất, là một thực thể có khả năng hành động để thực hiện những nhiệm vụ được giao. Một người đưa hàng, một luật sư hay một điệp viên là những tác nhân. Một robot cứu người sau động đất hay một robot hút bụi trong nhà là những tác tử. Một chương trình được cài trên máy tính để lọc thư rác hay một chương trình luôn xục xạo trên Internet để tìm những thông tin mới về một chủ đề là những tác tử. tác nhân thông minh là những tác nhân biết hành động với các phẩm chất của trí thông minh, tiêu biểu là biết nhận thức môi trường xung quanh và biết hướng các hành động tới việc đạt mục đích. Một robot hút bụi sẽ là thông minh nếu biết tìm đến các chỗ bẩn trong phòng để hút bụi và không đi tới những chỗ đã làm.
1.1.2. Đối tượng và mục tiêu nghiên cứu của TTNT
TTNT nghiên cứu về cách hành xử thông minh với mục tiêu là xây dựng lý thuyết đầy đủ để có thể giải thích được hoạt động thông minh của sinh vật và áp dụng được các hiểu biết vào các máy móc nói chung, nhằm phục vụ cho con người.
- Về mặt kỹ thuật: Tạo ra các máy thông minh để giải quyết vấn đề thực tế dùng các kỹ thuật TTNT.
- Về mặt khoa học: Phát triển các khái niệm và thuật ngữ để hiểu được các hành xử thông minh của sinh vật.
1.1.3. Những tiền đề cơ bản của TTNT
Những tiền đề ban đầu cho sự ra đời của TTNT là những nghiên cứu lý thuyết sâu sắc của các chuyên gia về logic hình thức, tâm lý học nhận thức (cognitive Psychology) và điều khiển học (Cybernetics).
A Turing, người đặt nền móng lý thuyết cho tin học, tác giả của mô hình máy tính vạn năng đã đưa ra mô hình máy tính dựa trên những phép tính logic cơ bản: AND, OR và NOT. Khi đó dự án này không được chấp nhận. Do chịu ảnh hưởng của các chuyên gia Mỹ, người ta đã tiến hành chế tạo ra những máy tính đầu tiên, thực hiện các phép tính số học cơ bản. Dầu vậy, một nhóm các chuyên gia tin học vẫn tiếp tục nghiên cứu khả năng của máy tính xử lý các dữ liệu phi số, các ký hiệu.
Một cách độc lập, các chuyên gia tâm lý học nhận thức cũng đã tạo dựng những mô hình dùng máy tính để mô phỏng hành vi của con người khi giải quyết những bài toán đòi hỏi sự sáng tạo. Lúc đó, các chương trình TTNT lại quá phức tạp, quá tốn kém nên không thể đưa ra áp dụng trong thực tiễn.