Tài liệu Phát triển năng lực tư duy thuật toán cho học sinh khi dạy học câu lệnh rẽ nhánh trong tin học lớp 11

TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 VIỆN CÔNG NGHỆ THÔNG TIN ----------------------- CHU HUY HOÀNG PHÁT TRIỂN NĂNG LỰC TƢ DUY THUẬT TOÁN CHO HỌC SINH KHI DẠY HỌC CÂU LỆNH RẼ NHÁNH TRONG TIN HỌC LỚP 11 KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Sƣ phạm Tin học HÀ NỘI, 2019 TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 VIỆN CÔNG NGHỆ THÔNG TIN ----------------------- CHU HUY HOÀNG PHÁT TRIỂN NĂNG LỰC TƢ DUY THUẬT TOÁN CHO HỌC SINH KHI DẠY HỌC CÂU LỆNH RẼ NHÁNH TRONG TIN HỌC LỚP 11 KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Sƣ phạm Tin học Ngƣời hƣớng dẫn khoa học TS. LƢU THỊ BÍCH HƢƠNG HÀ NỘI, 2019 LỜI CẢM ƠN Trong quá trình thực hiện khóa luận “Phát triển năng lực tư duy thuật toán cho học sinh khi dạy học câu lệnh rẽ nhánh trong Tin học lớp 11”, ngoài sự cố gắng của bản thân, em đã nhận đƣợc sự giúp đỡ tận tình, tạo điều kiện của các thầy, cô giáo trong Viện Công nghệ Thông tin, đặc biệt là cô giáo hƣớng dẫn – TS. Lƣu Thị Bích Hƣơng. Em xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất của mình tới cô Lƣu Thị Bích Hƣơng đã tận tình giúp đỡ, hƣớng dẫn và chỉ bảo cho em trong suốt quá trình thực hiện khóa luận. Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ Thông tin của trƣờng ĐHSP Hà Nội 2 đã tận tình truyền đạt kiến thức trong những năm em học tập. Vốn kiến thức tiếp thu đƣợc trong quá trình học tập không chỉ là nền tảng cho quá trình nghiên cứu khóa luận mà còn là hành trang quý báu để em bƣớc vào đời một cách vững chắc và tự tin. Cuối cùng em xin cảm ơn các thầy cô giáo trong tổ Toán – Tin – CN của trƣờng THPT Xuân Hòa – Phúc Yên – Vĩnh Phúc, đặc biệt là cô hƣớng dẫn thực tập Nguyễn Thị Thu Trang đã tạo mọi điều kiện giúp đỡ và đóng góp ý kiến để em thực hiện khóa luận này. Hà Nội, tháng 5 năm 2019 Sinh viên thực hiện Chu Huy Hoàng LỜI CAM ĐOAN Em xin cam đoan đây là công trình nghiên cứu riêng của em và đƣợc sự hƣớng dẫn của TS. Lƣu Thị Bích Hƣơng. Các kết quả, số liệu nêu trong khóa luận này chƣa đƣợc công bố ở bất kỳ công trình khoa học nào. Những số liệu kết quả đƣợc chính em thu thập trong thời gian thực tập tại trƣờng THPT Xuân Hòa. Ngoài ra, trong khóa luận có sử dụng các cơ sở lý thuyết đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện bất kỳ gian lận nào, em xin chịu hoàn toàn trách nhiệm về nội dung khóa luận của mình. Hà Nội, tháng 5 năm 2019 Sinh viên thực hiện Chu Huy Hoàng DANH MỤC CÁC VIẾT TẮT CN Công nghệ ĐK Điều kiện GV Giáo viên HS Học sinh SGK Sách giáo khoa THPT Trung học phổ thông DANH MỤC HÌNH Hình 1.1: Mô hình chung cấu trúc năng lực ................................................... 13 Hình 1.2: 5 phẩm chất và 10 năng lực của học sinh cần đạt đƣợc.................. 20 Hình 2.1: Sơ đồ của cấu trúc rẽ nhánh if – then.............................................. 26 Hình 2.2: Thuật toán kiểm tra a là số chẵn ..................................................... 28 Hình 2.3: Sơ đồ cấu trúc rẽ nhánh if – then – else .......................................... 29 Hình 2.4: Thuật toán tìm max của a và b ........................................................ 31 Hình 2.5: Thuật toán giải phƣơng trình bậc nhất: ax + b = 0 ......................... 34 Hình 2.6: Thuật toán giải phƣơng trình bậc 2 ................................................. 36 DANH MỤC BẢNG Bảng 1.1: Bảng tóm tắt các năng lực chung và biểu hiện của từng năng lực.................................................................................................. 14 Bảng 1.2: Ý kiến GV về việc dạy học nhằm phát triển năng lực tƣ duy thuật toán ....................................................................................... 20 Bảng 1.3: Kết quả điều tra về ý thức học tập và phƣơng pháp học môn Tin học của học sinh ..................................................................... 22 Bảng 2.1: So sánh hai dạng câu lệnh If – then ................................................ 24 Bảng 2.2: Một số ví dụ về câu lệnh rẽ nhánh.................................................. 25 Bảng 3.1: Thống kê kết quả học tập môn Tin học trƣớc thực nghiệm ........... 39 Bảng 3.2: Kết quả điểm sau thực nghiệm ....................................................... 52 MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1: CƠ SỞ LÍ LUẬN VÀ THỰC TIỄN........................................... 6 1.1. Sự hình thành khái niệm thuật toán ........................................................... 6 1.1.1. Nguồn gốc của từ thuật toán ................................................................... 6 1.1.2. Sự hình thành khái niệm thuật toán trong Tin học.................................. 6 1.1.3. Khái niệm thuật toán đƣợc dạy ở trƣờng phổ thông ............................... 8 1.2. Các tính chất của thuật toán ....................................................................... 9 1.3. Phát triển năng lực tƣ duy thuật toán ....................................................... 11 1.3.1. Nguồn gốc của năng lực........................................................................ 11 1.3.2. Khái niệm năng lực ............................................................................... 12 1.3.3. Khái niệm năng lực Tin học .................................................................. 13 1.3.4. Khái niệm năng lực tƣ duy thuật toán ................................................... 13 1.3.5. Các năng lực cần phát triển cho học sinh trung học phổ thông ............ 14 1.4. Điều tra thực trạng dạy học theo định hƣớng phát triển tƣ duy thuật toán trong Tin học lớp 11 ........................................................................................ 20 1.4.1. Điều tra thăm dò ý kiến giáo viên ......................................................... 20 1.4.2. Điều tra thăm dò ý kiến học sinh .......................................................... 22 1.4.3. Đánh giá chung ..................................................................................... 23 CHƢƠNG 2: PHÁT TRIỂN NĂNG LỰC TƢ DUY THUẬT TOÁN CHO HỌC SINH KHI DẠY HỌC CÂU LỆNH RẼ NHÁNH TRONG TIN HỌC 11 ..................................................................................................................... 24 2.1. Mục tiêu của chủ đề ................................................................................. 24 2.2. Câu lệnh rẽ nhánh..................................................................................... 24 2.3. Phân tích một số nội dung dạy học câu lệnh rẽ nhánh trong Tin học 11 ..... 25 2.3.1. Ý nghĩa của câu lệnh rẽ nhánh .............................................................. 25 2.3.3. Câu lệnh ghép và ví dụ .......................................................................... 34 CHƢƠNG 3: THỰC NGHIỆM SƢ PHẠM ................................................... 38 3.1. Mục đích, đối tƣợng và phƣơng pháp thực nghiệm sƣ phạm .................. 38 3.1.1. Mục đích thực nghiệm sƣ phạm ............................................................ 38 3.1.2. Nhiệm vụ của thực nghiệm sƣ phạm .................................................... 38 3.1.3. Đối tƣợng thực nghiệm sƣ phạm........................................................... 38 3.1.4. Phƣơng pháp thực nghiệm sƣ phạm...................................................... 39 3.2. Triển khai thực nghiệm sƣ phạm ............................................................. 39 3.2.1. Tiến hành giảng dạy trên lớp ................................................................ 39 3.2.2. Tổ chức thực nghiệm............................................................................. 52 3.2.3. Kết quả thực nghiệm ............................................................................. 52 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 54 TÀI LIỆU THAM KHẢO ............................................................................... 56 PHỤ LỤC 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 theo định hƣớng phát triển 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 [8]. 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"[4]. 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 [9]. 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 1 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. 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, em chọn đề tài “Phát triển năng lực tư duy thuật toán cho học sinh khi dạy học câu lệnh rẽ nhánh trong Tin học lớp 11” để nghiên cứu. 2. Mục đích nghiên cứu Mục tiêu của khóa luậ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 Tin học. Một cách cụ thể, khóa luận đƣa ra một số cách tiếp cận trong 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. 2 3. Khách thể, đối tƣợng và phạm vi nghiên cứu  Đối tƣợng nghiên cứu Đối tƣợng nghiên cứu của khóa luậ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.  Phạm vi nghiên cứu Về phạm vi lý thuyết, khóa luậ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, khóa luận hƣớng đến lớp đối tƣợng HS lớp 11 THPT. 4. Nhiệm vụ nghiên cứu  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 độ Tin học. - 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.  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 ở trƣờng phổ thông. 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.  Đề xuất giải pháp - Xây dựng các cách tiếp cận trong dạy học thuật toán trong môn Tin học ở trƣờng THPT để rèn luyện và phát triển tƣ duy thuật toán HS.  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 tiết thực nghiệm sƣ phạm. 5. Phƣơng pháp nghiên cứu - Phƣơng pháp nghiên cứu lý thuyết: Nghiên cứu các văn bản, nghị quyết của Đảng, của chính phủ, của ngành giáo dục về đổi mới phƣơng pháp dạy học ở trƣờng phổ thông. - Phƣơng pháp lấy ý kiến chuyên gia: Tham khảo ý kiến của các nhà khoa học về dạy học phát triển năng lực tƣ duy thuật toán. - Phƣơng pháp điều tra xã hội học: Điều tra thực trạng giáo dục nghiệp vụ sƣ phạm và rèn luyện kĩ năng dạy học phát triển năng lực tƣ duy thuật toán cho học sinh. - Phƣơng pháp thực nghiệm sƣ phạm: Tổ chức thực nghiệm sƣ phạm để kiểm chứng các giải pháp đề xuất. 6. Giả thuyết khoa học Nếu ứng dụng thành công dạy học phát triển năng lực tƣ duy thuật toán cho HS thông qua dạy học câu lệnh rẽ nhánh sẽ góp phần cho việc giáo dục và phát triển năng lực tƣ duy thuật toán cho HS của trƣờng THPT Xuân Hòa nói riêng và học sinh THPT nói chung. Từ đó, HS có thể tự xây dựng và giải quyết các bài toán khác. 7. Cấu trúc của khóa luận Ngoài phần mở đầu, kết luận, tài liệu tham khảo và phụ lục thì nội dung chính của khóa luận đƣợc trình bày trong 3 chƣơng: 4 Chƣơng 1: Cơ sở lí luận và thực tiễn. Chƣơng 2: Phát triển năng lực tƣ duy thuật toán cho học sinh khi dạy học câu lệnh rẽ nhánh trong Tin học 11. Chƣơng 3: Thực nghiệm sƣ phạm. 5 CHƢƠNG 1: CƠ SỞ LÍ LUẬN VÀ THỰC TIỄ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 Nguồn gốc từ "thuật toán" (algorithm) bắt nguồn từ tên gọi của nhà Toán học cổ đại ngƣời Trung Á, Mohamed ibn Musa al-Khowarizmi, 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 alKhwarizm, 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 [10]. Theo Steven C. Althoen & Robert J. Bumcrot (1988), họ cho rằng 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. Nhƣng Donald E. Knuth (1980) lại nghĩ khác và 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 ở 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. 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 [10]. 1.1.2. Sự hình thành khái niệm thuật toán trong Tin học Bàn về thuật toán Robert Sedgewick (1946) cho rằng: "Khi viết một chƣơng trình máy tính, ta thƣờng cài đặt một phƣơng pháp đã đƣợc nghĩ ra trƣớc đó để giải quyết một vấn đề. Phƣơng pháp này thƣờng độc lập với một máy tính cụ thể sẽ đƣợc dùng, nó hầu nhƣ thích hợp nhƣ nhau cho nhiều máy tính". Từ "thuật toán" đƣợc dùng trong Khoa học máy tính để mô tả một phƣơng pháp giải bài toán thích hợp cho việc cài đặt nhƣ là các chƣơng trình máy tính1 . Thuật toán là "chất liệu" ("stuff") của Khoa học máy tính: chúng 6 là đối tƣợng nghiên cứu trung tâm trong nhiều, nếu không nói là hầu hết, các lĩnh vực của Tin học" [10]. Quan điểm về thuật toán của Robert không đi ngƣợc lại các định nghĩa hình thức đúng đắn về thuật toán nhƣ đã đề cập trên đây, và cũng giống nhƣ các nhà Khoa học máy tính khác, Robert lƣợc bỏ các thuật ngữ phức tạp của Toán học, để lột tả một cách dễ hiểu rằng một thuật toán một khi nó đƣợc mô tả bởi một ngƣời làm về Khoa học máy tính thì nó phải đủ gần gũi tựa nhƣ giả mã (pseudo code), cũng nhƣ đủ độ dễ chuyển đổi sang một mã nguồn (source code) nào đó không phụ thuộc vào phần cứng máy tính. Trong khi Chung-Yang Huang et al. (2009) cho rằng: “Một thuật toán là một danh sách có thứ tự các chỉ dẫn đƣợc chỉ ra chính xác để thực hiện một công việc hay giải quyết một bài toán. Nó có thể đƣợc mô tả trong ngôn ngữ tự nhiên, giả mã, sơ đồ, hoặc thậm chí trong ngôn ngữ lập trình” [10]. João Fernando Peixoto Ferreira (2010) đã đƣa ra quan điểm của mình nhƣ sau: “Khi ta nói rằng Toán học là thuật toán một cách tự nhiên, không có nghĩa là thuật toán dùng để giải toán. Ở đây, chúng tôi muốn nói rằng các nguyên tắc và kĩ thuật đƣợc phát triển để xây dựng và giải quyết những vấn đề thuật toán có thể đƣợc sử dụng để giải quyết nhiều vấn đề Toán học”, và ông đã định nghĩa “Một thuật toán là một dãy xác định các chỉ dẫn mà nó có thể đƣợc thực hiện một cách hệ thống trong lời giải bài toán đã cho” [10]. Kết luận - Các định nghĩa thuật toán đều hƣớng đến đối tƣợng thực hiện thuật toán, đối tƣợng cuối cùng là máy tính. - Các thuật toán đƣợc nhấn mạnh đến tính giải đƣợc, tính đúng đắn, tính dừng, và tính xác định. - Thuật toán có các hình thức biểu diễn nhƣ: ngôn ngữ tự nhiên, giả mã, sơ đồ, và ngôn ngữ lập trình. - Một thuật toán không đƣợc xem là một lời bài toán bao gồm cả việc chứng minh tính đúng đắn của lời giải. Nói cách khác, có thể xem thuật toán 7 là một lời giải tóm tắt cho một bài toán, lƣợc bỏ đi rất nhiều các giải thích chi tiết. 1.1.3. Khái niệm thuật toán được dạy ở trường phổ thông Khái niệm bài toán: "Trong phạm vi Tin học, "bài toán" là một việc nào đó ta muốn máy tính thực hiện". Trong định nghĩa bài toán đƣợc nêu ở trên, cụm từ "một việc nào đó" bao gồm các bài toán giải đƣợc theo thuật toán thuộc lĩnh vực Toán học và bao gồm các bài toán của riêng Tin học [5]. Ví dụ 1.1: Ví dụ xét những việc sau đây: 1 Hãy in lên màn hình một dòng văn Thuộc “bài toán” của riêng Tin bản chuyển động. học 2 Hãy chứng minh tập các số nguyên Nói chung thuộc “bài toán” tố là vô tận. của riêng Toán học. 3 Hãy giải bất phƣơng trình bậc nhất Thuộc “bài toán” của Toán học ax + b ≤ 0 với các số thực a, b cho và Tin học. trƣớc. 4 Hãy kiểm tra xem một dãy số có lập Thuộc “bài toán” của Toán học thành cấp số cộng không. và Tin học. 5 Hãy tập lái xe ô tô trên sân tập. Không thuộc “bài toán” của Toán học hoặc Tin học. Định nghĩa thuật toán: "Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác đƣợc sắp xếp theo một trình tự nhất định sao cho khi thực hiện dãy thao tác ấy, từ Input (là dữ liệu vào của bài toán), ta nhận đƣợc output (là dữ liệu ra của bài toán) cần tìm" [5]. Định nghĩa trên đây nhấn mạnh dãy “thao tác” phải đảm bảo hai tính chất: (1) tính hữu hạn để đảm bảo thuật toán phải dừng lại sau một số bƣớc thực hiện, và (2) tính có qui tắc để đảm bảo các chỉ dẫn (các thao tác) trong thuật toán đƣợc viết theo một qui định nhất quán về cách mô tả, biểu diễn chúng. 8 Định nghĩa về thuật toán đƣợc nêu trên đây hàm ý nhấn mạnh việc chỉ ra một qui trình rõ ràng và chính xác để tìm ra kết quả (output) từ dữ liệu vào (input) của bài toán. Định nghĩa này còn ngụ ý thuật toán không bị đòi hỏi phải giải quyết các yêu cầu định tính của các bài toán trong Toán học (ví dụ nhƣ chứng minh sự tồn tại hay không tồn tại lời giải của bài toán) mà nhiệm vụ chính của thuật toán là thực hiện các yêu cầu định lƣợng với tốc độ nhanh nhất chấp nhận đƣợc (ví dụ tìm số hạng thứ một nghìn của dãy Fibocacii trong thời gian không quá 10 giây). Ví dụ 1.2: Dãy Fibonacii Nhà Toán học Fibonacii đã phát hiện ra qui luật sinh sản của loài thỏ nhƣ sau: Số thỏ ở hai thế hệ đầu tiên qui ƣớc là 1 (thỏ bố và thỏ mẹ), còn số thỏ từ thế hệ thứ 3 trở đi bằng tổng số thỏ ở hai thế hệ ngay trƣớc đó. Vậy số lƣợng thỏ của các hệ liên tiếp tạo thành một dãy đặc biệt (gọi là dãy Fibonacii) có dạng: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Vấn đề đặt ra là với một số n cho trƣớc nào đó, hãy tìm số hạng thứ n của dãy Fibonacii. Ở góc độ Toán học, bài toán này giải đƣợc (tồn tại nghiệm). Cụ thể, nếu gọi f(n) là số lƣợng thỏ ở thế hệ thứ n thì f(n) có thể tính đƣợc theo công thức qui nạp sau đây: f(n)={ ( ) ( ) Tuy nhiên, ngƣời làm toán chỉ có thể dừng lại ở việc thành lập đƣợc công thức trên đây, chứ không thể trong thời gian vài giây trả lời đƣợc số hạng thứ 100 của dãy Fibonacii cụ thể bằng bao nhiêu. Trả lời đƣợc câu hỏi định lƣợng đó trong thời gian vài giây là nhiệm vụ của Tin học. Nếu thuật toán tính f(n) dựa vào công thức qui nạp Toán học trên thì nó đƣợc gọi là thuật toán đệ qui. Chƣơng trình cài đặt thuật toán đệ qui thƣờng đòi hỏi chi phí rất cao về bộ nhớ máy tính và thời gian thực hiện. Do đó, Tin học thƣờng tìm kiếm một thuật toán khác, gọi là thuật toán lặp, tốn ít thời gian và bộ nhớ hơn để tính f(n) với n không nhỏ, thậm chí khá lớn. 1.2. Các tính chất của thuật toán Các tính chất cơ bản của thuật toán bao gồm: 9 (1) Tính dừng, (2) Tính xác định, (3) Tính đúng đắn, (4) Tính luôn tồn tại Input, Output, (5) Tính phổ dụng, (6) Tính hiệu quả. Trong chƣơng trình Tin học phổ thông, HS đƣợc dạy chính thức ba tính chất đầu tiên của thuật toán đó là tính dừng, tính xác định và tính đúng đắn. Tuy nhiên GV có thể giới thiệu ba tính chất còn lại, đó là tính luôn tồn tại Input, Output; tính phổ dụng; và tính hiệu quả. Tính luôn có Input/Output đƣợc nhắc đến nhƣ một sự ngầm định. Tính phổ dụng đƣợc nhắc đến để nhấn mạnh một thuật toán nên giải quyết những bài toán tổng quát thay vì giải quyết những bài toán riêng lẻ. Riêng tính hiệu quả của thuật toán đƣợc giới thiệu rất hạn chế ở bậc học phổ thông và nó chủ yếu đƣợc đề cập đến đối với những thuật toán và chƣơng trình mà chúng dễ nhận ra cách tổ chức lại dữ liệu tốt hơn, hoặc có cách cải tiến thuật toán một cách tự nhiên để chƣơng trình chạy nhanh hơn. Việc đánh giá một thuật toán “tốt hơn” so với thuật toán khác dựa vào những đánh giá trực quan, dƣới đây là một ví dụ: Ví dụ 1.3: So sánh hai thuật toán sắp xếp Hai thuật toán cho trong bảng dƣới đây đều thể hiện thuật toán sắp xếp tăng dần dãy số , , ..., cho trƣớc theo phƣơng pháp sắp xếp chọn trực tiếp. Hãy đánh giá, so sánh hai thuật toán này. Thuật toán 1 Thuật toán 2 Bƣớc 1. Với mỗi i nhận giá trị từ 1 Bƣớc 1. Với mỗi i nhận giá trị từ 1 đến n-1 thực hiện các công việc sau: đến n-1 thực hiện công việc sau: Bƣớc 1.1. Khởi gán k  i; Với mỗi j nhận giá trị từ i+1 < thì đổi giá trị của Bƣớc 1.2. Với mỗi j nhận giá đến n, nếu và cho nhau nhƣ sau: trị từ i+1 đến n, nếu < thì gán 10 lại k  j; x ; ai  Bƣớc 1.3. Nếu k ≠ i thì đổi giá Bƣớc 2. Đƣa ra dãy trị của và aj cho nhau nhƣ sau: đƣợc sắp xếp. x  ; Bƣớc 2. Đƣa ra dãy , ;  x; ; , , ..., đã  x; , ..., đã đƣợc sắp xếp. GV có thể phâ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.3. Phát triển năng lực tƣ duy thuật toán 1.3.1. Nguồn gốc của năng lực Từ cuối thế kỉ XIX đến nay đã có nhiều ý kiến khác nhau về bản chất và nguồn gốc của năng lực. Hiện nay đã có xu hƣớng thống nhất trên một số quan điểm cơ bản, quan trọng về lí luận cũng nhƣ thực tiễn.  Một là: Những yếu tố bẩm sinh, di truyền là điều kiện cần thiết ban đầu cho sự phát triển năng lực. Đó là điều kiện cần nhƣng chƣa đủ.  Hai là: Năng lực của con ngƣời có nguồn gốc xã hội, lịch sử. Con ngƣời từ khi sinh ra đã có sẵn những tố chất nhất định cho sự phát triển các năng lực tƣơng ứng, nhƣng nếu không có môi trƣờng xã hội thì cũng không phát triển đƣợc. Xã hội đã đƣợc các thế hệ trƣớc cải tạo, xây dựng và để lại các dấu ấn đó cho các thế hệ sau trong môi trƣờng Văn hóa - Xã hội.  Ba là: Năng lực có nguồn gốc từ hoạt động và là sản phẩm của hoạt động. Sống trong môi trƣờng xã hội tự nhiên do các thế hệ trƣớc tạo ra và chịu sự tác động của nó, con ngƣời ở thế hệ sau không chỉ đơn giản sử dụng hay thích ứng với các thành tựu của các thế hệ trƣớc để lại, mà 11