Chương 1 CƠ SỞ LÍ LUẬN VÀ THỰC TIỄN 1. Quy trình thuật toán và quy trình tựa thuật toán 1. Quy trình thuật toán a) Thuật toán Hàng ngày con người tiếp xúc với rất nhiều bài toán từ đơn giản đến phức tạp. Đối với một số bài toán tồn tại những quy tắc xác định nhằm mô tả quá trình giải bài toán đó.
Từ việc mô tả quá trình ấy, người ta đi đến khái niệm trực giác về thuật toán. Theo Bùi Văn Nghị (1996): “Thuật toán là một khái niệm cơ bản, được hiểu như một quy tắc mô tả những chỉ dẫn rõ ràng và chính xác để người (hay máy) thực hiện một loạt thao tác nhằm đạt được mục đích đặt ra hay giải một lớp bài toán nhất định ”. [10, trang 16 - 18] Theo Nguyễn Bá Kim (2011): “Thuật giải theo nghĩa trực giác được hiểu như một dãy hữu hạn những chỉ dẫn thực hiện được theo một trình tự, kết thúc sau một số hữu hạn bước và đem lại kết quả là biến đổi thông tin vào (INPUT) của một lớp bài toán thành thông tin ra (OUTPUT) mô tả lời giải bài toán đó.”[6, trang 376] Theo Vương Dương Minh (1996): “Thuật giải là một quy tắc chính xác và đơn trị quy định một số hữu hạn những thao tác sơ cấp theo một trình tự xác định trên những đối tượng sao cho sau một số hữu hạn những thao tác ta thu được kết quả mong muốn.”[7, trang 12] Theo bách khoa toàn thư mở Wikipedia: Thuật giải là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán. Từ những quan niệm trên có thể thấy rằng, quan niệm về thuật toán (thuật giải) của các nhà khoa học có thể có sự khác nhau về mặt ngôn ngữ biểu đạt, nhưng bản chất của chúng thống nhất với nhau, đều quan niệm rằng thuật toán (thuật giải) là một quy trình gồm các bước, với việc thực hiện theo các bước đó sẽ đi đến lời giải bài toán.
5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bởi vậy, trong luận này này chúng tôi đồng nhất thuật ngữ “thuật toán” và “thuật giải”. b) Tính chất của thuật toán Thuật toán có những tính chất cơ bản sau: Tính đơn trị: Mỗi thao tác trong thuật toán phải đơn trị; nghĩa là hai chủ thể (người/ máy) thực hiện cùng một thao tác thì phải cho cùng một kết quả. Nhờ đó ta có thể lập trình giao cho các thiết bị tự động thực hiện thuật giải thay thế cho con người. Tính dừng: Sau một số hữu hạn lần thực hiện các thao tác phải đi đến kết thúc, không được lặp lại mãi.
Tính phổ dụng: Thuật toán phải áp dụng được cho một lớp các bài toán có cùng cấu trúc với những dữ liệu cụ thể khác nhau. Từ ba tính chất cơ bản nói trên, có thể suy ra một số tính chất sau: Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau. Tính đúng đắn: Thuật toán phải đảm bảo tính đúng đắn tức là phải giải quyết đúng vấn đề đặt ra, làm đúng công việc mà ta mong muốn, không cho phép kết quả sai hoặc không đầy đủ, bỏ sót trường hợp. Ngoài ra người ta thường chú ý tới tính chất nang cao của thuật toán là tính hiệu quả (tính tối ưu): thực hiện nhanh, tốn ít thiết bị lưu trữ các kết quả trung gian, đáp ứng được nhu cầu của thực tiễn.
c) Các hình thức biểu diễn thuật toán Thuật toán tồn tại dưới nhiều hình thức khác nhau. Trong môn toán và trong thực tế người ta thường gặp những hình thức biểu diễn thuật toán sau: Ngôn ngữ tự nhiên và ngôn ngữ toán học; sơ đồ khối; ngôn ngữ phỏng trình và các ngôn ngữ lập trình. d) Quy trình thuật toán “Quy trình là một trình tự phải tuân theo để tiến hành một công việc nào đó”. [12] Một quy trình có thể chia thành các bước; mỗi bước là một hoạt động nhằm một mục đích nhất định; một hoạt động có thể có nhiều thao tác.
Quy trình thuật toán được hiểu là quy trình thực hiện các bước của một thuật toán nào đó. Thuật toán giải phương trình bậc hai gồm các bước sau: 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Bước 1: Xác định hệ số a,b, c. Bước 2: Tính biệt thức b 2 4ac hoặc ' b' 2 ac Bước 3: Xét dấu hoặc ' từ đó kết luận. +) Nếu 0 hoặc ' 0 thì phương trình vô nghiệm.
+) Nếu 0 hoặc ' 0 thì phương trình có nghiệm có nghiệm kép b b ' x1 x2 hoặc x1 x2 . 2a a +) Nếu 0 hoặc ' 0 thì phương trình có hai nghiệm phân biệt b b ' ' x1 x1 2a hoặc a b b ' ' x1 x1 . Quy trình tựa thuật toán Trong luận văn này chúng tôi đồng nhất một số thuật ngữ sau: “quy trình tựa thuật toán”, “quy trình có tính chất thuật toán”, “quy trình tựa thuật giải”. Theo Bùi Văn Nghị (1996): Trong nhà trường phổ thông, “Một quy trình có tính chất thuật toán là; (1) quy trình có một trình tự xác định, các thao tác nối tiếp nhau được sắp xếp từ đơn giản đến phức tạp; (2) Các thao tác được chỉ dẫn rõ ràng, chính xác;(3) Theo quy trình, người thực hiện nhất định sẽ đi đến kết quả của bài toán; Nếu kết quả chưa có ở thao tác này thì sẽ có ở các thao tác khác tiếp theo.
Sau một số hữu hạn các thao tác; (4) Quy trình giúp học sinh giải được tất cả các bài toán cùng loại trong các sách giáo khoa, sách bài tập.”[6, trang 19] Theo Nguyễn Bá Kim: “Trong quá trình dạy học người ta thường gặp một số quy tắc tuy chưa mang đủ các đặc điểm đặc trưng cho thuật giải, nhưng có một số trong các đặc điểm đó và đã tỏ ra có hiệu lực trong việc chỉ dẫn hành động và giải toán. Đó là những quy tắc tựa thuật giải được hiểu như một dãy hữu hạn những chỉ dẫn thực hiện được theo một trình tự xác định nhằm biến đổi thông tin vào của một lớp bài toán thành những thông tin ra mô tả lời giải của những bài toán đó. Quy trình tính khoảng cách từ điểm A đến mặt phẳng (P). 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Bước 1: Tìm mặt phẳng (Q) qua A và vuông góc với (P) Bước 2: Tìm giao tuyến d ( P) (Q) Bước 3: Trong (Q) hạ AH d tại H Bước 4: Độ dài AH là khoảng cách từ A đến (P).
Cách tìm đường vuông góc chung của hai đường thẳng chéo nhau trong không gian trong sách giáo khoa Hình học 11 [16, tr 117] có thể xem như một quy trình tựa thuật toán: Hình 1.2 “Cho hai đường thẳng chéo nhau a và b. Do đó a’ và b cắt nhau tại một điểm. Gọi điểm này là N. Gọi ( ) là mặt phẳng chứa a và a’, ∆ là đường thẳng đi qua N và vuông góc với 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Như vậy ∆ nằm trong ( ) nên cắt đường thẳng a tại M và cắt đường thẳng b tại N, đồng thời ∆ cùng vuông góc với cả a và b. Do đó ∆ là đường vuông góc chung của a và b”. Quy trình bốn bước của Polya1 để giải một bài toán gồm các bước sau: Bước 1: Hiểu bài toán Để hiểu rõ bài toán chúng ta đi trả lời các câu hỏi như: Cái gì chưa biết? Cái gì đã cho? Điều kiện của bài toán là gì? Điều kiện có đủ để xác định được ẩn không?…. Nếu là bài toán hình học, chúng ta tiến hành vẽ hình hay sử dụng các ký hiệu thích hợp mô tả bài toán, viết giả thiết, kết luận….
Bước 2: Tìm lời giải Để giúp HS xây dựng được chương trình giải, GV thường gợi ý HS bằng các câu hỏi như: - Em đã gặp bài toán này lần nào chưa? Em có biết bài toán nào gần giống bài toán này không? - Đây là một bài toán có liên quan mà em đã có lần giải rồi. Có thể sử dụng kết quả hay phương pháp của nó không? Có cần phải đưa thêm một số yếu tố phụ thì mới sử dụng được nó không? Nếu em chưa giải được bài toán đã đề ra, thì hãy thử giải một bài toán có liên quan. Em có biết bài toán nào có liên quan mà dễ hơn không? Một trường hợp riêng? Một bài toán tương tự? Một bài toán tổng quát? - Em đã sử dụng mọi dữ kiện chưa? Đã để ý đến mọi khái niệm chủ yếu trong bài toán chưa? Bước 3: Trình bày lời giải Khi thực hiện chương trình GV cần chú ý HS kiểm tra lại từng bước thông qua các câu hỏi như: Em đã thấy rõ ràng là mỗi bước đều đúng chưa? Em có thể chứng minh là nó đúng không? Bước 4: Nhìn lại Giải xong bài toán không có nghĩa là bài toán đó đã kết thúc. GV nên hướng dẫn HS hình thành dần thói quen xem xét lại lời giải bài toán thông qua các câu hỏi: - Em có thể kiểm tra lại kết quả hay quá trình giải bài toán không? 1 (G.
Polya, "How to Solve It", 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6: (1) understanding the problem; (2) devising a plan, (3) carrying out the plan, (4) looking back). 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com - Có thể tìm được kết quả một cách khác không? - Em có thể sử dụng kết quả hay phương pháp đó cho một bài toán nào khác không? Quy trình này được mỗi người vận dụng theo cách riêng của mình, theo kinh nghiệm riêng của bản thân và đạt được mức độ khác nhau. Tuy rằng quy trình này không hướng dẫn người giải toán một cách tỉ mỉ, chi tiết từng thao tác cụ thể, mà chỉ là những định hướng suy nghĩ, gợi ý thao tác, song do tầm khái quát và dung nạp được nhiều kinh nghiệm quí báu, nên đã nhiều chục năm quy trình đó đó vẫn tỏ ra có hiệu quả.5 (Minh họa giải một bài toán theo 4 bước của Polya) Cho tứ diện đều ABCD có cạnh bằng a. Gọi I là trung điểm của AD, J là điểm đối xứng với D qua C, K là điểm đối xứng với D qua B.