CHƯƠNG 2 TỔNG QUAN VỀ GIẢI QUYẾT VẤN ĐỀ
1. KHÁI NIỆM VẤN ĐỀ-BÀI TOÁN
Khi nào chúng ta phải suy nghĩ? Có thể thấy ngay là khi phải trả lời câu hỏi của giáo viên, làm một bài toán hoặc giải quyết một vấn đề nhưmua gì tặngbạn ngày sinh nhật…
Có thể nói, mọi cá nhân cũng như mọi cộng đồng xã hội phải liên tục giải quyết những vấn đề và bài toán đặt ra trong quá trình tồn tại và phát triển. Cuộc sống là một chuỗi vấn đề mà ta phải nói: “Thông thường, nhiều người quan niệm vấn đề có nghĩa rộng hơn bài toán và bài toán là một loại vấn đề màđể giải quyết phải liên quan ít nhiều đến tính toán: bài toán trong vật lý, hóa học, xây dựng, kinh tế… Cho nên từ vấn đề vẫn thường được dùng với nghĩa rộng hơn trong toán học”.
Nhà toán học cổ Hy Lạp Pitago đã phân chia mọi vấn đề mà con người phải giải quyết thành hai loại:
+ Theorema là vấn đề cần được khẳng định tính đúng-sai.
Chúng ta thường quen với loại vấn đề này qua việc chứng minh cácđịnh lý trong toán học, đặc biệt là hình học.
+ Problema là vấn đề cần tìm giải pháp để đạt được một mục tiêu xácđịnh từ những điều kiện ban đầu nàođó. Các ví dụ minh họa điển hình cho loại bài toán này là bài toán dựng hình, tổng hợp hóa chất, tìm đường đi ngắn nhất, thi công công trình nhanh nhất, mua sắm tiết kiệm nhất…
Nhưnhiều nhà nghiên cứu việc giải quyết vấn đề - bài toán đã chỉ ra sau này, cả hai loại vấn đề mà Pitago nêu rađều có thể diễn đạt theo một sơ đồ chung:
38
A→B Ở đây:
- A có thể là giả thiết, điều kiện ban đầu - B có thể là kết luận, mục tiêu cần đạt.
-→là suy luận, giải pháp cần xác định
Theo sơ đồ này, việc cho một vấn đề - bài toán có nghĩa là cho A và B. Việc giải quyết vấn đề - bài toán có ý nghĩa là xuất phát từ A dùng một số hữu hạn các bước suy luận có lý hoặc hành động thích hợp để đạt được B. Để cho việc giải quyết vấn đề - bài toán được xác định cũng phải chỉ ra tập các thao tác cơ bản được dùng trong suy luận hoặc hànhđộng, nghĩa là những điều kiện ràng bược đối với yếu tố “→” trong sơ đồ đã nêu.Đối với tin học sơ đồ nàyđược hiểu với nghĩa A là Input (thông tin vào), B là Output (thông tin ra) và →là chương trình tạo thành từ các lệnh cơbản của máy cho phép biến đổi A thành B.
Như ta đã thấy, chương trình chỉ là một cách mã hóa lại thuật toán hoặc thuật giải đã được xây dựng để giải quyết vấn đề - bài toánđã cho.
Điều khó khăn nhất hiện nay đối với việc xây dựng thuật toán hoặc thuật giải là tính không xác định của hầu hết mọi vấn đề và bài toán. Tính không xácđịnh này thường thể hiện qua:
+ Thông báo về A hoặc B khôngđầy đủ, rõ ràng.
Ngay cả bài toán trong toán học thường được xem là mẫu mực của việc diễn đạt chính xác cũng giả định phần lớn thông tin về A và B tiềm ẩn trong đầu người giải. Thông báo về A và B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó.Ví dụ, bài toán:
Cho: số nguyên duơng n, các số thực a0, a1, …, an. Tìm: Số thực x sao cho a0+ a1x +…+ anxn= 0.
Khi một người không biết số nguyên dương, số thực là gì…
thì không hiểu được bài toán chứ chưa nói đến việc tìm cách giải.
+ Thông báo về các điều kiện đặt ra cho cách giải (→) thường được nêu ra trong bài toán hoặc vấn đề. Đối với các bài toán trong sách thì thường được hiểu ngầm được phép dùng mọi kiến thức về toán đã học cho tới phần đó của giáo trình.
Có thể nói: thuật toán hay thuật giải cung cấp đủ lượng thông tin (không thừa không thiếu) để giải quyết vấn đề - bài toán. Chính vì những lý do nêu trên, hiện nay để giải một vấn đề trên máy tính, việc thiết kế xây dựng thuật giải vẫn chủ yếu được thực hiện bởi con người. Từ những thông tin được phản ánh rõ ràng hoặc tiềm ẩn trong các thông báo A, B hoặc “→”, cùng với các tri thức liên quan có trong đầu người giải quyết vấn đề - bài toán sẽ được kiến tạo nên thuật toán hay thuật giải cần thiết. Đây là công việc có tính trí tuệ cao và quyết định sự thành công của việc giải quyết vấn đề - bài toánđược đặt ra.
Từ khi có máy tính điện tử, các nhà khoa học đã tìm cách chuyển giao dần dần các bước giải quyết vấn đề cho máy. Đã có nhiều công trình nghiên cứu tự động hóa việc lập chương trình khi thuậttoánđược viết theo một qui định chặt chẽ nàođó. Tuy nhiên, muốn tự động hóa xây dựng thuật toán hay thuật giải – nghĩa là chỉ cần đưa ra nội dung vấn đề vào máy, một chương trình có sẵn trong máy sẽ phân tích vấn đề, tìm hoặc xây dựng thuật toán hay thuật giải rồi biến thành chương trình giải quyết vấn đề - bài toán. Chúng ta cần phải làm sao biểu diễn được nội dung bài toán - vấn đề, cũng nhưmọi tri thức liên quan đến bài toán - vấn đề dưới dạng tường minh và hết sức đầy đủ. Đây chính là lĩnh vực hết sức mới mẻ và có ý nghĩa thực tiễn vô cùng lớn lao: xây dựng một trí tuệ nhân tạo cho máy. Gần đây, đã có một số kết quả nghiên cứu biểu diễn tri thức trong máy và xây dựng được một số hệ giải bài toán tự động trong một số lĩnh vực hẹp của logic, đại số, hình học…. Những hệ này thực
40
chất là một cơsở tri thức về lĩnh vực vấn đề cần giải quyết được kết hợp với một chương trình suy diễn để tạo sinh được thuật toán hay thuật giải cần thiết. Những hệ giải quyết vấn đề dựa trên cơ sở tri thức mở rộng hơn cùng vớicác chương trình “tư duy” mạnh hơn đang được phát triển và ứng dụng trong rất nhiều lĩnh vực. Những hệ này thường được gọi là hệ chuyên gia hay hệ cơsở tri thức.