Tải bản chuẩn giáo án chuyên đề Khoa học máy tính 11 KNTT Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
Tải về bản chuẩn giáo án chuyên đề học tập Khoa học máy tính 11 bộ sách mới kết nối tri thức Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị. Giáo án soạn chi tiết, hướng dẫn học sinh hoạt động để tìm tòi, khám phá ra kiến thức mới, vận dụng chúng vào việc giải quyết các vấn đề của học tập và của thực tiễn cuộc sống. Mời thầy cô kéo xuống tham khảo
Rõ nét về file powerpoint trình chiếu. => Xem thêm
Ngày soạn:…/…/…
Ngày dạy:…/…/…
BÀI 7. THIẾT KẾ THUẬT TOÁN THEO KĨ THUẬT CHIA ĐỂ TRỊ
- MỤC TIÊU
- Về kiến thức
Sau bài học này, HS sẽ:
- Biết và thực hiện được một số thiết kế thuật toán bằng kĩ thuật chia để trị.
- Thực hành được thiết kế một số bài toán sử dụng kĩ thuật chia để trị đơn giản.
- Năng lực
Năng lực chung:
- Năng lực tự chủ: Biết lựa chọn các nguồn tài liệu học tập phù hợp.
- Năng lực giải quyết vấn đề và sáng tạo: Xác định và tìm hiểu được các thông tin liên quan đến vấn đề, đề xuất giải pháp giải quyết vấn đề trong bài học.
- Năng lực giao tiếp và hợp tác: Thực hiện tốt nhiệm vụ trong hoạt động nhóm.
Năng lực tin học:
- Hình thành, phát triển năng lực giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.
- Phẩm chất:
- Hình thành ý thức trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
- Có ý thức vận dụng kiến thức, kĩ năng đã học ở nhà trường vào thực tiễn.
- THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
- Đối với giáo viên
- SGK, SGV, Giáo án;
- Máy tính đã cài đặt Python và máy chiếu;
- Hình ảnh, sơ đồ minh họa cho các bước thực hiện trên một mẫu dữ liệu đơn giản hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh họa.
- Đối với học sinh
- SGK, vở ghi.
- Điện thoại có cài sẵn phần mềm Python (nếu có).
III. TIẾN TRÌNH DẠY HỌC
- HOẠT ĐỘNG KHỞI ĐỘNG
- Mục tiêu:
- HS làm quen các bài toán có liên quan đến thiết kế thuật toán theo kĩ thuật chia để trị.
- Kích thích sự tò mò cho người học.
- Nội dung: GV cho các nhóm HS trao đổi để nhận ra các tính chất chung nhất của các bài toán này.
- Sản phẩm học tập: HS dựa vào kiến thức và hiểu biết cá nhân để đưa ra câu trả lời.
- Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ học tập
- GV đặt vấn đề: Trong bài học này em sẽ thiết kế lời giải cho hai bài toán sau:
- Bài toán tính lũy thừa exp(a, n) = an với a là số bất kì (khác 0), n là số nguyên không âm, ở đây an được hiểu là tích của n lần giá trị: an = a a … a (n lần).
- Ban Giám hiệu nhà trường cần tìm một bạn lớp em có chiều cao đúng bằng 1,7 m hoặc gần với chiều cao đó nhất để tham gia tập đội hình thể thao.
- GV đặt câu hỏi yêu cầu HS thảo luận: Với hai bài toán trên em sẽ thực hiện như thế nào?
Bước 2: HS thực hiện nhiệm vụ học tập
- HS lắng nghe, suy nghĩ và đưa ra câu trả lời.
Bước 3: Báo cáo kết quả hoạt động và thảo luận
- GV mời HS trả lời câu hỏi.
- Các HS khác nhận xét, nêu ý kiến khác (nếu có).
Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập
- GV nhận xét, đánh giá, tuyên dương câu trả lời của HS.
- GV dẫn dắt vào nội dung bài mới: Để trả lời cho câu hỏi này, chúng ta vào bài học ngày hôm nay - Bài 7. Thiết kế thuật toán theo kĩ thuật chia để trị.
- HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1. Tìm hiểu bài toán tính lũy thừa
- Mục tiêu: HS hiểu được cách thiết lập thuật toán tính lũy thừa nhanh bằng chia để trị.
- Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 1 SGK trang 33, đọc thông tin mục 1, thảo luận nhóm và xây dựng kiến thức mới.
- Sản phẩm học tập: HS nêu được cách giải bài toán tính lũy thừa bằng chia để trị và trả lời được các Câu hỏi củng cố kiến thức SGK trang 34.
- Tổ chức hoạt động:
|
HOẠT ĐỘNG CỦA GV - HS |
DỰ KIẾN SẢN PHẨM |
|
Bước 1: GV chuyển giao nhiệm vụ học tập - GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 33: Hãy thiết lập thuật toán và chương trình tính lũy thừa an với a là số bất kì khác 0, n là số nguyên không âm. - GV mô tả bài toán và yêu cầu các nhóm giải bài toán bằng cách tính thông thường, bằng tay và chương trình. - GV giới thiệu ý tưởng mới giải bài toán tính lũy thừa theo kĩ thuật chia để trị. - Sau khi thực hiện việc cài đặt chương trình, GV cho các nhóm thảo luận về độ phức tạp thời gian của thuật toán. - GV kết luận về nội dung độ phức tạp thời gian của thuật toán. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr34) để củng cố kiến thức: + Câu 1: Mô tả các bước tính bằng tay phép tính lũy thừa 211 theo hai chương trình trên. Các nào nhanh hơn? + Câu 2: Phép tính a21 sẽ cần dùng bao nhiêu phép nhân? Bước 2: HS thực hiện nhiệm vụ học tập - Các nhóm HS tìm hiểu lời giải của bài toán tính lũy thừa bằng chia để trị trong SGK. - HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi. - GV theo dõi, hỗ trợ HS trong quá trình học tập. Bước 3: Báo cáo kết quả hoạt động và thảo luận - GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình. - Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr34) Câu 1: Tính tay 211. - Tính theo phương pháp cũ. Cần thực hiện 10 lần phép nhân với 2. - Tính theo phương pháp chia để trị mới. Bước 1. Tính 2 x 2 = 22 Bước 2. Tính 4 x 4 = 24 Bước 3. Tính 24 x 2 = 25 Bước 4. Tính 25 x 25 = 210 Bước 5. Tính 210 x 2 = 211 Vậy theo cách tính mới chỉ cần 5 phép nhân. Câu 2: Tính a21 a21 = a x a10 x a10 Theo bài trên, tính a10 cần 4 phép nhân, vậy suy ra cần 4 + 2 = 6 phép nhân cho a21. - Các HS còn lại nhận xét, bổ sung (nếu có). Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt. - GV tổng kết lại nội dung. - GV chuyển sang nội dung tiếp theo. |
1. Bài toán tính lũy thừa - Hoạt động 1 Vì an = a x an-1 nên có thể thiết lập ngay chương trình tính hàm lũy thừa đơn giản như sau: Chương trình 1. Tính lũy thừa theo cách tự nhiên. Chương trình 2. Tính lũy thừa theo cách nhị phân nhanh (chia để trị). *Kết luận - Hàm exp(a,n) trên được thiết lập theo kĩ thuật chia để trị có độ phức tạp thời gian O(logn). |
Hoạt động 2. Tìm hiểu bài toán tìm kiếm nhị phân mở rộng
- Mục tiêu: HS hiểu được bài toán và cách giải theo kĩ thuật chia để trị của bài toán tìm kiếm nhị phân mở rộng.
- Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 2 SGK trang 34, đọc thông tin mục 2, thảo luận nhóm và xây dựng kiến thức mới.
- Sản phẩm học tập: HS nêu được cách giải bài toán tìm kiếm nhị phân mở rộng bằng chia để trị và trả lời được các Câu hỏi củng cố kiến thức SGK trang 36.
- Tổ chức hoạt động:
|
HOẠT ĐỘNG CỦA GV - HS |
DỰ KIẾN SẢN PHẨM |
|
Bước 1: GV chuyển giao nhiệm vụ học tập - GV chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 2 SGK trang 34: Xây dựng thuật toán cho bài toán sau: Cho trước dãy các số đã được sắp xếp tăng dần. Với giá K cho trước cần tìm phần tử của dãy gốc có giá trị gần với K nhất. - GV mô tả bài toán và yêu cầu các nhóm trao đổi, thực hiện bài toán theo cách tìm kiếm tuần tự, tức là thuật toán tự nhiên. - Sau đó, GV thiết kế theo phương pháp chia để trị, cách làm này sẽ là một mở rộng của thuật toán tìm kiếm nhị phân đã biết từ các bài trước. - GV kết luận về bài toán tìm kiếm nhị phân mở rộng. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr36) để củng cố kiến thức: + Câu 1: Hãy giải thích kĩ hơn chương trình 2 ở trên tại các dòng 4 và 6. + Câu 2: Nêu những điểm khác biệt của chương trình trên với chương trình tìm kiếm nhị phân đã biết. Bước 2: HS thực hiện nhiệm vụ học tập - Các nhóm HS tìm hiểu lời giải của bài toán tìm kiếm nhị phân mở rộng trong SGK. - HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi. - GV theo dõi, hỗ trợ HS trong quá trình học tập. Bước 3: Báo cáo kết quả hoạt động và thảo luận - GV mời đại diện các nhóm trình bày kết quả thảo luận của nhóm mình. - Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr36) Câu 1: - Dòng 4 mô tả trường hợp A có một phần tử thì đáp số luôn là phần tử duy nhất này. - Dòng 6 mô tả trường hợp A có hai phần tử, đáp án sẽ là phần tử nào gần K hơn về giá trị. Câu 2: Chương trình trên khác thuật toán tìm kiếm nhị phân như sau: - Cách xử lí các trường hợp cơ sở khi A có 1 hoặc 2 phần tử. - Sau mỗi bước lặp (hoặc sau mỗi lần gọi đệ quy), phạm vi tìm kiếm sẽ tìm tiếp ở một trong hai khoảng [mid, right] hay [left, mid], điều này khác biệt với tìm kiếm nhị phân là sau mỗi vòng lặp miền tìm kiếm sẽ là [left, mid – 1] hoặc [mid + 1, right]. - Các HS còn lại nhận xét, bổ sung (nếu có). Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt. - GV tổng kết lại nội dung. - GV chuyển sang nội dung luyện tập. |
2. Bài toán tìm kiếm nhị phân mở rộng - Hoạt động 2 Chương trình 1. Sử dụng tìm kiếm tuần tự Chương trình 2. Sử dụng tìm kiếm nhị phân *Kết luận - Thuật toán tìm kiếm nhị phân mở rộng có độ phức tạp thuật toán O(logn). |
- HOẠT ĐỘNG LUYỆN TẬP
- Mục tiêu: HS vận dụng kiến thức, hoàn thành bài tập phần Luyện tập.
- Nội dung: GV giao nhiệm vụ, HS thảo luận.
- Sản phẩm học tập: HS áp dụng kiến thức về thiết kế thuật toán theo kĩ thuật chia để trị để giải các bài toán.
- Tổ chức thực hiện:
--------------- Còn tiếp ---------------
MỘT VÀI THÔNG TIN
- Giáo án tải về là giáo án bản word, dễ dàng chỉnh sửa nếu muốn
- Font chữ: Time New Roman, trình bày rõ ràng, khoa học.
- Tất cả các bài đều soạn như mẫu ở trên
THỜI GIAN BÀN GIAO GIÁO ÁN:
- Nhận đủ cả năm ngay và luôn
PHÍ GIÁO ÁN:
- Phí giáo án: 350k/cả năm
CÁCH ĐẶT TRƯỚC:
- Bước 1: gửi phí vào tk: 10711017 - Chu Văn Trí - Ngân hàng ACB (QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo đặt trước
Từ khóa tìm kiếm:
Tải giáo án chuyên đề Khoa học máy tính 11 KNTT, giáo án chuyên đề học tập Khoa học máy tính 11 Kết nối Bài 7: Thiết kế thuật toán theo kĩ, soạn giáo án chuyên đề Khoa học máy tính kết nối Bài 7: Thiết kế thuật toán theo kĩ