Kênh giáo viên » Giáo án chuyên đề Tin học 11 Định hướng khoa học máy tính kết nối tri thức

Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 9: Sắp xếp trộn (P1)

Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 11 - Định hướng Khoa học máy tính bộ sách kết nối tri thức Bài 9: Sắp xếp trộn (P1). Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghệ nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng, mời quý thầy cô tham khảo bài demo.

Hướng dẫn tải giáo án

Xem toàn bộ: Giáo án chuyên đề Tin học 11 Khoa học máy tính kết nối tri thức đủ cả năm

Ngày soạn:…/…/…

Ngày dạy:…/…/…

BÀI 9. SẮP XẾP TRỘN

MỤC TIÊU
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.

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:

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

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 đề: 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.

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

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

- 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 – tr41)

Câu 1: Thực hiện bằng tay trộn hai dãy B = 1, 4, 7 và C = 2, 3, 6.

Mỗi bước sau mô tả một thao tác đơn thực hiện trộn hai dãy B, C, kết quả trả về dãy mới A.

Bước 1. Đưa 1 vào A.

Bước 2. Đưa 2 vào A.

Bước 3. Đưa 3 vào A.

Bước 4. Đưa 4 vào A.

Bước 5. Đưa 6 vào A.

Bước 6. Đưa 7 vào A.

Kết thúc dãy A sẽ là 1, 2, 3, 4, 6, 7.

Câu 2: Thực hiện sắp xếp trộn dãy 3, 2, 7, 1, 6, 5 theo sơ đồ.

- 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. Ý 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ị.

Hoạt động 2. Tìm hiểu mô tả thuật toán sắp xếp trộn

Mục tiêu: HS hiểu rõ các bước chính của sắp xếp trộn.
Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 2 SGK trang 41, đọ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 mô tả được 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 43.
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 41:

Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn.

- GV yêu cầu các nhóm thảo luận về các bước chính của sắp xếp trộn.

- GV chốt lại: Có thể hiểu sắp xếp trộn luôn bao gồm hai quá trình:

(1) Tách dãy gốc thành hai dãy con với mỗi dãy con có kích thước ½ dãy ban đầu. Dùng đệ quy để sắp xếp hai dãy con này.

(2) Sau đó, dùng thuật toán trộn để trộn hai dãy con đã sắp xếp thành dãy ban đầu nhưng đã được sắp xếp.

Thuật toán sắp xếp trộn được mô tả tổng quát như sau:

Trong đó lệnh 6 chính là thuật toán "trộn" đóng vai trò rất quan trọng của sắp xếp trộn.

- GV phân tích để HS hiểu được bản chất và ý nghĩa 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 – tr43) để củng cố kiến thức:

+ Câu 1: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại dòng 6 có nhiều nhất là bao nhiêu bước lặp?

+ Câu 2: Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một phần 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 các bước thực hiệ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

- 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 – tr43)

Câu 1: Vòng lặp 6 có nhiều nhất là m + n bước lặp.

Câu 2: Nếu dãy gốc có 1 phần tử thì thuật toán sắp xếp trộn sẽ không thực hiện gì và trả về ngay dãy gốc.

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

2. Mô tả thuật toán sắp xếp trộn

- Hoạt động 2

a) Thuật toán trộn hai dãy (merge algorithm)

- Giả sử cho trước hai dãy đã được sắp thứ tự B và C có số phần tử lần lượt là m, n. Thuật toán merge(B, C) sẽ được thực hiện "trộn" hai dãy trên và đưa kết quả vào dãy A. Quy trình trộn này rất tự nhiên và được minh họa trong sơ đồ hình 9.2

Thuật toán 1. Thuật toán trộn hai dãy

b) Thuật toán sắp xếp trộn (mergeSort)

- Thuật toán sắp xếp trộn được mô tả bởi hàm mergeSort(A) trong chương trình sau.

Thuật toán 2. Thuật toán sắp xếp trộn

- Đoạn chương trình sau sẽ thực hiện sắp xếp dãy A và đưa kết quả đã sắp xếp vào dãy B. Lời gọi hàm đệ quy là:

1 A = [2, 1, 10, 0, -7, -20, 19, 100, -3, -2, 9, 11]

2 B = mergeSort(A)

*Kết luận

- Thuật toán sắp xếp trộn sẽ bao gồm một hàm mergeSort(), hàm này sẽ tiến hành các bước chính của thuật toán và gọi hàm trộn hai dãy đã sắp xếp merge() khi thực hiện bước kết hợp.

Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II