Giải thích được thuật toán tìm kiếm nhị phân.
Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên bộ dữ liệu vào có kích thước nhỏ.
Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa.

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:
Giải thích được thuật toán tìm kiếm nhị phân.
Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân trên bộ dữ liệu vào có kích thước nhỏ.
Giải thích được mối liên quan giữa sắp xếp và tìm kiếm, nêu được ví dụ minh họa.

3. Phẩm chất

Các hoạt động khuyến khích các em hợp tác làm việc có trách nhiệm, có sự trao đổi, tôn trọng ý kiến người khác. Giúp các em có điều kiện học tập lẫn nhau.
Chia sẻ niềm vui khi cùng nhau hoàn thành một sản phẩm.

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: Thông qua hoạt động, đặt HS vào tình huống thực tiễn chứa đựng vấn đề cần giải quyết.

b. Nội dung:

- GV cho HS đọc tình huống trong SGK và yêu cầu HS đưa ra cách giải quyết tình huống.

- GV nhấn mạnh nhu cầu thuật toán tìm kiếm khác.

c. Sản phẩm học tập: HS nêu được bài toán tìm kiếm trong thực tiễn và nhu cầu tìm hiểu thuật toán tìm kiếm khác.

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

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

- GV cho HS đọc tình huống trong SGK và xử lí tình huống: Việc kinh doanh mở rộng, số lượng khách hàng của cửa hàng bán giống cây trồng nhà An lên đến hàng trăm người. Việc tìm kiếm tên khách hàng trong danh sách thật khó khăn. Em có gợi ý gì cho bạn An để việc tìm kiếm được dễ dàng hơn không?

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

- HS đọc tình huống trong SGK và xử lí tình huống: Để việc tìm kiếm của An được dễ dàng hơn, bạn có thể:

+ Sắp xếp danh sách để tìm dễ hơn.

+ Đưa danh sách vào phần mềm soạn thảo văn bản hoặc bảng tính và sử dụng chức năng tìm kiếm của phần mềm để tìm kiếm.

- HS hoạt động nhóm và thực hiện nhiệm vụ.

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

- HS lắng nghe cách xử lí tình huống của bạn và nhận xét.

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.

- GV nhấn mạnh nhu cầu cần có thuật toán tìm kiếm khác để giải quyết bài toán tìm kiếm nhanh hơn và cách tìm kiếm nhanh hơn là tìm kiếm một danh sách đã được sắp xếp.

- GV dẫn dắt HS vào bài học: Bài 15: Thuật toán tìm kiếm nhị phân.

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

Hoạt động 1: 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 hoạt động của thuật toán tìm kiếm nhị phân, đánh giá và so sánh với thuật toán tìm kiếm tuần tự. HS thấy được ý nghĩa của bài toán sắp xếp đối với bài toán tìm kiếm.

b. Nội dung:

- GV tổ chia cho HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 1. Thuật toán tìm kiếm nhị phân SGK tr.74 và trả lời câu hỏi HD1.

- GV trình bày sơ đồ khối của thuật toán và hoàn thiện HD1.

- GV tổ chức cho HS đọc nội dung Mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên SGK tr.76 và nêu các bước cụ thể.

- GV tổ chức cho HS làm việc cá nhân và thực hiện hoạt động câu hỏi SGK tr.76.

c. Sản phẩm học tập: Thuật toán tìm kiếm nhị phân và các bước mô tả thuật toán tìm kiếm nhị phân bằng ngôn ngữ tự nhiên.

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

Hoạt động 2: Sắp xếp và tìm kiếm

a. Mục tiêu: Thông qua hoạt động:

- HS hiểu được mối liên quan giữa sắp xếp và tìm kiếm, từ đó dẫn dắt sang bài học tiếp theo về các thuật toán sắp xếp.

- HS luyện tập biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân với bộ dữ liệu đầu vào có kích thước nhỏ.

b. Nội dung:

- GV tổ chia cho HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 2. Sắp xếp và tìm kiếm SGK tr.76, 77 và trả lời câu hỏi HD2.

- GV tổ chức cho HS làm việc cá nhân và thực hiện hoạt động câu hỏi SGK tr.77.

c. Sản phẩm học tập: Biểu diễn và mô phỏng được hoạt động của thuật toán tìm kiếm nhị phân với bộ dữ liệu đầu vào có kích thước nhỏ.

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

Hoạt động 2. Trò chơi tìm số

- GV tổ chức HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 2. Sắp xếp và tìm kiếm SGK tr.76, 77.

- GV tổ chức cho HS làm việc cặp đôi, thực hiện Hoạt động 2. Trò chơi tìm số:

+ Chuẩn bị: Hai bạn chơi A, B và 10 tâm thẻ ghi 10 số khác nhau (các số đều nhỏ hơn 20). Ví dụ, 10 số trên các tấm thẻ là 2, 3, 5, 6, 8, 9, 11, 15, 16, 18. Giả sử A giữ 10 tấm thẻ và B là người tìm kiếm.

+ Yêu cầu: Bạn sử dụng thuật toán tìm kiếm nhị phân để tìm một số nhỏ hơn 20 trong các tấm thẻ của bạn A.

+ Cách chơi:

