Luận án Phát triển tư duy thuật toán cho học sinh thông qua dạy học thuật toán ở trường trung học phổ thông

KHOA HỌC GIÁO DỤC Chuyên ngành: Lý luận và phƣơng pháp dạy học bộ môn toán Mã số: 62 14 01 11 NGƢỜI HƢỚNG DẪN KHOA HỌC 1: PGS.TS Lê Khắc Thành 2: PGS.TS. Hồ Cẩm Hà HÀ NỘI - 2015 - i - LỜI CAM ĐOAN Tôi xin cam đoan đây công trình nghiên cứu do chính tôi thực hiện. Các kết quả nghiên cứu đƣợc trình bày trong luận án là trung thực, khách quan và chƣa đƣợc công bố bởi bất kỳ tác giả nào hay ở bất cứ công trình nào khác. Các thông tin trích dẫn trong luận án này đều đƣợc chỉ rõ nguồn gốc. Tác giả Nguyễn Chí Trung - ii - LỜI CẢM ƠN Tôi muốn tỏ lòng biết ơn đến rất nhiều ngƣời, với nhiều cách khác nhau đã giúp đỡ Tôi hoàn thành luận án này. Trƣớc hết, tôi xin chân thành cảm ơn PGS.TS Lê Khắc Thành và PGS.TS Hồ Cẩm Hà – các thầy cô trực tiếp hƣớng dẫn và động viên Tôi trong suốt quá trình nghiên cứu luận án. Chân thành cảm ơn GS.TS Bùi Văn Nghị, và các Thầy cô thuộc bộ môn Lý luận và Phƣơng pháp dạy học toán, khoa Toán Tin, trƣờng Đại học Sƣ phạm Hà nội, đã có những góp ý quí báu trong suốt quá trình sinh hoạt tại bộ môn, để luận án đƣợc hoàn thiện tốt hơn. Tôi chân thành cảm ơn GS.TSKH Nguyễn Bá Kim và các thầy cô trong Hội đồng bộ môn đã giúp chọn tên luận án phù hợp, phản ánh đúng nội dung nghiên cứu. Tôi chân thành cảm ơn PGS.TS Vũ Quốc Chung đã hƣớng dẫn tôi trong giai đoạn hoàn thiện luận án để luận án có chất lƣợng tốt hơn. Trân trọng cảm ơn Quý phòng ban và Quý trƣờng Đại học Sƣ phạm Hà nội đã hỗ trợ toàn bộ kinh phí đào tạo cũng nhƣ tạo nhiều điều kiện thuận lợi cho Tôi trong thời gian học tập và hoàn thành chƣơng trình tiến sỹ. Chân thành cảm ơn các thầy cô của bộ môn Lý luận và Phƣơng pháp dạy học, Ban chủ nhiệm khoa Công nghệ thông tin đã cho phép và tạo điều kiện thuận lợi cho tôi đƣợc học chƣơng trình tiến sỹ. Chân thành cảm ơn các thầy cô trong khoa, các bạn bè đồng nghiệp và các em sinh viên đã chia sẻ và động viên cho tôi trong thời gian học tập. Đặc biệt nhất, trong luận án này tôi xin dành sự biết ơn đến gia đình nhất là vợ và các con đã sát cánh chia sẻ trong suốt thời gian nghiên cứu luận án. - iii - BẢNG CÁC CỤM TỪ VIẾT TẮT Từ viết tắt Viết đầy đủ CNTT Công nghệ thông tin ĐC Đối chứng GV Giáo viên HS Học sinh NT Nông thôn PPDH Phƣơng pháp dạy học PTĐT Phƣơng trình đƣờng thẳng PTTH Phân tích, tổng hợp SGK Sách giáo khoa SGV Sách giáo viên THPT Trung học phổ thông TN Thực nghiệm TongBiet Tổng điểm đánh giá mức độ nhận biết TongHieu Tổng điểm đánh giá mức độ thông hiểu TongPTTH Tổng điểm đánh giá mức độ phân tích, tổng hợp TongVDung Tổng điểm đánh giá mức độ vận dụng TP Thành phố TX Thị xã XLBiet Xếp loại mức độ nhận biết XLHieu Xếp loại mức độ thông hiểu XLPTTH Xếp loại mức độ phân tích, tổng hợp XLVD Xếp loại mức độ vận dụng - iv - MỤC LỤC MỞ ĐẦU ......................................................................................................... 1 1. Lý do chọn đề tài ......................................................................................... 1 2. Mục tiêu nghiên cứu .................................................................................... 2 3. Nhiệm vụ nghiên cứu ................................................................................... 2 3.1. Nghiên cứu lý luận .................................................................................... 2 3.2. Nghiên cứu thực tiễn ................................................................................. 2 3.3. Đề xuất giải pháp ...................................................................................... 3 3.4. Thực nghiệm sƣ phạm .............................................................................. 3 4. Đối tƣợng nghiên cứu .................................................................................. 3 5. Phạm vi nghiên cứu ..................................................................................... 3 6. Phƣơng pháp nghiên cứu ............................................................................. 4 6.1. Nghiên cứu lý luận .................................................................................... 4 6.2. Khảo sát điều tra thực tiễn ........................................................................ 4 6.3. Nghiên cứu trƣờng hợp ............................................................................. 4 6.4. Thực nghiệm sƣ phạm .............................................................................. 4 6.5. Thống kê Toán học ................................................................................... 4 7. Giả thuyết khoa học ..................................................................................... 4 8. Các luận điểm bảo vệ và đóng góp của luận án ........................................... 5 8.1. Về mặt lý luận ........................................................................................... 5 8.2. Về mặt thực tiễn ........................................................................................ 5 9. Cấu trúc và tóm tắt nội dung của luận án .................................................... 5 CHƢƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN VỀ VIỆC DẠY HỌC THUẬT TOÁN ............................................................................................... 7 1.1. SỰ HÌNH THÀNH KHÁI NIỆM THUẬT TOÁN .................................. 7 1.1.1. Nguồn gốc của từ thuật toán .................................................................. 7 1.1.2. Sự hình thành khái niệm thuật toán trong Toán học .............................. 7 1.1.3. Khái niệm thuật toán trong Khoa học máy tính ..................................... 10 1.1.4. Khái niệm thuật toán đƣợc dạy ở trƣờng phổ thông .............................. 13 1.2. CÁC TÍNH CHẤT CỦA THUẬT TOÁN................................................ 14 1.2.1. Các tính chất cơ bản của thuật toán ....................................................... 14 1.2.2. Các tính chất mở rộng ............................................................................ 15 1.3. TỔNG QUAN VỀ NHỮNG CÁCH TIẾP CẬN DẠY HỌC THUẬT TOÁN .......................................................................................................................... 19 1.3.1. Dạy học thuật toán trong một số nội dung Toán học ............................. 19 - v - 1.3.2. Dạy học thuật toán thông qua các câu đố và câu đố giống nhƣ trò chơi .......................................................................................................................... 19 1.3.3. Dạy học thuật toán bằng phƣơng pháp trực quan hóa thuật toán .......... 20 1.3.4. Dạy học thuật toán theo hƣớng phát triển tƣ duy thuật toán ................. 21 1.3.5. Dạy học thuật toán theo các mức trừu tƣợng của tƣ duy thuật toán ...... 26 BÌNH LUẬN .................................................................................................... 28 1.4. THỰC TIỄN DẠY HỌC THUẬT TOÁN Ở TRƢỜNG TRUNG HỌC PHỔ THÔNG ........................................................................................................... 28 1.4.1. Nghiên cứu, khảo sát thực tiễn dạy học thuật toán ................................ 28 1.4.2. Kết quả khảo sát điều tra tình hình học thuật toán ................................ 29 1.4.3. Thực tế dạy học thuật toán trong môn Toán và môn Tin học ............... 31 1.4.4. Đánh giá và đề xuất ............................................................................... 33 KẾT LUẬN CHƢƠNG 1 ................................................................................ 34 CHƢƠNG 2. CÁC BIỂU HIỆN VÀ CÁC CẤP ĐỘ CỦA SỰ PHÁT TRIỂN TƢ DUY THUẬT TOÁN .............................................................................. 35 2.1. KHÁI NIỆM TƢ DUY THUẬT TOÁN .................................................. 35 2.1.1. Những căn cứ để đề xuất khái niệm tƣ duy thuật toán .......................... 35 2.1.2. Khái niệm tác nhân và khái niệm tƣ duy thuật toán .............................. 36 2.2. CÁC BIỂU HIỆN CỦA SỰ PHÁT TRIỂN TƢ DUY THUẬT TOÁN TRONG GIẢI BÀI TẬP TOÁN THEO THUẬT TOÁN ............................... 37 Bài toán về các chất dinh dƣỡng ...................................................................... 38 2.2.1. Hiểu bài toán .......................................................................................... 38 2.2.2. Hiểu hƣớng giải quyết giải bài toán ....................................................... 40 2.2.3. Hiểu thuật toán giải bài toán .................................................................. 41 2.2.4. Thực hiện đƣợc thuật toán giải bài toán ................................................ 43 2.2.5. Xây dựng đƣợc thuật toán tƣơng đƣơng ................................................ 44 2.2.6. Đánh giá đƣợc thuật toán ....................................................................... 45 2.2.7. Cải tiến thuật toán hoặc xây dựng đƣợc thuật toán mới ........................ 46 2.3. CÁC BIỂU HIỆN CỦA TƢ DUY THUẬT TOÁN TRONG GIẢI BÀI TOÁN DỰA VÀO CÁC CÔNG CỤ TÍNH TOÁN TỰ ĐỘNG ..................... 46 2.3.1. Xác định bài toán ................................................................................... 47 2.3.2. Hiểu ý tƣởng thuật toán ......................................................................... 48 2.3.3. Hiểu thuật toán ....................................................................................... 50 2.3.4. Thực hiện đƣợc thuật toán ..................................................................... 54 2.3.5. Xây dựng đƣợc thuật toán tƣơng đƣơng ................................................ 56 2.3.6. Đánh giá đƣợc thuật toán ....................................................................... 57 - vi - 2.3.7. Cải tiến đƣợc thuật toán hoặc thiết kế đƣợc thuật toán mới .................. 58 2.4. CÁC CẤP ĐỘ CỦA SỰ PHÁT TRIỂN TƢ DUY THUẬT TOÁN........ 58 2.4.1. Ý nghĩa của việc xác định các cấp độ tƣ duy thuật toán........................ 58 2.4.2. Các cấp độ tƣ duy thuật toán ................................................................. 59 2.4.3. Những biểu hiện của các cấp độ tƣ duy thuật toán ................................ 60 2.4.4. Ví dụ minh họa về các cấp độ tƣ duy thuật toán ................................... 61 KẾT LUẬN CHƢƠNG 2 ................................................................................ 68 CHƢƠNG 3. MỘT SỐ TIẾP CẬN MỚI TRONG DẠY HỌC PHÁT TRIỂN TƢ DUY THUẬT TOÁN CHO HỌC SINH TRUNG HỌC PHỔ THÔNG .......................................................................................................................... 70 3.1. PHƢƠNG PHÁP THAO TÁC HÓA TRONG DẠY HỌC THUẬT TOÁN .......................................................................................................................... 70 3.1.1. Phƣơng pháp chia để trị và mô đun hóa thuật toán ............................... 70 3.1.2. Phƣơng pháp thao tác hóa trong dạy học thuật toán .............................. 77 3.1.3. Sự phát triển tƣ duy thuật toán trong dạy học thuật toán theo phƣơng pháp thao tác hóa ...................................................................................................... 89 3.2. PHƢƠNG PHÁP LÀM MỊN DẦN TRONG DẠY HỌC THUẬT TOÁN .......................................................................................................................... 91 3.2.1. Khái niệm phƣơng pháp làm mịn dần trong dạy học thuật toán ........... 91 3.2.2. Tổng quan về các cách tiếp cận làm mịn dần ........................................ 92 3.2.3. Quá trình làm mịn dần từ ngoài vào ...................................................... 92 3.2.4. Phân biệt “mô đun thuật toán” và “gói thuật toán” ............................... 98 3.2.5. Sự phát triển tƣ duy thuật toán trong dạy học thuật toán theo phƣơng pháp làm mịn dần từ ngoài vào ................................................................................ 98 3.3. PHƢƠNG PHÁP TINH CHẾ TRONG DẠY HỌC THUẬT TOÁN ...... 100 3.3.1. Giới thiệu phƣơng pháp tinh chế và các khái niệm liên quan ............... 100 3.4.2. Nguyên tắc tinh chế dựa trên ngôn ngữ và sự phát triển của tƣ duy thuật toán ................................................................................................................... 103 3.4.3. Tinh chế tƣơng đƣơng theo từng bƣớc của quá trình xây dựng thuật toán .......................................................................................................................... 105 3.4.5. Sự phát triển của tƣ duy thuật toán trong quá trình tinh chế tƣơng đƣơng .......................................................................................................................... 109 3.4.6. Tinh chế nâng cấp .................................................................................. 111 3.4.7. Sự phát triển tƣ duy thuật toán trong quá trình tinh chế nâng cấp......... 116 KẾT LUẬN CHƢƠNG 3 ................................................................................ 117 CHƢƠNG 4. THỰC NGHIỆM SƢ PHẠM ................................................ 119 - vii - 4.1. MỤC ĐÍCH, PHƢƠNG PHÁP ĐÁNH GIÁ VÀ QUI TRÌNH THỰC NGHIỆM ......................................................................................................... 119 4.1.1. Mục đích, mục tiêu và nhiệm vụ của thực nghiệm sƣ phạm ................. 119 4.1.2. Phƣơng pháp đánh giá trong thực nghiệm sƣ phạm .............................. 119 4.2. QUI TẮC MÃ HÓA VÀ QUI ĐỔI ĐIỂM ............................................... 121 4.2.1. Qui đổi và mã hóa điểm bài kiểm tra - đánh giá tổng kết ...................... 121 4.2.2. Qui đổi và mã hóa điểm bài tập nhóm - Đánh giá ngang hàng và tự đánh giá ..................................................................................................................... 122 4.2.3. Qui đổi và mã hóa điểm từ phiếu khảo sát ............................................ 123 4.3. THỰC NGHIỆM 1 ................................................................................... 124 4.3.1. Giới thiệu thực nghiệm .......................................................................... 124 4.3.2. Kết quả đánh giá bài tập nhóm .............................................................. 125 4.3.3. Kết quả làm bài kiểm tra ........................................................................ 128 4.3.4. Kết quả đánh giá về phƣơng pháp dạy học của GV .............................. 130 4.3.5. Kết luận thực nghiệm 1 .......................................................................... 133 4.4. THỰC NGHIỆM 2 ................................................................................... 134 4.4.1. Giới thiệu thực nghiệm 2 ....................................................................... 134 4.4.2. Kết quả đánh giá bài tập nhóm và bài kiểm tra ..................................... 134 4.4.3. Kết quả đánh giá về phƣơng pháp dạy học của giáo viên ..................... 140 4.5. ĐỀ XUẤT VÀ KIẾN NGHỊ ..................................................................... 142 4.5.1. Về việc dạy học thuật toán ở trƣờng trung học phổ thông .................... 142 4.5.2. Về điều chỉnh một số nội dung của học phần PPDH chuyên ngành môn Tin học .................................................................................................................... 142 KẾT LUẬN CHƢƠNG 4 ................................................................................ 143 KẾT LUẬN ..................................................................................................... 144 CÁC CÔNG TRÌNH CỦA TÁC GIẢ .......................................................... 147 TÀI LIỆU THAM KHẢO ............................................................................. 148 - viii - DANH MỤC CÁC VÍ DỤ Ví dụ 1. 1. Dãy Fibonacii ................................................................................ 14 Ví dụ 1. 2. So sánh hai thuật toán sắp xếp ...................................................... 15 Ví dụ 1. 3. Hệ phƣơng trình đại số tuyến tính ................................................. 17 Ví dụ 1. 4. Công thức tính tích phân không sử dụng đƣợc ............................. 17 Ví dụ 2. 1. Chọn các cuộc họp ........................................................................ 35 Ví dụ 2. 2. Hiểu rõ bài toán ............................................................................. 38 Ví dụ 2. 3. Phát biểu đƣợc bài toán tổng quát ................................................. 39 Ví dụ 2. 4. Đƣa ra đƣợc đầy đủ công cụ và hƣớng giải quyết bài toán ........... 40 Ví dụ 2. 5. Hiểu rõ thuật toán .......................................................................... 41 Ví dụ 2. 6. Vận dụng đƣợc thuật toán ............................................................. 43 Ví dụ 2. 7. Xây dựng đƣợc thuật toán tƣơng đƣơng ....................................... 44 Ví dụ 2. 8. Chỉ ra đƣợc hạn chế và ƣu điểm của thuật toán ............................ 45 Ví dụ 2. 9. Tìm hƣớng giải khác cho bài toán ................................................. 46 Ví dụ 2. 10. Phát biểu đƣợc bài toán tổng quát và tổ chức tốt dữ liệu ............ 47 Ví dụ 2. 11. Hiểu rõ ý tƣởng thuật toán .......................................................... 48 Ví dụ 2. 12. Hiểu rõ thuật toán ........................................................................ 50 Ví dụ 2. 13. Áp dụng và mô phỏng thuật toán ................................................ 54 Ví dụ 2. 14. Xây dựng đƣợc phiên bản mô tả mới cho thuật toán .................. 56 Ví dụ 2. 15. Đánh giá tính chất và hiệu quả của thuật toán ............................ 57 Ví dụ 2. 16. Phát hiện sai sót và cải tiến thuật toán ........................................ 58 Ví dụ 2. 17. Xác định tham số để các nghiệm của phƣơng trình bậc hai thỏa mãn một hệ thức cho trƣớc ...................................................................................... 62 Ví dụ 2. 18. So sánh một số với các nghiệm của phƣơng trình bậc hai .......... 65 Ví dụ 3. 1. Tìm các số đặc trƣng của mẫu số liệu ........................................... 72 Ví dụ 3. 2. Tìm các số đặc trƣng của các mẫu số liệu: Dùng sơ đồ khối ........ 75 Ví dụ 3. 3. Thuật toán tìm số trung bình tổng quát ......................................... 78 Ví dụ 3. 4. Tìm phƣơng trình đƣờng thẳng – Bài toán 1 (Hình học lớp 10) ... 81 Ví dụ 3. 5. Tìm phƣơng trình đƣờng thẳng – Bài toán 2 (Hình học lớp 10) ... 86 Ví dụ 3. 6. Làm mịn từ ngoài vào một lần ...................................................... 93 Ví dụ 3. 7. Tinh chế theo từng bƣớc của quá trình xây dựng thuật toán ......... 105 Ví dụ 3. 8. Tinh chế nâng cấp ......................................................................... 112 Ví dụ 3. 9. Về cách ƣớc lƣợng, đánh giá hiệu quả thuật toán ......................... 113 - ix - DANH MỤC CÁC BẢNG Bảng 1. 1. Bảng thống kê tổng hợp ................................................................. 29 Bảng 1. 2. Thống kê mô tả (Descriptive Statistics) ......................................... 30 Bảng 1. 3. Mô tả tần suất (Frequency table) ................................................... 30 Bảng 1. 4. Giá trị các thang đo theo từng đối tƣợng học sinh ......................... 31 Bảng 1. 5. Báo cáo các giá trị trung bình của các thang đo nhận thức ........... 31 Bảng 4. 1. Qui tắc qui đổi điểm của một bài tập trong đề kiểm tra ................ 122 Bảng 4. 2. Bảng qui tắc qui đổi điểm của bài tập nhóm ................................. 123 Bảng 4. 3. Bảng qui đổi điểm sang các thang đo khảo sát .............................. 124 Bảng 4. 4. Thống kê kết quả bài tập nhóm của các lớp thực nghiệm ............. 125 Bảng 4. 5. Thống kê kết quả bài tập nhóm của các lớp đối chứng ................. 126 Bảng 4. 6. Bảng tổng hợp: So sánh kết quả làm bài tập nhóm giữa các lớp thực nghiệm và các lớp đối chứng ........................................................................... 127 Bảng 4. 7. Thống kê kết quả làm bài kiểm tra của các lớp thực nghiệm ........ 128 Bảng 4. 8. Thống kê kết quả làm bài kiểm tra của các lớp đối chứng ............ 129 Bảng 4. 9. Bảng tổng hợp: So sánh kết quả làm bài kiểm tra giữa các lớp thực nghiệm và các lớp đối chứng ........................................................................... 130 Bảng 4. 10. Điểm trung bình đánh giá PPDH của GV .................................... 131 Bảng 4. 11. Kiểm định giả thuyết thống kê ..................................................... 132 Bảng 4. 12. Thống kê kết quả bài tập nhóm của các lớp thực nghiệm ........... 135 Bảng 4. 13. Thống kê kết quả làm bài kiểm tra của các lớp thực nghiệm ...... 136 Bảng 4. 14. Thống kê kết quả bài tập nhóm của các lớp đối chứng ............... 137 Bảng 4. 15. Thống kê kết quả làm bài kiểm tra của các lớp đối chứng .......... 138 Bảng 4. 16. Bảng tổng hợp: So sánh kết quả làm bài tập nhóm giữa các lớp thực nghiệm và các lớp đối chứng ........................................................................... 139 Bảng 4. 17. Bảng tổng hợp: So sánh kết quả làm bài kiểm tra giữa các lớp thực nghiệm và các lớp đối chứng ........................................................................... 139 Bảng 4. 18. Điểm trung bình đánh giá PPDH của GV .................................... 140 Bảng 4. 19. Kiểm định giả thuyết thống kê ..................................................... 141 - x - DANH MỤC CÁC HÌNH VẼ VÀ BIỂU ĐỒ Hình 1. 1. Tìm cách đi qua mê cung ............................................................... 24 Hình 1. 2. Vừa đi vừa đánh dấu ...................................................................... 25 Hình 1. 3. Thuật toán giải quyết vấn đề của Luay Nakhleh ............................ 26 Hình 2. 1. Miền nghiệm của hệ điều kiện và tập các phƣơng án của bài toán 41 Hình 2. 2. Các giao điểm của các đƣờng thẳng đƣợc tính bởi thuật toán ....... 55 Hình 2. 3. Đồ thị hàm bậc hai trong trƣờng hợp có hai nghiệm ..................... 67 Hình 3. 1. Một số mô đun thuật toán giải bài toán tính các số đặc trƣng ....... 77 Hình 3. 2. Sơ đồ thuật toán P ở dạng “thô” ..................................................... 94 Hình 3. 3. Sơ đồ thuật toán Q .......................................................................... 95 Hình 3. 4. Sơ đồ thuật toán P ở dạng mịn (cách 1) ......................................... 96 Hình 3. 5. Sơ đồ thuật toán P ở dạng mịn (cách 2) ......................................... 97 Hình 3. 6. Dãy cần sắp xếp đƣợc chia thành 2 đoạn ....................................... 110 Hình 3. 7 Chuyển phần tử nhỏ nhất về đầu dãy con ....................................... 112 Biều đồ 4. 1. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm và bài tập . ....................... 125 Biều đồ 4. 2. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm. ............................................... 126 Biều đồ 4. 3. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và nhóm lớp đối chứng. ........................................................................................ 128 Biều đồ 4. 4. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. ................................................. 128 Biều đồ 4. 5. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. ................................................. 129 Biều đồ 4. 6. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm. ......................................... 135 Biều đồ 4. 7. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS các lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. ................................................. 136 Biều đồ 4. 8. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm. ............................................... 137 Biều đồ 4. 9. Biểu đồ biểu diễn số lƣợng và tỉ lệ HS nhóm lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. ................................................. 138 Biều đồ 4. 10. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và nhóm lớp đối chứng. ........................................................................................ 140 1 MỞ ĐẦU 1. Lý do chọn đề tài Bàn về tƣ duy, Pascal cho rằng “Tư duy tạo nên sự cao cả của con người”; Descartes nói “Tôi tư duy tức là tôi tồn tại”; Emerson nói “Tư duy là hạt giống của hành động”; H.Poincaré dùng hình ảnh “Tư duy là một tia sáng giữa đêm tối. Nhưng chính tia sáng ấy là tất cả”. Bàn về dạy học, rèn luyện tƣ duy, nguyên thủ tƣớng Phạm Văn Đồng nói “Điều chủ yếu không phải là nhồi nhét một mớ kiến thức hỗn độn mà là phương pháp suy nghĩ, phương pháp nghiên cứu, phương pháp học tập, phương pháp giải quyết vấn đề”. Theo ngạn ngữ cổ Hy lạp thì “Dạy học không phải là rót kiến thức vào một chiếc thùng rỗng mà là thắp sáng lên những ngọn lửa”. Theo Lê Hải Yến (2008), mục tiêu của bậc học phổ thông là hình thành và phát triển đƣợc nền tảng tƣ duy của HS trong thời đại mới, bao gồm nhóm kiến thức, kĩ năng cơ bản của các môn học phổ thông, nhóm các kĩ năng tƣ duy và nhóm các phẩm chất nhân cách và đạo đức. Trong đó, các kĩ năng tƣ duy có thể kể đến nhƣ biết cách suy luận, phát hiện, giải quyết vấn đề, biết cách học, cách tự học, có tƣ duy sáng tạo, ... Thông qua dạy kiến thức và kỹ năng để đạt đƣợc mục tiêu là hình thành và phát triển năng lực tƣ duy - trí tuệ của HS, thông qua việc dạy và học tƣ duy, chúng ta sẽ tạo đƣợc nền móng trí tuệ - cách suy nghĩ để giải quyết các vấn đề trong thực tiễn sau này cho mỗi HS khi bƣớc vào đời. Vậy, mục tiêu quan trọng của quá trình dạy và học là giúp cho HS phát triển được tư duy. Hồ Sỹ Đàm và các cộng sự (2006) đã khẳng định mục tiêu trên đây trong dạy học môn Tin học bậc học phổ thông và nhấn mạnh: Mục tiêu của môn Tin học là “nhằm cung cấp cho HS những kiến thức phổ thông về ngành khoa học Tin học, hình thành và phát triển khả năng tư duy thuật toán, năng lực sử dụng các thành tựu của ngành khoa học này trong học tập và trong các lĩnh vực hoạt động của mình sau này". Nguyễn Bá Kim (2009) đã đề cập đến ―dạy học qui tắc phương pháp” trong dạy học môn Toán, cụ thể là dạy thuật giải và những qui tắc tựa thuật giải. Dạy thuật giải nhằm dạy cho HS kiến tạo tri thức, đặc biệt là tri thức phương pháp. Đây là một nội dung rất quan trọng, vì nó dạy cho HS tư duy thuật giải, hay nói rộng hơn là dạy HS phƣơng pháp tiếp cận giải quyết một vấn đề một cách khoa học. Ở môn Toán, có những tri thức phƣơng pháp là các thuật giải và qui tắc tựa thuật giải đƣợc chƣơng trình qui định dạy tƣờng minh. Ở môn Tin học, tất cả các bài toán đều đƣợc dạy tƣờng minh thuật toán. Có thể nói rằng thuật toán là phƣơng pháp giải quyết 2 vấn đề lấy nền tảng là Toán học, đƣợc phát triển mạnh mẽ trong ngành Khoa học máy tính, và nó trở thành mối quan tâm của cả hai phạm trù Toán học và Tin học. Vậy thuật toán là nội dung dạy học mà nó mở ra nhiều cơ hội nhất để rèn luyện và phát triển tƣ duy nói chung và tƣ duy thuật toán nói riêng cho HS. Trong những năm gần đây, dạy học theo định hướng phát triển năng lực đã trở thành xu hƣớng chính đối với nhiều nƣớc trên thế giới, đặc biệt là các nƣớc phát triển thuộc OECD (Organisation for Economic Co-operation and Development-Tổ chức hợp tác và phát triển kinh tế). Dạy học thuật toán có thể xem nhƣ góp vai trò đáng kể trong dạy học định hƣớng phát triển năng lực giải quyết vấn đề. Bởi lẽ, dạy học thuật toán hƣởng ứng mục tiêu đào tạo hình mẫu con ngƣời có năng lực tự quyết và có khả năng ứng xử và giải quyết các vấn đề trong khoa học và thực tiễn. Với sự đảm bảo của Toán học, thuật toán trong lĩnh vực Khoa học máy tính bồi dƣỡng cho HS phƣơng pháp tƣ duy hiệu quả trong học tập những môn học khác ở trƣờng phổ thông, nhất là trong những kiến thức tích hợp và liên môn với Toán và Tin học. Với những lý do trên, chúng tôi chọn đề tài “Phát triển tư duy thuật toán cho HS thông qua dạy học thuật toán ở trường trung học phổ thông” để nghiên cứu.. 2. Mục tiêu nghiên cứu Mục tiêu của luận án là đề xuất đƣợc một số cách tiếp cận trong dạy học thuật toán nhằm phát triển tƣ duy thuật toán cho HS trong dạy học môn Toán và môn Tin học. Một cách cụ thể, luận án đƣa ra một số cách tiếp cận mới trong dạy học giải bài tập toán theo thuật toán ở một số nội dung của môn Toán và dạy học các thuật toán giải các bài toán dựa vào máy tính thuộc lĩnh vực của môn Tin học. Những cách tiếp cận này nhằm thúc đẩy và hƣớng dẫn HS tƣ duy đúng đắn và hiệu quả trong giải quyết vấn đề, tức là nhằm phát triển tƣ duy thuật toán cho HS. 3. Nhiệm vụ nghiên cứu 3.1. Nghiên cứu lý luận Nghiên cứu các vấn đề sau đây: - Khái niệm thuật toán ở góc độ Toán học và Khoa học máy tính. - Khái niệm thuật toán đƣợc dạy ở môn Tin học trong trƣờng phổ thông. - Các tính chất và đánh giá hiệu quả thuật toán. - Những xu hƣớng dạy học thuật toán hiện nay ở trong nƣớc và trên thế giới. 3.2. Nghiên cứu thực tiễn 3 Khảo sát và đánh giá chất lƣợng dạy học thuật toán và lập trình trong môn Tin học ở một số trƣờng phổ thông. Đánh giá thực tế dạy học thuật toán trong môn Toán. Từ các điều tra và đánh giá trên, đƣa ra các đề xuất phƣơng hƣớng nâng cao hiệu quả dạy học thuật toán. 3.3. Đề xuất giải pháp - Xây dựng các cách tiếp cận mới trong dạy học thuật toán trong môn Toán và môn Tin học ở trƣờn...hân tích cho HS thấy thuật toán 1 tuy dài dòng hơn nhƣng lại “tốt hơn” thuật toán 2, vì thuật toán 1 thực hiện với số lần ít nhất các thao tác hoán đổi giá trị hai phần tử trong dãy số, trong khi đó, thuật toán 2 có thể thực hiện dƣ thừa các thao tác này. 1.2.2. Các tính chất mở rộng 1.2.2.1. Tính hiệu quả của thuật toán đƣợc đo bởi độ phức tạp thuật toán Thời gian thực hiện thuật toán (runing time of algorithm) và độ phức tạp thuật toán (complexity of algorithm) đƣợc Aho A.V., Hopcroft J.E. & Ullman J.D. (1974) đề cập chi tiết trong cuốn sách nổi tiếng với tựa đề “Thiết kế và phân tích thuật toán” (The Design and Analysic of Computer Algorithm). Những vấn đề này đƣợc các tác giả trình bầy lại trong “Cấu trúc dữ liệu và thuật toán” (Data Structures and Algorithms) theo cách thuận lợi cho việc đánh giá hiệu quả của các thuật toán mà chúng đƣợc cài đặt trên các ngôn ngữ lập trình bậc cao (xem Aho A.V., Hopcroft 16 J.E. & Ullman J.D., 1983). Theo các tác giả, thời gian thực hiện thuật toán đƣợc biểu diễn nhƣ một hàm T(n) của kích thƣớc dữ liệu đầu vào n, ví dụ T(n) = C.n2 với C là hằng số1. Hàm T(n) đƣợc tính bằng số lần thực hiện các thao tác sơ cấp (hay các phép tính cơ bản) trong thuật toán. Các phép tính cơ bản bao gồm bốn loại: (1) Lời gọi thủ tục và hàm; (2) Câu lệnh gán; (3) Phép tính số học; (4) Phép toán logic và phép toán so sánh. Hiệu quả của thuật toán đƣợc đánh giá dựa vào hàm thời gian thực hiện thuật toán trong trƣờng hợp dữ liệu đầu vào ở trạng thái “xấu nhất” (worst case running time). Ví dụ, để kiểm tra xem có hay không một phần tử nào đó trong một dãy gồm n số, hiệu quả của thuật toán tìm kiếm tuần tự từ đầu dãy đến cuối dãy đƣợc đánh giá trong trƣờng hợp dữ liệu đầu vào xấu nhất, đó là dãy số mà phần tử cần tìm nằm ở cuối dãy hoặc không có trong dãy. Khi đó, thuật toán phải thực hiện nhiều nhất các phép so sánh giá trị cần tìm với các số trong dãy. Dãy số có n phần tử nên số phép so sánh là n và do đó, thời gian thực hiện thuật toán là T(n) = n. Hiệu quả của thuật toán còn đƣợc đánh giá dựa vào độ tăng (growth rate) của hàm thời gian thực hiện thuật toán. Nó đƣợc biểu thị qua khái niệm “big-O”. Cụ thể nhƣ sau: Thời gian thực hiện thuật toán T(n) đƣợc gọi là có bậc không quá g(n), kí hiệu T(n) = O(g(n)), nếu tồn tại hằng số dƣơng C và số không âm n0 sao cho T(n) ≤ C.g(n) với mọi n ≥ n0. Khi đó hàm g(n) đƣợc xem là độ phức tạp của thuật toán đang xét. Đôi khi ta cũng nói “thuật toán có độ phức tạp (hoặc độ tăng) cỡ g(n)”. Ví dụ, nếu thời gian thực hiện thuật toán là T(n) = 5n2 + 12n + 9, với n là độ lớn của dữ liệu đầu vào, thì T(n) ≤ 5n2 + 12n2 + 9n2  T(n) ≤ 26n2 với n > 0. Vậy nếu đặt g(n) = n 2 , C = 26, n0 = 0, thì T(n) ≤ C.g(n) với n > n0 hay T(n) = O(n 2). Do đó, độ phức tạp thuật toán là cỡ n2, hoặc thuật toán có “độ phức tạp bình phƣơng”. Thông thƣờng, một thuật toán có thể có các độ phức tạp sau đây: hằng số (C) , logarit (log2n), tuyến tính (n), bậc hai (n 2), bậc ba (n3), đa thức (nk), và hàm mũ (an). Việc đánh giá hiệu quả thuật toán thông qua độ phức tạp (hay độ tăng của hàm thời gian thực hiện thuật toán) đƣợc giới thiệu một cách hệ thống ở bậc đại học. Ở bậc phổ thông, hiệu quả thuật toán thƣờng đánh giá trực tiếp thông qua hàm thời gian thực hiện thuật toán, ví dụ, “hiệu quả thuật toán” là T(n) = 5n2 + 12n + 9. Tính hiệu quả của thuật toán còn đƣợc đánh giá một cách trực quan dựa trên tính khả thi hoặc dựa trên phân tích tính ổn định của thuật toán. Đặng Quang Á (2009) 1 Với khái niệm này, thời gian thực hiện thuật toán phụ thuộc vào chính thuật toán chứ không phụ thuộc vào các yếu tố bên ngoài nhƣ tốc độ máy tính và chất lƣợng của chƣơng trình dịch (chƣơng trình cài đặt thuật toán thành chƣơng trình thực hiện đƣợc trên máy tính). 17 đã đƣa ra hai tình huống điển hình và thú vị minh họa các thuật toán không hiệu quả vì vi phạm tính khả thi và tính ổn định nhƣ dƣới đây: 1.2.2.2. Tính khả thi của thuật toán Một thuật toán đảm bảo tính khả thi nếu nó thực hiện được trong một thời gian chấp nhận được đối với người dùng. Ví dụ 1. 3. Hệ phƣơng trình đại số tuyến tính Cho hệ phƣơng trình đại số tuyến tính ,bAx  (1) trong đó A là ma trận vuông cấp n với định thức khác 0. Về lý thuyết có thể giải hệ trên bằng công thức Cramer: ,    iix (i =1,..., n), (2) trong đó ,det A còn i nhận đƣợc từ  bằng cách thay cột thứ i bởi cột tự do b. Nhƣng việc tính toán ra nghiệm bằng số cụ thể lại là một việc không đơn giản. Theo công thức (2) cần phải tính n +1 định thức cấp n. Mỗi định thức là tổng của n! số hạng, mỗi số hạng là tích của n thừa số. Do vậy, để tính mỗi số hạng cần thực hiện n-1 phép nhân. Nhƣ vậy, tất cả số phép tính nhân cần thực hiện trong (2) là Q = n!(n+1)(n-1). Giả sử n = 20. Khi đó 20107073.9 Q . Nếu tốc độ của máy tính là 100 triệu phép tính/giây thì thời gian để thực hiện khối lƣợng tính toán trên là 9106965.2  giờ = 5100782.3  năm. Đây là một thời gian lớn vô cùng! Và nhƣ vậy, thuật toán nêu trên là hoàn toàn không khả thi dù máy tính có tăng tốc độ lên gấp hàng nghìn, hàng vạn lần. Hơn nữa, trên đây ta mới chỉ xét việc giải một hệ cỡ 20, mà thực tế khoa học và công nghệ đòi hỏi phải giải các hệ phƣơng trình đại số tuyến tính cỡ hàng vạn, hàng triệu hoặc hơn thế nữa. Vì thế, cần phải nghiên cứu đề xuất các phƣơng pháp hiệu quả để có thể giải đƣợc các hệ thống phƣơng trình cỡ lớn. 1.2.2.3. Tính ổn định của thuật toán Một thuật toán gọi là ổn định nếu sai số tính toán (do máy tính làm tròn số) không bị khuếch đại trong quá trình tính. Ví dụ 1. 4. Công thức tính tích phân không sử dụng đƣợc Giả sử cần tính tích phân )1(1 1 0   ndxexI xn n . Tích phân từng phần: đặt u = xn thì du = nxn-1dx; đặt dv = ex-1dx thì v = ex-1. 18 Ta đƣợc: Ngoài ra ta có .3679.0 1 )1( 1 0 11 1 0 1    e xedxexI xx Từ đây ta thu đƣợc công thức truy hồi (qui nạp) tính In về mặt lý thuyết: Về mặt thực tế, công thức trên đây đƣợc thực hiện trên máy tính đã không cho kết quả mong muốn khi n lớn. Lập trình trên ngôn ngữ Pascal (chƣơng trình sử dụng kiểu số thực với độ chính xác gấp đôi), ta nhận đƣợc dãy giá trị tích phân từ I1 đến I25 nhƣ bảng kết quả sau (liệt kê theo từng hàng): 0.3679 0.2642 0.2073 0.1709 0.1455 0.1268 0.1124 0.1009 0.0916 0.0839 0.0774 0.0718 0.0669 0.0627 0.0590 0.0555 0.0572 -0.0295 1.5596 -30.1924 635.0403 -13969.8864 321308.3881 -7711400.3133 192785008.8325 Kết quả giảm dần từ 0.3679 (khi n = 1) đến 0.0555 (khi n = 16). Kết quả sau đó (các số in đậm) thay đổi thất thƣờng và giá trị tuyệt đối tăng rất nhanh. Điều này hoàn toàn không phù hợp với lý thuyết vì theo lý thuyết thì 0nI khi n do đó Hiện tƣợng kết quả tính toán nI nêu trên là sự không ổn định của thuật toán: sai số ban đầu khi tính I1 = 1/e  0.3679 đã bị khuyếch đại trong quá trình tính. Nguyên nhân: Thay vì I1 = 1/ e, ta thu đƣợc  11 ~ II , trong đó  là sai số. Giả sử các tính toán tiếp theo không mắc phải sai số. Với n = 2 ta đƣợc: Thu đƣợc 2 ~ I với sai số 2 ~ 22  II . Tƣơng tự, ở bƣớc thứ n thay cho giá trị đúng nI ta thu đƣợc giá trị gần đúng nI ~ với sai số ! ~ nII nn  . Do đó, dù  có bé thì khi n đủ lớn, sai số vẫn đủ lớn và ta không thể nhận đƣợc giá trị chấp nhận đƣợc là gần đúng cho nI . Vậy ta có thể kết luận rằng công thức tính tích phân In mặc dù rất đẹp mắt, nhƣng lại không sử dụng đƣợc trong tính toán thực tiễn. .1 1 1 1 0 11 0 1     n xnxn n nIdxexnexI .3679.0 ,2,1 1 1    I nnII nn . 1 1 0 1 0    n dxxI nn .22)21()(21 ~ 21 ~ 21112   IIIII 19 1.3. TỔNG QUAN VỀ NHỮNG CÁCH TIẾP CẬN DẠY HỌC THUẬT TOÁN 1.3.1. Dạy học thuật toán trong một số nội dung Toán học Judith Gal-Ezer & Orna Lichtenstein (1996) đã phát triển nghiên cứu của Donald E. Knuth (1980), khẳng định mối quan hệ mật thiết giữa tƣ duy thuật toán và tƣ duy Toán học, đồng thời đề xuất phƣơng pháp dạy học kiến thức về tập hợp trong Toán học dựa trên thuật toán và thông qua đó hình thành cho HS thuật toán. João F. Ferreira et al. (2011) cho rằng mặc dù các thuật toán tự nhiên chiếm một phần lớn trong Toán học nhƣng những kỹ năng cần thiết để trình bày một cách hệ thống và giải quyết các bài toán theo thuật toán không đƣợc thiết lập là một phần của giáo dục Toán học. Đặc biệt là logic, đó là trung tâm để phát triển thuật toán, hiếm khi đƣợc dạy một cách rõ ràng tại các cấp học trƣớc đại học và nó đƣợc coi là trừu tƣợng trong Toán học. Do đó, thuật toán không cần phải đƣợc giảng dạy nhƣ là một chủ đề độc lập. Từ nhận xét này, các tác giả đề nghị giới thiệu cho HS THPT các nguyên lý tính toán và kỹ thuật giải quyết các bài toán theo thuật toán nhờ hỗ trợ bởi logic tính toán. Hơn nữa các tác giả đã dùng các bài toán vui để truyền đạt các nguyên lý và dùng các công cụ phần mềm, phân tích Alloy và Netlogo để làm sinh động mô hình. 1.3.2. Dạy học thuật toán thông qua các câu đố và câu đố giống nhƣ trò chơi Đại diện cho các nghiên cứu về phương pháp câu đố và trò chơi trực quan, là Anany Levitin (2005). Tác giả đề nghị sử dụng rộng rãi các câu đố và các câu đố giống như trò chơi trong việc giảng dạy, phân tích thuật toán. Để minh họa cho ý tƣởng này, tác giả lấy ví dụ là những câu đố cổ điển của Toán học vui. Các ví dụ này minh họa tất cả các khía cạnh của phân tích thuật toán. Hơn nữa, tác giả đã nêu ra những thuận lợi trong việc sử dụng câu đố trong giảng dạy phân tích thuật toán là: - Các câu đố tác động tới cách nghĩ về thuật toán của HS bằng một mức độ khái quát hơn, tách rời giữa lập trình và các ngôn ngữ máy tính. - Các câu đố cho ta thấy các chiến lƣợc thiết kế thuật toán. Nó đƣợc xem nhƣ một công cụ giải quyết vấn đề rất hữu dụng ở những nơi cách xa Khoa học máy tính. - Giải câu đố giúp HS phát triển óc sáng tạo và kĩ năng giải quyết vấn đề . Đây là phẩm chất mà bất cứ nhà Khoa học máy tính tƣơng lai nào cũng nên cố gắng đạt đƣợc. 20 - Câu đố luôn luôn thu hút sự tham gia của HS hơn. Nó làm cho HS làm việc chăm chỉ hơn qua những vấn đề giao cho họ. Trong cách tiếp cận dạy học thuật toán này, Anany Levitin đặc biệt nhấn mạnh các tính chất quan trọng của thuật toán nhƣ tính bất biến và tính khả thi. 1.3.3. Dạy học thuật toán bằng phƣơng pháp trực quan hóa thuật toán Đại diện cho các nghiên cứu về phương pháp trực quan hóa thuật toán, là Sahar S. Shabanah et al. (2010). Theo các tác giả, cấu trúc dữ liệu và các thuật toán là các chủ đề nền tảng quan trọng trong giáo dục Khoa học máy tính. Tuy nhiên, chúng thƣờng rất phức tạp và khó hiểu. Vì vậy, cần một chiến lƣợc học tập mới, mang lại lợi ích từ trò chơi máy tính phổ biến và hứa hẹn giúp HS hiểu đƣợc các thuật toán tốt hơn. Giải pháp ở đây là thiết kế trò chơi máy tính để giúp HS hình dung đƣợc thuật toán. Để giảng dạy một thuật toán, một trò chơi giáo dục trên máy tính, đƣợc gọi là "trò chơi thuật toán", phải là một trò chơi mô phỏng hành vi của thuật toán một cách trực quan và biểu thị bằng đồ họa các đặc trƣng của cấu trúc dữ liệu của thuật toán. Nhóm tác giả đã trình bày các nội dung sau đây: - Duyệt lại lịch sử của trò chơi máy tính đƣợc sử dụng trong giáo dục và những chức năng, đặc điểm mà một trò chơi giáo dục phải đạt đƣợc. - Tham gia trò chơi giáo dục khuyến khích các hình thức hoạt động tích cực nhƣ quan sát, phản hồi, thay đổi, xây dựng và trình bày . - Sự trực quan hóa trò chơi thuật toán đảm bảo các đặc trƣng: Cuốn hút HS học thuật toán, tạo động lực cho HS vƣợt qua thử thách và kiến tạo kiến thức (hiểu thuật toán). - Các bƣớc phát triển một công cụ phát triển trò chơi để thỏa mãn những đặc điểm nêu trên. Để có thể thực hiện đƣợc phƣơng pháp trực quan hóa thuật toán thông qua trò chơi giáo dục của nhóm Sahar S. Shabanah, cần phải tạo ra đƣợc các trò chơi tƣơng ứng cho từng thuật toán từ các phần mềm công cụ phát triển trò chơi, và hiểu đƣợc những khái niệm cơ bản nhƣ “thuộc tính trò chơi”, các “mô-đun cơ bản của trò chơi” và các “yếu tố thiết kế trò chơi”. Phƣơng pháp trực quan trong dạy học thuật toán đƣợc nhóm Tomasz Müldner & Elhadi Shakshuki (2004) nâng lên ở mức độ cao hơn nhằm bồi dƣỡng các cấp độ trừu tƣợng trong tƣ duy thuật toán cho sinh viên ngành Khoa học máy tính. Điều này sẽ đƣợc giới thiệu kĩ hơn những nội dung tiếp theo. 1.3.4. Dạy học thuật toán theo hƣớng phát triển tƣ duy thuật toán Trong số hiếm những ngƣời nghiên cứu sâu về chủ đề dạy học thuật toán cho HS phổ thông có lẽ phải kể đến Vƣơng Dƣơng Minh (1996) với luận án ―Phát triển 21 tư duy thuật toán cho HS trong khi dạy học các hệ thống số ở trường phổ thông‖. Tác giả đã nghiên cứu PPDH thuật toán trên các hệ thống số ở trƣờng phổ thông. Trƣớc hết tác giả đƣa ra định nghĩa trực giác nhƣng chính xác về thuật toán nhƣ sau: “Thuật giải là một qui tắc chính xác và đơn trị 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 đối tượng sao cho sau một số hữu hạn thao tác đó ta thu được kết quả mong muốn”. Dựa trên định nghĩa này, các bài toán số học và các bài toán giải bằng phƣơng pháp số ở trƣờng phổ thông đƣợc tác giả chỉ ra các bƣớc đơn trị và xác định (thuật thoán) để giải quyết. Trong luận án và bài báo của mình, Vƣơng Dƣơng Minh (1990, 1996) đã đƣa ra hệ thống các tƣ tƣởng chủ đạo về phát triển tƣ duy thuật giải trong môn Toán nhƣ sau: (1) Rèn luyện cho HS các hoạt động tƣ duy thuật giải trong khi và nhằm vào thực hiện những yêu cầu Toán học. (2) Gợi động cơ và hƣớng đích cho các hoạt động tƣ duy thuật giải bao gồm: - Gợi động cơ và hƣớng đích mở đầu các hoạt động tƣ duy thuật giải; - Gợi động cơ và hƣớng đích trong khi tiến hành các hoạt động tƣ duy thuật giải. - Gợi động cơ kết thúc hoạt động tƣ duy thuật giải. (3) Truyền thụ cho HS những tri thức phƣơng pháp về tƣ duy thuật giải trong khi tổ chức, điều khiển tập luyện các hoạt động tƣ duy thuật giải. (4) Phân bậc các hoạt động. Bùi Văn Nghị, Vƣơng Dƣơng Minh, Nguyễn Anh Tuấn (2005) đã đơn giản hóa khái niệm thuật toán để tiệm cận với thuật toán giải bài toán trên máy tính nhƣ sau: ―Thuật toán được hiểu như một quy trình 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‖. Từ định nghĩa này, các tác giả nêu ra các đặc điểm của thuật toán, có thể đƣợc tóm tắt nhƣ sau: - Đó là một dãy hữu hạn các bƣớc sắp xếp theo một trình tự nhất định. - Mỗi bƣớc là một thao tác sơ cấp, có thể là một thuật toán đã biết. Các bƣớc rõ ràng, thao tác chính xác. - Có tính kết thúc và tính phổ dụng. Theo các tác giả, ―Tư duy thuật toán là cách suy nghĩ để nhận thức, để giải quyết vấn đề một cách có trình tự (sắp xếp lần lượt, thứ tự trước sau)‖. 22 Nguyễn Bá Kim (2009) đã trình bày khá rõ ràng một số vấn đề cơ bản về thuật giải1, về các qui tắc tựa thuật giải, và về rèn luyện tƣ duy thuật giải trong dạy học giải một số bài toán. Các qui tắc tựa thuật giải đƣợc xem là một loại tri thức phương pháp đặc biệt và hữu hiệu trong giải toán với ba cấp độ tăng dần (có thể xem chi tiết trong Nguyễn Bá Kim, 2009). Về khái niệm thuật giải và qui tắc tựa thuật giải: Nguyễn Bá Kim (2009) đƣa ra một phát biểu trực quan về thuật giải nhƣ sau: “Thuật giải theo nghĩa trực giác được hiểu là như một dãy hữu hạn những chỉ dẫn thực hiện một cách đơn trị, 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 của một lớp bài toán thành thông tin ra mô tả lời giải của lớp bài toán đó”. Theo tác giả, ngoài thuật giải, còn có những qui tắc tựa thuật giải và chúng rất có hiệu lực trong việc chỉ dẫn hành động và giải toán. ―Qui tắc tựa thuật giải được hiểu là một dãy hữu hạn những chỉ dẫn thực hiện 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 thông tin ra mô tả lời giải bài toán đó‖. Khác với thuật giải, qui tắc tựa thuật giải không đảm bảo chắc chắn sau một số hữu hạn bƣớc thì đem lại kết quả là lời giải của lớp bài toán; kết quả thực hiện sau mỗi chỉ dẫn có thể không đơn trị; và mỗi chỉ dẫn trong qui tắc có thể chƣa mô tả hành động một cách xác định. Về khái niệm tư duy thuật toán: Nguyễn Bá Kim (2009) gián tiếp nêu khái niệm tƣ duy thuật toán khi cho rằng việc phát triển tƣ duy thuật giải cho HS là nhằm rèn luyện cho HS 5 loại hoạt động sau đây: (i) Thực hiện những hoạt động theo một trình tự xác định phù hợp với một thuật giải cho trƣớc; (ii) Phân tích một hoạt động thành những hoạt động thành phần đƣợc thực hiện theo một trình tự xác định; (iii) Mô tả chính xác quá trình tiến hành một hoạt động; (iv) Khái quát hóa một hoạt động trên những đối tƣợng riêng lẻ thành một hoạt động trên một lớp đối tƣợng; (v) So sánh những con đƣờng khác nhau cùng thực hiện một công việc và phát hiện con đƣờng tối ƣu. Trong “Tiếp cận nhiều mặt vào hoạt động lập trình”, Lê Khắc Thành (2008) đã trình bày tiếp cận lập trình dựa trên phƣơng diện thuật toán. Theo tác giả, 5 loại hoạt 1 “Thuật toán” và “thuật giải” là hai cách dịch khác nhau của từ “algorithm”. Tuy nhiên một số nhà khoa học Việt Nam cho rằng “thuật giải” (hay “giải thuật”) là mở rộng của khái niệm “thuật toán” để chấp nhận tính gần tối ƣu (ví dụ thuật toán tham lam), tính gần đúng (ví dụ các thuật toán xấp xỉ) và đặc biệt là tính đa trị tại mỗi bƣớc thực hiện thuật toán (ví dụ giải thuật ngẫu nhiên và “qui tắc tựa thuật giải” trong giải toán). 23 động trên đây biểu thị mối quan hệ chặt chẽ giữa thuật toán và tƣ duy thuật toán. Trong đó, để phát triển tƣ duy thuật toán, tác giả cho rằng cần tập luyện cho HS những khả năng sau đây: (i) Thực hiện những hoạt động theo một trình tự xác định phù hợp với một thuật giải cho trƣớc; (ii) Mô tả chính xác quá trình tiến hành một hoạt động; (iii) Khái quát hóa một hoạt động trên những đối tƣợng riêng lẻ thành một hoạt động trên một lớp đối tƣợng; (iv) Cải tiến thuật giải để tiết kiệm thời gian chạy máy hoặc tiết kiệm bộ nhớ. Bên cạnh đó, tác giả đã chỉ ra các bƣớc xây dựng thuật toán và nhấn mạnh việc tìm nhiều thuật toán cho một bài toán; phân tích hoạt động thành những hoạt động thành phần và đánh giá thuật toán. Nhóm các tác giả trên thế giới nghiên cứu về dạy học phát triển tƣ duy thuật toán có thể kể đến Parsons (2006) và Gerald Futsche (2006). Parsons đã có một đề xuất rèn luyện tƣ duy thuật toán cho ngƣời học, trong khi không phát biểu tƣờng minh khái niệm về tƣ duy thuật toán. Gerald Futsche đã đề cập trực tiếp đến khái niệm tư duy thuật toán (Algorithmic Thinking). Theo Gerald Futsche, tƣ duy thuật toán là một trong những năng lực quan trọng nhất cần đạt đƣợc trong nền giáo dục Tin học, nó có thể phát triển độc lập từ việc học lập trình. Tác giả cho rằng: Tư duy thuật toán là sự kết nối các năng lực của tư duy theo cách nào đó để hiểu và xây dựng được thuật toán, bao gồm: (1) Năng lực phân tích bài toán đã cho. (2) Năng lực xác định tính chính xác của bài toán. (3) Năng lực tìm ra các thao tác cơ bản tương ứng với bài toán đã cho. (4) Năng lực xây dựng một thuật giải chính xác bằng cách sử dụng các thao tác cơ bản. (5) Năng lực tư duy về tất cả các trường hợp (bình thường và đặc biệt) có thể xảy ra của một bài toán. (6) Năng lực nâng cao hiệu quả của một thuật toán. Hai năng lực đầu tiên giúp HS thực hiện tốt nhiệm vụ “Xác định bài toán”. Các năng lực còn lại giúp HS hiểu và làm tốt nhiệm vụ “Mô tả thuật toán”. Trong đó, năng lực 3 và 4 đƣợc xem là những năng lực tìm ra các thao tác cơ bản để mô tả thuật giải bài toán, năng lực 5 và 6 đƣợc xem là những năng lực tƣ duy giúp HS xây dựng đƣợc một thuật toán đảm bảo tính đúng đắn và tính hiệu quả. Gerald đề nghị nên dùng các bài toán khó nhƣng phát biểu bài toán dễ hiểu để rèn luyện tƣ duy thuật toán cho ngƣơi học, và nhằm giúp HS hiểu đƣợc các khái 24 niệm cơ bản gắn kết với thuật toán nhƣ: Tính chính xác (correctness), tính dừng (termination), tính hiệu quả (efficiency/determinism), tính song song (parallelism). Để minh họa cho quan điểm của mình, Gerald Futsche đã chọn bài toán “Tìm đường trong mê cung‖. Yêu cầu của bài toán này là chỉ ra một thuật toán để theo đó một ngƣời đi qua đƣợc mê cung từ một lối vào (start) đến một lối ra (goal) đã cho nào đó. Hình 1. 1. Tìm cách đi qua mê cung Gerald Futsche phân tích quá trình tìm ra thuật toán đúng đắn thông qua quá trình tối ƣu hóa dần các thao tác cơ bản biểu thị “cách đi” thoát khỏi mê cung. Quá trình này có thể tóm tắt qua các bƣớc sau đây: Bước 1: Phân tích bài toán Bài toán đƣợc xác định 3 nhiệm vụ cần giải quyết, đó là: - Tìm đường đi ra khỏi mê cung, - Tìm đường đi xuyên qua mê cung, hoặc - Tìm đường đi đến một vị trí cụ thể nào đó bên trong mê cung Các nhiệm vụ trên dẫn đến một nhiệm vụ chung đó là: - Tìm đường đi từ vị trí A tới vị trí B (Nhiệm vụ chung) Bước 2: Xác định thao tác cơ bản thứ nhất: ―Đi theo hành lang bên trái‖. Tại bƣớc này, tác giả phân tích để chứng tỏ thao tác cơ bản “Đi theo hành lang bên trái” có thể là lời giải bài toán, nghĩa là cách đi đó có thể xuất phát từ lối vào và thoát khỏi mê cung bằng một lối ra xác định. Bên cạnh đó, tác giả cũng đƣa ra ví dụ về những mê cung mà cách đi theo hành lang bên trái không thể thoát khỏi mê cung vì đi vào đƣờng cụt, trong khi có đƣờng ra khỏi mê cung không bằng cách đi đó. Bước 3: Xác định thao tác cơ bản thứ hai : ―Đi theo hành lang ngẫu nhiên‖. Bƣớc 3 này nhằm giải quyết hạn chế của cách đi cứng nhắc bằng cách cho phép đi theo các hành lang một cách ngẫu nhiên. Tuy nhiên cách đi này lại quá tốn kém về mặt chi phí bộ nhớ và thời gian, do sự bùng nổ cấu hình tất cả các cách đi và có thể gặp phải bế tắc mới do nó không kiểm tra đƣợc hành lang đã đi qua và dẫn đến 25 đi quanh quẩn trong một dãy các hành lang khép kín. Bước 4: Xác định thao tác cơ bản thứ ba: ―Vừa đi vừa đánh dấu‖. Dựa trên ƣu điểm và hạn chế của cách đi theo hành lang ngẫu nhiên, tác giả đề xuất thuật toán “Cuộn len của Ariadne” nhằm đánh dấu những hành lang đã đi qua để tránh bị đi quẩn trong các chu trình trong mê cung. Thuật toán “Cuộn len của Ariadne” đã đƣa ra đƣợc lời giải đúng đắn (xem Hình 1. 2). Hình 1. 2. Vừa đi vừa đánh dấu Bản chất của thuật toán “Cuộn len của Ariadne” chính là bản chất của thuật toán Backtracking quen thuộc để giải quyết lớp bài toán “quay lui vét cạn”. Đó là những bài toán có đặc trƣng nghiệm gồm nhiều thành phần, mỗi thành phần có một tập các khả năng để chọn lựa. Tại mỗi bƣớc của thuật toán, một khả năng chƣa đƣợc xét sẽ đƣợc chọn là thành phần tiếp theo của nghiệm. Quá trình này sẽ dẫn đến hai khả năng: (1) Chọn đƣợc thành phần nghiệm cuối cùng và kết thúc thuật toán; (2) Bế tắc, tức là không thể chọn đƣợc thành phần thứ k tiếp theo của nghiệm. Khi đó thuật toán “quay lui” về thành phần nghiệm trƣớc đó, nghĩa là hủy bỏ thành phần thứ k-1 vừa chọn, chọn lại thành phần thứ k-1 khác trong tập các khả năng dành cho nó, trƣớc khi “đi tiếp” đến thành phần thứ k. Nếu tập khả năng của thành phần thứ k-1 đã đƣợc xem xét hết thì thuật toán lại cho phép “quay lui” về thành phần nghiệm thứ k-2 để chọn lại. Nhƣ vậy khả năng “quay lui” giúp thuật toán xem xét tất cả các khả năng cho các thành phần nghiệm ở các bƣớc trƣớc để tìm thành phần nghiệm ở bƣớc hiện tại. Do đó, thuật toán có thể chứng minh đƣợc tính vô nghiệm (ví dụ mê cung không có đƣờng ra) vì nó có thể xem xét mọi khả năng cho tất cả các thành phần của nghiệm. Cùng với Gerald Futschek, Luay Nakhleh (2012a, 2012b) đã đề xuất các bƣớc tƣ duy để tìm ra thuật giải cho một bài toán nhƣ Hình 1. 3. 26 Hình 1. 3. Thuật toán giải quyết vấn đề của Luay Nakhleh 1.3.5. Dạy học thuật toán theo các mức trừu tƣợng của tƣ duy thuật toán Một số khái niệm của Khoa học máy tính đã đƣợc các nhà khoa học nghiên cứu ở góc độ giáo dục, ví dụ nhƣ Hammond M., Rogers P. (2007) đã điều tra khái niệm máy tính đƣợc dạy nhƣ thế nào từ bậc tiểu học đến bậc trung học. Đặc biệt, công trình nghiên cứu của Jacob Perrennet (2005) và Jacob Perrennet et al. (2010) tập trung vào khái niệm thuật toán trong giáo dục đại học, giống nhƣ cách làm của nhóm Haberman B. & Averbuch H., Ginat D. (2005). Nhóm Tomasz Müldner & Elhadi Shakshuki (2004) đã đề xuất mô hình giải thích thuật toán gắn liền với các mức trừu tượng trong tư duy thuật toán để dạy học thuật toán cho riêng sinh viên ngành Khoa học máy tính. Theo các tác giả, thuật toán đƣợc giải thích ở các mức trừu tƣợng khác nhau theo chiều từ trên xuống dƣới và gắn liền với một xu hƣớng lập trình cụ thể (lập trình hướng đối tượng). Với kiểu lập trình này, có hai mức trừu tƣợng chính trong tƣ duy thuật toán: mức đặc tả đối Sai Hoànthành (Done) Tốt (Good) (1) Chính xác (correct)? (2) Hiệu quả (efficient)? (3) Dễ dàng thực thi (easy to implement)? (4) ....? (1) Chính xác (correct)? (2) Hiệu quả (efficient)? (3) ...? Hiểu bài toán (Understand the problem) Thực hiện thuật toán (Implement the algorithm) Tốt (Good) Đúng Sai Đúng Thiết kế thuật toán (Design an algorithm) 27 tượng và mức đặc tả các hành vi của đối tượng. Ở mức đặc tả đối tƣợng, ngƣời học phải hiểu và định nghĩa đƣợc lớp đối tƣợng, bao gồm việc mô tả các vùng dữ liệu và mô tả các hành vi của đối tƣợng bằng các tên hàm trong dạng khai báo tổng quát. Ở mức đặc tả hành vi của đối tƣợng, ngƣời học phải hiểu và định nghĩa đƣợc các hàm của lớp đối tƣợng. Quá trình định nghĩa những hàm này có thể phát sinh những hàm mới để chi tiết hóa những thao tác nhỏ trong từng hành vi của đối tƣợng. Do đó, giữa hai mức này, có những mức trừu tƣợng trung gian. Nhƣ vậy, các mức trừu tượng trong tư duy thuật toán ở đây có thể được hiểu là các mức tư duy trong việc hiểu và mô tả từng mức trừu tượng của thuật toán. Nhóm của Jacob Perrenet (2005) cho rằng Khoa học máy tính có thể đƣợc mô tả nhƣ một khoa học trừu tƣợng và trừu tƣợng đƣợc coi là một nguyên tắc cơ bản và cần thiết trong giải quyết bài toán Khoa học máy tính và phát triển phần mềm. Do đó, chìa khóa cho sự thành công trong tính toán nằm trong khả năng thực hiện những tư duy trừu tượng (abstract thinking) và thể hiện kỹ năng trừu tượng (abstraction skills). Jacob Perrenet et al. (2010) đã định nghĩa: “Trừu tượng là mang đến một cấp độ tổng hợp cao hơn từ một cách nhìn (phát biểu, mô hình, luận thuyết) để có thể áp dụng chung đối với nhiều trường hợp hơn”. Định nghĩa này đƣợc chấp nhận bởi các nhân viên từ nhiều ngành kỹ thuật, bao gồm cả ngành Khoa học máy tính. Nó đƣợc sử dụng để mô tả các cấp độ trừu tƣợng của tƣ duy và hành động trong một loạt các lĩnh vực khác nhau. Từ định nghĩa này, nhóm Jacob Perrenet et al. (2010) đề xuất bốn cấp độ trừu tượng trong tư duy thuật toán của sinh viên tƣơng ứng với bốn cấp độ trừu tƣợng của thuật toán nhƣ sau:  Cấp độ thực hiện: thuật toán là một hoạt động cụ thể trên một máy tính đặc biệt cụ thể, thời gian thực hiện của nó đƣợc xác định bởi máy tính.  Cấp độ chương trình: thuật toán là một quá trình, mô tả bởi một ngôn ngữ lập trình có thể thực thi, thời gian thực hiện phụ thuộc vào dữ liệu đầu vào.  Cấp độ đối tượng: thuật toán không liên kết với một ngôn ngữ lập trình cụ thể, nó có thể đƣợc xem nhƣ một đối tƣợng (so với quá trình). Trong khi xây dựng cấu trúc dữ liệu và các thuộc tính bất biến đƣợc sử dụng, các thuộc tính nhƣ tính dừng và “đơn thể” (module thuật toán) có liên quan, thời gian thực hiện thuật toán đƣợc xét trong thuật toán là hàm của dữ liệu đầu vào.  Cấp độ bài toán: thuật toán có thể đƣợc xem nhƣ một hộp đen; Ở góc độ “cho một bài toán, kiểu thuật toán nào là phù hợp với nó?” thì các bài toán có thể phân loại bằng các thuật toán phù hợp, mỗi bài toán có một độ phức tạp riêng. 28 BÌNH LUẬN Phƣơng pháp sử dụng thuật toán để dạy một số nội dung của môn Toán nhƣ ý kiến của nhóm João F. Ferreira et al. (2011) có lẽ không phù hợp với tinh thần giảm tải kiến thức cho phổ thông. Hơn nữa nó không nhấn mạnh vào việc tìm ra phƣơng pháp riêng để dạy học thuật toán cho HS phổ thông. Phƣơng pháp sử dụng câu đố và những câu đố giống nhƣ trò chơi của Anany Levitin (2005) là một phƣơng pháp hay, vì nó có thể tạo ra cho HS sự hứng thú khi học thuật toán. Song những loại câu đố đó thƣờng khó, không phù hợp với nội dung dạy học những thuật toán cơ bản ở trƣờng phổ thông Việt Nam. Phƣơng pháp trực quan hóa thuật toán tuy là một ý tƣởng tuyệt vời trong việc cuốn hút HS học thuật toán một cách tự nhiên và cũng rèn luyện cho HS các hoạt động tích cực trong học tập. Tuy nhiên nó lại không thành công nhiều trong việc rèn luyện tƣ duy trừu tƣợng. Phƣơng pháp trực quan hóa thuật toán bằng mô hình giải thích thuật toán - AE của Tomasz Müldner & Elhadi Shakshuki (2004) là một cách rất tốt để giúp ngƣời học hiểu đƣợc những tính chất nâng cao của thuật toán, tuy nhiên phƣơng pháp này cũng gặp phải những khó khăn về việc thiết kế phần mềm đồ họa để mô phỏng thuật toán. Có thể nói rằng quan điểm về những năng lực tƣ duy thuật toán của Gerald Futsche (2006) và những hoạt động rèn luyện tƣ duy giải thuật của Nguyễn Bá Kim (2009) và Lê Khắc Thành (2009) là thống nhất với nhau, hỗ trợ bổ sung cho nhau. Nhƣng có lẽ không nên chỉ sử dụng những bài toán khó để rèn luyện tƣ duy thuật toán cho HS. Bốn cấp độ trừu tƣợng trong tƣ duy thuật toán (cấp độ thực hiện, cấp độ chương trình, cấp độ đối tượng, và cấp độ bài toán) mà nhóm Jacob Perrenet (2010) đã chỉ ra khá thuyết phục. Song, trong nghiên cứu của mình, các tác giả không chỉ ra rõ ràng một “khung công việc” cụ thể để rèn luyện cho sinh viên các cấp độ trừu tƣợng này khi dạy học thuật toán. Hơn nữa đây là những đòi hỏi cao về mặt tƣ duy trừu tƣợng đối với sin... Bob 0.23 0.38 0.23 0.15 - 13 Claire 0.20 0.20 0.20 0.20 0.20 20 David 0.19 0.31 0.25 0.19 0.06 16 Elaine - - - - - 0 Total Received 0.91 1.18 0.89 0.68 0.33 4 Bước 2: Tính số điểm WebPA cho mỗi HS - Vì số HS không tham gia đánh giá là m = 1, số HS tham gia đánh giá là n = 5, nên theo công thức (3), ta có nhân tố phụ là: ff = n/m = 5/4 = 1.25; Nhân tố phụ trong trƣờng hợp không có HS tham gia đánh giá nhằm thƣởng thêm điểm cho các HS tham gia đánh giá. - 29 - - Vì m < n nên công thức (4) sẽ đƣợc bỏ qua. Theo công thức (5) ta nhận đƣợc tổng điểm của các HS nhƣ sau: Alice = 0.91  1.25 = 1.13 Bob = 1.18  1.25 = 1.48 Claire = 0.89  1.25 = 1.12 David = 0.68  1.25 = 0.86 Elaine = 0.33  1.25 = 0.42 Có thể kiểm tra nhanh để thấy tổng điểm thực của tất cả các HS phải bằng số HS trong nhóm, tức là bằng 5. Nếu tổng này nhỏ hơn 5 thì có thể do việc làm tròn đến 2 chữ số thập phân chƣa chính xác. Bước 3: Tính điểm cuối cùng cho từng HS Giả sử GV đánh giá nhóm này đạt p = 80% công việc đã giao. a) Nếu GV không sử dụng thêm trọng số để cho điểm thì điểm phần trăm của mỗi HS đƣợc tính theo công thức (8) nhƣ sau: Alice = 1.13  80 = 90.40% Bob = 1.48  80 = 118.28% = 100% (không cho điểm quá 100) Claire = 1.12  80 = 89.51% David = 0.86  80 = 68.42% Elaine = 0.42  80 = 33.39% b) Nếu GV sử dụng trọng số để cho điểm thì theo công thức (6), điểm cố định đƣợc thƣởng cho mọi HS trong nhóm là fix = 40% (là một nửa của p = 80%). Vậy điểm phần trăm của mỗi HS đƣợc tính theo công thức (7) nhƣ sau: Alice = 40 + (1.13  40) = 85.20% Bob = 40  (1.14  40) = 99.14% Claire = 40 + (1.12  40) = 84.75% David = 40 + (0.86  40) = 74.21% Elaine = 40 + (0.42  40) = 56.70% Cuối cùng, giả sử GV xác định điểm phạt cho HS không tham gia đánh giá là plt = 20% thì điểm cuối cùng của Elaine đƣợc tính theo công thức (9) là: Nếu không dùng trọng số: Elaine = 33.39 - 20 = 13.39% Nếu có dùng trọng số: Elaine = 56.70 - 20 = 36.70% Bước 4: Trả kết quả điểm cuối cùng cho từng học sinh Theo các kết quả trên đây, điểm cuối cùng công bố cho các HS theo thang điểm 10 có thể chọn từ một trong hai cột của Bảng PL7.3 sau đây: - 30 - Bảng PL7. 3. Điểm webPA cuối cùng công bố cho học sinh Trọng số 0% của 80% Trọng số 50% của 80% Alice 9.04 8.52 Bob 10.00 9.91 Claire 8.95 8.48 David 6.84 7.42 Elaine 1.34 3.67 Quan sát Bảng PL7.3 ta thấy, trong cả hai trƣờng hợp dùng trọng số và không dùng trọng số, tƣơng quan điểm của các HS đƣợc đánh giá nhất quán từ bƣớc đầu tiên đến bƣớc cuối cùng. Nghĩa là có thể xếp loại các HS về mức độ hoàn thành nhiệm vụ đƣợc giao theo thứ tự giảm dần nhƣ sau: Bob  Alice  Claire  David  Elain. Về ý nghĩa của các tham số trong thuật toán, ta có thể tóm tắt nhƣ sau: Nhân tố phụ nhằm thƣởng thêm điểm cho các HS gánh vác công việc của HS không tham gia đánh giá. Bên cạnh đó, điểm phạt hiển nhiên có tác dụng trừ điểm HS không tham gia đánh giá. Trọng số thƣờng đƣợc sử dụng để phản ánh sự hƣởng lợi từ việc tham gia nhóm học tập. Ví dụ nhƣ trƣờng hợp Elaine, tuy không tham gia đánh giá, nhƣng nhờ có trọng số phụ mà điểm của Elain là 3.67 (cao hơn 1.34 khi không có trọng số). Hƣớng dẫn tự đánh giá và đánh giá ngang hàng Để việc cho điểm thƣởng (đánh giá và tự đánh giá) diễn ra bình đẳng, công bằng và chính xác, trƣớc đó GV đã đƣa ra các qui định về cách cho điểm, gọi là tiêu chuẩn đánh giá (standard assessment/ assessment criteria) thông qua việc đối chiếu với một hệ thống các mẫu hỏi (giống nhƣ "barem" cho điểm). Chú ý: Thuật toán webPA sử dụng các tính toán WebPA mở rộng ở bƣớc 3.1 thì đƣợc gọi là thuật toán webPA mở rộng. - 31 - PHỤ LỤC 8: CÔNG CỤ THỰC NGHIỆM SƢ PHẠM 8.1 Phiếu khảo sát Dƣới đây là phiếu khảo sát thực nghiệm sƣ phạm. Trƣớc khi phát phiếu này cho HS, các dòng tô đậm đƣợc loại bỏ. Các dòng tô đậm chỉ dùng cho nhà nghiên cứu. Phiếu khảo sát bao gồm 20 câu. Các câu hỏi của phiếu thể hiện 6 thang đo chính sau đây: (1) Thang đo 1 (NQ): Việc thực hiện nội qui lên lớp của GV: Câu 1 (1 câu hỏi). (2) Thang đo 2 (TĐ): Thái độ quan tâm đến HS: Câu 2 (1 câu hỏi). (3) Thang đo 3 (NVSP): Nghiệp vụ sƣ phạm: Câu 3, 4, 5 (3 câu hỏi). (4) Thang đo 4a (PPDH1): PPDH thông thƣờng: Từ câu 6 đến câu 9 (4 câu hỏi). (5) Thang đo 4b (PPDH2): PPDH đặc thù đối với từng kiểu tiếp cận dạy học thuật toán. Từ câu 10 đến câu 15 (6 câu hỏi). (6) Thang đo 4c (PPDH): PPDH chung. Từ câu 6 đến câu 15 (10 câu hỏi). (7) Thang đo 5 (KTDG): Hoạt động kiểm tra đánh giá. Từ câu 16 đến 19 (4 câu hỏi). (8) Thang đo 6 (TC): Thái độ suy nghĩ chủ quan của HS. Câu 20 (1 câu hỏi). Số lƣợng câu hỏi trong các thang đo quan trọng nhiều hơn các thang đo phụ. Phiếu khảo sát tập trung vào ba thang đo: thang đo số 4a (PPDH) với 4 câu hỏi; thang đo 4b (PPDH thuật toán) với số câu hỏi nhiều nhất (6 câu hỏi), và thang đo 5 (hoạt động kiểm tra đánh giá) với 4 câu hỏi. Các thang đo còn lại là các thang đo phụ có số lƣợng câu hỏi rất ít nhằm bổ sung thêm thông tin. Tất cả các câu hỏi này đƣợc sử dụng chung cho tất cả các đợt thực nghiệm. Riêng thang đo về phƣơng pháp dạy học thuật toán có 6 câu hỏi để trống trong phiếu khảo sát dƣới đây (gồm các câu 10, 11, 12, 13, 14, 15) vì chúng sẽ đƣợc thay đổi theo từng đợt thực nghiệm. 8.1.1. Nội dung phiếu khảo sát PHIẾU LẤY Ý KIẾN CỦA HỌC SINH VỀ VIỆC GIẢNG DẠY CỦA GIÁO VIÊN Để hoàn chỉnh phần thực nghiệm trong nghiên cứu giáo dục của chúng tôi nhằm nâng cao hiệu quả dạy học thuật toán, tôi tiến hành lấy ý kiến phản hồi của các bạn học sinh sau khi các bạn đƣợc học một số tiết về thuật toán theo phƣơng pháp tiếp cận mới. Tôi rất mong các bạn học sinh cung cấp các thông tin phản hồi theo mẫu điều tra ý kiến ngƣời học dƣới đây: Ngƣời dạy: ............................................ Tên bài: ........... ..................................... Trƣờng thực tập: ............................... Lớp: ............... Họ tên học sinh: (Dòng này các em có thể bỏ trống): Ngày khảo sát: ...................Năm học ......... - ............ - 32 - Tô đậm các số tƣơng ứng trong bảng câu hỏi dƣới đây theo suy nghĩ của bạn về từng vấn đề trong quá trình học môn học trên, theo thang đánh giá sau: 1 = không đồng ý 2 = phân vân 3 = đồng ý 4 = hoàn toàn đồng ý (Ghi chú: 1 là mức đánh giá thấp nhất, 4 là mức đánh giá cao nhất) Các vấn đề cần trả lời Tô đậm điểm phù hợp nhất Các hoạt động giảng dạy của GV Thang đo 1: Việc thực hiện nội quy lên lớp     1 Giáo viên thực hiện nghiêm túc giờ lên lớp     Thang đo 2: Thái độ quan tâm đến HS 2 Giáo viên nhiệt tình giảng dạy và có trách nhiệm     Thang đo 3: Nghiệp vụ sƣ phạm 3 Giáo viên có cách truyền đạt rõ ràng dễ hiểu.     4 Tiết học có đầy đủ các bƣớc: kiểm tra đầu giờ, dạy nội dung bài mới, củng cố và giao bài tập về nhà.     5 Giáo viên luôn phân bổ và sử dụng thời gian trên lớp một cách hợp lý và hiệu quả.     Thang đo 4: Phƣơng pháp dạy học 6 Để học sinh hứng thú với bài học mới, giáo viên thƣờng mở đầu bằng các ví dụ thực tế, hoặc gợi mở từ những kiến thức đã học.     7 Bài học dễ theo dõi vì có hệ thống, có nội dung đƣợc nhấn mạnh là trọng tâm.     8 Giáo viên lắng nghe và góp ý sửa chữa cách diễn đạt của học sinh khi phát biểu hoặc trao đổi trong giờ học.     9 Có tổ chức cho lớp hoạt động theo nhóm tham gia đóng góp, xây dựng bài, cuối cùng báo cáo lại trƣớc lớp.     10     11     12     13     14     15     Các hoạt động kiểm tra đánh giá của GV Thang đo 5: Hoạt động kiểm tra đánh giá 16 Có hình thức khuyến khích học sinh tự đánh giá     - 33 - 17 Bài kiểm tra có đầy đủ yêu cầu dễ và khó     18 Bài tập nhóm và bài kiểm tra không vƣợt quá yêu cầu kiến thức đã học     19 Kết quả học tập đƣợc đánh giá chính xác, công bằng.     Cảm nhận của HS Thang đo 6: Thái độ, suy nghĩ chủ quan của học sinh 20 Em thực sự hứng thú với các giờ học của bài này. Sau giờ học cái mà em thu đƣợc không chỉ có kiến thức mà còn là phƣơng pháp học tập hiệu quả     Chân thành cảm ơn sự đóng góp ý kiến của các em học sinh ! 8.1.2. Câu hỏi của thực nghiệm 1: Dạy học thuật toán theo phƣơng pháp làm mịn dần Trong 20 câu hỏi của phiếu khảo sát nhƣ trình bày trên đây, 6 câu hỏi (từ câu 10 đến câu 15) để trống dùng để đánh giá PPDH thuật toán theo cách tiếp cận làm mịn dần. Sáu câu hỏi này nhƣ sau: Câu 10) Ý tƣởng thuật toán luôn tính đến việc sử dụng một thuật toán nào đó đƣợc giả định là đã biết. Câu 11) Việc sử dụng “gói thuật toán” giúp cho biểu diễn thuật toán tổng thể đơn giản dễ hiểu hơn. Câu 12) Việc xây dựng từng gói thuật toán con đơn giản hơn là xây dựng toàn bộ thuật toán không sử dụng các gói thuật toán con. Câu 13) Các gói thuật toán con có thể xây dựng trƣớc hoặc xây dựng sau thuật toán chính. Câu 14) Nhờ có ý tƣởng đóng gói và mở gói thuật toán con nên thuật toán chính đầy đủ và chi tiết dễ giải thích hơn. Câu 15) Cách xây dựng thuật toán mà em đƣợc học giúp em định hình cách suy nghĩ khi giải quyết một bài toán. 8.1.2. Câu hỏi của thực nghiệm 2: Dạy học thuật toán theo kĩ thuật tinh chế Trong phiếu thực nghiệm đợt thứ hai, 6 câu hỏi (từ câu 10 đến câu 15) để trống dùng để đánh giá PPDH thuật toán theo kĩ thuật tinh chế nhƣ sau: Câu 10) Ý tƣởng thuật toán đƣợc phát biểu theo nhiều các khác nhau, cách sau dựa vào cách trƣớc đó. Câu 11) Thuật toán đƣợc biểu diễn theo nhiều các khác nhau, cách sau dựa vào cách trƣớc đó. Câu 12) Thao tác gán là thao tác nhỏ nhất không thể phân chia thành các thao tác nhỏ hơn, nhƣng thao tác đổi chỗ thì có thể phân chia đƣợc thành các thao tác nhỏ hơn. - 34 - Câu 13) Việc sử dụng nhiều mô tả thuật toán tƣơng đƣơng giúp em hiểu đƣợc thuật toán hơn. Câu 14) Có thể xây dựng một thuật toán mà mỗi bƣớc của nó thực hiện một công việc nào đó, công việc này có thể mô tả chi tiết hơn bằng các bƣớc bên trong. Câu 15) Quá trình xây dựng thuật toán mà em đƣợc học giúp em định hình đƣợc quá trình xây dựng một thuật toán sao cho càng ngày càng chi tiết đƣợc thuật toán. 8.1.3. Câu hỏi của thực nghiệm 3: Dạy học thuật toán theo phƣơng pháp thao tác hóa Thực nghiệm 3 không đƣợc trình bày trong chƣơng 4 của luận án. Trong phiếu thực nghiệm thứ ba này, 6 câu hỏi (từ câu 10 đến câu 15) để trống dùng để đánh giá PPDH thuật toán theo phƣơng pháp thao tác hóa nhƣ sau: Câu 10) Giáo viên có sử dụng một số khái niệm mới không có trong SGK, nhƣng các khái niệm này giúp cho việc hiểu thuật toán dễ dàng hơn. Câu 11) Giáo viên có sử dụng những phiếu học tập, và việc thực hiện các phiếu học tập này là quá trình hình thành dần thuật toán ngày một rõ ràng hơn. Câu 12) Ba loại thao tác đƣợc sử dụng trong xây dựng thuật toán (thao tác cơ sở, thao tác cơ bản và thao tác tổng hợp) giúp cho việc xây dựng thuật toán rõ ràng hơn. Câu 13) Các thao tác cơ sở chung (gán, kiểm tra, nhập, xuất, và chuyển) giúp ta định hƣớng xây dựng các thuật toán đơn giản chỉ bằng cách sử dụng các thac tác này, ví dụ nhƣ xây dựng các thuật toán tính giá trị một đa thức, tính diện tích một tam giác, kiểm tra ba số thực cho trƣớc có tạo hành ba cạnh của một tam giác hay không. Câu 14) Thao tác cơ bản đƣợc xây dựng từ thao tác cơ sở, ví dụ thao tác đổi chỗ là thao tác cơ bản. Điều này giúp cho việc mô tả thuật toán trở nên ngắn gọn hơn. Câu 15) Thao tác tổng hợp là loại thao tác khó, nhƣng có thể giúp xây dựng thuật toán để giải quyết các bài toán phức tạp một cách dễ dàng hơn. 8.2. Bài tập nhóm Bài tập nhóm đƣợc đánh giá dựa trên kiểu tự đánh giá và đánh giá ngang hàng. GV là ngƣời quyết định điểm cuối cùng của từng thành viên trong nhóm theo thuật toán WebPA (xem Phụ lục 7). Thang đo về các cấp độ tƣ duy thuật toán đƣợc xác định nhờ qui tắc mã hóa và qui đổi điểm đƣợc nêu rỏ ở Chƣơng 4. Dƣới đây là bài tập nhóm của các đợt thực nghiệm. 8.2.1. Bài tập nhóm của thực nghiệm 1 Thực nghiệm sƣ phạm 1 nhằm đánh giá sự phát triển tƣ duy thuật toán cũng nhƣ hiệu quả học tập thuật toán của HS sau khi đƣợc dạy học thuật toán theo phương pháp làm mịn dần. Các nhóm HS ở đợt thực nghiệm 1 đƣợc giao thực hiện duy nhất một bài tập sau đây: - 35 - Hãy xây dựng thuật toán tìm các số nguyên nguyên tố trong đoạn [a, b] nào đó, với giá trị của a và b đƣợc cho trƣớc và 1  a < b  106. 8.2.2. Bài tập nhóm của thực nghiệm 2 Thực nghiệm sƣ phạm 2 nhằm đánh giá sự phát triển tƣ duy thuật toán cũng nhƣ hiệu quả học tập thuật toán của HS sau khi đƣợc dạy học thuật toán theo kĩ thuật tinh chế. Các nhóm HS ở đợt thực nghiệm 2 đƣợc giao thực hiện duy nhất một bài tập sau đây: Cho hai dãy sau đây: - Dãy (a) gồm n phần tử, trong đó ai là tên HS thứ i trong lớp; i = 1, 2, ..., n. - Dãy (b) gồm n phần tử, trong đó bi là điểm kiểm tra môn Toán của HS có tên xác định bởi ai trong lớp; i = 1, 2, ..., n. Giả thiết 20  n  50. Hãy xây dựng thuật toán nhập các danh sách (a) và (b), sau đó đƣa ra danh sách gồm 10 HS trong lớp có điểm kiểm tra môn Toán cao nhất. 8.2.2. Bài tập nhóm của thực nghiệm 3 Thực nghiệm sƣ phạm 3 nhằm đánh giá sự phát triển tƣ duy thuật toán cũng nhƣ hiệu quả học tập thuật toán của HS sau khi đƣợc dạy học thuật toán theo phương pháp thao tác hóa. Đây là một thực nghiệm đặc biệt: Các lớp đối chứng không đƣợc học về các loại thac tác sơ cấp, cơ bản, và tổng hợp, do đó bài tập nhóm của các lớp thực nghiệm khác với bài tập nhóm của các lớp đối chứng , cụ thể nhƣ sau: 8.2.2.1. Bài tập nhóm đối với các lớp thực nghiệm CÂU HỎI VÀ BÀI TẬP Bài 1. Thao tác cơ bản A. là thao tác nhỏ nhất, gồm có các thao tác cơ sở B. là thao tác đƣợc xây dựng trên các thao tác cơ sở, mô tả thuật toán giải quyết một bài toán độc lập. C. thƣờng đƣợc “đóng gói” thành một thao tác mới để sử dụng nhƣ một thao tác cơ sở D. giúp cho việc giải quyết bài toán trở nên rõ ràng dễ hiểu hơn. Hãy chỉ ra phƣơng án ghép sai. Bài 2. Thao tác tổng hợp A. là thao tác mà trong đó có ít nhất một thao tác cơ bản. B. là thao tác chỉ gồm có các thao tác cơ bản mà không có thao tác cơ sở C. là thao tác đƣợc xây dựng trên các thao tác cơ bản và/hoặc từ chính các thao tác tổng hợp khác đã biết. D. là thao tác đƣợc xây dựng trên các thao tác tổng hợp đã đƣợc xây dựng trƣớc đó. Hãy chỉ ra phƣơng án sai - 36 - Bài 3. Hãy điền vào bảng các thao tác và các chỉ dẫn còn thiếu trong thuật toán kiểm tra tính nguyên tố của số nguyên dƣơng N dƣới đây: STT Thao tác Thuật toán Bắt đầu thuật toán chính Input: n Output: “n là số nguyên tố‖ hoặc ― n không là số nguyên tố‖ 1 Nhập Bước 1: .................................... 2 Bước 2: N = 1 thì thông báo N không nguyên tố rồi kết thúc 3 Bước 3: Nếu N < 4 thì thông báo ....; 4 Bước 4: i ← 2; 5 Bước 5: i >  N thì thông báo .....; 6 Bước 6: Nếu N chia hết cho i thì ....; 7 Bước 7: ....................................... Kết thúc thuật toán chính Bài 4. Hãy điền vào chỗ chấm để hoàn chỉnh thuật toán Chuyển max về đầu dãy (ai, a2, , an) dƣới đây STT Thao tác Thuật toán Bắt đầu thủ tục Chuyển max (ai, a2, , an) Input: ai, a2, , an Output: ai, a2, , an trong đó ai là phần tử lớn nhất 1 Bước 1: k  i; 2 . Bước 2: ..................; 3 . Bước 3: Nếu aj > ak thì k j; 4 Bước 4: Nếu ............thì thực hiện Bƣớc 6; 5 Bước 5: Tăng ...........và quay lại ............; 6 Bước 6: Nếu k ≠ i thì .......................; Kết thúc thủ tục Chuyển max (ai, a2, , an); Bài 5. Sử dụng kết quả ở Bài 4, hãy điền chỗ chấm để hoàn chỉnh thuật toán sắp xếp một dãy số gồm n số nguyên a1, a2, , an theo thứ tự không tăng: STT Thao tác Thuật toán Bắt đầu thuật toán chính Input: n, a1, a2, , an Output: a1, a2, , an đƣợc sắp xếp không tăng 1 Bước 1: i  1; 2 Bước 2: Chuyển max (ai, a2, , an); - 37 - 3 Bước 2.1: k  i; 4 Bước 2.2: ...............; 5 Bước 2.3: Nếu aj < ak thì .. 6 Bước 2.4: Nếu ....... thì thực hiện Bƣớc 2.6; 7 Bước 2.5: Tăng ....... và quay lại Bƣớc 2.3; 8 Bước 2.6: Nếu k ≠ i thì .; 9 Bước 3: Nếu ..... thì i  i + 1 và ............; 10 Bước 4: In ra dãy (a); 8.2.2.2. Bài tập nhóm đối với các lớp đối chứng BÀI TẬP Bài 1. Hãy sắp xếp lại các dòng lệnh sau đây theo từng bƣớc để thu đƣợc một mô tả thuật toán đúng đắn sắp xếp tăng dần dãy (a) = (ai, a2, , an), đồng thời điền vào chỗ trống tên các bƣớc cần thiết. 1) Nhập n và nhập a1, a2, , an; 2) i  1; 3) j  i + 1; 4) Nếu j ≥ n thì thực hiện bƣớc ... ; 5) Tăng j j + 1 và quay lại bƣớc ...; 6) k  i; 7) Nếu k ≠ i thì Doicho(ak, ai) và thực hiện bƣớc .... 8) Nếu i < n1 thì i  i + 1 rồi quay lại bƣớc .... 9) Nếu aj < ak thì gán k  j; 10) In ra dãy a1, a2, , an và Kết thúc thuật toán Bài 2. Để sắp xếp không tăng dãy n số nguyên, một học sinh đã viết thuật toán nhƣ sau: Bước 1: Nhập n và nhập ai, a2, , an Bước 2: i  1; Bước 3: Tìm k là vị trí của phần tử lớn nhất trong dãy từ phần tử ở vị trí i đến phần tử ở vị trí cuối cùng của dãy (a) bằng lệnh: k  VitriMax(ai, a2, , an); Bước 4: Nếu k ≠ i thì Doicho(ak, ai); Bước 5: Nếu i < n 1 thì i i + 1 rồi quay lại bƣớc 3 Bước 6: In ra dãy ai, a2, , an và Kết thúc thuật toán. 1) Hãy biểu thị chi tiết hơn chỉ dẫn đƣợc viết là Doicho(ak, ai) ở trong thuật toán. 2) Hãy biểu thị chi tiết hơn chỉ dẫn đƣợc viết là VitriMax(ai, a2, , an) ở trong thuật toán - 38 - 8.3. Bài kiểm tra Nhƣ đã đƣợc giải thích trong chƣơng 4, đề kiểm tra gồm 3 bài tập, bài 1 có vai trò nhƣ thang đo cấp độ thực hiện, bài 2 có vai trò nhƣ thang đo cấp độ chuyển giao, và bài 3 có vai trò nhƣ thang đo cấp độ thiết kế. 8.3.1. Bài kiểm tra của thực nghiệm 1 Bài kiểm tra của thực nghiệm 1 có nội dung nhƣ sau: Đề kiểm tra (Thời gian làm bài 60 phút) Bài 1. Hãy xem xét thuật toán dƣới đây: Bước 1. Nhập p; Bước 2. Khởi tạo i  1; d  1; Bước 3. Nếu p mod i = 0 thì d  d + 1; Bước 4. i  i + 1; Bước 5. Nếu i < p div 2 thì quay về bƣớc 3, ngƣợc lại thì thực hiện bƣớc 6. Bước 6. Nếu d = p thì gán ok  true, ngƣợc lại, gán ok  false; Bước 7. Kết thúc. Hãy cho biết giá trị của biến ok (bằng true hay false) trong các trƣờng hợp p đƣợc nhập các giá trị sau đây: (A) p = 6 (B) p = 19 (C) p = 23 (D) p = 28 Bài 2. Thuật toán dƣới đây kiểm tra xem một dãy (a) gồm n số nguyên đã đƣợc sắp xếp tăng dần hay chƣa. Tuy nhiên, trong thuật toán có một số chỗ còn khuyết (kí hiệu là dấu hỏi chấm kèm theo số thứ tự). Hãy điền vào những chỗ khuyết đó các chỉ thị cần thiết để thu đƣợc thuật toán đầy đủ. Bước 1. Nhập số nguyên n và dãy (a) gồm n số nguyên dƣơng a1, a2, ..., an; Bước 2. Khởi tạo t  1; i  ?1; Bước 3. Nếu ai > ai+1 thì t  0; Bước 4. i  ?2; Bước 5. Nếu i < ?3 thì quay về bƣớc 3, ngƣợc lại, thực hiện tiếp bƣớc 6; Bước 6. Nếu t = 1 thì thông báo dãy (a) vừa nhập là dãy đã đƣợc sắp xếp tăng dần; ngƣợc lại, thông báo ?4; Bước 7. Kết thúc. Bài 3. Cho dãy (a) gồm n số nguyên dƣơng a1, a2, ..., an. Hãy xây dựng thuật toán sắp xếp tăng dần các phần tử ở nửa bên trái của dãy (a), từ phần tử thứ nhất đến phần tử thứ k = [n/2], các phần tử còn lại giữ nguyên. - 39 - 8.3.2. Bài kiểm tra của thực nghiệm 2 Bài kiểm tra của đợt thực nghiệm 2 có nội dung nhƣ sau: Đề kiểm tra (Thời gian làm bài 60 phút) Bài 1. Hãy thực hiện các yêu cầu độc lập sau đây: Câu 1. Hãy điền vào các ô trống trong bảng sau đây để nhận đƣợc hai cách diễn đạt thuật toán tƣơng đƣơng theo từng hàng (bằng ngôn ngữ tự nhiên và bằng ngôn ngữ biểu diễn thuật toán của Tin học): STT Cách 1 Cách 2 1 Hoán đổi giá trị của a và b cho nhau; ..... 2 .... i  i + 1; 3 Nếu ai không lớn hơn aj thì tiến hành “đổi chỗ” ai và aj cho nhau. ..... 4 .... ..... 5 .... Nếu n mod i = 0 thì d  d + i; Câu 2. Cho thuật toán sau đây: Bước 1. Nhập số nguyên n (với 2  n  100) và dãy (a) gồm n số nguyên dƣơng a1, a2, ..., an; Bước 2. i  1; Bước 3. Xét dãy con xác định bởi phần tử đầu dãy là ai, thực hiện các bƣớc sau đây: Bước 3.1. j  n; k  i; Bước 3.2. Nếu aj < ai thì lƣu lại vị trí của aj : k  j; Bước 3.3. j  j - 1; Bước 3.4. Nếu j > i thì quay về Bƣớc 3.2, ngƣợc lại thực hiện tiếp bƣớc 4; Bước 4. Nếu k  i thì thực hiện “đổi chỗ”: tg  ai; ai  ak; ak  min, ngƣợc lại thì thực hiện tiếp bƣớc 5. Bước 5. Chuyển sang dãy con tiếp theo: i  i + 1; Bước 6. Nếu i < n thì quay về bƣớc 3, ngƣợc lại thì thực hiện tiếp bƣớc 7; Bước 7. Xuất ra dãy a1, a2, ..., an đã đƣợc sắp xếp tăng dần. Bước 8. Kết thúc. Hãy chọn khẳng định đúng trong các khẳng định sau đây: (A) Thuật toán thực hiện nhiệm vụ sắp xếp giảm dần dãy (a); (B) Thuật toán thực hiện sai nhiệm vụ sắp xếp giảm dần dãy (a); (B) Thuật toán thực hiện nhiệm vụ sắp xếp tăng dần dãy (a); (C) Thuật toán thực hiện sai nhiệm vụ sắp xếp tăng dần dãy (a); - 40 - Bài 3. Hãy biểu diễn lại thuật toán ở câu 2 của bài 1 bằng sơ đồ khối và mô phỏng lại thuật toán đối với dữ liệu đầu vào sau đây: n = 5, và dãy (a1, a2, a2, a3, a4, a5) = (5, 8, 1, 9, 6) Bài 4. Cho (a) gồm n phần tử là các số nguyên dƣơng (1 n  103). Hãy xây dựng thuật toán thực hiện việc sắp xếp giảm dần dãy (a) theo một phƣơng pháp mà trong đó, mỗi lần thực hiện quá trình đổi chỗ đối với một dãy con, phần tử nhỏ nhất đƣợc chuyển về vị trí cuối dãy con. 8.3.2. Bài kiểm tra của thực nghiệm 3 Riêng bài kiểm tra của thực nghiệm 3 đƣợc thiết kế dƣới dạng một phiếu trắc nghiệm với yêu cầu HS thực hiện trong thời gian của một tiết học. Các phần in đậm trong phiếu không đƣợc công bố với HS. Nội dung của phiếu trắc nghiệm (kể cả phần in đậm) nhƣ sau: PHIẾU TRẢ LỜI TRẮC NGHIỆM (Thời gian làm bài 45 phút) Hướng dẫn: Với mỗi khẳng định trong bảng dƣới đây, nếu hoàn toàn đồng ý thì tô đậm vào ô , nếu đồng ý một phần thì tô đậm vào ô , nếu phân vân (không biết rõ câu trả lời là đồng ý hay không đồng ý) thì tô đậm vào ô , nếu không đồng ý thì tô đậm vào ô . Các vấn đề cần trả lời Tô đậm điểm phù hợp nhất STT Thang đo 1: Mức độ thực hiện 1 Thuật toán đƣợc tóm tắt nhƣ dƣới đây là thuật toán tìm m là giá trị lớn nhất của dãy số a1, a2, , an. Bước 1: Khởi tạo m  a1; Bước 2: Với i nhận giá trị từ 2 đến n, Nếu m < ai thì gán m  ai;     2 Thuật toán tìm max (giá trị lớn nhất) của một dãy n số có thể thực hiện so sánh từ phải sang trái dựa trên ý tƣởng sau đây: Bắt đầu với max gán bằng an, sau đó ta lần lƣợt so sánh max với an-1, an-2, , a1, nếu gặp phần tử ai nào mà lớn hơn max thì ta gán giá trị của nó cho max (i = n1, n2, , 1).     4 Thuật toán tìm giá trị lớn nhất của một dãy số nguyên giống thuật toán tìm kiếm có hay không có một phần tử trong một dãy số ở chỗ: Chúng đều mô tả quá trình duyệt toàn bộ các phần tử trong dãy số để so sánh (với giá trị     - 41 - cần tìm hoặc giá trị lớn nhất vừa tìm đƣợc). Thang đo 2: Cấp độ chuyển giao 5 Thuật toán tìm giá trị nhỏ nhất của một dãy số đƣợc sử dụng trong thuật toán sắp xếp tăng dần.     6 Dƣới đây là ý tƣởng thuật toán sắp xếp một dãy số nguyên n phần tử a1, a2,,...,an theo thứ tự giảm dần. - Đầu tiên, với dãy gồm n phần tử, ta chọn phần tử lớn nhất để đổi chỗ nó với phần tử ở vị trí 1. - Làm tƣơng tự nhƣ trên với dãy n1 phần tử còn lại, tức là coi phần tử ở vị trí đầu dãy mới là phần tử ở vị trí 2 của dãy ban đầu, ta chọn phần tử lớn nhất của dãy mới này đƣa về vị trí 2 đó. - Làm tƣơng tự nhƣ trên với dãy n2 phần tử còn lại và cứ tiếp tục nhƣ thế đến khi dãy còn lại chỉ có 1 phần tử thì toàn bộ dãy ban đầu đã đƣợc sắp xếp.     7 Đoạn chƣơng trình sau thực hiện hoán đổi giá trị của hai biến x và y cho trƣớc Bước 1: Nhập giá trị cho các biến x và y Bước 2: x ← x + y; Bước 2: y ← x  y; Bước 3: x ← x  y; Bước 4: Đƣa ra giá trị mới của x và y.     Thang đo 3: Cấp độ thiết kế 8 Nếu thuật toán trong câu 7 đƣợc kí hiệu là Doicho(x, y) thì thuật toán sau đây dùng để chuyển phần tử nhỏ nhất về vị trí thứ k trong dãy a1,a2,, ak (2 ≤ k ≤ n) Bước 1: Khởi tạo min  a1; i  2; Bước 2: Nếu min > ai thì Doicho(ai , an); Bước 3: Nếu i = k thì thực hiện bƣớc 5; Bước 4: Tăng i  i + 1; và quay về bƣớc 2; Bước 5: Kết thúc.     9 Nếu thuật toán trong câu 8 đƣợc kí hiệu là TimMin(k) thì thuật toán sau đây dùng để sắp xếp giảm dần dãy số a1,a2,, an (n ≥ 1). Bước 1: Nhập n và dãy a1, a2, , an; Bước 2: i  2; Bước 3: Nếu i > n thì đƣa ra dãy a1, a2, , an rồi kết thúc; Bước 4: TimMin(2);     - 42 - Bước 5. i  i + 1 rồi quay về bƣớc 3; 10 Trong thuật toán sắp xếp tăng dần, dựa trên ý tƣởng lần lƣợt chuyển phần tử nhỏ nhất về đầu các dãy con, có thể có phƣơng pháp thực hiện khác với cách thực hiện trong SGK.     - 43 - PHỤ LỤC 9: THỰC NGHIỆM 3 9.1. Giới thiệu thực nghiệm 3 Thực nghiệm sƣ phạm thứ ba nhằm kiểm tra hiệu quả của cách tiếp cận dạy học thuật toán theo phương pháp thao tác hóa và phƣơng pháp dạy học tích cực đƣợc lựa chọn sử dụng để dạy học thuật toán theo cách tiếp cận này là phương pháp dạy học chương trình hóa. Thực nghiệm 3 là một thực nghiệm đặc biệt vì nó chủ yếu hƣớng đến đối tƣợng HS khá. Thực nghiệm sƣ phạm đƣợc tiến hành trên hai nhóm lớp của trƣờng THPT Thạch Thất, Hà Nội. - Nhóm lớp thực nghiệm gồm hai lớp 10A3 (42 HS) và 10A14 (47HS); - Nhóm lớp đối chứng gồm hai lớp 10A11 (48HS) và 10A12 (48HS). Theo đánh giá của GV dạy bộ môn Toán và GV dạy bộ môn Tin thì các lớp này có học lực môn Tin học tƣơng đƣơng nhau. Nhóm lớp thực nghiệm (kí hiệu là TN) đƣợc dạy học thuật toán theo phƣơng pháp thao tác hóa, còn nhóm lớp đối chứng (kí hiệu là ĐC) vẫn dạy theo phƣơng pháp truyền thống. 9.2. Tóm tắt kết quả thực nghiệm Quá trình thực nghiệm lần thứ ba ba diễn ra nhƣ hai lần thực nghiệm trƣớc đây. Dƣới đây là hệ thống các bảng và biểu đồ so sánh kết quả làm bài tập nhóm và làm bài kiểm tra giữa hai nhóm lớp thực nghiệm và đối chứng. Biểu đồ 9.1. Biểu đồ biểu diễn số lƣợng và tỷ lệ HS các lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm. - 44 - Biểu đồ 9. 12. Biểu đồ biểu diễn số lƣợng và tỷ lệ HS các lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài tập nhóm. Biểu đồ 9.3. Biểu đồ biểu diễn số lƣợng và tỷ lệ HS các lớp thực nghiệm đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. - 45 - Biểu đồ 9.4. Biểu đồ biểu diễn số lƣợng và tỷ lệ HS các lớp đối chứng đạt các cấp độ tƣ duy thuật toán đối với bài kiểm tra. Biểu đồ 9. 5. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và nhóm lớp đối chứng đối với bài tập nhóm - 46 - Biểu đồ 9. 6. So sánh chuẩn tƣ duy thuật toán giữa nhóm lớp thực nghiệm và nhóm lớp đối chứng đối với bài kiểm tra. 9.3. Nhận xét và đánh giá kết quả thực nghiệm Từ các dữ liệu thống kê đƣợc trực quan hóa trên các biểu đồ, đặc biệt là hai biểu đồ so sánh cuối cùng (Biểu đồ 9.5 và Biểu đồ 9.6), ta có những nhận xét nhƣ sau: - Không có HS nào của các lớp thực nghiệm mà không đạt chuẩn tƣ duy thuật toán đối với bài tập nhóm (0% không đạt cấp độ thực hiện), trong khi đó, có đến gần một phần ba số HS của các lớp đối chứng không đạt đƣợc chuẩn tƣ duy thuật toán (26%). - Đối với bài kiểm tra, tồn tại một tỷ lệ HS nhỏ các HS lớp thực nghiệm không đạt chuẩn tƣ duy thuật toán (5.6%), nhƣng tỷ lệ HS không đạt chuẩn tƣ duy thuật toán cao hơn 10% (cụ thể là đạt 16.7%). - Hai kết quả so sánh về bài tập nhóm và bài kiểm tra cho thấy, khi làm bài tập nhóm, HS ở các lớp thực nghiệm đƣợc trao đổi, thảo luận, chia sẻ kinh nghiệm cho nhau nên kết quả làm bài tập nhóm tốt hơn khi so với làm bài kiểm tra độc lập. Tuy nhiên có lẽ ý thức và khả năng làm việc theo nhóm của HS các lớp đối chứng chƣa đạt phát huy đƣợc lợi ích của nhóm học tập. Các kết quả so sánh trên đây đã khẳng định đƣợc rằng việc vận dụng phƣơng pháp dạy học chƣơng trình hóa vào dạy học thuật toán theo phƣơng pháp thao tác hóa có tác dụng tốt hơn so với các phƣơng pháp dạy học thuật toán thông thƣờng trong việc đảm bảo chuẩn tƣ duy thuật toán cho HS. Để thuận lợi cho việc so sánh, đánh giá về các cấp độ tƣ duy cao hơn, giữa nhóm các lớp thực nghiệm và nhóm các lớp đối chứng, khi làm bài tập nhóm và khi làm bài kiểm - 47 - tra, ta có thể sử dụng hai bảng thống kê tổng hợp sau đây (Bảng 9.1 và Bảng 9.2). Bảng 9.1. Bảng tổng hợp: So sánh kết quả làm bài tập nhóm giữa các lớp thực nghiệm và các lớp đối chứng Bảng 9.2. Bảng tổng hợp: So sánh kết quả làm bài kiểm tra giữa các lớp thực nghiệm và các lớp đối chứng Theo các bảng thống kê ta thấy: - Ở kết quả làm bài tập nhóm, HS của các lớp thực nghiệm đạt 29.2% cấp độ chuyển giao và 11.2% ở cấp độ thiết kế, trong khi đó, HS của các lớp đối chứng chỉ đạt 22.5% cấp độ chuyển giao và 3.4% cấp độ thiết kế. - Ở kết quả làm bài kiểm tra, tỷ lệ HS của các lớp thực nghiệm đạt cấp độ chuyển giao (88.8%) chỉ cao hơn một chút so với tỷ lệ HS của các lớp đối chứng ở cấp độ này (83.1%); Nhƣng đối với cấp độ thiết kế, tỷ lệ HS của các lớp thực nghiệm đạt đến 78.7% trong khi HS của các lớp đối chứng chỉ đạt đƣợc 46.1%. Các kết quả trên đây cho thấy HS ở nhóm các lớp thực nghiệm đạt tỷ lệ cao hơn HS ở nhóm các lớp đối chứng không chỉ đối với cấp độ thực hiện thuật toán mà còn ở cả hai cấp độ cao hơn (cấp độ chuyển giao và cấp độ thiết kế), và không chỉ đối với bài tập nhóm mà còn ở cả bài kiểm tra. Nếu để ý đến các cột biểu thị mức cao và mức trung bình ở cấp độ chuyển giao và cấp độ thiết kế trong hai Bảng 9.1 và Bảng 9.2 ta còn thấy một kết quả quan trọng, đó là cách tiếp cận mới trong dạy học thuật toán còn có tác dụng nâng tỷ lệ HS đạt đƣợc các mức cao của các cấp độ tƣ duy thuật toán.