Chuyên đề Khoa học máy tính 11 cánh diều: Tải giáo án bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn (P1)

Mẫu giáo án chuyên đề khoa học máy tính 11 cánh diều. Chi tiết chuyên đề bài 4 Kĩ thuật chia để trị trong thuật toán sắp xếp trộn (P1). Giáo án được biên soạn chi tiết. Có thể tải về tham khảo. Cách tải nhanh chóng, dễ dàng. Ngoài ra, hệ thống có đủ giáo án các bài khác của chuyên đề khoa học máy tính 11 cánh diều

Nội dung giáo án

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

Ngày dạy: .../.../...

BÀI 4. KĨ THUẬT CHIA ĐỂ TRỊ TRONG THUẬT TOÁN SẮP XẾP TRỘN

(2 tiết)

MỤC TIÊU
Kiến thức

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

Hiểu được các bước cần thực hiện khi giải bài toán sắp xếp dãy số bằng thuật toán sắp xếp trộn.
Biết được cách cài đặt thuật toán sắp xếp trộn.
Nêu được ý tưởng kĩ thuật chia để trị tổng quát bằng đệ quy.
Biết được các bước cơ bản của kĩ thuật chia để trị để giải một bài toán.

Năng lực

Năng lực chung:

Năng lực giao tiếp và hợp tác: biết chủ động trong giao tiếp, tự tin phát biểu ý kiến của bản thân về kĩ thuật chia để trị trong thuật toán sắp xếp trộn.
Năng lực tự chủ và tự học: Xác định được nhiệm vụ học tập Chuyên đề môn Tin học 11 – Khoa học máy tính qua việc tìm hiểu
Năng lực giải quyết vấn đề và sáng tạo: Vận dụng các kiến thức giải quyết được các vấn đề liên quan.

Năng lực riêng:

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: Xác định được các bước cần thực hiện, cách cài đặt khi giải bài toán sắp xếp dãy số bằng thuật toán sắp xếp chọn và ý tưởng, các bước cơ bản của kĩ thuật chia để trị.

'2. Phẩm chất

Chăm chỉ: có ý thức đánh giá điểm mạnh, điểm yếu của bản thân, thuận lợi, khó khăn trong học tập để xây dựng kế hoạch học tập; tích cực tìm tòi và sáng tạo trong học tập, có ý chí vượt qua khó khăn để đạt kết quả tốt trong học tập.
Trách nhiệm: tích cực, tự giác và nghiêm túc rèn luyện, tu dưỡng đạo đức; sẵn sàng chịu trách nhiệm về lời nói và hành động của bản thân.

THIẾT BỊ DẠY HỌC
Đối với giáo viên

Giáo án, sách CĐHT, SGV Tin học 11 – Khoa học máy tính bộ Cánh diều.
Máy tính cá nhân có cài đặt phần mềm mô phỏng thuật toán, máy chiếu, màn hình chiếu.

Đối với học sinh

Vở ghi, sách CĐHT Tin học 11 – Khoa học máy tính bộ Cánh diều.
Tư liệu có liên quan đến nội dung bài học và dụng cụ học tập.

III. TIẾN TRÌNH DẠY HỌC

HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU)
a) Mục tiêu: Khơi dậy sự tò mò của HS muốn tìm hiểu một thuật toán sắp xếp khác tốt hơn các thuật toán đã học trong các bài trước. Kĩ thuật hướng đến chính là chia để trị.
b) Nội dung: HS trả lời câu hỏi mở đầu có nội dung liên quan đến bài học.
c) Sản phẩm: HS trình bày các bước sắp xếp một dãy số gồm 4 phần tử bằng cách chia làm hai nửa dãy, sắp xếp mỗi nửa dãy theo chiều tăng dần và ghép hai nửa dãy đã sắp xếp lại thành dãy hoàn chỉnh sắp xếp theo chiều tăng dần.
d) Tổ chức thực hiện:

Bước 1: Chuyển giao nhiệm vụ:

- GV yêu cầu HS trả lời câu hỏi phần Khởi động trang 38 sách CĐHT:

Bài 2 giới thiệu kĩ thuật đệ quy trong phương pháp chia để trị. Nhiều bài được giải quyết dễ dàng bằng cách sử dụng kĩ thuật đệ quy. Ví dụ: Em hãy chia đôi dãy gồm bốn số (7, 3, 8, 2) làm hai nửa để thực hiện công việc sắp xếp bốn số này theo thứ tự tăng dần của giá trị.

Gợi ý: 7 3 8 2 -> 3 7 2 8 -> 2 3 7 8

Bước 2: Thực hiện nhiệm vụ học tập:

- HS đọc SGK, thực hiện công não để có câu trả lời cho các câu hỏi.

Bước 3: Báo cáo, thảo luận:

- Các học sinh xung phong phát biểu trả lời.

Bước 4: Kết luận và nhận xét:

- GV nhận xét, đánh giá và dẫn vào bài: Trong bài học này các em sẽ được học một ví dụ điển hình của phương pháp chia để trị là thuật toán sắp xếp trộn dùng kĩ thuật đệ quy: Bài 4. Kĩ thuật chia để trị trong thuật toán sắp xếp trộn.

HÌNH THÀNH KIẾN THỨC MỚI

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: Nêu được ý tưởng chính, gốc của sắp xếp trộn.
b) Nội dung: HS thảo luận, đọc sách CĐHT trang 38-40 để tìm hiểu nội dung ý tưởng thuật toán sắp xếp trộn.
c) Sản phẩm: Nêu được các bước cơ bản của kĩ thuật chia để trị cho thuật sắp xếp trộn.
d) Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

- GV yêu cầu HS đọc nội dung trang 38 sách CĐHT và trả lời câu hỏi sau:

Thầy giáo lớp Thanh An mời 5 bạn học sinh lên bảng, xếp ngẫu nhiên thành một hàng ngang, từ trái sang phải là các bạn có tên Thi, An, Hòa, Lâm, Mai. Em hãy giúp thầy giáo yêu cầu 5 bạn thực hiện lần lượt các bước trong hai giai đoạn sau để sắp xếp thành hàng tăng dần theo chiều cao từ trái sang phải.

- GV mời 5 bạn có chiều cao tương đối khác nhau lên bảng và thực hiện các bước hoạt động như mô tả trong sách CĐHT.

+ Giai đoạn 1: Ở giai đoạn này, với mỗi lượt, mỗi dãy được chia làm hai dãy nhỏ với mục tiêu sắp xếp tăng dần trên từng dãy nhỏ. Quá trình kết thúc khi mỗi dãy có đúng một bạn.

+ Giai đoạn 2: Ở giai đoạn này, với mỗi lượt, cứ hai dãy liên tiếp được tách ra từ Giai đoạn 1 theo trình tự lượt ngược lại 3, 2, 1 sẽ được kết hợp lại thành một dãy. Sau mỗi lượt, các bạn trong từng dãy nhỏ có chiều cao tăng dần.

- GV hướng dẫn HS phân tích và rút ra các đặc trưng của 3 bước cơ bản trong kĩ thuật chia để trị: Chia, Trị, Kết hợp.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

1. Ý tưởng thuật toán sắp xếp trộn

- Thầy giáo lớp Thanh An chia dần 5 bạn thành các dãy nhỏ giúp việc sắp xếp vị trí các bạn tăng dần theo chiều cao trở nên thuận lợi và dễ dàng. Cách làm trên của thầy giáo thể hiện ba bước cơ bản của kĩ thuật chia để trị cho hoạt động trên như sau:

1. Chia: Chia một dãy thành 2 dãy nhỏ.

2. Trị: Sắp xếp mỗi dãy nhỏ theo cách giống như sắp xếp ban đầu. Quá trình này kết thúc khi mỗi dãy nhỏ chỉ còn một bạn.

3. Kết hợp: Cứ hai dãy liên tiếp đã được sắp xếp kết hợp lại thành một dãy các bạn được sắp xếp theo chiều cao tăng dần. Bước này được làm lần lượt từ các dãy kích thước nhỏ đến lớn.

*Kết luận