Bước 1. A úp lần lượt 10 chiếc thẻ lên bàn theo thứ tự các số từ bé đến lớn.
Bước 2. B cho A biết con số mình cần tìm.
Bước 3. B chọn tấm thẻ ở vị trí giữa.
Bước 4. A hé mở tấm thẻ và trả lời B bằng cách nói một trong ba cụm từ “bằng nhau”, “lớn hơn” hoặc “bé hơn” tùy thuộc vào kết quả so sánh số bạn B cần tìm với số ở vị trí giữa của dãy.
Bước 5. Tùy vào câu trả lời của A mà B chọn nửa dãy tiếp theo để tìm kiếm.
Bước 6. Lặp lại các bước 3, 4, 5 cho đến khi B tìm thấy số cần tìm hoặc đã tìm hết dãy số.
Bước 7. Hoán đổi vị trí của A và B trong lượt chơi tiếp theo.

- GV chốt kiến thức:

* Câu hỏi/SGK tr.77

- GV tổ chức cho HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.77:

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

- HS hoạt động nhóm, quan sát hình 15.1, đọc hiểu mục 2. Sắp xếp và tìm kiếm SGK tr.76, 77.

- HS làm việc cặp đôi, thực hiện Hoạt động 2. Trò chơi tìm số.

- HS hoạt động cặp đôi và trả lời mục câu hỏi SGK tr.77.

- 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 và hoàn thành bài tập.

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

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

2. Sắp xếp và tìm kiếm

- Sắp xếp giúp cho việc tìm kiếm được thực hiện nhanh hơn.

* Hoạt động 2. Trò chơi tìm số

* Câu hỏi/SGK tr.77

Ví dụ thực tế cho thấy mối liên quan giữa sắp xếp và tìm kiếm:

+ Tìm kiếm sách trong thư viện, tên sách được sắp xếp theo thứ tự của chữ cái

+ Tìm kiếm hàng hóa trong siêu thị, loại hàng hóa được sắp xếp riêng từng khu (thực phẩm đông lạnh, thực phẩm khô, đồ gia dụng,…)

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.

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

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

- GV nêu yêu cầu:

+ Câu 1. Cho danh sách tên các nước sau đây: Bolivia, Albania, Scotland, Canada, Vietnam, Iceland, Portugal, Greenland, Germany.

a) Em hãy sắp xếp danh sách tên các nước theo thứ tự trong bảng chữ cái.

b) Em hãy liệt kê các bước lặp tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân.

c) Em hãy so sánh số bước lặp thực hiện tìm kiếm ở phần b với số bước lặp thực hiện tìm kiếm ở phần Luyện tập của bài 14.

+ Câu 2. Em hãy cho ví dụ một bài toán tìm kiếm trong thực tế mà có thể thực hiện bằng thuật toán tìm kiếm nhị phân. Hãy thực hiện thuật toán tìm kiếm nhị phân để giải quyết bài toán đó.

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à thực hiện nhiệm vụ.

- 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 một số HS trình bày kết quả:

+ Câu 1. a) Sắp xếp danh sách 9 nước theo thứ tự của bảng chữ cái: Albania, Bolivia, Canada, Germany, Greenland, Iceland, Portugal, Scotland, Vietnam.

b) Các bước lặp tìm kiếm tên nước Iceland trong danh sách đã sắp xếp theo thuật toán tìm kiếm nhị phân:

Bước 1. Chọn phần tử số 5 ở giữa, đó là Greenland. So sánh theo thứ tự chữ cái Tiếng Anh ta có Iceland > Greenland, do đó vùng tìm kiếm thu hẹp chỉ còn nửa sau của danh sách (từ phần tử thứ 6 đến thứ 9).
Bước 2. Chọn phần từ số 7 ở giữa, đó là Portugal. So sánh theo thứ tự chữ cái Tiếng Anh ta có Iceland < Portugal, do đó vùng tìm kiếm thu hẹp chỉ còn nửa trước của danh sách (từ phần tử thứ 6 đến thứ 7).
Bước 3. Chọn phần tử số 6 ở giữa, đó là Iceland. So sánh theo thứ tự chữ cái Tiếng Anh ta có Iceland = Iceland, tìm thấy tên nước cần tìm nên thuật toán dừng lại.

c) So sánh số bước thực hiện của thuật toán tìm kiếm nhị phân với thuật toán tìm kiếm tuyến tính:

Thuật toán tìm kiếm nhị phân thực hiện 3 bước.
Theo danh sách đã sắp xếp, Iceland ở vị trí thứ 6. Nếu tìm kiếm theo thuật toán tìm kiếm tuần tự, cần thực hiện 6 bước. Như vậy, thực hiện tìm kiếm theo thuật toán tìm kiếm nhị phân nhanh hơn so với thuật toán tìm kiếm tuần tự.

+ Câu 2. HS có thể lấy ví dụ là các bài tập trong phần Vận dụng của Bài 14.

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

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.

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ặp đôi và thực hiện các bài tập sau: Em tìm một từ tiếng Anh trong quyển từ điển theo cách nào? Tại sao em lại dùng cách đó?

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

- HS thảo luận nhóm và vận dụng kiến thức đã học, kiến thức thực tế để thực hành.

- 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 HS thực hành lập danh sách những cuốn sách mà em có và sử dụng thuật toán tìm kiếm tuần tự để tìm một cuốn sách trong danh sách đó.

- 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À: