Các câu hỏi về trí tuệ nhân tạo và đáp án
Câu hỏi 1: Các dấu hiệu đặc trưng để đánh giá trí tuệ máy.
Câu hỏi 2: Những vấn đề chưa được giải quyết trong Trí tuệ nhân tạo
Câu hỏi 3: Chiến lược giải quyết vấn đề của con người
Câu hỏi 4: Nêu một số ứng dụng của Trí tuệ nhân tạo mà bạn biết
Câu hỏi 5: Thế nào là bài toán phát biểu chỉnh, bài toán phát biểu không chỉnh?
Cho ví dụ.
Câu hỏi 6: Nêu phương pháp cơ bản để biểu diễn bài toán. Trình bày những hiểu
biết của bạn về phương pháp biểu diễn bài toán nhờ không gian trạng thái.
Câu hỏi 7: Xây dựng không gian trạng thái cho bài toán: trò chơi n2 –1 số, với n-3,
biết trạng thái xuất phát
1
2
5
4
6
7
3
8
Câu hỏi 8: Định nghĩa đồ thị VÀ/HOẶC, thế nào là đỉnh Và, đỉnh Hoặc ? Lấy ví
dụ
Câu hỏi 9: Sử dụng phương pháp giải quyết vấn đề nhờ quy bài toán về bài toán
con, giải bài toán tháp Hà Nội với n=3
Câu hỏi 10: Sự tương ứng giữa quy bài toán về bài toán con và Đồ thị Và/Hoặc.
Câu hỏi 11: Xây dựng đồ thị Và/Hoặc cho bài toán: Giải và biện luận phương trình
bậc 2: ax2 + bx + c = 0 với a,b,c là hằng số
Câu hỏi 12: Ưu nhược điểm của phương pháp tìm kiếm theo chiều rộng trong
không gian trạng thái
Câu hỏi 13: Ưu nhược điểm của phương pháp tìm kiếm theo chiều sâu trong không
gian trạng thái.
Câu hỏi 14:
1
1. Nêu thứ tự ưu tiên của các phép toán Logic mệnh đề
2. Cho p, q là các mệnh đề.
p: Hôm nay là thứ năm
q: Tôi có cuộc thi trắc nghiệm
Hãy diễn đạt mệnh đề sau thành các câu thông thường
a) q p
b) q p
c) q p
Câu hỏi 15: Trong các câu sau đây, câu nào là mệnh đề? Xác định giá trị chân lý
của các mệnh đề đó?
a) Mấy giờ rồi?
b) Xinh thế!
c) x+1 = 5 nếu x =2
d) 4 + x =5
e) x+y = y+z nếu x =z
f) Nếu bạn thi trượt kỳ thi cuối khóa thì bạn không được lên lớp
g) 6+4 =10
Câu hỏi 16: Cho p, q, r là các mệnh đề.
p: Bạn được điểm giỏi trong kỳ thi cuối khóa
q: Bạn làm hết các bài tập trong quyển sách này
r: Bạn sẽ được công nhận là giỏi ở lớp này
Hãy sử dụng p, q, r và các liên từ để viết các mệnh đề sau:
a) Bạn được điểm giỏi trong kỳ thi cuối khoá và bạn làm hết các bài tập
trong quyển sách này thì bạn được công nhận là giỏi ở lớp này
b) Để được công nhận là giỏi ở lớp này bạn cần phải được điểm giỏi ở kỳ thi
cuối khóa và làm hết các bài tập trong cuốn sách này
c) Bạn được điểm giỏi ở kỳ thi cuối khóa nhưng bạn không làm hết bài tập
trong cuốn sách này, bạn vẫn được công nhận là giỏi ở lớp này.
2
Câu hỏi 17: Ban đầu biến nguyên x được khởi tạo giá trị bằng 1. Xác định giá trị
của x sau mỗi khi gặp câu lệnh dưới đây trong chương trình máy tính
a) if 1+2 =3 then x := x+4
b) If ((1+1) =3) AND ((5-2) =3) then x := x+4
c) If (Not ((1+1) =3)) OR ((5-2) =4) then x := x+4
d) If ((x > 4) OR (x<1) OR (x=1)) then x:=x+4
Câu hỏi 18: Sử dụng bảng chân lý chứng minh luật giao hoán trong tập luật biến
đổi tương đương
Câu hỏi 19: Sử dụng bảng chân lý chứng minh luật kết hợp trong tập luật biến đổi
tương đương
Câu hỏi 20: Sử dụng bảng chân lý chứng minh luật phân phối trong tập luật biến
đổi tương đương
Câu hỏi 21: Sử dụng Logic vị từ và lượng từ tồn tại (), với mọi () để diễn đạt các
câu sau:
a) Mọi sinh viên ở lớp này đều học môn tin đại cương
b) Có ít nhất một sinh viên trong lớp này chưa bao giờ nhìn thấy chiếc máy
tính
c) Có ít nhất một sinh viên ở lớp này đã học môn tin đại cương
Câu hỏi 22: Tri thức được phân thành các dạng nào?
Câu hỏi 23: Giải thích các thành phần trong phương pháp biểu diễn tri thức bằng bộ
ba OAV. Lấy ví dụ minh họa
Câu hỏi 24: Sử dụng NNLT Prolog, lập chương trình giải và biện luận phương trình
bậc nhất
ax + b = 0
(a, b là các số thực nhập từ bàn phím)
Câu hỏi 25: Sử dụng NNLT Prolog, lập chương trình giải và biện luận phương trình
bậc nhất
ax2 + bx + c = 0
(a, b, c là các số thực nhập từ bàn phím)
3
Câu hỏi 26: Sử dụng NNLT Prolog, kiểm tra 3 số thực a, b, c (nhập từ bàn phím) có
lập thành một tam giác hay không. Nếu có tính chu vi và diện tích.
Câu hỏi 27: Giáo viên A dạy môn XLA và ĐHMT, Giáo viên B dạy môn TTNT,
Giáo viên C dạy các môn giống như giáo viên A.
Sử dụng NNLT Prolog, lập chương trình trả lời các câu hỏi:
+ Giáo viên C dạy môn gì?
+ Những giáo viên nào dạy môn TTNT và ĐHMT?
Câu hỏi 28:
Tìm những sự giống và khác nhau giữa các cấu trúc của máy tính hiện đại với cấu
trúc bộ não con người
Câu hỏi 29: Theo bạn khi ¸p dông c¸c kü thuËt cña TTNT, có những hËu qu¶ gì cã
kh¶ n¨ng tiªu cùc ®èi víi x· héi .
Câu hỏi 30: Cho c©y sau víi ®Ønh gèc A, tËp ®Ých DICH = {O,P}
A
B
D
C
E
H
G
F
K
M
L
N
O
P
Q
a) Mô tả tình trạng của danh sách đóng DONG và mở MO khi duyệt cây theo thuật
toán tìm kiếm sâu dần TKSD với độ sâu ban đầu k=2
b) Có nhận xét gì khi tìm kiếm với độ sâu ban đầu k=1?
A
B
D
H
C
E
K
G
F
L
M
Câu hỏi 31: Cho cây sau với đỉnh gốc A, tập đích DICH = {O,P}
N
P
4
O
Q
a) Ưu nhược điểm của tìm kiếm theo chiều sâu TKS
b) Mô tả tình trạng của danh sách đóng DONG và mở MO khi duyệt cây theo thuật
toán tìm kiếm theo chiều sâu TKSC
Câu hỏi 32: Cho cây sau với đỉnh gốc A, tập đích DICH = {N,Q}
A
B
D
C
E
H
G
F
K
L
N
M
O
P
Q
a) Trong thuật toán tìm kiếm theo chiều rộng TKR, danh sách Đóng và danh sách
Mở được xây dựng nhằm mục đích gì?
b) Mô tả tình trạng của danh sách đóng DONG và mở MO khi duyệt cây theo thuật
toán tìm kiếm theo chiều rộng TKR
5
Câu hỏi 33: Cho cây sau với đỉnh gốc A, tập đích DICH = {N,M}
A
3
B
2
4
5
E
3
C
4
F
2
G
3
K
J
D
2
H
6
L
3
M
3
I
2
N
a) Thuật toán tìm kiếm cực tiểu hoá giá thành được hiểu tối ưu theo mặt nào?
b) Mô tả tình trạng của danh sách đóng DONG và mở MO khi duyệt cây theo thuật
toán tìm kiếm cực tiểu hoá giá thành TKCT
Câu hỏi 34:
a) Cho đồ thị G là cặp G=(N,A), N là tập các nút, A là tập các cung. Nêu công thức
tổng quát của tập các đỉnh con bậc k của đỉnh n (với n N)
b) Áp dụng với cây với đỉnh gốc A, tìm tập đỉnh con bậc 3 của A B3(A)
A
B
D
H
N
C
E
K
G
F
O
M
L
P
Q
6
Câu hỏi 35:
a) Nêu các phương pháp để xây dựng đồ thị G=(N,A)
b) Cho cây với đỉnh gốc A, tìm tập đỉnh con bậc 3 của C B3(C)
A
B
C
E
K
N
G
F
L
O
M
P
Q
(lưu ý: Các câu hỏi 3,4,5,6,7,8 có thể sử dụng các cây khác nhau và tập Đích khác
nhau để tạo ra câu hỏi mới)
Câu hỏi 36: Lập bảng giá trị chân lý và nhận xét biểu thức Logic
[( q p) ( q r)] (p r)
Câu hỏi 37: Lập bảng giá trị chân lý và nhận xét biểu thức Logic
G = (p q) [p r ( r q)] r
Câu hỏi 38: Cho biểu thức G1 = a ( b c) và G2 = (a b) (a c)
Sử dụng luật biến đổi tương đương, chứng minh rằng G1 G2
Câu hỏi 39: Cho biểu thức G1 = a ( b c) và G2 = (a b) (a c) Sử dụng
luật biến đổi tương đương, chứng minh rằng G1 G2
Câu hỏi 40: Sử dụng bảng giá trị chân lý, tính giá trị của biểu thức Logic
G = (( p q) (q r)) (p r)
Câu hỏi 41: Sử dụng luật biến đổi tương đương, tính giá trị của biểu thức Logic
G = (p p q) q
Câu hỏi 42: Sử dụng luật biến đổi tương đương, chứng minh rằng biểu thức Logic
sau có hiệu lực: G= [ p (p q)] q
7
Câu hỏi 43: Sử dụng luật biến đổi tương đương, chứng minh rằng biểu thức Logic
sau có hiệu lực: G = (p q) (p q)
Câu hỏi 44: Sử dụng giải thuật Wong H, chứng minh rằng:
từ: n p, m n, p q, q r, r suy ra m
Câu hỏi 45: Sử dụng giải thuật Wong H,, chứng minh rằng:
từ m n, n p, q p, q r, r, suy ra m
Câu hỏi 46: Sử dụng giải thuật Wong H,, chứng minh rằng:
từa b, c b, c d, a suy ra d
Câu hỏi 47: Sử dụng giải thuật Wong H,, chứng minh rằng:
từ(ab) c, (bc) d, a , b suy ra d.
Câu hỏi 48: Sử dụng giải thuật Robinson, chứng minh rằng:
từm, m ( n p), p q, q (r f), m f, f n suy ra f
Câu hỏi 49: Sử dụng giải thuật Robinson, chứng minh rằng:.
từf b , a, a ( b c), c d, d (e f), a f, suy ra f
Câu hỏi 50: Sử dụng NNLT Prolog, lập chương trình tính tổng với n nguyên dương
nhập từ bàn phím
S = 1+2+3+ ….+ n
Câu hỏi 51: Sử dụng NNLT Prolog, lập chương trình tính tổng với n nguyên dương
nhập từ bàn phím
S = 1+3+ ….+ (2*n+1)
Câu hỏi 52: Sử dụng NNLT Prolog, lập chương trình tính tổng với n nguyên dương
nhập từ bàn phím
S = 2+4+ ….+ (2*n)
Câu hỏi 53: Sử dụng NNLT Prolog, lập chương trình tính tổng với n nguyên dương
nhập từ bàn phím
S = 1
1
1
1
.....
2
3
n
8
Câu hỏi 54: Tự sáng tạo và chứng minh định nghĩa của bạn về Trí tuệ nhân tạo.
Câu hỏi 55: Cho biết tiêu chuẩn của bạn đối với một phần mềm máy tính "thông
minh"
Câu hỏi 56: Những nghiên cứu về hoạt động của các hệ sinh học của con người có
liên quan gì đến công nghệ các chương trình TTNT? Cho dẫn chứng cụ thể.
Câu hỏi 57: Cho bài toán tháp Hà Nội với n =3.
1. Lập luận để biểu diễn bài toán theo phương pháp không gian trạng thái
2. Áp dụng giải thuật tìm kiếm theo chiều rộng TKR, mô tả tình trạng của danh
sách ĐONG và MO ở mỗi bước để tìm đường đi từ trạng thái đầu tới đích
Câu hỏi 58: Cho 2 bình rỗng có dung tích lần lượt là m và n lit, với số lượng nước
không hạn chế, tìm cách lấy ra k lít nước.
Với m=5, n = 4 và k= 3, chi phí để đổ nước từ bình này sang bình kia là 2, đổ nước
từ bình ra ngoài là 3, đổ nước từ ngoài vào bình là 4
1. Lập luận để biểu diễn bài toán theo phương pháp không gian trạng thái
2. Áp dụng giải thuật tìm kiếm cực tiểu hoá giá thành TKCT, mô tả tình trạng của
danh sách ĐONG và MO ở mỗi bước để tìm đường đi từ trạng thái đầu tới đích
Câu hỏi 59 : Cho 2 bình rỗng có dung tích lần lượt là m và n lit, với số lượng nước
không hạn chế, tìm cách lấy ra k lít nước.
Với m=4, n = 3 và k= 2, chi phí để đổ nước từ bình này sang bình kia là 3, đổ nước
từ bình ra ngoài là 4, đổ nước từ ngoài vào bình là 5
1. Lập luận để biểu diễn bài toán theo phương pháp không gian trạng thái
2. Áp dụng giải thuật tìm kiếm cực tiểu hoá giá thành TKCT, mô tả tình trạng của
danh sách ĐONG và MO ở mỗi bước để tìm đường đi từ trạng thái đầu tới đích
Câu hỏi 60: Cho 2 bình rỗng có dung tích lần lượt là m và n lit, với số lượng nước
không hạn chế, tìm cách lấy ra k lít nước. Với m=4, n = 3 và k= 2
1. Lập luận để biểu diễn bài toán theo phương pháp không gian trạng thái
9
2. Áp dụng giải thuật tìm kiếm theo chiều sâu TKS, mô tả tình trạng của danh sách
ĐONG và MO ở mỗi bước để tìm đường đi từ trạng thái đầu tới đích
Câu hỏi 61: Cho 2 bình rỗng có dung tích lần lượt là m và n lit, với số lượng nước
không hạn chế, tìm cách lấy ra k lít nước. Với m=5, n = 4 và k= 3
1. Lập luận để biểu diễn bài toán theo phương pháp không gian trạng thái
2. Áp dụng giải thuật tìm kiếm theo chiều rộng TKR, mô tả tình trạng của danh
sách ĐONG và MO ở mỗi bước để tìm đường đi từ trạng thái đầu tới đích
Câu hỏi 62:
Cho các biểu thức Logic mệnh đề sau đây:
1.(a b) c
2. c d
3. d (f h)
4. a h
5. h b
6. a
xem các biểu thức này là giả thiết ban đầu và đúng. Hãy dùng phương pháp hợp
giải R để chứng minh rằng f đúng
Câu hỏi 63:
Cho các biểu thức Logic mệnh đề sau đây:
1. m
2. m ( n p)
3. p q
4. q (r f)
5. m f
6. f n
xem các biểu thức này là giả thiết ban đầu và đúng. Hãy dùng phương pháp hợp
giải R để chứng minh rằng f đúng
Câu hỏi 64:Lập chương trình kiểm tra tính hoàn hảo của một số nguyên dương n
nhập từ bàn phím
10
Câu hỏi 65:Lập chương trình kiểm tra tính nguyên tố của một số nguyên dương n
nhập từ bàn phím
Câu hỏi 66: Sử dụng NNLT Prolog, lập chương tính tổng với N nguyên dương nhập
từ bàn phím:
S = 1! + 3! +.......+ (2*N+1)!
Câu hỏi 67: Sử dụng NNLT Prolog, lập chương tính tổng với N nguyên dương nhập
từ bàn phím:
S = 1+ 2! + 4! +.......+ (2*N)!
Câu hỏi 68: Sử dụng ngôn ngữ lập trình Prolog, lập chương trình tính XY với X,Y
nguyên dương nhập từ bàn phím.
Câu hỏi 69: Sử dụng ngôn ngữ lập trình Prolog, lập chương trình tính tổng
S 1
1 1
1
..... ( 1) n
2 3
n
với n nguyên dương nhập từ bàn phím
Câu hỏi 70: Sử dụng ngôn ngữ lập trình Prolog, lập chương trình tính tổng
S 1
1 1
1
..... (1) n 1
2 3
n
với n nguyên dương nhập từ bàn phím
11
ĐÁP ÁN & THANG ĐIỂM
1
2
3
4
Các dấu hiệu đặc trưng để đánh giá trí tuệ máy bao gồm: 8 dấu hiệu sau
- khả năng học: Có nghĩa là tìm cách biểu diễn tri thức, tìm cách vận dụng tri
thức để giải quyết vấn đề và tìm cách bổ sung tri thức bằng cách phát hiện tri
thức từ các thông tin có sẵn.
- khả năng mô phỏng quá trình suy diễn của con người
- khả năng tổng quát hoá, trừu tượng hoá quá trình suy diễn
- khả năng tự thích nghi với tình huống mới trong đó gồm có khả năng thu nạp tri
thức và dữ liệu
- khả năng tự giải thích hành vi
- khả năng sử dụng các tri thức, Heuristics
- khả năng xử lý các thông tin không đầy đủ, không chính xác
- khả năng tránh bùng nổ tổ hợp
* Một máy tính biết "suy nghĩ" phải làm được những việc sau: Trước hết nó phải
thu nhặt các kiến thức từ môi trường bên ngoài và biến chúng thành biểu diễn nội
tại của kiến thức đó bên trong máy tính. Khi gặp một câu hỏi hay một yêu cầu, nó
phải biểu diễn yêu cầu đó thành yêu cầu nội tại để suy luận và tìm ra câu trả lời,
đề ra kế hoạch hành động và thể hiện điều đó cho người hỏi.
Hai vấn đề thách thức còn mở đối với các nhà nghiên cứu TTNT trong giai đoạn
hiện nay là:
1. Trí tuệ nhân tạo có mô phỏng được phần lớn hoạt động của bộ não con người?
2. Liệu có tồn tại những khía cạnh trí tuệ con người về nguyên tắc là không mô
phỏng được trên máy tính?
Với các thành tựu đạt được cho thấy rằng các dự án xây dựng máy tính có
khả năng suy nghĩ là có tính thực tiễn, song trong nhiều lĩnh vực máy tính còn
thua xa so với hoạt động của hệ thần kinh con người.
Con người thường giải quyết vấn đề theo các chiến lược sau:
- ước lượng mức độ phức tạp của vấn đề đặt ra. Nếu bài toán đơn giản thì giải
quyết ngay bằng các thao tác cơ sở. Nếu phức tạp thì các cơ quan nào tìm cách
biểu diễn chi tiết nội dung của vấn đề tìm phương pháp phù hợp.
- Nới lỏng một vài ràng buộc của bài toán
- Chia bài toán thành các bài toán con cho đến khi nhận được các bài toán sơ cấp
có thể giải quyết được ngay.
- Tổng quát hoá bài toán: Chuyển các thông tin bên ngoài thành các kí hiệu làm
cho bài toán dễ giải hơn. Quá trình này tạo ra một mô hình trí tuệ của bài toán.
(Các chuyên gia tâm lý học nhận thức gọi mô hình này là không gian bài toán).
Trí tuệ nhân tạo có một số chuyên ngành như: Các phương pháp tìm kiếm lời
giải, Hệ chuyên gia, Máy học và ngôn ngữ, Lý thuyết nhận dạng, Mạng Neuron,
Người máy… Mỗi ngành có những sản phẩm đặc trưng riêng
12
- Kỹ thuật người máy
- Các chương trình trò chơi
- Mô hình hoá hoạt động của con người
- Xử lý các ngôn ngữ tự nhiên
- Suy luận và chứng minh định lý tự động
- Các hệ chuyên gia
- Các ngôn ngữ và môi trường dùng cho AI
- Học máy
- Xử lý phân tán song song và tính toán kiểu nảy sinh
5
* Bài toán phát biểu chỉnh (well-formed problems): đó là các bài toán có thể
biết được hình trạng đầu, hình trạng đích và có thể quyết định khi nào vấn đề
được coi là giải quyết xong. Hay nói một cách khác, với một lời giải giả định nào
đó có thể áp dụng một thuật toán để xác định xem nó có phải là lời giải thực sự
của bài toán không?
Ví dụ: Bài toán tháp Hà Nội: Cho 3 cọc 1,2,3. ở cọc 1 ban đầu có n đĩa sắp
xếp theo thứ tự to dần từ trên xuống dưới. Hãy dịch chuyển n đĩa đó sang cọc 3
sao cho: mỗi lần dịch chuyển chỉ làm với một đĩa, trong mỗi cọc không cho phép
đĩa to nằm trên đĩa nhỏ.
* Bài toán phát biểu không chỉnh (ill-formed probems): Đó là các bài toán
được phát biểu chưa đầy đủ, chưa chính xác, thiếu dữ liệu hay các bài toán phụ
thuộc vào không gian, thời gian.
Ví dụ: Bài toán tìm cách đi từ trường KT Vinh đến một siêu thị lớn nhất thành
phố Vinh (đối với người chưa đến Vinh lần nào) là bài toán phát biểu không
chỉnh vì:
+ đích đặt ra không tường minh
+ không chỉ ra phương cách đi
+ không gian bài toán không hữu hạn vì không biết siêu thị ở đâu
6
* Có 4 phương pháp cơ bản để biểu diễn bài toán
- Phương pháp biểu diễn bài toán nhờ không gian trạng thái
13
- Phương pháp quy bài toán về các bài toán con
- Phương pháp biểu diễn bài toán sử dụng Logic hình thức
- Lựa chọn phương pháp biểu diễn thích hợp
* Phương pháp biểu diễn bài toán nhờ không gian trạng thái
Đây là phương pháp biểu diễn bài toán dựa trên 2 khái niệm chính là trạng
thái (state) và toán tử (operator). Trong đó mỗi trạng thái là một hình trạng của
bài toán, các toán tử là các phép biến đổi từ trạng thái này sang trạng thái khác.
Tất cả các trạng thái được sinh ra xuất pháp từ trạng thái đầu và áp dụng các toán
tử được gọi là không gian trạng thái (state space).
Một cách biểu diễn trực quan đối với không gian trạng thái và các toán tử
là sử dụng đồ thị. Trong đó các đỉnh của đồ thị tương ứng với các trạng thái, còn
các cung tương ứng với các toán tử .
Để biểu diễn một cách đầy đủ bài toán trong không gian trạng thái ta cần phải
xác định các yếu tố sau:
+ dạng mô tả của các trạng thái
+ tập các toán tử và tác động của chúng lên các mô tả trạng thái
+ các trạng thái đầu và các trạng thái đích
1
2
14
DP
1
5
4
6
5
7
7
3
8
DL
1
5
7
2
6
4
3
8
DP
7
+ Các
tử:
+ Các
1
2
6
5
4
8
2
DL
7
3
1
2
6
4
6
5
4
3
8
DX
7
3
8
1
2
DP
5
4
6
7
3
8
1
4
2
5
6
7
3
8
toán
dịch
trạng
+ Trạng thái đích là
1
2
3
4
5
6
7
8
* Xây dựng không gian trạng thái như sau:
Tiếp tục các bước cho đến khi đạt được trạng thái đích. Số trạng thái được sinh ra
có thể xấp xỉ (1/2).9!
8
* Định nghĩa: Đồ thị (có hướng) và/hoặc là cặp G=(N, A), trong đó N là tập
các đỉnh, A là tập các cung, sao cho với mỗi đỉnh n ? N tất cả các đỉnh con của
nó m?B(n) đồng thời thuộc một trong hai kiểu đỉnh là đỉnh Và hay đỉnh hoặc.
- Đỉnh con m? B(n) là đỉnh và nếu bài toán ứng với đỉnh n không thể giải
thông qua một mình bài toán ứng với đỉnh m.
- Đỉnh con m? B(n) là đỉnh hoặc nếu bài toán ứng với đỉnh n có thể giải thông
qua một mình bài toán ứng với đỉnh m.
- Ví dụ : Giả sử bài toán A có thể giải quyết theo ba cách sau:
15
- Hoặc thông qua giải quyết đồng thời hai bài toán B và C.
- Hoặc giải quyết các bài toán D và E.
- Hoặc giải bài toán F (phát biểu tại A).
A
M
N
B
9
C
D
F
E
Đỉnh M, N là đỉnh Và. Còn đỉnh A là đỉnh Hoặc
Giả sử mỗi trạng thái là một bộ ba (i j k) trong đó:
+ đĩa C (to nhất) ở cọc i
+ đĩa B (trung bình) ở cọc j
+ đĩa A (bé nhất) ở cọc k.
Như vậy dữ liệu đầu vào và đầu ra của bài toán được biểu diễn như sau: (111)
(333).
* Có thể tách bài toán thành 3 bài toán con sau:
+ Bài toán con 1: (111) ? (122): chuyển 2 đĩa A, B từ cọc 1 sang cọc 2
+ Bài toán con 2: (122) ? (322): chuyển đĩa C từ cọc 1 sang cọc 3
+ Bài toán con 3: (322) ? (333): chuyển đĩa A,C từ cọc 2 sang cọc 3
Ta thấy bài toán con 2 là bài toán sơ cấp có thể giải quyết được ngay còn bài toán
con 1 và bài toán con 3 lại được phân rã tiếp và cuối cùng ta có sơ đồ phân rã :
(111) (333)
(111) (122)
(122) (322)
(322) (321)
(111) (113)
(113) (123)
(123) (122)
(322) (333)
16
(321) (331)
(331) (333)
10
* Sự tương ứng giữa quá trình quy bài toán về bài toán con v ới đồ th ị
Và/Hoặc
Quy bài toán về các bài toán con
Bài toán
Đồ thị và/hoặc
Đỉnh
Cung
Toán tử quy bài toán về bài toán
Đỉnh đầu (đỉnh gốc)
con
Bài toán ban đầu
Đỉnh cuối, đỉnh kết thúc
Các bài toán sơ cấp
Đỉnh và
Đỉnh hoặc
Các bài toán con phụ thuộc
Đồ thị con lời giải
Các bài toán con độc lập
Tìm đồ thị con lời giải.
Lời giải bài toán
Giải bài toán ban đầu.
11
ax2 + bx + c = 0
Dt = b2 - 4ac
Dt >0
Pt có 2 N
b Dt
x
2a
Dt =0
Dt <0
Pt có N kép
Pt VN
b Dt
x
2a
17
x
b
2a
12 Tìm kiếm rộng khảo sát không gian trạng thái theo từng mức. Chỉ đến khi trong
một mức cho trước không còn trạng thái nào để khảo sát thì mới chuyển sang
mức tiếp theo.
Ưu điểm: Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì
vậy sẽ tìm được lời giải nếu có Lúc nào cũng xem xét tất cả các nút ở mức n rồi mới
chuyển sang mức n+1 nên tìm kiếm rộng bao giờ cũng là tìm đường đi ngắn nhất đến
một nút đích..
Nhược điểm: Tìm kiếm lời giải theo thuật toán đã định trước, do vậy tìm kiếm
một cách máy móc; khi không có thông tin hỗ trợ cho quá trình tìm kiếm, không
nhận ra ngay lời giải. Không phù hợp với không gian bài toán kích thước lớn.
Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:
- Cần nhiều bộ nhớ theo số nút cần lưu trữ.
- Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài, số nút tăng.
- Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số
nút phải xử lý.
Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả
nhưng lời giải ở sâu. Do duyệt qua tất cả các nút, việc tìm kiếm không tập trung
vào một chủ đề.
13 Trong tìm kiếm sâu, khi một trạng thái được xét đến, tất cả các con của nó rồi đến
các thế sau của các con đó đều được xem xét ưu tiên trước bất kỳ một trạng thái
anh em nào của nó.
Ưu điểm : Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời
giải. Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi
các câu hỏi tập trung vào vấn đề chính. Do cách tìm của kỹ thuật này, nếu lời giải
ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian.
Tìm kiếm sâu sẽ nhanh chóng đi sâu vào không gian tìm kiếm. Nếu biết rõ đường
đi lời giải sẽ dài, tìm kiếm sâu sẽ không mất thời gian cho việc tìm kiếm một số
18
lượng lớn các trạng thái “nông cạn” trong đồ thị.
Tìm kiếm sâu hiệu quả hơn nhiều đối với loại không gian nhiều nhánh vì nó
không phải giữ tất cả các nút ứng với một mức trong danh sách mở.
Nhược điểm : Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật
toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin
nào hỗ trợ để phát hiện lời giải. Tìm kiếm sâu cũng có thể sa vào độ sâu “vô ích”
khi bỏ qua những đường đi ngắn hơn dẫn họ đến đích, hay thậm chí có thể bị sa
lầy trong một đường đi dài vô tận, không đến đích nào cả. Không phù hợp với
không gian bài toán lớn.
14 1. Nêu thứ tự ưu tiên của các phép toán Logic mệnh đề
thứ tự ưu tiên của các phép toán Logic như sau: , , , ,
2. Cho p, q là các mệnh đề.
p: Hôm nay là thứ năm
q: Tôi có cuộc thi trắc nghiệm
Diễn đạt mệnh đề sau thành các câu thông thường
a) q p
Hôm nay là thứ năm thì tôi có cuộc thi trắc nghiệm
b) q p
Tôi không có cuộc thi trắc nghiệm thì hôm nay không phải là thứ năm
c) q p
Tôi không có cuộc thi trắc nghiệm hoặc hôm nay không phải là thứ năm
15 a) Mấy giờ rồi? Không phải là mệnh đề
b) Xinh thế! Không phải là mệnh đề
c) x+1 = 5 nếu x =2 Là mệnh đề có giá trị False
d) 4 + x =5 Không phải là mệnh đề
e) x+y = y+z nếu x =z Là mệnh đề có giá trị TRue
f) Nếu bạn thi trượt kỳ thi cuối khóa thì bạn không được lên lớp Là mệnh đề có
giá trị True
g) 6+4 =10 Là mệnh đề có giá trị True
19
16 a) Bạn được điểm giỏi trong kỳ thi cuối khoá và bạn làm hết các bài tập trong
quyển sách này thì bạn được công nhận là giỏi ở lớp này
(p q) r
b) Để được công nhận là giỏi ở lớp này bạn cần phải được điểm giỏi ở kỳ thi cuối
khóa và làm hết các bài tập trong cuốn sách này
r (p q)
c) Bạn được điểm giỏi ở kỳ thi cuối khóa nhưng bạn không làm hết bài tập trong
cuốn sách này, bạn vẫn được công nhận là giỏi ở lớp này.
(p q) r
17 a) if 1+2 =3 then x := x+4
Do (1+2=3) là mệnh đề nhận giá trị đúng nên câu lệnh sau “then” được thực
hiện , x=5
b) If ((1+1) =3) AND ((5-2) =3) then x := x+4
Do ((1+1) =3) AND ((5-2) =3) là biểu thức Logic nhận giá trị sai nên câu lệnh
sau “then” không được thực hiện, x=1
c) If (Not ((1+1) =3)) OR ((5-2) =4) then x := x+4
Do (Not ((1+1) =3)) OR ((5-2) =4) là biểu thức logic nhận giá trị đúng nên câu
lệnh sau “then” được thực hiện x=5
d) If ((x > 4) OR (x<1) OR (x=1)) then x:=x+4
Do ((x > 4) OR (x<1) OR (x=1)) là biểu thức nhận giá trị đúng nên câu lệnh sau
“then” được thực hiện, x=5
20
- Xem thêm -