- Sắp xếp trộn là một thuật toán đệ quy điển hình của phương pháp chia để trị tổng quát bao gồm ba giai đoạn cơ bản: Chia, Trị và Kết hợp.

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

a) Mục tiêu: Nêu được các bước chính thực hiện sắp xếp trộn.
b) Nội dung: HS thảo luận, đọc sách CĐHT trang 40-43 để tìm hiểu nội dung thuật toán sắp xếp trộn.
c) Sản phẩm: Nêu được các bước chính của thực hiện sắp xếp trộn cho mô hình tổng quát của phương pháp chia để trị.
d) Tổ chức thực hiện:

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

- GV yêu cầu HS đọc nội dung trang 40,41 và giới thiệu bài toán:

Cho dãy số A gồm n phần tử A₀, A₁,…,A_n-1. Em hãy viết chương trình nhập vào số nguyên n và dãy số nguyên A có n phần tử A₀, A₁,…,A_n-1; sau đó sắp xếp dãy này theo thứ tự tăng dần dùng thuật toán sắp xếp trộn.

- GV hướng dẫn các bước giải toán một cách trực quan trên ví dụ.

- GV giới thiệu một ví dụ sắp xếp dãy số: 5, 4, 9, 8, 7, 1 dùng thuật toán trên.

- GV hướng dẫn HS thực hiện nội dung Thực hành trang 41 sách CĐHT.

Em hãy tìm hiểu các đoạn chương trình viết trên ngôn ngữ lập trình Python cho thuật toán sắp xếp trộn sau đây: Em hãy soạn thảo và chạy chương trình với các bộ dữ liệu thử nghiệm trong Bảng 1.

- GV hướng dẫn HS cài đặt lại thuật toán từ chương trình mẫu và chạy thông với các bộ dữ liệu vào khác nhau.

- Sau khi HS chạy chương trình mẫu, GV yêu cầu HS nêu các bước khi thực hiện thuật toán sắp xếp trộn.

- GV kết luận về các bước chính thực hiện thuật toán sắp xếp trộn.

Bước 2: Thực hiện nhiệm vụ

- HS tìm hiểu thông tin sách CĐHT, thực hiện nhiệm vụ và thảo luận trả lời câu hỏi.

Bước 3: Báo cáo, thảo luận

- Đại diện nhóm HS báo cáo.

- Một số HS nhóm khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định

- GV nhận xét kết quả thảo luận nhóm, thái độ làm việc của các HS.

- GV tổng quát lại kiến thức trọng tâm và yêu cầu HS ghi chép đầy đủ vào vở.

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

- Các bước của thuật toán sắp xếp trộn được thiết kế theo kĩ thuật đệ quy cho hàm sắp xếp trộn Merge_sort (A) như sau:

1. Chia: Chia dãy A thành hai dãy con (A₀, A₁,…,A_k) và (A_k, A_k+1,…,A_n-1) có số lượng phần tử chênh nhau không quá 1.

2. Trị: Sắp xếp mỗi dãy con bằng cách sử dụng lời gọi đệ quy Merge_sort () với đầu vào mới tương ứng cho dãy con cần sắp xếp. Hàm đệ quy dừng khi độ dài dãy cần sắp xếp bằng 1.

3. Kết hợp: Trộn hai dãy con đã được sắp xếp lại thành một dãy duy nhất được sắp xếp tăng dần. Thuật toán kết hợp duy trì ba biến chạy, hai biến chạy cho dãy hai con, một biến chạy cho dãy được sắp xếp cuối cùng, tăng các biến chạy tương ứng với các vị trí trong dãy lần lượt từ trái qua phải, lấy ra phần tử nhỏ hơn trong hai giá trị tại vị trí hai biến chạy của hai dãy con và gán vào vị trí biến chạy của dãy sắp xếp cuối cùng.

*Kết luận

- Sắp xếp trộn là thuật toán đệ quy điển hình cho mô hình tổng quát của phương pháp chia để trị bao gồm ba bước chính là: chia nhỏ ra thành hai bài toán con; giải từng bài toán con bằng đệ quy; kết hợp kết quả các bài toán con.

Đăng nhập để xem đáp án