Luận án Tiến sĩ Khoa học giáo dục: 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

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:213

Thêm vào BST

Báo xấu

266
lượt xem 66
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học giáo dục: 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI ------------------------------- NGUYỄN CHÍ TRUNG 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 LUẬN ÁN TIẾN SĨ KHOA HỌC GIÁO DỤC HÀ NỘI - 2015
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI ------------------------------- NGUYỄN CHÍ TRUNG 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 LUẬN ÁN TIẾN SĨ 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ƣờng THPT để rèn luyện và phát triển tƣ duy thuật toán HS. - Xây dựng hệ thống các khái niệm cơ bản nhƣ: tác nhân, tƣ duy thuật toán, mức thủ công và mức điều khiển trong mô tả thuật toán, độ phức tạp của biểu diễn thuật toán. - Xây dựng hệ thống các thang đo tƣ duy thuật toán, bao gồm các biểu hiện của sự phát triển tƣ duy thuật toán và các cấp độ tƣ duy thuật toán. 3.4. Thực nghiệm sƣ phạm - Vận dụng cách tiếp cận dạy học thuật toán đã đề xuất để dạy học một số tiết thực nghiệm sƣ phạm. - Thiết kế bộ công cụ đánh giá kết quả thực nghiệm sƣ phạm. - Sử dụng phần mềm phân tích dữ liệu thực nghiệm để đƣa ra các đánh giá và đề xuất. 4. Đối tƣợng nghiên cứu Đối tƣợng nghiên cứu của luận án là quá trình dạy học thuật toán ở trƣờng THPT mà thực chất là quá trình giáo dục thông qua dạy học thuật toán ở trƣờng THPT. Quá trình dạy học bao gồm việc dạy (hoạt động và giao lƣu của thầy) và việc học (hoạt động và giao lƣu của HS) với đối tƣợng chiếm lĩnh là nội dung thuật toán, còn bản thân việc học là đối tƣợng điều khiển của việc dạy. Quá trình giáo dục nhằm mục tiêu chủ đạo của việc dạy học phát triển tƣ duy thuật toán, thể hiện ở chỗ GV không những chỉ dạy HS kiến tạo đƣợc các tri thức về thuật toán mà còn cho HS nắm đƣợc những phƣơng thức tƣ duy nhƣ tƣ duy ngữ nghĩa, tƣ duy cú pháp, tƣ duy ngôn ngữ và đặc biệt là tƣ duy thuật toán. 5. Phạm vi nghiên cứu Về phạm vi lý thuyết, luận án tập trung nghiên cứu về lý luận và phƣơng pháp dạy học thuật toán ở trƣờng phổ thông. Về phạm vi đối tượng, luận án hƣớng đến lớp đối tƣợng HS đại trà lớp 10 và lớp 11 THPT, trong đó có một số nội liên quan đến đối tƣợng HS khá.
4 Về phạm vi nội dung, luận án nghiên cứu những bài toán của môn Toán có thể giải tổng quát theo thuật toán và những bài toán của môn Tin học đƣợc xây dựng thuật toán thuận lợi cho lập trình để giải quyết trên máy tính. 6. Phƣơng pháp nghiên cứu 6.1. Nghiên cứu lý luận Nghiên cứu lý luận bao gồm nghiên cứu những bài báo, tạp chí và sách về cách tiếp cận dạy học thuật toán, và các tài liệu liên quan nhƣ tâm lý học, giáo dục học, sách giáo khoa và sách giáo viên. Phân tích tài liệu lý luận trên đây để hoàn thành nhiệm vụ của đề tài. So sách quốc tế dựa trên cơ sở đánh giá, so sánh tài liệu, cách tiếp cận dạy học thuật toán ở trong nƣớc và trên thế giới. Phân tích tiên nghiệm trong nghiên cứu lý luận dựa vào lịch sử hình thành khái niệm thuật toán và các cách tiếp cận dạy học thuật toán khác nhau để dự kiến những hiện tƣợng có thể có của HS khi học thuật toán. Từ đó kiểm nghiệm hiện tƣợng đó trong thực nghiệm sƣ phạm về cách tiếp cận dạy học thuật toán đƣợc đề xuất. 6.2. Khảo sát điều tra thực tiễn Khảo sát - điều tra thực tiễn dạy học thuật toán hiện nay ở chƣơng trình Tin học lớp 10 và lớp 11, THPT, để phát hiện những thuật lợi và khó khăn trong việc dạy học thuật toán, giúp thu thập thông tin sinh động cho nghiên cứu. 6.3. Nghiên cứu trƣờng hợp Dạy học một số nội dung về thuật toán. Trao đổi với GV, theo dõi, ghi chép những trƣờng hợp này để xây dựng những tiêu chuẩn đánh giá, đo lƣờng các kết quả điều tra cụ thể. Trên cơ sở đó phân tích, đánh giá dựa trên phần mềm. 6.4. Thực nghiệm sƣ phạm Thiết kế bài tập nhóm, bài kiểm tra và phiếu trắc nghiệm. Xây dựng các thang đo tƣ duy thuật toán để đo chất lƣợng dạy và học thuật toán. Tiến hành thực nghiệm kết quả nghiên cứu. Phân tích số liệu thu thập đƣợc trên phần mềm để đƣa ra đánh giá và đề xuất. 6.5. Thống kê Toán học Thống kê Toán học ở đây dựa trên lý thuyết xác xuất thống kê và phân tích dữ liệu trong nghiên cứu giáo dục. Kết quả của phân tích dữ liệu là những số liệu về thống kê mô tả và những kết luận về thống kê suy luận. Những kết quả này đƣợc sử dụng để đánh giá những cách tiếp cận mới trong dạy học thuật toán của thực nghiệm sƣ phạm. 7. Giả thuyết khoa học
5 Nếu có cách tiếp cận mới, phù hợp trong dạy học thuật toán ở trƣờng THPT thì HS sẽ đƣợc phát triển tƣ duy thuật toán và đƣợc nâng cao hiệu quả học tập thuật toán. Nói một cách đầy đủ hơn, HS đƣợc phát triển tƣ duy thuật toán trong việc hiểu, thực hiện, đánh giá, chuyển giao và xây dựng thuật toán. Với cách tiếp cận mới, tƣ duy thuật toán đƣợc phân tích thành các cấp độ với các đánh giá tƣơng ứng, làm căn cứ cho việc tổ chức dạy học đem lại hiệu quả hơn trong dạy học thuật toán cho HS. 8. Các luận điểm bảo vệ và đóng góp của luận án 8.1. Về mặt lý luận Luận án có những đóng góp sau đây về mặt khoa học: Đề xuất đƣợc hệ thống lí luận cho những cách tiếp cận phù hợp trong dạy học thuật toán cho HS ở trƣờng THPT, nhằm phát triển tƣ duy thuật toán và nâng cao hiệu quả học tập thuật toán. Hệ thống lí luận này bao gồm: - Những khái niệm nền tảng bao gồm: tác nhân, tư duy thuật toán, những biểu hiện và các cấp độ của sự phát triển tư duy thuật toán, mô tả thuật toán ở hai mức thủ công và điều khiển. - Phương pháp thao tác hóa trong dạy học thuật toán và các khái niệm liên quan như mô đun thuật toán, thủ tục và hàm. - Phương pháp làm mịn dần trong dạy học thuật toán. - Phương pháp tinh chế trong dạy học thuật toán và các khái niệm liên quan như nguyên tắc tinh chế dựa trên ngôn ngữ, độ phức tạp của biểu diễn thuật toán. 8.2. Về mặt thực tiễn Luận án có những đóng góp sau đây về mặt thực tiễn: - Đề xuất một hƣớng tiếp cận mới trong dạy học thuật toán ở trƣờng THPT, góp phần rèn luyện cho HS tƣ duy giải quyết các vấn đề trong dạy học môn Toán và môn Tin học. - Đóng góp một xu hƣớng mới trong đào tạo sinh viên sƣ phạm Tin học nói riêng, lĩnh vực Toán - Tin nói chung trong trƣờng Đại học Sƣ phạm Hà Nội. 9. Cấu trúc và tóm tắt nội dung của luận án Ngoài một số phần nhƣ mở đầu, kết luận, và tài liệu tham khảo, luận án gồm 4 chƣơng sau đây: Chƣơng 1: Cơ sở lý luận về thực tiễn - Về cơ sở lý luận: Trình bày nguồn gốc của từ thuật toán, khái niệm thuật toán trong quá trình hình thành thuật toán trong Toán học và trong Khoa học máy
6 tính, các tính chất của thuật toán. Lịch sử vấn đề nghiên cứu cũng đƣợc giới thiệu chi tiết, bao gồm các xu hƣớng dạy học thuật toán hiện nay ở trong nƣớc và trên thế giới. - Về cơ sở thực tiễn: Trình bày kết quả khảo sát, điều tra tình hình học tập thuật toán hiện nay ở một số trƣờng THPT. 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 - Đề xuất các khái niệm cơ sở nhƣ tác nhân, tƣ duy thuật toán, - Trình bày các biểu hiện của sự phát triển tƣ duy thuật toán theo hai mức mô tả thuật toán: mức độ thủ công (giải bài toán theo thuật toán) và mức độ điều khiển (giải bài toán dựa vào máy tính). - Đƣa ra các cấp độ của sự phát triển tƣ duy thuật toán. Chƣơng 3: Một số cách tiếp cận mới trong dạy học thuật toán ở trƣờng THPT - Đề xuất ba cách tiếp cận mới trong dạy học thuật toán, bao gồm: Thao tác hóa, Làm mịn dần và Tinh chế. - Chỉ ra sự thúc đẩy và cách đánh giá sự phát triển tƣ duy thuật toán trong từng cách tiếp cận dạy học thuật toán. Chƣơng 4: Thực nghiệm sƣ phạm - Trình bày mục đích và phƣơng pháp thực nghiệm sƣ phạm. - Trình bày các công cụ cho thực nghiệm và cách qui đổi, mã hóa điểm số để thuận lợi cho xử lý dữ liệu thực nghiệm dựa trên phần mềm và để qui về các thang đo sự phát triển tƣ duy thuật toán. - Các kết quả của các đợt thực nghiệm. - Phân tích, đánh giá và đƣa ra các đề xuất.
7 CHƢƠNG 1. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN VỀ VIỆC DẠY HỌC THUẬT TOÁN 1.1. SỰ HÌNH THÀNH KHÁI NIỆM THUẬT TOÁN 1.1.1. Nguồn gốc của từ thuật toán Theo Steven C. Althoen & Robert J. Bumcrot (1988), từ "thuật toán" (algorithm) có nguồn gốc từ tên gọi Mohamed ibn Musa al-Khowarizmi, nhà Toán học cổ đại ngƣời Trung Á, ngƣời đã phát minh ra tập các qui tắc để thực hiện các phép toán cộng, trừ, nhân, và chia các số thập phân. Vào năm 1857, quyển sách đại số của ông bắt đầu đƣợc dịch sang chữ Latin. Trong bản dịch tiếng Anh, từ al-Khowarizmi (hoặc al-Khwarizm, nguyên bản Latin là “al-Khwârizmî”) đƣợc phát âm là "algoritmi" và sau này đƣợc nhiều ngƣời gọi là algorithm. Một điều thú vị là Steven và Robert giải thích tên gọi “Mohamed ibn Musa al- Khowarizmi” nghĩa là Mohamed, con trai của Musa, đến từ huyện Khowarizmi - nƣớc Cộng hòa xã hội chủ nghĩa Xô-Viết (Liên-Xô cũ) của ngƣời Kazakh, Turkmen, và Uzbek. Tuy nhiên Donald E. Knuth (1980) cho rằng phần tên gọi al- Khwârizmî lại không chứng minh đƣợc ông sinh ra ở Khwarizm. Vì công việc nghiên cứu của ông diễn ra ở Baghdad, ở nơi mà một số nhà khoa học vẫn gọi là “Ngôi nhà thông thái” (“House of Wisdom”) của Caliph al-Ma’mun - nhà tài trợ nổi tiếng cho các nhà nghiên cứu khoa học, đã từng mời nhiều ngƣời đến khóa học của ông để tuyển chọn và mở rộng những tài năng trên thế giới. Nhà sử học al-Tabari đã thêm từ "al-Qutrubbulli" vào tên của al-Khwârizmî, là có ý đề cập đến huyện Qutrubbulli gần Baghdad. Do đó, Knuth nghĩ rằng al-Khwârizmî đƣợc sinh ra ở Khwarizm và sống phần lớn cuộc đời ở Qutrubbull sau đƣợc triệu tập tới Baghdad của Caliph, nhƣng sự thật có thể sẽ không bao giờ đƣợc biết đến. 1.1.2. Sự hình thành khái niệm thuật toán trong Toán học Theo Dimitris Samaras (2009), thuật toán có vai trò quan trọng trong Toán học. Các tài liệu Toán học cổ điển đã bao gồm các mô tả về các thuật toán giải quyết các nhiệm vụ khác nhau nhƣ: tìm số nguyên tố, tìm ước số chung lớn nhất của hai số nguyên. Khái niệm thuật toán không đƣợc định nghĩa chính xác cho đến tận thế kỉ 20. Trƣớc thế kỉ 20, các nhà Toán học chỉ có một khái niệm trực giác (intuitive notation) về cái gọi là thuật toán. Khái niệm trực giác về thuật toán không đủ để có một cái nhìn sâu hơn về việc hiểu thuật toán. Năm 1900, tại hội nghị Toán học quốc tế ở Paris, nhà Toán học David Hilbert đã đƣa ra 23 bài toán nổi tiếng, mà theo ông
8 đây là những hƣớng nghiên cứu Toán học lý thú cho các nhà Toán học thế giới ở thế kỷ 20. Trong đó, yêu cầu của bài toán thứ 10 là “hãy tìm một qui trình bao gồm một số hữu hạn bƣớc thực hiện mà nó cho phép xác định một phƣơng trình Diophante có nghiệm nguyên hay không”1. Tại thời điểm này, Hilbert đã không sử dụng thuật ngữ “thuật toán” mà sử dụng cụm từ “qui trình với một số hữu hạn các bƣớc thực hiện” (cụm từ này thể hiện khái niệm trực giác về thuật toán). Trong phát biểu của mình, Hilbert đã giả định rằng “thuật toán” để kiểm tra là đã tồn tại, ta chỉ cần tìm ra nó. Nhƣng đến nay chúng ta đã biết không tồn tại một thuật toán mà nó có thể trả lời được câu hỏi “một đa thức cho trƣớc có nghiệm nguyên hay không”. Khái niệm trực giác về thuật toán đã không có tác dụng trong việc chỉ ra không tồn tại thuật toán để giải bài toán thứ 10 của Hilbert. Việc cung cấp khái niệm “không tồn tại một thuật toán để giải một bài toán đã cho” đòi hỏi phải có định nghĩa chính thức về thuật toán. Năm 1936, Alonzo Church và Alan Turing đã đề xuất định nghĩa hình thức cho khái niệm thuật toán (formal definitions for the concept of algorithm) (xem Goldberg, 2012). Church đã sử dụng một hệ thống khái niệm gọi là phép toán  (- calculus) để định nghĩa khái niệm thuật toán, còn Turing dùng máy Turing để định nghĩa khái niệm thuật toán2. Cả hai định nghĩa này đều tƣơng đƣơng và khá phức tạp, vì nó đƣợc phát biểu dài dòng và sử dụng các thuật ngữ và kí hiệu Toán học. Lý thuyết của Church và Turing đƣợc tổng kết lại trong luận đề Church-Turing. Luận đề này khẳng định mọi hàm Toán học tính được thì cũng có thể dùng các máy Turing để tính, và do đó cho phép định nghĩa các khái niệm nhƣ sự tính đƣợc của hàm hay thuật toán. Các định nghĩa hình thức khác về thuật toán đã đƣợc nhiều tác giả đề xuất nhƣ Kleene sử dụng các hàm truy hồi (recursive functions), Markov sử dụng các qui tắc đạo hàm và gọi chúng là thuật toán chuẩn (normal algorithm). Về mặt bản chất, các định nghĩa này đều tƣơng đƣơng với nhau và tƣơng đƣơng với máy Turing. 1 Nguyên bản tiếng Anh bài toán thứ 10 của Hilbert: “Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.” (Xem Barry Mazur (2010), “Hilbert’s Tenth Problem and Elliptuc Curves”, in Expository Articles - Notes for Basic Notations talk, Department of Mathematics, University of Harvard). 2 Máy Turing là một mô hình về thiết bị xử lý các ký tự, tuy đơn giản, nhƣng có thể thực hiện đƣợc tất cả các thuật toán máy tính. Máy Turing đƣợc xây dựng không dành cho việc trực tiếp chế tạo ra máy tính, mà là dành cho các thí nghiệm tƣởng tƣợng để tìm hiểu về các giới hạn của việc tính toán trên máy móc. Các máy Turing đã đƣợc Alan Turing trình bày vào năm 1936.