1
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP VINH
KHOA CÔNG NGHỆ
BỘ MÔN CÔNG NGHỆ THÔNG TIN
(LƯU HÀNH NỘI BỘ)
TRÍ TUỆ NHÂN TẠO
BIỂU DIỄN & TÌM KIẾM
TS. NGUYỄN NGỌC THUẦN
VINH, 2018
2
LỜI TỰA
Để có thêm lựa chọn “Tài liệu học tập” cho sinh viên trong quá trình học
tập, nghiên cứu; chủ động trong việc giảng dạy cho giáo viên. Sau nhiều năm giảng
dạy, chúng tôi biên tập lại một số vấn đề cơ bản của Môn học Trí tuệ nhân tạo trên
tinh thần rút gọn để phù hợp với đối tương - sinh viên ngành CNTT, trường Đại
học Công nghiệp Vinh – trường Đại học định hướng thực hành và vừa đảm bảo
những phần cơ bản nhất của môn học.
Với phương châm vừa giới thiệu lý thuyết vừa tăng cường các kỹ năng thực
hành, tập bài giảng tập trung giới thiệu các vấn đề liên quan đến biểu diễn tri thức
và các kỹ thuật tìm kiếm. Đây là giáo trình môn học Trí tuệ nhân tạo dành cho giáo
viên, sinh viên ngành CNTT trong công tác giảng dạy, nghiên cứu và học tập tại
trường Đại học Công nghiệp Vinh.
Giáo trình lựa chọn các vấn đề cơ bản từ các tài liệu chuyên ngành từ truyền
thống đến hiện đại và được tổ chức thành 04 chương; Chương 1, giới thiệu các
khái niệm cơ bản; Nêu vai trò, nhiệm vụ của môn học trong chương trình đào tạo
Đại học và trong đời sống xã hội; Các xu thế nghiên cứu trong tương lai gần trong
ứng dụng thực tiễn của TTNT. Chương 2, tập trung giới thiệu hai trong bốn cách
biểu diễn tri thức, đó là biểu diễn tri thức nhờ Lôgic và biểu diễn tri thức sử dụng
luật dẫn xuất; Còn biểu diễn tri thức sử dụng mạng ngữ nghĩa hoặc khung (Frame)
chỉ giới thiệu định nghĩa và cấu trúc của phương pháp. Chương 3, mô tả không
gian trạng thái với các bộ phận cấu thành nhằm phục vụ cho các giải pháp tìm
kiếm được trình bày trong phần tiếp theo. Chương 4, ngoài việc đưa ra các giải
pháp tìm kiếm truyền thống: Tìm kiếm theo chiều rộng, tìm kiếm theo chiều sâu,
giáo trình tập trung các giải pháp nâng cao: tìm kiếm với đường đi cực tiểu, tìm
kiếm với giá thành tối ưu – Phương pháp tìm kiếm tốt nhất đầu tiên (BFS); tìm
kiếm leo đồi với hàm đánh giá được chọn. Cuối mỗi phần, đều có các ví dụ, bài tập
minh họa và kiểm tra nhận thức của sinh viên.
Cùng với tập bài giảng, chúng tôi cung cấp tập các bài toán thực tiễn, giúp
người học có thêm cơ hội rèn luyện, kiểm tra khả năng lập trình trên các ngôn ngữ
lập trình bậc cao.
Chủ biên
TS. Nguyễn Ngọc Thuần
MỤC LỤC
3
Nội dung
Trang
Chương 1
Tổng quan về Trí tuệ nhân tạo.
1.1. Các khái niệm
1.2. Đối tượng và mục tiêu nghiên cứu
1.3. Vai trò của TTNT
1.4. Các kỹ thuật TTNT
1.5. Những vấn đề đặt ra trong tương lai cảu TTNT
1.6. Câu hỏi và Bài tập
1-5
1
2
2
3
4
5
Chương 2
Phương pháp biểu diễn tri thức và các giải thuật.
2.1. Biểu diễn tri thức nhờ Lôgic hình thức
2.1.1. Lô gic mệnh đề
2.1.2. Các luật đại số
2.1.3. Một số thuật giải chứng minh
Thuật toán Vương Hạo
Thuật toán Robinson
Các ví dụ
2.1.4. Bài tập
2.1.5 Lôgic vị từ
Các Định nghĩa và khái niệm
2.1.5.1. Cú pháp, ngữ nghĩa
2.1.5.2. Chuẩn hóa công thức
2.1.5.3. Ví dụ và Bài tập
2.2. Biểu diễn tri thức sử dụng luật dẫn xuất
2.2.1. Các khái niệm
2.2.2. Cấu trúc
2.2.3. Suy diễn trên luật sản xuất
2.2.3.1. Khái niệm
2.2.3.2. Các phương pháp suy diễn
Phương pháp suy diễn tiến
Phương pháp suy diễn lùi
2.2.4. Ví dụ và Bài tập
2.3. Biểu diễn tri thức sử dụng mạng ngữ nghĩa,
khung (Frame)
6 – 49
6 - 36
7 – 21
10 – 11
11 – 21
12 – 14
14 – 15
15 – 19
19 – 21
21 – 36
21 – 23
24 – 29
29 - 33
33 – 36
37 – 48
37
37
39 – 43
39
39
39 – 41
41 – 43
44 – 48
49
Chương 3
Biểu diễn bài toán trong không gian trạng thái
3.1. Các khái niệm
3.2. Mô tả trạng thái
3.3. Toán tử chuyển trạng thái
3.4. Không gian trạng thái của bài toán
3.5. Biểu diễn không gian trạng thái dưới dạng
Graf
50 – 61
50 – 51
52 – 53
54 – 56
57
58 – 59
4
3.6. Ví dụ và Bài tập
60 – 61
Chương 4
Các phương pháp tìm kiếm lời giải trong
không gian trạng thái
Mô tả bài toán
4.1. Phương pháp tìm kiếm theo chiều rộng
4.2. Phương pháp tìm kiếm theo chiều sâu
4.3. Phương pháp tìm kiếm tốt nhất đầu tiên
(Thuật toán BFS – Best First Search)
4.4. Tìm kiếm đường đi có giá thành cực tiểu
(Thuật toán ATK – Algorithm for Knowlegeable
Tree Search)
4.5. Tìm kiếm cực tiểu dùng hàm đánh giá
(Thuật toán A*)
4.6. Phương pháp tìm kiếm leo đồi
(Hill-climbing search)
62 – 90
62 – 63
63 – 69
69 – 74
74 – 79
80 – 84
84 – 87
87 - 90
TRÍ TUỆ NHÂN TẠO.
TS. Nguyễn Ngọc Thuần
Chương 1 TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO (TTNT).
1.1. Các khái niệm.
5
Trí tuệ nhân tạo (AI: Artificial Intelligence) là một ngành của khoa học máy tính
liên quan đến việc tự động hóa các hành vi thông minh. Trí tuệ nhân tạo (tương lai
của nhân loại) không có gì khác hơn là mô phỏng hoạt động của não người - mạng
nơ ron (Neural network). AI được xây dựng trên những nguyên lý lý thuyết vững
chắc, có khả năng ứng dụng được.
Những nguyên lý đó bao gồm: Các cấu trúc dữ liệu dùng cho biểu diễn tri thức;
Các thuật toán cần thiết để xử lý và áp dụng những tri thức đó; Các ngôn ngữ và kỹ
thuật lập trình dùng cho việc cài đặt chúng.
+ Khái niệm: TTNT - AI: Artificial Intelligence; (Trí tuệ, Tri thức - knowledge)
CSTT (Cơ sở tri thức)-Tập hợp các tri thức.
+ Vai trò, Chức năng của AI: Tìm kiếm, tập hợp những dữ liệu (mà con người gọi
là tri thức, kiến thức); Tìm kiếm CTDL thích hợp để biểu diễn các tri thức đó trong
MT; Tìm kiếm các Luật suy diễn phù hợp để từ các CSTT - một tập hợp các tri
thức được biểu diễn dưới dạng nào đó,
suy ra được các hành động đúng.
+ Các bộ phận cấu thành Hệ TT: CSTT + Bộ suy diễn. Bộ suy diễn là thành phần
cơ bản khác của các hệ tri thức. Như vậy hệ tri thức bảo trì một CSTT và được
trang bị một thủ tục suy diễn.
+ Bài toán của TTNT gồm các dạng:
- Cách biễu diễn tri thức và đánh giá;
- Các thuật toán xử lý TT và các yếu tố vượt trội.
- Học máy (Machine Learning - khác với việc máy là công cụ lưu trữ):
Đưa dữ liệu vào máy; Hệ thống thuật toán xử lý; Đưa ra kết quả - đây là
kiến thức thu/học được. Qúa trình được lặp lại cho đến khi thu được kết
quả mong đợi.
+ Mục tiêu của biểu diễn tri thức:
Để máy tính có thể sử dụng được tri thức, có thể xử lý tri thức, chúng ta cần biểu
diễn tri thức dưới dạng thuận tiện cho máy tính.
Trong Công Nghệ Thông Tin, Trí Tuệ Nhân Tạo (Artificial Intelligence) là một
ngành mới, nhưng đã và đang phát triển rất mạnh mẽ và đem lại nhiều kết quả to