Khoa Công ngh thông tin - Tr ng Đ i h c Bách Khoa ệ ườ ạ ọ
TH C HÀNH TRÍ TU NHÂN T OỰ Ệ Ạ
(AI: Artificial Intelligence)
1. Kh i l ng: : 1TC (15 ti t)ố ượ ế
- Gi h ng d n : 2 ti tờ ướ ẫ ế
các công c ph n m m Pascal, C, Java, VisuaBasic, .NET, Prolog, Scheme...ụ ầ ề
Các ph n m m ng d ng có trên m ng...ầ ề ứ ụ ạ
2. H c ph n tiên quy t: ọ ầ ế Tin h c đ i c ng, CTDL và TT, Toán r i r cọ ạ ươ ờ ạ
3. H c ph n song hành: ọ ầ : Trí tu nhân t o.ệ ạ
4. M c tiêu:ụ
5. Tài li u h c t p: ệ ọ ậ
- Trí tu nhân t o_L p trình ti n hóaệ ạ ậ ế . Ts Nguy n Đình Thúc. Nhà xu t b n giáo d c.ễ ấ ả ụ
- Nh p môn trí tu nhân t oậ ệ ạ . H c vi n Công ngh b u chính vi n thông.ọ ệ ệ ư ễ
- Ph ng pháp gi i các bài toán trong Tin h c. ươ ả ọ ThS Tr n Đ c Huyên.ầ ứ
- Các tài li u trên Internet....ệ
6. N i dung chi ti t h c ph n:ộ ế ọ ầ
Bu i 1:ổ Suy lu n logicậ
- Công c l p trình s d ng: Turbo Prolog ho c Visual Prolog.ụ ậ ử ụ ặ
- Tài li u h ng d n: ệ ướ ẫ http://www.mediafire.com/?9b5ycmmyogj
- Danh sách bài t p SV ph i hoàn thi n t i l p.ậ ả ệ ạ ớ
Câu 1:
Cho t p mênh đ :ậ ề
1) Ông T ăn táoư
2) Ông T ăn camư
3) Cam là th c ănứ
4) Món ăn mà ng i ăn không ch t (s ng) g i là th c ănườ ế ố ọ ứ
5) Ông T đang s ngư ố
H i táo có ph i là th c ăn?ỏ ả ứ
Câu 2:
Ta có c s tri th c c a h chuyên gia v ơ ở ứ ủ ệ ề b nh c m cúmệ ả nh sau:ư
1) “N uế b nh nhân rát h ng và viêm nhi m ệ ọ ễ thì viêm h ng và đi ch a h ng”.ọ ữ ọ
2) “N uế thân nhi t >37ệo thì s t”ố
3) “N uế m trên 7 ngày và s t ố ố thì viêm nhi m”ễ
4) “N uế s t và ho và kèm theo khó th ho c kèm theo ti ng ran ố ở ặ ế thì viêm ph i”ổ
a. Hãy bi u di n các tri th c trên d i logic m nh đ .ể ễ ứ ướ ệ ề
b. Có b nh nhân khai: “Thân nhi t >37ệ ệ o” và “ m trên 7 ngày” k t lu n b nh nhân này bỐ ế ậ ệ ị
gì?
Câu 3:
Gi s chúng ta bi t các thông tin sau đây:ả ử ế
1) Ông Ba nuôi 1 con chó.
2) Ho c ông Ba ho c ông An đã gi t con mèo BiBi.ặ ặ ế
3) M i ng i nuôi chó đ u yêu quý đ ng v t.ọ ườ ề ộ ậ
4) Ai yêu quý đ ng v t cũng không gi t đ ng v t.ộ ậ ế ộ ậ
5) Chó mèo đ u là đ ng v t.ề ộ ậ
K t lu n ai đã gi t con mèo BiBi.ế ậ ế
Câu 4:
Gi s chúng ta bi t các thông tin sau đây:ả ử ế
1) M i ng i đ u ch t.ọ ườ ề ế
Giáo viên h ng d n: Võ Đ c Hoàngướ ẫ ứ
Khoa Công ngh thông tin - Tr ng Đ i h c Bách Khoa ệ ườ ạ ọ
2) M i ph n đ u ch t.ọ ụ ữ ề ế
3) Th n thánh không ch t.ầ ế
4) T t c nh ng ng i b nh ph i đ c đi u tr .ấ ả ữ ườ ệ ả ượ ề ị
5) Beatrice là ph n .ụ ữ
6) Christel là ph n .ụ ữ
7) Marta là ph n .ụ ữ
8) Socrate là ng i.ườ
9) Zeus là th n thánh.ầ
10) Socrate b b nh.ị ệ
Suy lu n Socrate có đ c đi u tr hay không?.ậ ượ ề ị
-----------------------------------------------------------------------------------------------------------------
Bu i 2:ổ Thu t toánậ
Ph n ôn t p NN l p trình và thu t toánầ ậ ậ ậ
Câu 1: Trò ch i 8 quân c (C ta canh)ơ ờ ờ
Tám (8) quân c đ c ch ra trong hình, g m m t b ng kích th c 3x3 v i 8 quân cờ ượ ỉ ồ ộ ả ướ ớ ờ
d c đánh s t 1 đ n 8 và m t ô tr ng. M t quân c đ ng c nh ô tr ng có th đi vào ôượ ố ừ ế ộ ố ộ ờ ứ ạ ố ể
tr ng. M c tiêu là luôn luôn ti n t i v trí các quân c nh trong hình bên ph i (tr ng tháiố ụ ế ớ ị ờ ư ở ả ạ
đích).
Tr ng thái đ uạ ầ Tr ng thái đíchạ
Hãy trình bày thu t toán và vi t ch ng trình demo đ di chuy n các quân c sao choậ ế ươ ể ể ờ
s b c di chuy n là th p nh t (t i u). D li u đ c đ c t file là ma tr n vuông 3x3.ố ướ ể ấ ấ ố ư ữ ệ ượ ọ ừ ậ
Câu 2: Trò ch i vi t sơ ế ố
Hai ng i ch i v i nhau trò ch i nh sau: v i 1 s a đang có s n, đ n l t mình ch i,ườ ơ ớ ơ ư ớ ố ẵ ế ượ ơ
ng i đó s vi t s a+1 hay 2a v i đi u ki n s m i vi t này không v t qua s nguyênườ ẽ ế ố ớ ề ệ ố ớ ế ượ ố
d ng N cho tr c. V i s b t đ u là 1, ai vi t đ c s N tr c thì xem nh th ng.ươ ướ ớ ố ắ ầ ế ượ ố ướ ư ắ
Xem nh máy là ng i đi sau. Trình bày thu t toán và vi t ch ng trình mô t trò ch iư ườ ậ ế ươ ả ơ
sao cho kh năng th ng c a máy cao. D li u đ c đ c t bàn phím.ả ắ ủ ữ ệ ượ ọ ừ
Câu 3: Bài toán phân vi cệ
Có n chi ti t máy Jế1, J2, ..., Jn c n gia công l n l t trên 3 máy A, B, Cầ ầ ượ v i th i gian hoànớ ờ
thành t ng ng c a 1 chi ti t là Tươ ứ ủ ế A, TB, TC. Các chi ti t t Jế ừ 1, J2, ..., Jn có th gia công theoể
th t b t kỳ tuy nhiên m t chi ti t Jứ ự ấ ộ ế i ph i đ c gia công l n l t theo th t trên máy Aả ượ ầ ượ ứ ự
máy B máy C.
Trình bày thu t toán và vi t ch ng trình mô t sao cho t ng th i gian gia công hoànậ ế ươ ả ổ ờ
thành n chi ti t là th p nh t (t i u). D li u đ c đ c t file có d ng nh sau:ế ấ ấ ố ư ữ ệ ượ ọ ừ ạ ư
DULIEU.INP
n //s chi ti t c n gia côngố ế ầ
J1A, J2A,...., JnA //th i gian gia công các chi ti t trên máy Aờ ế
J1B, J2B,...., JnB //th i gian gia công các chi ti t trên máy Bờ ế
J1C, J2C,...., JnC //th i gian gia công các chi ti t trên máy Cờ ế
K t qu xu t ra là th t các công vi cế ả ấ ứ ự ệ
Giáo viên h ng d n: Võ Đ c Hoàngướ ẫ ứ
1 2 3
4 5 6
7 8
Khoa Công ngh thông tin - Tr ng Đ i h c Bách Khoa ệ ườ ạ ọ
Câu 4: Bài toán ng i du l chườ ị
M t ng i khách du l ch mu n đi thăm n thành ph đ c đánh s t 1ộ ườ ị ố ố ượ ố ừ n và quay l iạ
thành ph xu t phát. M ng l i giao thông gi a n thành ph này là hai chi u và đ c choố ấ ạ ướ ữ ố ề ượ
b i ma tr n A[i,j] trong đó A[i,j]=1 n u có đ ng đi t thành ph i đ n thành ph j,ở ậ ế ườ ừ ố ế ố
A[i,j]=0 trong tr ng h p ng c l i.ườ ợ ượ ạ
Hãy thi t l p l trình cho ng i khách hay thông báo không t n t i l i gi i. D li uế ậ ộ ườ ồ ạ ờ ả ữ ệ
đ c đ c t file có d ng nh sau:ượ ọ ừ ạ ư
DULIEU.INP
Dòng 1: Ghi s nguyên n (n<=20).ố
Dòng i+1 (1<=i<=n) ghi n s nguyên không âm (0 ho c 1).ố ặ
K t qu xu t ra chu trình đ ng đi. (Chu trình HAMILTON)ế ả ấ ườ
Câu 5: Bài toán h th ng dây di nệ ố ệ
M t công ty c n thay toàn b h th ng dây đi n cho N phòng làm vi c. Cho bi t s độ ầ ộ ệ ố ệ ệ ế ơ ồ
m ng l i đi n hi n có c a n căn phòng đ c bi u di n b ng ma tr n A[i,j] trong đóạ ướ ệ ệ ủ ượ ể ễ ằ ậ
A[i,j] chính là đ dài c a dây đi n n i gi a 2 phòng i và j (A[i,j]=A[j,i], A[i,j]=0 n u khôngộ ủ ệ ố ữ ế
có (không th ) dây n i gi a phòng i và j). Hãy l p trình tính đ dài c a dây d n c n sể ố ữ ậ ộ ủ ẫ ầ ử
d ng sao cho c N phòng d u có đi n và s l ng này là ít nh t. ụ ả ề ệ ố ượ ấ
D li u đ c đ c t file có N+1 dòng d ng nh sau: DULIEU.INPữ ệ ượ ọ ừ ạ ư
Dòng 1: Ghi s nguyên N.ố
Dòng i+1 (1<=i<=N) ghi N s nguyên A[i,1] A[i,2] .........A[i,N].ố
Các s ghi trên 1 dòng cách nhau ít nh t 1 d u cách.ố ấ ấ
K t qu xu t ra màn hình cách n i và t ng đ dài nh nh t.ế ả ấ ố ổ ộ ỏ ấ
Câu 6: Trò ch i đoán sơ ố
C u bé nghĩ ra 1 s (G i là S) g m b n ch s (không nh t thi t khác nhau) trong sáuậ ố ọ ồ ỗ ữ ố ấ ế
ch s t u 1 đ n 6. Đ tìm s đó máy l n l t đ a ra các s d đoán (g i là M), m i sữ ố ừ ế ể ố ầ ượ ư ố ự ọ ỗ ố
g m 4 ch s không nh t thi t khác nhau. V i m i l n d đoán, máy nh n đ c 2 câu trồ ữ ố ấ ế ớ ỗ ầ ự ậ ượ ả
l i c a c bé cho 2 câu h i sau.ờ ủ ậ ỏ
+ Có bao nhiêu ch s trong M là ch s trong S nh ng v trí xu t hi n c a m i ch sữ ố ữ ố ư ị ấ ệ ủ ỗ ữ ố
đó là sai?
+ Có bao nhiêu ch s trong M là ch s trong S và đ ng th i v trí xu t hi n c a m iữ ố ữ ố ồ ờ ị ấ ệ ủ ỗ
ch s đ u đúng?ữ ố ề
Yêu c u: ầHãy hi n lên màn hình các s máy d đoán và nói m i s đó nh n 2 câu tr l iệ ố ự ỗ ố ậ ả ờ
t bàn phím c a c u bé cho đ n khi đ c s đúng nh c u bé nghĩ. (S l n d đoán khôngừ ủ ậ ế ượ ố ư ậ ố ầ ự
quá 6 l n).ầ
Ví d : ụ S c n tìm là ố ầ 5436
1234
Đúng s - Đúng v trí : ố ị 1
Đúng s - Sai v trí : ố ị 1
2156
Đúng s - Đúng v trí : ố ị 1
Đúng s - Sai v trí : ố ị 1
1416
Đúng s - Đúng v trí : ố ị 2
Đúng s - Sai v trí : ố ị 0
5436
Đúng s - Đúng v trí : ố ị 4
Đúng s - Sai v trí : ố ị 0
Ch n đúng sọ ố
Giáo viên h ng d n: Võ Đ c Hoàngướ ẫ ứ
Khoa Công ngh thông tin - Tr ng Đ i h c Bách Khoa ệ ườ ạ ọ
Câu 7: Chia quà
Trong ngày sinh nh t Tom và Jerry nh n đ c N đ ch i (N<=40). Trên đ ch i i có giáậ ậ ượ ồ ơ ồ ơ
ti n là Xềi. Hai anh em quy t đ nh m i ng i ph i có trách nhi m b o qu n 1 ph n s quàế ị ỗ ườ ả ệ ả ả ầ ố
và phân chia sao cho chênh l ch t ng giá tr ti n đ ch i mà m i ng i ph i b o qu n là ítệ ổ ị ề ồ ơ ỗ ườ ả ả ả
nh t. Hãy giúp Tom bà Jerry phân chia trách nhi m. D li u đ c t file text có d ng sau:ấ ệ ữ ệ ọ ừ ạ
Dòng 1 : ghi s nguyên d ng N.ố ươ
Dòng 2 : Ghi N s nguyên d ng t ng ng v i giá tr N đ v t.ố ươ ươ ứ ớ ị ồ ậ
Câu 8: Tô màu b n đả ồ
Có 1 b n đ có N n c. M i n c đ c tô 1 màu đ phân bi t. Các n c li n k nhauả ồ ướ ỗ ướ ượ ể ệ ướ ề ề
không đ c tô cùng màu v i nhau. Hãy xác đ nh s màu t i thi u đ tô b n đ sao cho cácượ ớ ị ố ố ể ể ả ồ
mi n k nhau không đ c tô cùng màu.ề ề ượ
◊ File d liêu đâu vao: GRAPH.INP co câu trucư( ) * * + + +
n m (n đ nh:1,2,...,n; m là s c nh)ỉ ố ạ
x1 y1(danh sách m c nh)ạ
x2 y2
....
xm ym
................
◊ File kêt qua: COLOR.OUT+ ,
VERTEX: 1 2 ... n
COLOR: c1c2... cn
◊ Vi du:+ )
GRAPH.INP COLOR.OUT
10 18 VERTEX: 1 2 3 4 5 6 7 8 9 10
1 2 COLOR: 2 3 2 1 1 1 2 3 2 3
1 4
1 5
1 8
2 3
2 5
2 6
3 5
3 6
3 8
4 7
5 7
5 8
5 9
6 9
6 10
8 9
9 10
------ ----------
5 5 VERTEX: 1 2 3 4 5
1 2 COLOR: 1 2 1 2 3
2 3
3 4
4 5
5 1
Câu 9: Ng i lái đòườ
Giáo viên h ng d n: Võ Đ c Hoàngướ ẫ ứ
Khoa Công ngh thông tin - Tr ng Đ i h c Bách Khoa ệ ườ ạ ọ
Vi t ch ng trình mô ph ng bài toán ng i lái đò (có th có giao di n đ h a). Bàiế ươ ỏ ườ ể ệ ồ ọ
toán phát bi u nh sau: ể ư
T i b n sông n có b p c i, sói và dê mu n bác lái đò ch qua sông. Bi t r ng t i m tạ ế ọ ắ ả ố ở ế ằ ạ ộ
th i đi m thuy n c a bác lái đò ch ch t i đa đ c 2 khách. N u sói và dê đ ng riêng v iờ ể ề ủ ỉ ở ố ượ ế ứ ớ
nhau (không có m t bác lái đò và b p c i) thì sói s ăn th t dê. N u dê và b p c i đ ngặ ắ ả ẽ ị ế ắ ả ứ
riêng v i nhau (không có m t bác lái đò và sói) thì dê s ăn b p c i. ớ ặ ẽ ắ ả
Ký hi u b sông mà sói, dê, b p c i và bác lái đò đang đ ng là 1, b sông bên kia là 2.ệ ờ ắ ả ứ ờ
Hãy vi t ch ng trình gi i quy t bài toán trên.ế ươ ả ế
Câu 10: Qua sông
Vi t ch ng trình mô ph ng bài toán qua sông (có th có giao di n đ h a). Bài toánế ươ ỏ ể ệ ồ ọ
phát bi u nh sau: ể ư
T i b n sông n có 3 th y tu và 3 con qu mu n qua sông. Bi t r ng t i m t th i đi mạ ế ọ ầ ỷ ố ế ằ ạ ộ ờ ể
thuy n ch ch t i đa đ c 2 khách. N u b t c trên b nào, bên này ho c bên kia thì sề ỉ ở ố ượ ế ấ ứ ở ờ ặ ố
con qu ph i bé h n ho c b ng s th y tu, ng c l i qu s ăn th t th y tu. ỷ ả ơ ặ ằ ố ầ ượ ạ ỷ ẽ ị ầ
Hãy vi t ch ng trình gi i quy t bài toán trên.ế ươ ả ế
-----------------------------------------------------------------------------------------------------------------
Bu i 3:ổ AI
1. ng d ng m ng neural nhân t o trong nh n d ng ch vi t tay.Ứ ụ ạ ạ ậ ạ ữ ế
2. ng d ng thu t toán đàn ki n gi i bài toán Ng i du l ch.Ứ ụ ậ ế ả ườ ị
3. ng d ng mô hình Markov n (HMM) trong nh n d ng ti ng nói.Ứ ụ ẩ ậ ạ ế
4. ng d ng K thu t Support Vector Machine trong phân lo i văn b n.Ứ ụ ỹ ậ ạ ả
5. ng d ng thu t toán di truy n gi i bài toán Ng i du l ch.Ứ ụ ậ ề ả ườ ị
6. ng d ng DTW trong xác th c ch ký t đ ng.Ứ ụ ự ữ ự ộ
7. ng d ng m ng neural nhân t o trong ph c h i nh.Ứ ụ ạ ạ ụ ồ ả
8. ng d ng mô hình Markov n trong nh n d ng hình nh c ch .Ứ ụ ẩ ậ ạ ả ử ỉ
9. Tìm hi u mô hình cây nh phân trong xây d ng t đi n đa ng .ể ị ự ừ ể ữ
10. Tìm hi u ng d ng logic m trong vi c d đoán ch ng khoán.ể ứ ụ ờ ệ ự ứ
Giáo viên h ng d n: Võ Đ c Hoàngướ ẫ ứ