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