Mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên một bộ dữ liệu đầu vào có kích thước nhỏ.
Biết được tìm kiếm nhị phân nhanh hơn tìm kiếm tuần tự.
Nêu được ý nghĩa của việc chia một bài toán thành những bài toán nhỏ hơn.

2. Năng lực

Năng lực chung:
Tự chủ và tự học: biết lắng nghe và chia sẻ ý kiến cá nhân với bạn, nhóm và GV. Tích cực tham gia các hoạt động trong lớp.
Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của thầy cô.
Giải quyết vấn đề và sáng tạo: biết phối hợp với bạn bè khi làm việc nhóm, có sáng tạo khi tham gia các hoạt động tin học.
Năng lực riêng:
Biết biểu diễn và mô phỏng thuật toán tìm kiếm

3. Phẩm chất

Có ý thức trách nhiệm đối với việc sử dụng thông tin.

II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU

1. Đối với giáo viên

SGK, SGV, SBT Tin học 7.
Máy tính, máy chiếu.

2. Đối với học sinh

SGK, SBT Tin học 7.

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

A. HOẠT ĐỘNG KHỞI ĐỘNG

a. Mục tiêu: Gợi mở, dẫn dắt HS nhận biết các hàm thông dụng.

b. Nội dung: GV trình bày vấn đề; HS dựa vào hiểu biết để trả lời câu hỏi.

c. Sản phẩm học tập: HS trả lời được câu hỏi phần Khởi động.

d. Tổ chức thực hiện:

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

- GV nêu câu hỏi: Nếu phải tìm một số trong dãy đã sắp xếp theo thứ tự tăng dần hoặc giảm dần, em có cách nào tìm nhanh hơn tìm kiếm tuần tự không?

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

- HS trả lời câu hỏi

- GV hướng dẫn, hỗ trợ HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời câu hỏi:

Em sẽ chia đôi dãy làm hai phần để tìm kiếm nhanh hơn.

- GV mời HS khác lắng nghe, nhận xét, bổ sung.

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

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV dẫn dắt HS vào bài học: Phương pháp chia đôi dần, loại bỏ nửa dãy chắc chắn không chứa số x cần tìm kiếm là một phương pháp giúp ta nhanh chóng tìm được kết quả trong bài toán tìm kiếm một số trong dãy số đã sắp thứ tự. Bài học ngày hôm nay chúng ta sẽ cùng nhau tìm hiểu về phương pháp tìm kiếm này. – Bài 2: Tìm kiếm nhị phân

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

Hoạt động 1: Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

a. Mục tiêu: Thông qua hoạt động, HS nắm được các hàm có sẵn trong Excel.

b. Nội dung: GV trình bày vấn đề; HS đọc thông tin SGK.55 và trả lời câu hỏi.

c. Sản phẩm học tập: HS nêu và ghi được vào vở quy tắc chung khi sử dụng hàm trong Excel.

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ụ

- GV tổ chức cho HS tìm hiểu nội dung phần Hoạt động và yêu cầu HS suy nghĩ và trả lời câu hỏi

Có 8 thẻ, mỗi thẻ ghi một số nguyên trên đó. Tất cả các thẻ được sắp xếp thành dãy theo thứ tự không giảm của các số ghi trên đó và đặt sấp mặt ghi số xuống bàn để em không nhìn thấy. Cô giáo đọc một số, gọi là X chẳng hạn. Cần trả lời câu hỏi: Có hay không một thẻ ghi số X? Hãy sử dụng ít nhất số lần lật một thẻ lên xem mà vẫn trả lời được câu hỏi. Bạn Thanh An cho rằng chỉ cần không quá 3 lần lật thẻ là trả lời được. Em đồng ý với Thanh An không? Vì sao?

à Gợi ý: Em đồng ý với ý kiến của bạn Thanh An. Vì khi ta chia đôi để tìm một số trong dãy thì ta có thể tìm được kết quả nhanh hơn. Nên sẽ không tìm quá ba lần lật thẻ.

- GV yêu cầu HS đọc phần Ví dụ trong mục 1 – SGK tr.81, 82 và trình bày lại ý tưởng chia đôi dần để tìm một số trong một dãy số.

- GV lấy ví dụ minh họa trường hợp không tìm thấy x bằng cách thay đổi x = 44 của ví dụ trong SGK thành tìm x = 45 trong dãy số, yêu cầu HS sử dụng phương pháp chia đồi dần để tìm x

Tìm x – 45 trong dãy 8 phần tử đã xếp thứ tự không giảm (6, 12, 18, 42, 44, 55, 67, 94)

- GV kết luận kiến thức trọng tâm về phương pháp chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự.

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

- HS đọc thông tin SGK.81, 82 và trả lời câu hỏi.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời câu hỏi.

- GV mời HS khác nhận xét, bổ sung.

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

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV chuyển sang nội dung mới.

1. Chia đôi dần để tìm kiếm một số trong dãy số đã sắp thứ tự

- Ý tưởng: chia đôi dần để tìm một số trong một dãy số

- Ví dụ: Tìm x = 44 trong dãy 8 phần tử đã sắp xếp thứ tự không giảm

	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈
Xuất phát	6	12	18	42	44	55	67	94
Bước 1				42	44	55	67	94
Bước 2					44	55
Bươc 3					44

- Giải thích

+ Chia đôi lần 1: Phạm vi tìm kiếm là dãy từ a₁ đến a₈. Lấy a₄ là số có vị trí giữa dãy. Vì x > a₄ nên nửa đầu dãy chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa sau của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con từ a₅đến a₈.

+ Chia đôi lần 2: Phạm vi tìm kiếm là dãy từ a₅ đến a₈. Lấy a₆ là số có vị trí giữa dãy. Vì x < a₆ nên nửa sau chắc chắn không chứa x = 44, tiếp theo chỉ cần tìm trong nửa đầu của dãy. Như vậy, phạm vi tìm kiếm tiếp theo là dãy con chỉ còn một số a₅.

Phạm vi tìm kiếm chỉ còn 1 số kết thúc thuật toán với kết quả: Tìm thấy x ở vị trí thứ 5

Hoạt động 2: Thuật toán tìm kiếm nhị phân

a. Mục tiêu: Thông qua hoạt động, HS hiểu được về thuật toán tìm kiếm nhị phân

b. Nội dung: GV trình bày vấn đề; HS đọc thông tin SGK 82,và trả lời câu hỏi.

c. Sản phẩm học tập: HS nêu và ghi được khái niệm về thuật toán tìm kiếm nhị phân và mô tả thuật toán.

d. Tổ chức hoạt động:

Hoạt động 3: Tìm hiểu phương pháp “chia để trị” với bài toán tìm kiếm

a. Mục tiêu: Thông qua hoạt động, HS hiểu được phương pháp “chia để trị” với bài toán tìm kiếm

b. Nội dung: GV trình bày vấn đề; HS đọc nhiệm vụ - SGK tr.82 và thực hành nhiệm vụ.

c. Sản phẩm học tập: Kết quả thảo luận tìm hiểu về phương pháp “chia để trị” với bào toán tìm kiếm

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 nhắc lại về câu chuyện ngụ ngôn “bó đũa”: Để bẻ được nhiều chiếc đũa, cần chia bó đũa thành các bó nhỏ hơn à lời giáo huấn thêm thúy từ xưa về chiến lược “chia để trị”

- GV liên hệ từ câu chuyện ngụ ngôn “bó đũa”, đưa ra khái niệm về phương pháp “chia để trị” với bài toán tìm kiếm.

- GV yêu cầu HS đọc thông tin mục 3 trong SGK – tr83, trình bày về thuật toán tìm kiếm nhị phân

- GV hướng dẫn HS đọc phần Tóm tắt bài học – SGK tr.83 để tổng kết lại bài học.

- GV cho HS đọc phần Bài đọc thêm trong SGK – tr83

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

- HS đọc thông tin mục 3 SGK. 83, trả lời câu hỏi

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV gọi đại diện HS trả lời câu hỏi

- GV mời HS khác nhận xét, bổ sung.

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

- GV đánh giá, nhận xét, chuẩn kiến thức.

- GV chuyển sang nội dung mới.

3. Phương pháp “chia để trị” với bài toán tìm kiếm

- Để giải một bài toán lớn, người ta tìm cách chia bài toán ban đầu ra thành các bài toán nhỏ hơn rồi giải những bài toán nhỏ hơn sẽ dễ hơn. Cách làm này gọi là “chia để trị”

- Thuật toán tìm kiếm nhị phân chia bài toán ban đầu thành hai bài toán con nhỏ hơn và chỉ phải tiếp tục giải một trong hai bài toán con đó. Áp dụng liên tiếp cách này cho đến khi nhận được kết quả.

C. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Thông qua hoạt động, HS củng cố kiến thức đã học.

b. Nội dung: GV nêu nhiệm vụ; HS trả lời để luyện tập các kiến thức đã học.

c. Sản phẩm học tập: HS trả lời câu hỏi phần luyện tập và câu hỏi phần tự kiểm tra trong SGK – tr83

d. Tổ chức hoạt động:

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

- GV yêu cầu HS làm việc cá nhân trả lời câu hỏi phần luyện tập và câu hỏi phần tự kiểm tra

* Luyện tập : Cho dãy số 5, 11, 18, 39, 41, 52, 63, 70. Hãy mô tả diễn biến từng bước tìm kiếm nhị phân để tìm kiếm x = 60 trong dãy trên

* Tự kiểm tra

Câu 1. Hãy mô tả quy trình chia đôi dần để thực hiện tìm kiếm nhị phân

Câu 2. Theo em, có phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân không? Giải thích tại sao.

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

- HS vận dụng kiến thức đã học và trả lời câu hỏi.

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời:

* Luyện tập Tìm kiếm x = 60.

Bước 1. Ta sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy. Ta sẽ chia ngay vị trí a6 (a6=52) vì x > a6. Phạm vi tìm kiếm tiếp theo là từ a7 đến a8.

Bước 3. Khi đó phạm vi tìm kiếm chỉ có a7 đến a8 và ta thấy không có số nào bằng x. Kết thúc thuật toán không tìm thấy kết quả x.

* Tự kiểm tra

Câu 1.

Bước 1. Sắp xếp dãy theo thứ tự không giảm.

Bước 2. Ta chia đôi dãy số để tìm x trong dãy.

Bước 3. Lấy phần tử đứng giữa dãy để so sánh với x.

Nếu phần tử đó chính là x thì kết luận đã tìm thấy x và kết thúc thuật toán.

Ngược lại, ta có thể xác định được x chắc chắn không có trong nửa đầu hay nửa sau của dãy. Từ đó ta xác định được phạm vi tìm kiếm và thực hiện tìm kiếm trong phạm vi nữa dãy còn lại, sẽ được lặp lại theo cách như thế cho đến khi tìm được kết quả.

Câu 2.

Vì khi dãy có thứ tự thì mới áp dụng được tìm kiếm nhị phân nên không phải với bất cứ dãy số nào cũng có thể áp dụng được thuật toán tìm kiếm nhị phân.

- GV mời đại diện HS khác nhận xét, bổ sung.

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

- GV đánh giá, nhận xét, chuẩn kiến thức.

D. HOẠT ĐỘNG VẬN DỤNG

a. Mục tiêu: Thông qua hoạt động, HS củng cố kiến thức đã học.

b. Nội dung: GV nêu nhiệm vụ; HS vận dụng kiến thức đã học, kiến thức thực tế để trả lời câu hỏi.

c. Sản phẩm học tập: Câu trả lời của HS trong phần Vận dụng SGK tr.83

d. Tổ chức hoạt động:

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

- GV yêu cầu HS thảo luận nhóm và thực hiện các bài tập sau: Em hãy mô tả cách tra cứu, tìm giải nghĩa một từ trong từ điển. Có thể gọi cách tìm đó là áp dụng thuật toán tìm kiếm nhị phân không?.

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

- HS vận dụng kiến thức đã học trả lời câu hỏi

- GV hướng dẫn, theo dõi, hỗ trợ HS nếu cần thiết.

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- GV mời đại diện HS trả lời câu hỏi

Cách tra cứu, tìm giải nghĩa từ điển:

Danh sách các giá trị dữ liệu không được sắp xếp và có thể được thay đổi bằng cách sử dụng các phương thức tích hợp sẵn. Từ điển được sử dụng để tạo ra một bản đồ cho các khóa (keys) độc nhất tới giá trị (values). Từ điển sẽ sắp xếp một tập các đối tượng (khóa) đến một tập các đối tượng là giá trị, do đó người sử dụng có thể tạo ra một danh sách các đối tượng không theo thứ tự. Các từ điển được tạo ra có thể biến đổi được, có nghĩa là chúng có thể được thay đổi tùy theo mục đích của người dùng.

Ta gọi cách tìm kiếm đó là thuật toán nhị phân.

- GV mời đại diện HS khác nhận xét, bổ sung.

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

- GV đánh giá, nhận xét, chuẩn kiến thức, kết thúc tiết học.

E. HƯỚNG DẪN VỀ NHÀ: