Giáo án chuyên đề KHMT 11 kết nối: Bài 7 Thiết kế thuật toán theo kĩ thuật chia để trị

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 7 Thiết kế thuật toán theo kĩ thuật chia để trị. 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 7. THIẾT KẾ THUẬT TOAacute;N THEO KĨ THUẬT CHIA ĐỂ TRỊ

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

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

Biết vagrave; thực hiện được một số thiết kế thuật toaacute;n bằng kĩ thuật chia để trị.
Thực hagrave;nh được thiết kế một số bagrave;i toaacute;n sử dụng kĩ thuật chia để trị đơn giả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:

- HS lagrave;m quen caacute;c bagrave;i toaacute;n coacute; liecirc;n quan đến thiết kế thuật toaacute;n theo kĩ thuật chia để trị.

- Kiacute;ch thiacute;ch sự tograve; mograve; cho người học.

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 đề: Trong bagrave;i học nagrave;y em sẽ thiết kế lời giải cho hai bagrave;i toaacute;n sau:

Bagrave;i toaacute;n tiacute;nh lũy thừa exp(a, n) = aⁿ với a lagrave; số bất kigrave; (khaacute;c 0), n lagrave; số nguyecirc;n khocirc;ng acirc;m, ở đacirc;y aⁿ được hiểu lagrave; tiacute;ch của n lần giaacute; trị: aⁿ = a a hellip; a (n lần).
Ban Giaacute;m hiệu nhagrave; trường cần tigrave;m một bạn lớp em coacute; chiều cao đuacute;ng bằng 1,7 m hoặc gần với chiều cao đoacute; nhất để tham gia tập đội higrave;nh thể thao.

- GV đặt cacirc;u hỏi yecirc;u cầu HS thảo luận: Với hai bagrave;i toaacute;n trecirc;n em sẽ thực hiện như thế nagrave;o?

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 7. Thiết kế thuật toaacute;n theo kĩ thuật chia để trị.

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

Hoạt động 1. Tigrave;m hiểu bagrave;i toaacute;n tiacute;nh lũy thừa

Mục tiecirc;u: HS hiểu được caacute;ch thiết lập thuật toaacute;n tiacute;nh lũy thừa nhanh bằng chia để trị.
Nội dung: GV yecirc;u cầu HS tigrave;m hiểu Hoạt động 1 SGK trang 33, đọ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 caacute;ch giải bagrave;i toaacute;n tiacute;nh lũy thừa bằng chia để trị vagrave; trả lời được caacute;c Cacirc;u hỏi củng cố kiến thức SGK trang 34.
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 33:

Hatilde;y thiết lập thuật toaacute;n vagrave; chương trigrave;nh tiacute;nh lũy thừa aⁿ với a lagrave; số bất kigrave; khaacute;c 0, n lagrave; số nguyecirc;n khocirc;ng acirc;m.

- GV mocirc; tả bagrave;i toaacute;n vagrave; yecirc;u cầu caacute;c nhoacute;m giải bagrave;i toaacute;n bằng caacute;ch tiacute;nh thocirc;ng thường, bằng tay vagrave; chương trigrave;nh.

- GV giới thiệu yacute; tưởng mới giải bagrave;i toaacute;n tiacute;nh lũy thừa theo kĩ thuật chia để trị.

- Sau khi thực hiện việc cagrave;i đặt chương trigrave;nh, GV cho caacute;c nhoacute;m thảo luận về độ phức tạp thời gian của thuật toaacute;n.

- GV kết luận về nội dung độ phức tạp thời gian của thuật toaacute;n.

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

+ Cacirc;u 1: Mocirc; tả caacute;c bước tiacute;nh bằng tay pheacute;p tiacute;nh lũy thừa 2¹¹theo hai chương trigrave;nh trecirc;n. Caacute;c nagrave;o nhanh hơn?

+ Cacirc;u 2: Pheacute;p tiacute;nh a²¹ sẽ cần dugrave;ng bao nhiecirc;u pheacute;p nhacirc;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 lời giải của bagrave;i toaacute;n tiacute;nh lũy thừa bằng chia để trị 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; tr34)

Cacirc;u 1: Tiacute;nh tay 2¹¹.

- Tiacute;nh theo phương phaacute;p cũ. Cần thực hiện 10 lần pheacute;p nhacirc;n với 2.

- Tiacute;nh theo phương phaacute;p chia để trị mới.

Bước 1. Tiacute;nh 2 x 2 = 2²

Bước 2. Tiacute;nh 4 x 4 = 2⁴

Bước 3. Tiacute;nh 2⁴ x 2 = 2⁵

Bước 4. Tiacute;nh 2⁵ x 2⁵ = 2¹⁰

Bước 5. Tiacute;nh 2¹⁰ x 2 = 2¹¹

Vậy theo caacute;ch tiacute;nh mới chỉ cần 5 pheacute;p nhacirc;n.

Cacirc;u 2: Tiacute;nh a²¹

a²¹ = a x a¹⁰ x a¹⁰

Theo bagrave;i trecirc;n, tiacute;nh a¹⁰cần 4 pheacute;p nhacirc;n, vậy suy ra cần 4 + 2 = 6 pheacute;p nhacirc;n cho a²¹.

- 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. Bagrave;i toaacute;n tiacute;nh lũy thừa

- Hoạt động 1

Vigrave; aⁿ = a x a^n-1necirc;n coacute; thể thiết lập ngay chương trigrave;nh tiacute;nh hagrave;m lũy thừa đơn giản như sau:

Chương trigrave;nh 1. Tiacute;nh lũy thừa theo caacute;ch tự nhiecirc;n.

Chương trigrave;nh 2. Tiacute;nh lũy thừa theo caacute;ch nhị phacirc;n nhanh (chia để trị).

*Kết luận

- Hagrave;m exp(a,n) trecirc;n được thiết lập theo kĩ thuật chia để trị coacute; độ phức tạp thời gian O(logn).

Hoạt động 2. Tigrave;m hiểu bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng

Mục tiecirc;u: HS hiểu được bagrave;i toaacute;n vagrave; caacute;ch giải theo kĩ thuật chia để trị của bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng.
Nội dung: GV yecirc;u cầu HS tigrave;m hiểu Hoạt động 2 SGK trang 34, đọ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 necirc;u được caacute;ch giải bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng bằng chia để trị vagrave; trả lời được caacute;c Cacirc;u hỏi củng cố kiến thức SGK trang 36.
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 34:

Xacirc;y dựng thuật toaacute;n cho bagrave;i toaacute;n sau: Cho trước datilde;y caacute;c số đatilde; được sắp xếp tăng dần. Với giaacute; K cho trước cần tigrave;m phần tử của datilde;y gốc coacute; giaacute; trị gần với K nhất.

- GV mocirc; tả bagrave;i toaacute;n vagrave; yecirc;u cầu caacute;c nhoacute;m trao đổi, thực hiện bagrave;i toaacute;n theo caacute;ch tigrave;m kiếm tuần tự, tức lagrave; thuật toaacute;n tự nhiecirc;n.

- Sau đoacute;, GV thiết kế theo phương phaacute;p chia để trị, caacute;ch lagrave;m nagrave;y sẽ lagrave; một mở rộng của thuật toaacute;n tigrave;m kiếm nhị phacirc;n đatilde; biết từ caacute;c bagrave;i trước.

- GV kết luận về bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng.

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

+ Cacirc;u 1: Hatilde;y giải thiacute;ch kĩ hơn chương trigrave;nh 2 ở trecirc;n tại caacute;c dograve;ng 4 vagrave; 6.

+ Cacirc;u 2: Necirc;u những điểm khaacute;c biệt của chương trigrave;nh trecirc;n với chương trigrave;nh tigrave;m kiếm nhị phacirc;n đatilde; biế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 lời giải của bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng 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; tr36)

Cacirc;u 1:

- Dograve;ng 4 mocirc; tả trường hợp A coacute; một phần tử thigrave; đaacute;p số luocirc;n lagrave; phần tử duy nhất nagrave;y.

- Dograve;ng 6 mocirc; tả trường hợp A coacute; hai phần tử, đaacute;p aacute;n sẽ lagrave; phần tử nagrave;o gần K hơn về giaacute; trị.

Cacirc;u 2: Chương trigrave;nh trecirc;n khaacute;c thuật toaacute;n tigrave;m kiếm nhị phacirc;n như sau:

- Caacute;ch xử liacute; caacute;c trường hợp cơ sở khi A coacute; 1 hoặc 2 phần tử.

- Sau mỗi bước lặp (hoặc sau mỗi lần gọi đệ quy), phạm vi tigrave;m kiếm sẽ tigrave;m tiếp ở một trong hai khoảng [mid, right] hay [left, mid], điều nagrave;y khaacute;c biệt với tigrave;m kiếm nhị phacirc;n lagrave; sau mỗi vograve;ng lặp miền tigrave;m kiếm sẽ lagrave; [left, mid ndash; 1] hoặc [mid + 1, right].

- 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 luyện tập.

2. Bagrave;i toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng

- Hoạt động 2

Chương trigrave;nh 1. Sử dụng tigrave;m kiếm tuần tự

Chương trigrave;nh 2. Sử dụng tigrave;m kiếm nhị phacirc;n

*Kết luận

- Thuật toaacute;n tigrave;m kiếm nhị phacirc;n mở rộng coacute; độ phức tạp thuật toaacute;n O(logn).

HOẠT ĐỘNG LUYỆN TẬP
Mục tiecirc;u: HS vận dụng kiến thức, hoagrave;n thagrave;nh bagrave;i tập phần Luyện tập.
Nội dung: GV giao nhiệm vụ, HS thảo luận.
Sản phẩm học tập: HS aacute;p dụng kiến thức về thiết kế thuật toaacute;n theo kĩ thuật chia để trị để giải caacute;c bagrave;i toaacute;n.
Tổ chức thực hiện:

--------------- Cograve;n tiếp ---------------