Giáo án chuyên đề KHMT 11 kết nối: Bài 9 Sắp xếp trộn (P1)

Trọn bộ giáo án chuyên đề tin học khoa học máy tính 11 sách kết nối tri thức cả năm file word. Giáo án bài 9 Sắp xếp trộn (P1). Bài soạn bám sát theo chương trình mới được trình bày khoa học, kiến thức trọng tâm, dễ dàng giảng dạy và chỉnh sửa đơn giản khi cần.

Nội dung chi tiết

Ngagrave;y soạn:hellip;/hellip;/hellip;

Ngagrave;y dạy:hellip;/hellip;/hellip;

BAgrave;I 9. SẮP XẾP TRỘN

MỤC TIEcirc;U
Về kiến thức

Sau bagrave;i học nagrave;y, HS sẽ:

Biết vagrave; trigrave;nh bagrave;y được caacute;ch thiết kế thuật toaacute;n sắp xếp trộn bằng kĩ thuật chia để trị.
Thực hiện được lập trigrave;nh theo thuật toaacute;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 caacute;c nguồn tagrave;i liệu học tập phugrave; hợp.
Năng lực giải quyết vấn đề vagrave; saacute;ng tạo: Xaacute;c định vagrave; tigrave;m hiểu được caacute;c thocirc;ng tin liecirc;n quan đến vấn đề, đề xuất giải phaacute;p giải quyết vấn đề trong bagrave;i học.
Năng lực giao tiếp vagrave; hợp taacute;c: Thực hiện tốt nhiệm vụ trong hoạt động nhoacute;m.

Năng lực tin học:

Higrave;nh thagrave;nh, phaacute;t triển năng lực giải quyết vấn đề với sự hỗ trợ của cocirc;ng nghệ thocirc;ng tin vagrave; truyền thocirc;ng.

Phẩm chất:

Higrave;nh thagrave;nh yacute; thức traacute;ch nhiệm, tiacute;nh cẩn thận khi lagrave;m việc nhoacute;m, phẩm chất lagrave;m việc chăm chỉ, chuyecirc;n cần để hoagrave;n thagrave;nh một nhiệm vụ.
Coacute; yacute; thức vận dụng kiến thức, kĩ năng đatilde; học ở nhagrave; trường vagrave;o thực tiễn.

THIẾT BỊ DẠY HỌC VAgrave; HỌC LIỆU
Đối với giaacute;o viecirc;n

SGK, SGV, Giaacute;o aacute;n;
Maacute;y tiacute;nh đatilde; cagrave;i đặt Python vagrave; maacute;y chiếu;
Higrave;nh ảnh, sơ đồ minh họa cho caacute;c bước thực hiện trecirc;n một mẫu dữ liệu đơn giản hoặc coacute; thể sử dụng caacute;c phần mềm mocirc; phỏng thuật toaacute;n để minh họa.

Đối với học sinh

SGK, vở ghi.
Điện thoại coacute; cagrave;i sẵn phần mềm Python (nếu coacute;).

III. TIẾN TRIgrave;NH DẠY HỌC

HOẠT ĐỘNG KHỞI ĐỘNG
Mục tiecirc;u:

- Hướng sự tograve; mograve; của học sinh muốn tigrave;m hiểu một thuật toaacute;n sắp xếp khaacute;c tốt hơn hẳn caacute;c thuật toaacute;n sắp xếp khaacute;c tốt hơn hẳn caacute;c thuật toaacute;n sắp xếp đatilde; biết như thuật toaacute;n sắp xếp chegrave;n, sắp xếp chọn, sắp xếp nổi bọt.

- Kĩ thuật hướng đến chiacute;nh lagrave; chia để trị.

Nội dung: GV cho caacute;c nhoacute;m HS trao đổi để nhận ra caacute;c tiacute;nh chất chung nhất của caacute;c bagrave;i toaacute;n nagrave;y.
Sản phẩm học tập: HS dựa vagrave;o kiến thức vagrave; hiểu biết caacute; nhacirc;n để đưa ra cacirc;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 đatilde; biết tigrave;m kiếm nhị phacirc;n trecirc;n caacute;c datilde;y đatilde; sắp xếp coacute; độ phức tạp thời gian tốt hơn so với caacute;c thuật toaacute;n tigrave;m kiếm trecirc;n datilde;y chưa sắp xếp. Chiacute;nh vigrave; thế, việc sắp xếp thocirc;ng tin theo một trigrave;nh tự nagrave;o đoacute; luocirc;n đoacute;ng vai trograve; quan trọng trong caacute;c bagrave;i toaacute;n tigrave;m kiếm thocirc;ng tin. Tuy nhiecirc;n, một số thuật toaacute;n sắp xếp magrave; em đatilde; biết như sắp xếp chegrave;n, sắp xếp chọn, sắp xếp nổi bọt, ... đều coacute; độ phức tạp thời gian O (n² ) (n - kiacute;ch thước datilde;y cần sắp xếp). Cacirc;u hỏi đặt ra lagrave;: Liệu coacute; hay khocirc;ng một caacute;ch sắp xếp datilde;y với thời gian tốt hơn O (n²)?

