Tìm hiểu về trí tuệ nhân tạo
2
LỜI NÓI ĐẦU
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 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. 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 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.
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ở chuyên
ngành trong chƣơng trình đào tạo Cử nhân Tin học, ngoài mục đích 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 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 Huế.
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 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. 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 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 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 một cách dễ dàng.
Các nội dung trình bày trong cuốn sách đã từng đƣợc giảng cho sinh viên ngành
Công nghệ Thông tin tại Đại học Huế trong những năm vừa qua.
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
học Huế, Trƣờng Đại học Khoa học và đặc biệt là Ban chủ nhiệm Khoa Công
nghệ Thông tin và các đồng nghiệp thuộc Bộ môn Khoa học Máy tính. Chúng
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à
gíup cho cuốn sách sớm đƣợc hoàn thành.
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
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 các
đồng nghiệp và sinh viên để cuốn sách ngày càng hoàn thiện.
Huế, tháng 7 năm 2004
Tác giả
3
MỤC LỤC
Chƣơng 0. Mở đầu 2
1. Tổng quan về Khoa học Trí ruệ nhân tạo 2
2. Lịch sử phát triển của Trí tuệ nhân tạo 5
3. Một số vấn đề Trí tuệ nhân tạo quan tâm 8
4. Các khái niêm cơ bản 10
Chƣơng 1. Biểu diễn bài toán trong không gian trạng thái 12
1. Đặt vấn đề 12
2. Mô tả trạng thái 12
3. Toán tử chuyển trạng thái 14
4. Không gian trạng thái của bài toán 17
5. Biểu diễn không gian trạng thái dƣới dạng đồ thị 18
6. Bài tập 21
Chƣơng 2.
Các phƣơng pháp tìm kiếm lời giải trong không gian trạng thái 23
1. Phƣơng pháp tìm kiếm theo chiều rộng 23
2. Phƣơng pháp tìm kiếm theo chiều sâu 30
3. Phƣơng pháp tìm kiếm sâu dần 34
4. Phƣơng pháp tìm kiếm tốt nhất đầu tiên 36
5. Tìm kiếm đƣờng đi có giá thành cực tiểu - Thuật toán AT 39
6. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* 43
7. Phƣơng pháp tìm kiếm leo đồi 46
8. Phƣơng pháp sinh và thử 49
9. Phƣơng pháp thoả mãn ràng buộc 51
10. Cài đặt một số giải thuật. 53
11. Bài tập 72
Chƣơng 3
Phân rã bài toán – Tìm kiếm lời giải trên đồ thị Và/Hoặc 90
1. Đặt vấn đề 90
2. Đồ thị Và/Hoặc 92
3. Các phƣơng pháp tìm kiếm lời giải trên đồ thị Và/Hoặc 94
4. Cây tìm kiếm và các đấu thủ 104
Chƣơng 4.
Biểu diễn bài toán bằng logic và các phƣơng pháp chứng minh 107
1. Biểu diễn vấn đề hờ logic hình thức 108
2. Một số giải thuật chứng minh 130
4
3. Ví dụ và bài tập 138
Chƣơng 5. Tri thức và các phƣơng pháp suy diễn 148
1. Tri thức và dữ liệu 148
2. Các dạng mô tả tri thức 149
3. Suy diễn trên luật sản xuất 152
Tài liệu tham khảo 163
5
Chƣơng 0 MỞ ĐẦU
1. Tổng quan về khoa học Trí tuệ nhân tạo.
Trong 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.
Con ngƣời thƣờng tự cho mình là sinh vật thông minh vì khả năng trí tuệ đóng
vai trò quan trong trong cuộc sống. Trong văn học cũng đã từng có những câu
chuyện đề cao về trí thông minh của con ngƣời.
Trí Tuệ Nhân Tạo chỉ mới hình thành từ năm 1956. Tuy nhiên, việc nghiên
cứu trí tuệ đã có từ lâu. Trên 2000 năm trƣớc, các nhà triết học đã tìm hiểu về
cách thức nhìn nhận, học tập, nhớ và suy lý. Việc ra đời của máy tính điện tử
vào những năm 50 của thế kỷ 20 đã sinh ra khuynh hƣớng đƣa các lĩnh vực
nghiên cứu trí tuệ về các vấn đề lý thuyết và thực nghiệm trên máy.
1.1. Đối tƣợng và mục tiêu nghiên cứu của trí tuệ nhân tạo.
Trí tuệ nhân tạo nghiên cứu về cách hành xử thông minh (intelligent
behaviour) với mục tiêu là xây dựng lý thuyết đầy đủ về thông minh để 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 AI.
- 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.2. Vai trò của Trí Tuệ Nhân Tạo.
Trí tuệ nhân tạo bao quát rất nhiều lĩnh vực nghiên cứu hẹp. Nó nghiên cứu
từ các lĩnh vực tổng quát nhƣ máy nhận biết, suy luận logic, đến các bài toán
nhƣ chơi cờ, chứng minh định lý. Thƣờng thì các nhà khoa học ở các lĩnh vực
6
khác tìm đến với trí tuệ nhân tạo ở các kỹ thuật hệ thống hoá và tự động hoá các
xử lý tri thức cũng nhƣ các phƣơng pháp thuộc lĩnh vực mang tính ngƣời.
Trí tuệ nhân tạo nghiên cứu kỹ thuật làm cho máy tính có thể “suy nghĩ một
cách thông minh” và mô phỏng quá trình suy nghĩ của con ngƣời khi đƣa ra
những quyết định, lời giải. Trên cơ sở đó, thiết kế các chƣơng trình cho máy tính
để giải quyết bài toán.
Sự ra đời và phát triển của Trí tuệ nhân tạo đã tạo ra một bƣớc nhảy vọt về
chất trong kỹ thuật và kỹ nghệ xử lý thông tin. Trí tuệ nhân tạo chính là cơ sở
của công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền
thống dựa trên văn bản giấy tờ. Điều này đƣợc thể hiện qua các mặt sau:
- Nhờ những công cụ hình thức hoá (các mô hinh logic ngôn ngữ, logic
mờ,...), các tri thức thủ tục và tri thức mô tả có thể biểu diễn đƣợc trong
máy. Do vậy quá trình giải bài toán đƣợc tiến hành hữu hiệu hơn.
- Mô hình logic ngôn ngữ đã mở rộng khả năng ứng dụng của máy tính
trong lĩnh vực đòi hỏi tri thức chuyên gia ở trình độ cao, rất khó nhƣ: y
học, sinh học, địa lý, tự động hóa.
- Một số phần mềm trí tuệ nhân tạo thể hiện tính thích nghi và tính mềm
dẻo đối với các lớp bài toán thuộc nhiều lĩnh vực khác nhau.
- Khi máy tính đƣợc trang bị các phần mềm trí tuệ nhân tạo ghép mạng sẽ
cho phép giải quyết những bài toán cỡ lớn và phân tán.
1.3. Các kỹ thuật Trí tuệ nhân tạo.
Có nhiều kỹ thuật nghiên cứu, phát triển ngành khoa học Trí tuệ nhân tạo.
Tuy vậy, các kỹ thuật Trí tuệ nhân tạo thƣờng khá phức tạp khi cài đặt cụ thể, lý
do là các kỹ thuật này thiên về xử lý các ký hiệu tƣợng trƣng và đòi hỏi phải sử
dụng những tri thức chuyên môn thuộc nhiều lĩnh vực khác nhau.
Do vậy, các kỹ thuật Trí tuệ nhân tạo hƣớng tới khai thác những tri thức về
lĩnh vực đang quan tâm đƣợc mã hoá trong máy sao cho đạt đƣợc mức độ tổng
quát; dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với ngôn ngữ
7
tự nhiên; dễ sửa đổi, hiệu chỉnh, dễ sử dụng, khai thác nhằm thu hẹp các khả
năng cần xét để đi tới lời giải cuối cùng.
Các kỹ thuật Trí tuệ nhân tạo cơ bản bao gồm :
- Lý thuyết giải bài toán và suy diễn thông minh: Lý thuyết giải bài toán
cho phép viết các chƣơng trình giải câu đố, chơi các trò chơi thông qua
các suy luận mang tính ngƣời; các hệ thống chứng minh định lý. Ngoài ra
các hệ thống hỏi đáp thông minh còn cho phép lƣu trữ và xử lý khối lƣợng
lớn các thông tin.
- Lý thuyết tìm kiếm may rủi: Lý thuyết này bao gồm các phƣơng pháp
và kỹ thuật tìm kiếm với sự hỗ trợ của thông tin phụ để giải bài toán một
cách có hiệu quả.
- Các ngôn ngữ về Trí tuệ nhân tạo: Để xử lý các tri thức ngƣời ta không
chỉ sử dụng các ngôn ngữ lập trình dùng cho các xử lý dữ liệu số, mà cần
có ngôn ngữ khác. Các ngôn ngữ chuyên dụng này cho phép lƣu trữ và xử
lý thông tin ký hiệu. Một số ngôn ngữ đƣợc nhiều ngƣời biết đến là
IPL.V,LISP, PROLOG.
- Lý thuyết thể hiện tri thức và hệ chuyên gia: Trí tuệ nhân tạo là khoa
học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, lƣợc đồ, logic vị từ,
khung là các phƣơng pháp thể hiện tri thức thông dụng. Việc gắn liền
cách thể hiện và sử dụng tri thức là cơ sở hình thành hệ chuyên gia.
- Lý thuyết nhận dạng và xử lý tiếng nói: Giai đoạn phát triển đầu của
Trí tuệ nhân tạo gắn với lý thuyết nhận dạng. Các phƣơng pháp nhận dạng
chính gồm: nhận dạng hình học, nhận dạng dùng tâm lý học, nhận dạng
theo phƣơng pháp hàm thế, dùng máy nhận dạng. ứng dụng của phƣơng
pháp này trong việc nhận dạng chữ viết, âm thanh.
- Ngƣời máy: Cuối những năm 70, ngƣời máy trong công nghiệp đã đạt
đƣợc nhiều tiến bộ. Ngƣời máy có bộ phận cảm nhận và các cơ chế hoạt
có thể bạn quan tâm
Lý luận chung và thực trạng về bảo hiểm nhân thọ- các biện pháp nhằm n...
70
675
278
Kinh tế quản lý
70
(New)
Tìm hiểu thực trạng công nhân xây dựng : độ tuổi, kinh nghiệm, đào tạo...
67
714
303
Kinh tế quản lý
67
(New)
Hiểu biết các công cụ của chiến lược marketing hỗn hợp và áp dụng vào...
26
887
331
Kinh tế quản lý
26
(New)
Luận văn thạc sĩ: Tìm hiểu các đặc trưng của ảnh vân tay và hệ thống n...
23
951
441
Thạc sĩ cao học
23
(New)
Luận văn: So sánh hiệu quả kinh tế giữa mô hình trồng lúa 3 vụ và 2 vụ...
95
827
411
Báo cáo, luận văn khác
95
(New)
Giải pháp nhằm hoàn thiện công tác đào tạo nhân lực, nâng cao năng suấ...
56
928
316
Kinh tế quản lý
56
(New)
Tìm hiểu vấn đề quản lý và phát triển nguồn nhân lực, đồng thời đưa ra...
76
887
310
Kinh tế quản lý
76
(New)
Phân tích tổng quát thực trạng tín dụng, tìm hiểu các nhân tố tác động...
97
704
274
Kinh tế quản lý
97
(New)
thông tin tài liệu
Tài liệu cung cấp cái nhìn tổng quan về trí tuệ nhân tạo và ứng dụng thực tiễn
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
×
