Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 9: Sắp xếp trộn

Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 9: Sắp xếp trộn

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 và trình bày được cách thiết kế thuật toán sắp xếp trộn bằng kĩ thuật chia để trị.

- Thực hiện được lập trình theo thuật toán sắp xếp trộn.

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 hoặc có thể sử dụng các phần mềm mô phỏng thuật toán để minh họa.

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:

- Hướng sự tò mò của học sinh muốn tìm hiểu một thuật toán sắp xếp khác tốt hơn hẳn các thuật toán sắp xếp khác tốt hơn hẳn các thuật toán sắp xếp đã biết như thuật toán sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt.

- Kĩ thuật hướng đến chính là chia để trị.

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

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 vấn đề: Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp thời gian tốt hơn so với các thuật toán tìm kiếm trên dãy chưa sắp xếp. Chính vì thế, việc sắp xếp thông tin theo một trình tự nào đó luôn đóng vai trò quan trọng trong các bài toán tìm kiếm thông tin. Tuy nhiên, một số thuật toán sắp xếp mà em đã biết như sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt, ... đều có độ phức tạp thời gian O (n² ) (n - kích thước dãy cần sắp xếp). Câu hỏi đặt ra là: Liệu có hay không một cách sắp xếp dãy với thời gian tốt hơn O (n²)?

- GV đặt câu hỏi yêu cầu HS thảo luận: Liệu kĩ thuật chia để trị có thể áp dụng cho bài toán sắp xếp được không? Nếu có thì có làm tăng hiệu quả của sắp xếp được không?

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 9. Sắp xếp trộn.

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

Hoạt động 1. Tìm hiểu ý tưởng thuật toán sắp xếp trộn

a. Mục tiêu: HS hiểu được ý tưởng chính, gốc của sắp xếp trộn.

b. Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 1 SGK trang 40, đọc thông tin mục 1, thảo luận nhóm và xây dựng kiến thức mới.

c. Sản phẩm học tập: HS nêu được ý tưởng thuật toán sắp xếp trộn và trả lời được các Câu hỏi củng cố kiến thức SGK trang 41.

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 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 40: Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn để biết thuật toán này là mô hình kĩ thuật chia để trị. Em có nhận xét gì về đặc thù của các giai đoạn 1, 2, 3 trong sơ đồ dưới đây? - GV yêu cầu các nhóm quan sát và thực hiện ý tưởng chính của sắp xếp trộn theo sơ đồ hình 9.1 - GV nêu ý nghĩa của việc trộn: Trộn hai dãy đã sắp xếp thành một dãy lớn hơn cũng sẽ được sắp xếp. - GV giao cho các nhóm nghiên cứu và mô tả ú tưởng của sắp xếp trộn theo ba bước Chia, Trị và Kết hợp. - GV kết luận về ý tưởng chia để trị của sắp xếp trộn. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr41) để củng cố kiến thức: + Câu 1: Hãy thực hiện thao tác trộn hai dãy sau: B = 1, 4, 7; C = 2, 3, 6. + Câu 2: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước tương tự trê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 ý tưởng thuật toán sắp xếp trộn 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

1. Ý tưởng thuật toán sắp xếp trộn - Hoạt động 1 Giai đoạn 1. Từ dãy gốc ban đầu chúng ta tách chia đôi làm hai dãy con, mỗi dãy con có kích thước bằng ½ kích thước của dãy gốc. Quá trình này chính là bước Chia của kĩ thuật chia để trị. Giai đoạn 2. Khi tất cả các dãy con thu được đều chỉ còn một phần tử. Tất cả các dãy này hiển nhiên đều đã được sắp xếp đúng. Đây chính là bước Trị tương ứng của chiến lược chia để trị. Giai đoạn 3. Từ các dãy đã sắp xếp xong, chúng ta sẽ trộn chúng lại với nhau, mỗi lần trộn hai dãy đã sắp xếp để tạo thành một dãy lớn hơn cũng được sắp xếp đúng. Quá trình trộn sẽ kết thúc khi nhân được đúng một dãy chính là dãy ban đầu nhưng đã sắp xếp xong. Đây chính là quá trình Kết hợp tương ứng của kĩ thuật chia để trị. *Kết luận Ý tưởng của thuật toán sắp xếp trộn được thực hiện qua 3 bước: Chia nhỏ dãy gốc thành các dãy với kích thước nhỏ hơn (bằng ½ dãy ban đầu), tiếp tục cho đến khi nhận được các dãy con đã sắp xếp đúng thì tiến hành trộn các dãy này để nhận được kết quả cuối cùng. Các bước trên chính là kĩ thuật chia để trị.

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

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

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

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

• Giáo án Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui

---