- GV đặt cacirc;u hỏi yecirc;u cầu HS thảo luận: Liệu kĩ thuật chia để trị coacute; thể aacute;p dụng cho bagrave;i toaacute;n sắp xếp được khocirc;ng? Nếu coacute; thigrave; coacute; lagrave;m tăng hiệu quả của sắp xếp được khocirc;ng?

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

- HS lắng nghe, suy nghĩ vagrave; đưa ra cacirc;u trả lời.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời HS trả lời cacirc;u hỏi.

- Caacute;c HS khaacute;c nhận xeacute;t, necirc;u yacute; kiến khaacute;c (nếu coacute;).

Bước 4: Đaacute;nh giaacute; kết quả, thực hiện nhiệm vụ học tập

- GV nhận xeacute;t, đaacute;nh giaacute;, tuyecirc;n dương cacirc;u trả lời của HS.

- GV dẫn dắt vagrave;o nội dung bagrave;i mới: Để trả lời cho cacirc;u hỏi nagrave;y, chuacute;ng ta vagrave;o bagrave;i học ngagrave;y hocirc;m nay - Bagrave;i 9. Sắp xếp trộn.

HOẠT ĐỘNG HIgrave;NH THAgrave;NH KIẾN THỨC

Hoạt động 1. Tigrave;m hiểu yacute; tưởng thuật toaacute;n sắp xếp trộn

Mục tiecirc;u: HS hiểu được yacute; tưởng chiacute;nh, gốc của sắp xếp trộn.
Nội dung: GV yecirc;u cầu HS tigrave;m hiểu Hoạt động 1 SGK trang 40, đọc thocirc;ng tin mục 1, thảo luận nhoacute;m vagrave; xacirc;y dựng kiến thức mới.
Sản phẩm học tập: HS necirc;u được yacute; tưởng thuật toaacute;n sắp xếp trộn vagrave; trả lời được caacute;c Cacirc;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 thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 1 SGK trang 40:

Quan saacute;t vagrave; thực hiện caacute;c bước theo yacute; tưởng của thuật toaacute;n sắp xếp trộn để biết thuật toaacute;n nagrave;y lagrave; mocirc; higrave;nh kĩ thuật chia để trị.

Em coacute; nhận xeacute;t gigrave; về đặc thugrave; của caacute;c giai đoạn 1, 2, 3 trong sơ đồ dưới đacirc;y?

- GV yecirc;u cầu caacute;c nhoacute;m quan saacute;t vagrave; thực hiện yacute; tưởng chiacute;nh của sắp xếp trộn theo sơ đồ higrave;nh 9.1

- GV necirc;u yacute; nghĩa của việc trộn: Trộn hai datilde;y đatilde; sắp xếp thagrave;nh một datilde;y lớn hơn cũng sẽ được sắp xếp.

- GV giao cho caacute;c nhoacute;m nghiecirc;n cứu vagrave; mocirc; tả uacute; tưởng của sắp xếp trộn theo ba bước Chia, Trị vagrave; Kết hợp.

- GV kết luận về yacute; tưởng chia để trị của sắp xếp trộn.

- GV cho HS thảo luận cặp đocirc;i, trả lời Cacirc;u hỏi (SGK ndash; tr41) để củng cố kiến thức:

+ Cacirc;u 1: Hatilde;y thực hiện thao taacute;c trộn hai datilde;y sau: B = 1, 4, 7; C = 2, 3, 6.

+ Cacirc;u 2: Thực hiện sắp xếp datilde;y 3, 2, 7, 1, 6, 5 theo caacute;c bước tương tự trecirc;n.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu yacute; tưởng thuật toaacute;n sắp xếp trộn trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi (SGK ndash; tr41)

Cacirc;u 1: Thực hiện bằng tay trộn hai datilde;y B = 1, 4, 7 vagrave; C = 2, 3, 6.

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

Bước 1. Đưa 1 vagrave;o A.

Bước 2. Đưa 2 vagrave;o A.

Bước 3. Đưa 3 vagrave;o A.

Bước 4. Đưa 4 vagrave;o A.

Bước 5. Đưa 6 vagrave;o A.

Bước 6. Đưa 7 vagrave;o A.

Kết thuacute;c datilde;y A sẽ lagrave; 1, 2, 3, 4, 6, 7.

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

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (nếu coacute;).

Bước 4: Đaacute;nh giaacute; kết quả, thực hiện nhiệm vụ học tập

- GV nhận xeacute;t, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;m tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

1. Yacute; tưởng thuật toaacute;n sắp xếp trộn

- Hoạt động 1

Giai đoạn 1. Từ datilde;y gốc ban đầu chuacute;ng ta taacute;ch chia đocirc;i lagrave;m hai datilde;y con, mỗi datilde;y con coacute; kiacute;ch thước bằng frac12; kiacute;ch thước của datilde;y gốc. Quaacute; trigrave;nh nagrave;y chiacute;nh lagrave; bước Chia của kĩ thuật chia để trị.

Giai đoạn 2. Khi tất cả caacute;c datilde;y con thu được đều chỉ cograve;n một phần tử. Tất cả caacute;c datilde;y nagrave;y hiển nhiecirc;n đều đatilde; được sắp xếp đuacute;ng. Đacirc;y chiacute;nh lagrave; bước Trị tương ứng của chiến lược chia để trị.

Giai đoạn 3. Từ caacute;c datilde;y đatilde; sắp xếp xong, chuacute;ng ta sẽ trộn chuacute;ng lại với nhau, mỗi lần trộn hai datilde;y đatilde; sắp xếp để tạo thagrave;nh một datilde;y lớn hơn cũng được sắp xếp đuacute;ng. Quaacute; trigrave;nh trộn sẽ kết thuacute;c khi nhacirc;n được đuacute;ng một datilde;y chiacute;nh lagrave; datilde;y ban đầu nhưng đatilde; sắp xếp xong. Đacirc;y chiacute;nh lagrave; quaacute; trigrave;nh Kết hợp tương ứng của kĩ thuật chia để trị.

*Kết luận

Yacute; tưởng của thuật toaacute;n sắp xếp trộn được thực hiện qua 3 bước: Chia nhỏ datilde;y gốc thagrave;nh caacute;c datilde;y với kiacute;ch thước nhỏ hơn (bằng frac12; datilde;y ban đầu), tiếp tục cho đến khi nhận được caacute;c datilde;y con đatilde; sắp xếp đuacute;ng thigrave; tiến hagrave;nh trộn caacute;c datilde;y nagrave;y để nhận được kết quả cuối cugrave;ng. Caacute;c bước trecirc;n chiacute;nh lagrave; kĩ thuật chia để trị.

Hoạt động 2. Tigrave;m hiểu mocirc; tả thuật toaacute;n sắp xếp trộn

Mục tiecirc;u: HS hiểu rotilde; caacute;c bước chiacute;nh của sắp xếp trộn.
Nội dung: GV yecirc;u cầu HS tigrave;m hiểu Hoạt động 2 SGK trang 41, đọc thocirc;ng tin mục 2, thảo luận nhoacute;m vagrave; xacirc;y dựng kiến thức mới.
Sản phẩm học tập: HS mocirc; tả được thuật toaacute;n sắp xếp trộn vagrave; trả lời được caacute;c Cacirc;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 thagrave;nh caacute;c nhoacute;m, yecirc;u cầu thảo luận để hoagrave;n thagrave;nh Hoạt động 2 SGK trang 41:

Cugrave;ng thực hiện caacute;c bước cụ thể triển khai yacute; tưởng vagrave; cagrave;i đặt chương trigrave;nh cho thuật toaacute;n sắp xếp trộn.

- GV yecirc;u cầu caacute;c nhoacute;m thảo luận về caacute;c bước chiacute;nh của sắp xếp trộn.

- GV chốt lại: Coacute; thể hiểu sắp xếp trộn luocirc;n bao gồm hai quaacute; trigrave;nh:

(1) Taacute;ch datilde;y gốc thagrave;nh hai datilde;y con với mỗi datilde;y con coacute; kiacute;ch thước frac12; datilde;y ban đầu. Dugrave;ng đệ quy để sắp xếp hai datilde;y con nagrave;y.

