CHUYÊN ĐỀ: TÌM HIỂU BÀI TOÁN VÀ THUẬT TOÁN
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (201.01 KB, 19 trang ) SỞ GD&ĐT VĨNH PHÚC thể chọn một ngôn ngữ lập trình thích hợp. - Tin học là một môn học mới ở các trường phổ thông nên học sinh còn nhiều bỡ ngỡ khi tiếp cận với môn học này. Nội dung tin học lớp 10 là nền tảng lập trình lớp 11 - một nội dung mới lạ đối với đa số học sinh với nhiều khái niệm, thuật ngữ, cấu trúc dữ liệu mà học sinh mới được tiếp xúc lần đầu. Chính vì vậy mà học sinh dễ mắc sai lầm khi lập trình giải quyết các bài toán. Nguyên nhân dẫn đến những khó khăn mà học sinh thường gặp là rất phong phú nhưng có thể thấy một số nguyên nhân chính sau đây: + Học sinh thường gặp khó khăn khi xác định bài toán. + Khó liên hệ phương pháp giải một bài toán trong toán học với thuật giải trong tin học. - Tuy nhiên mọi thứ điều có điểm khởi đầu của nó, với học sinh việc học, tìm hiểu về bài toán và thuật toán là khởi đầu cho việc tiếp cận ngôn ngữ lập trình bậc cao, qua đó giúp các em có thêm một định hướng, một niềm đam mê về lập trình, về nghề nghiệp mà các em chọn sau này. B. NỘI DUNG CHUYÊN ĐỀ: TÌM HIỂU VỀ BÀI TOÁN VÀ THUẬT TOÁN I. Hệ thống kiến thức sử dụng trong chuyên đề Tiết 1: Bài toán và thuật toán (mức khái niệm) 1 + Khái niệm bài toán + Khái niệm thuật toán + Cách biểu diễn thuật toán + Các tính chất của thuật toán Tiết 2: Bài toán và thuật toán (mức nhận biết) Bài toán tìm GTLN, bài toán giải phương trình bậc 2 Tiết 3, 4, 5: Luyện tập (Vận dụng kiến thức đã học xây dựng thuật toán cho một số bài toán cơ bản) II. Mục tiêu của chuyên đề 1. Kiến thức - Biết khái niệm bài toán và thuật toán, các tính chất của thuật toán. - Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước, - Hiểu một số bài toán thông dụng và. - Xây dựng được thuật toán cho một số bài toán cơ bản. 2. Kĩ năng - Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước - Nhận biết và hình thành ý tưởng giải bài toán để xây dựng thuật toán 3. Thái độ - Giúp học sinh hiểu rõ tầm quan trọng của thuật toán. - Làm cho học sinh yêu thích lập trình, yêu thích môn học hơn. - Tự giác, tích cực, chủ động trong thực hành 4. Định hướng phát triển năng lực - Phát triển năng lực tự học, tự giải quyết các vấn đề gặp phải trong cuộc sống, làm việc nhóm. III. Hình thức, phương pháp, kĩ thuật dạy học - Hình thức: dạy học trên lớp. - Phương pháp, kĩ thuật dạy học: + Đàm thoại. + Làm việc nhóm. + Thuyết trình. + Phát hiện và giải quyết vấn đề, hoạt động cá nhân. IV. Chuẩn bị của giáo viên và học sinh 1. Chuẩn bị của giáo viên - Máy tính, máy chiếu, máy ảnh, giấy A0 2 - Phấn, bảng bút, giáo án word. - Một số thông tin bổ trợ cho chuyên đề. - Bảng kế hoạch phân công, tổ chức nhiệm vụ cho học sinh. 2. Chuẩn bị của học sinh. - Máy tính. - Giấy A4, A0, thước kẻ, bút, băng dính, bút màu... - Sách giáo khoa, vở ghi. V. Thiết kế các hoạt động dạy học Tiết 1: Bài toán và thuật toán Hoạt động 1: Đặt vấn đề (1) Mục tiêu: o Tạo tinh thần thỏa mái, môi trường thân thiện cho học sinh trước khi vào bài học o Tạo động cơ để học sinh có nhu cầu quan tâm, tìm hiểu về bài toán, thuật toán (2) Phương pháp/ kỹ thuật dạy học: hoạt động cá nhân, hoạt động nhóm (3) Phương tiện dạy học: Máy tính, máy chiếu. (4) Sản phẩm: Học sinh có nhu cầu tìm hiểu về bài toán (5) Nội dung: GV đưa ra một số ví dụ và yêu cầu học sinh trả lời câu hỏi: Ví dụ 1: Tính tổng S=1k+2k+….+nk Ví dụ 2: Tìm USCLN và BSCNN của 2 số a, b. Ví dụ 3: Giải phương trình bậc 2: ax2 + bx + c = 0. Mỗi ví dụ trên có phải là một bài toán? Học sinh trả lời. GV dẫn dắt vào bài: Trong Toán học ta nhắc nhiều đến khái niệm "bài toán" và ta hiểu đó là những việc mà con người cần phải thực hiện sao cho từ những dữ kiện đã có phải tìm ra hay chứng minh một kết quả nào đó. Vậy khái niệm "bài toán" trong Tin học có khác gì không? Hoạt động 2: Tìm hiểu khái niệm bài toán (1) Mục tiêu: o Học sinh hiểu được khái niệm bài toán, Input, Output o Hiểu được từ thông tin vào (input) cần tìm được thông tin ra (output) (2) Phương pháp/ kỹ thuật dạy học: Thuyết trình, Hoạt động nhóm (3) Phương tiện dạy học: Máy tính, máy chiếu, máy ảnh (4) Sản phẩm: Học sinh hiểu được bài toán, dữ liệu vào/ra 3 HOẠT ĐỘNG CỦA GIÁO VIÊN HOẠT ĐỘNG CỦA HỌC SINH GV chia lớp thành 4 nhóm 1. Khái niệm bài toán: Dẫn dắt vấn đề: Trong nhà trường có phần mềm quản lý học sinh. Nếu ta yêu cầu đưa ra những học sinh có điểm TB từ 7 trở lên thì đó là bài toán. Hay đơn giản là yêu cầu máy cho ra kết quả của một phép tính nhân, chia, cộng, trừ ... đó cũng là bài toán. - Câu trả lời mong đợi: Trong Tin GV? Theo các em "bài toán" trong Tin học học "bài toán" được hiểu là được hiểu như thế nào ? những việc mà con người muốn máy tính thực hiện. Ví dụ: Giải phương trình, quản lý thông tin về - Nghe và ghi học sinh ... là bài toán. GV? Mỗi nhóm hãy nêu một vài ví dụ về bài - Các nhóm độc lập thảo luận và toán trong Tin học ? đưa ra bài toán GV? Đứng trước một bài toán, công việc đầu - Câu trả lời mong đợi: Công việc tiên là gì? đầu tiên là đi xác định đâu là dữ kiện đã cho vào đâu là cái cần tìm. GV: Rất đúng. Khi máy tính giải bài toán cần - Nghe và ghi quan tâm đến 2 yếu tố: - Input: thông tin đưa vào máy. - Output: thông tin muốn lấy từ máy theo Input. GV: Các nhóm hay đưa ra Input và Output với - Thảo luận. Các nhóm trình bày mỗi bài toán mà các nhóm đã lấy ví dụ ở trên? ví dụ theo yêu cầu GV xét các ví dụ và đề nghị nhận xét. - Nhận xét GV kết luận - Ghi chép Hoạt động 3: Tìm hiểu khái niệm thuật toán 4 (1) Mục tiêu: o Học sinh hiểu được khái niệm thuật toán o Biết cách biểu diễn thuật toán (2) Phương pháp/ kỹ thuật dạy học: Thuyết trình, Hoạt động nhóm (3) Phương tiện dạy học: Máy tính, máy chiếu, máy ảnh (4) Sản phẩm: Học sinh hiểu được bài toán, dữ liệu vào/ra, hình thành ý tưởng xây dựng thuật toán HOẠT ĐỘNG CỦA GIÁO VIÊN HOẠT ĐỘNG CỦA HỌC SINH Chuyển vấn đề: Muốn máy tính đưa ra được Output từ Input đã cho thì cần phải có chương trình, mà muốn viết được chương trình cần có thuật toán. Vậy thuật toán là gì ? 2. Khái niệm thuật toán: GV: để nắm được khái niệm thuật toán là gì, - Các nhóm thảo luận 5 phút và trước hết mời các nhóm hãy trình bày ý tưởng cử đại diện lên bảng trình bày. và cách giải đối với các ví dụ về bài toán mà các nhóm đã lấy ở phần trước? GV: Nhận xét cách giải và dẫn dắt. - HS lắng nghe GV?: Các nhóm đã trình bày chính là thuật - HS trả lời: Thuật toán để giải toán. Vậy thuật toán là gì? 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ự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm. GV giải thích thêm về các khái niệm như: dãy - HS lắng nghe hữu hạn các lệnh, sắp xếp theo một trình tự nhất định. - HS trả lời: Thuật toán dùng để GV? Tác dụng của thuật toán là gì ? giải một bài toán. GV đưa ra ví dụ về bài tìm UCLN của 2 số M, - HS đứng tại chỗ xác định Input N. Xác định Input và Output của bài toán. và Output. 5 HOẠT ĐỘNG CỦA GIÁO VIÊN HOẠT ĐỘNG CỦA HỌC SINH Ví dụ: Thuật toán tìm UCLN của 2 số M và N: Input: 2 số nguyên dương M, N Output: UCLN của 2 số M và N GV: ghi thuật toán lên bảng. - Nghe và ghi B1: Nhập M, N B2: Nếu M = N thì UCLN là M (hoặc N) B5 B3: Nếu M > N thì M M - N, quay lại B2 B4: N N - M rồi quay lại B2 B5: Đưa ra kết quả UCLN rồi kết thúc - Nghe và ghi GV: lấy ví dụ cụ thể với 2 số (12 , 8) và giải thích thuật toán qua từng bước: B1: Nhập M = 12, N = 8 M > N B3: M = 12 - 8 = 4, N = 8 N > M B4: M = 4, N = 8 - 4 = 4 M = N UCLN(12 , 8) = 4 - Nghe và ghi GV: cách viết thuật toán theo từng bước như trên gọi là cách liệt kê. Ngoài ra thuật toán còn được diễn tả bằng sơ đồ - Nghe và ghi khối với các quy định. - Các thao tác nhập xuất dữ liệu - Thao tác so sánh - Các phép toán - Quy định trình tự các thao tác GV: lấy lại ví dụ tìm UCLN của 2 số M và N GV trình chiếu sơ đồ thuật toán lên. Chỉ cho HS - Nghe, quan sát và vẽ sơ đồ 6 HOẠT ĐỘNG CỦA GIÁO VIÊN thấy các bước thực hiện của thuật toán được mô tả trong sơ đồ. HOẠT ĐỘNG CỦA HỌC SINH - HS ghi lại sơ đồ thuật toán và hình dung ra các bước giải của thuật toán - HS lên bảng điền lại các ghi chú và giải thích vì sao lại điền thế. GV: xoá các ghi chú Đ, S trên sơ đồ, yêu cầu 1 HS viết lại và giải thích vì sao ? GV? Dựa vào thuật toán vừa xây dựng cho các bài toán mà các nhóm đã đưa ra, hãy nêu các - Các nhóm thảo luận, dựa vào tính chất của thuật toán? SGK và đưa ra tính chất đối với * Các tính chất của thuật toán: bài toán đã lấy ví dụ và xây dựng - Tính xác định: các bước giải phải rõ ràng thuật toán không gây ra sự lẫn lộn hoặc nhập nhằng. - Lắng nghe và ghi - Tính dừng: Thuật toán phải dừng lại sau một số bước giải. - Tính đúng: Kết quả sau khi thực hiện thuật giải phải là kết quả đúng dựa theo một định nghĩa hoặc một kết quả cho trước. - Tính hiệu quả: + Phải sử dụng dung lượng bộ nhớ là nhỏ nhất. + Số phép toán ít nhất. + Thuật toán dễ hiểu không? + Dễ khai báo trên máy tính. Hoạt động 4: Luyện tập vận dụng 7 (1) Mục tiêu: Học sinh vận dụng được kiến thức đã học nêu được ý tưởng viết thuật toán cho bài toán cụ thể (2) Phương pháp/ kỹ thuật dạy học: Hoạt động nhóm/ hoạt động cá nhân (3) Phương tiện: Máy tính, máy chiếu, giấy A4, máy ảnh (4) Sản phẩm: Báo cáo kết quả hoạt động của nhóm mình Hoạt động của giáo viên GV giao nhiệm vụ cho HS: Nhóm 1: Trình bày thuật toán giải bài toán Tính tổng S=1k+2k+….+nk Hoạt động của học sinh Các nhóm thảo luận + Xác định bài toán + Nêu ý tưởng giải bài toán + Viết thuật toán theo cách liệt kê, sơ đồ khối hoặc cả 2 cách Nhóm 2: Trình bày thuật toán giải bài toán tìm USCLN và BSCNN của 2 số (Trường hợp hết thời gian GV a, b hướng dẫn học sinh thực hiện ở Nhóm 3: Trình bày thuật toán giải bài nhà) toán Giải PTB2 ax2 + bx + c = 0 Nhóm 4: Trình bày thuật toán giải bài toán Giải PT ax + b = 0 GV kiểm tra kết quả thực hiện của HS. Hoạt động 5: Hoạt động mở rộng (1) Mục tiêu: Giúp học sinh luyện tập sâu hơn về ý tưởng xây dựng thuật toán. (2) Phương pháp/ kỹ thuật dạy học: Hoạt động cá nhân tại nhà (3) Phương tiện: SGK (4) Sản phẩm: Học sinh xây dựng được thuật toán Hoạt động của giáo viên GV đưa ra bài toán: Nhập vào từ bàn phím hai số nguyên dương M và N (M |