Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị

Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU

1. Về kiến thức

Sau bài học này, HS sẽ:

- Biết cách thiết kế và viết chương trình giải một số bài toán theo kĩ thuật chia để trị.

- Thực hành viết chương trình giải một số bài toán theo kĩ thuật chia để trị.

2. 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.

3. 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.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đố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.

- Sử dụng phần mềm mô phỏng thuật toán để minh họa thêm trong quá trình giảng dạy.

2. Đố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

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu:

- HS làm quen với các bài toán sẽ được học thiết kế trong bài.

- Kích thích sự tò mò cho người học.

b. Nội dung: GV cho các nhóm HS trao đổi câu hỏi Mở đầu.

c. 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.

d. Tổ chức thực hiện:

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV đặt câu hỏi yêu cầu HS thảo luận: Cho một dãy số A bất kì. Để xác định một số C cho trước xuất hiện trong dãy A bao nhiêu lần thì làm 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: Hôm nay, chúng ta sẽ vận dụng những kiến thức đã học về thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị. - Bài 8: Thực hành thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị.

B. HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động: Thực hành

a. Mục tiêu: Viết được chương trình thiết kế thuật toán tìm kiếm theo kĩ thuật chia để trị.

b. Nội dung: GV yêu cầu HS tìm hiểu nhiệm vụ, tìm hiểu yêu cầu và các bước thực hiện.

c. Sản phẩm học tập: Các chương trình mà HS viết ra.

d. 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 giới thiệu bài toán: Tìm số lần lặp của một giá trị trên dãy đã sắp xếp. Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Hãy tìm xem trong dãy trên có bao nhiêu phần tử có giá trị bằng C. Ví dụ, nếu A = [0, 1, 2, 2, 2, 2 ,4 ,5 ,5 ,6], C = 2 thì kết quả cần tìm là 4. - GV yêu cầu HS thảo luận theo nhóm đôi, trình bày và thực hiện cài đặt phương án giải đầu tiên của bài toán với thuật toán tìm kiếm tuần tự. - GV gợi ý: Cách giải này sẽ có độ phức tạp thời gian O(n), với n là kích thước dãy đầu vào. - GV giới thiệu ý tưởng chia để trị của bài toán dựa trên thuật toán tìm kiếm nhị phân. - GV phân công các nhóm tìm hiểu và trình bày thuật toán. - GV giải thích nhanh cách tính thời gian của thuật toán này và kết luận: Độ phức tạp thời gian của thuật toán chỉ là O(logn), nhanh hơn hẳn so với cách tìm bằng phương pháp tìm kiếm tuần tự. Bước 2: HS thực hiện nhiệm vụ học tập - HS chia nhóm, thảo luận thực hiện theo các bước SGK. - GV hướng dẫn, theo dõi, hỗ trợ HS khi cần. Bước 3: Báo cáo kết quả hoạt động và thảo luận - GV mời đại diện một số nhóm trình bày kết quả Nhiệm vụ. - HS xung phong thực hiện các nhiệm vụ và giải thích. - GV mời HS nhóm khác nhận xét, bổ sung. Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nhận xét, tổng kết, chuyển sang nội dung luyện tập.

Thực hành Nhiệm vụ - Ý tưởng: Trước tiên, nhận xét rằng bài tập này có thể dễ dàng giải bằng phương pháp tìm kiếm tuần tự đã quen biết. Gọi count là số lần xuất hiện của C trong dãy. Thực hiện tìm kiếm tuần tự với C, mỗi lần tìm thấy C, tăng biến count lên 1. - Chương trình đơn giản như sau: - Thuật toán trên có một vòng lặp tại dòng 3 thực hiện n lần (n = len(A)), do đó thời gian chạy là O(n). - Chương trình hoàn chỉnh có thể như sau: - Lệnh gọi đệ quy của hàm tìm kiếm là: countNum(A,0,len(A) – 1,C) Nhận xét: - Chương trình trên hoàn toàn tương tự thuật toán tìm kiếm nhị phân, điểm khác biệt tại các dòng lệnh từ 6 đến 13 khi xử lí trường hợp A[mid] = C. - Các dòng 2, 3 là phần cơ sở của đệ quy. - Việc "chia" được thực hiện tại dòng 5. Các lệnh tiếp theo chính là "trị". Bài toán này khá đơn giản nên sau khi "trị" sẽ thu được luôn kết quả. - Trong hầu hết các trường hợp việc xử lí tại dòng 6 đến dòng 13 sẽ mất O(1) thời gian. Trong một số trường hợp xấu nhất, ví dụ dãy ban đầu bao gồm toàn các số C thì việc xử lí khi A[mid] = C sẽ mất O(n) thời gian.

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 11 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 11 Bài 9: Sắp xếp trộn

• Giáo án Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

• Giáo án Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

• Giáo án Chuyên đề Tin học 11 Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

• Giáo án Chuyên đề Tin học 11 Bài 13: Kĩ thuật duyệt quay lui

---