(2) Sau đoacute;, dugrave;ng thuật toaacute;n trộn để trộn hai datilde;y con đatilde; sắp xếp thagrave;nh datilde;y ban đầu nhưng đatilde; được sắp xếp.

Thuật toaacute;n sắp xếp trộn được mocirc; tả tổng quaacute;t như sau:

Trong đoacute; lệnh 6 chiacute;nh lagrave; thuật toaacute;n "trộn" đoacute;ng vai trograve; rất quan trọng của sắp xếp trộn.

- GV phacirc;n tiacute;ch để HS hiểu được bản chất vagrave; yacute; nghĩa của sắp xếp trộn.

- GV cho HS thảo luận cặp đocirc;i, trả lời Cacirc;u hỏi (SGK ndash; tr43) để củng cố kiến thức:

+ Cacirc;u 1: Trong chương trigrave;nh 1 (trộn hai datilde;y B, C), vograve;ng lặp tại dograve;ng 6 coacute; nhiều nhất lagrave; bao nhiecirc;u bước lặp?

+ Cacirc;u 2: Mocirc; tả caacute;c bước thực hiện chương trigrave;nh 2 nếu datilde;y gốc A chỉ coacute; một phần tử.

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

- Caacute;c nhoacute;m HS tigrave;m hiểu caacute;c bước thực hiện sắp xếp trộn trong SGK.

- HS thảo luận nhoacute;m, hoagrave;n thagrave;nh bagrave;i tập phần Cacirc;u hỏi.

- GV theo dotilde;i, hỗ trợ HS trong quaacute; trigrave;nh học tập.

Bước 3: Baacute;o caacute;o kết quả hoạt động vagrave; thảo luận

- GV mời đại diện caacute;c nhoacute;m trigrave;nh bagrave;y kết quả thảo luận của nhoacute;m migrave;nh.

- Đại diện caacute;c nhoacute;m xung phong trả lời Cacirc;u hỏi (SGK ndash; tr43)

Cacirc;u 1: Vograve;ng lặp 6 coacute; nhiều nhất lagrave; m + n bước lặp.

Cacirc;u 2: Nếu datilde;y gốc coacute; 1 phần tử thigrave; thuật toaacute;n sắp xếp trộn sẽ khocirc;ng thực hiện gigrave; vagrave; trả về ngay datilde;y gốc.

- Caacute;c HS cograve;n lại nhận xeacute;t, bổ sung (nếu coacute;).

Bước 4: Đaacute;nh giaacute; kết quả, thực hiện nhiệm vụ học tập

- GV nhận xeacute;t, bổ sung, tuyecirc;n dương ghi điểm caacute;c nhoacute;m lagrave;m tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung tiếp theo.

2. Mocirc; tả thuật toaacute;n sắp xếp trộn

- Hoạt động 2

a) Thuật toaacute;n trộn hai datilde;y (merge algorithm)

- Giả sử cho trước hai datilde;y đatilde; được sắp thứ tự B vagrave; C coacute; số phần tử lần lượt lagrave; m, n. Thuật toaacute;n merge(B, C) sẽ được thực hiện "trộn" hai datilde;y trecirc;n vagrave; đưa kết quả vagrave;o datilde;y A. Quy trigrave;nh trộn nagrave;y rất tự nhiecirc;n vagrave; được minh họa trong sơ đồ higrave;nh 9.2

Thuật toaacute;n 1. Thuật toaacute;n trộn hai datilde;y

b) Thuật toaacute;n sắp xếp trộn (mergeSort)

- Thuật toaacute;n sắp xếp trộn được mocirc; tả bởi hagrave;m mergeSort(A) trong chương trigrave;nh sau.

Thuật toaacute;n 2. Thuật toaacute;n sắp xếp trộn

- Đoạn chương trigrave;nh sau sẽ thực hiện sắp xếp datilde;y A vagrave; đưa kết quả đatilde; sắp xếp vagrave;o datilde;y B. Lời gọi hagrave;m đệ quy lagrave;:

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

2 B = mergeSort(A)

*Kết luận

- Thuật toaacute;n sắp xếp trộn sẽ bao gồm một hagrave;m mergeSort(), hagrave;m nagrave;y sẽ tiến hagrave;nh caacute;c bước chiacute;nh của thuật toaacute;n vagrave; gọi hagrave;m trộn hai datilde;y đatilde; sắp xếp merge() khi thực hiện bước kết hợp.