Tài liệu 70 câu hỏi về trí tuệ nhân tạo + đá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ừ(ab) c, (bc) 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