Giáo án NLS Tin học 11 KHMT kết nối Bài 19: Bài toán tìm kiếm

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

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

BÀI 19: BÀI TOÁN TÌM KIẾM

I. MỤC TIÊU:

1. Kiến thức: 

Học xong bài này, HS đạt các yêu cầu sau:

• Biết được ý nghĩa của bài toán tìm kiếm trên thực tế.
• Biết và thực hiện được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân.

2. Năng lực 

Năng lực chung:

• Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập 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 GV.
• Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.

Năng lực riêng: 

• Biết được ý nghĩa của bài toán tìm kiếm trên thực tế.
• Biết và thực hiện được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân.
• Thực hiện được các chương trình tìm kiếm tuần tự và tìm kiếm nhị phân trên một mảng dữ liệu tuyến tính.

Năng lực số:

• 1.2.NC1a: Phân tích đặc điểm dữ liệu đầu vào (đã sắp xếp hay chưa) để lựa chọn thuật toán tìm kiếm phù hợp tối ưu.
• 6.2.NC1a: Sử dụng Chatbot AI để mô phỏng từng bước chạy của thuật toán (Trace Table) và sinh dữ liệu lớn (Big Data) để kiểm chứng hiệu năng.
• 5.2.NC1a: Hiện thực hóa thuật toán thành mã nguồn Python chạy được.
• 6.1.NC1a: Phát hiện và xử lý các lỗi logic thường gặp trong thuật toán tìm kiếm nhị phân (như vòng lặp vô hạn, tính sai chỉ số mid).

3. Phẩm chất

• Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.

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

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

• SGK, tài liệu giảng dạy, giáo án PPT.
• Máy tính, máy chiếu.
• Video AI tạo bằng công cụ AI được dùng để khởi động bài học.

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

• SGK, SBT Tin học 11, vở ghi chép.
• Tài liệu, thiết bị có liên quan đến nội dung bài học.
• Thiết bị di động/máy tính có kết nối Internet (sử dụng theo nhóm).

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

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

a) Mục tiêu: HS làm quen với bài toán tìm kiếm thông qua một trò chơi quen thuộc.

b) Nội dung: GV tổ chức cho HS chơi trò chơi/trả lời câu hỏi ở phần Mở đầu, thông qua trò chơi để giới thiệu bài toán chính sẽ được học trong bài là bài toán tìm kiếm.

c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra. 

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

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

- GV yêu cầu xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.

- GV dẫn dắt, đặt vấn đề cho HS: Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thể được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Người chơi mỗi lần chỉ được lật một thẻ để xe giá trị số in trên đó. Nếu giá trị số in trên thẻ lật lên bằng số K cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối.

- GV đặt câu hỏi yêu cầu HS trả lời: Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?

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

- HS xem video và suy nghĩ câu trả lời.

- HS lắng nghe, suy nghĩ câu trả lời.

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

- GV gọi đại diện một số HS trả lời.

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

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá và kết luận.

[6.1.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.

2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).

1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]

- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Bài 19: Bài toán tìm kiếm

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

Hoạt động 1: Tìm hiểu bài toán tìm kiếm trên thực tế 

a) Mục tiêu: Giúp HS hiểu được mô hình bài toán tìm kiếm tổng quát, biết được ý nghĩa quan trọng của bài toán tìm kiếm.

b) Nội dung: GV tổ chức cho HS thực hiện nhiệm vụ theo nhóm và tìm hiểu được mô hình bài toán tìm kiếm trong thực tế.

c) Sản phẩm: HS nêu được ý nghĩa của bài toán tìm kiếm.

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

Hoạt động 2: Tìm hiểu tìm kiếm tuần tự

a) Mục tiêu: Giúp HS biết và thực hiện được các bước của thuật toán tìm kiếm tuần tự.

b) Nội dung: GV tổ chức cho HS thực hiện nhiệm vụ theo nhóm và nêu được các bước của thuật toán tìm kiếm tuần tự.

c) Sản phẩm: HS nêu được các bước của thuật toán tìm kiếm tuần tự.

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

…………………………………………..

…………………………………………..

…………………………………………..
 

Hoạt động 3: Tìm hiểu tìm kiếm nhị phân

a) Mục tiêu: Giúp HS biết và hiểu được các bước thực hiện của thuật toán tìm kiếm nhị phân.

b) Nội dung: GV tổ chức cho HS thực hiện nhiệm vụ theo nhóm và nêu được các bước của thuật toán tìm kiếm nhị phân.

c) Sản phẩm: HS nêu được các bước của thuật toán tìm kiếm nhị phân.

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

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

a) Mục tiêu: HS củng cố kiến thức về bài toán tìm kiếm.

b) Nội dung: HS trả lời câu hỏi trắc nghiệm và hoàn thành bài tập phần Luyện tập trang 93 SGK.

c) Sản phẩm học tập: Gợi ý trả lời câu hỏi về bài toán tìm kiếm.

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

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

- GV tổ chức trò chơi trắc nghiệm nhanh trên Quizizz hoặc Kahoot để củng cố toàn bài.

- GV cung cấp mã QR hoặc đường Links cho HS làm Phiếu bài tập, trả lời nhanh một số câu hỏi trắc nghiệm tổng kết bài học.

…………………………………………..

…………………………………………..

…………………………………………..
 

1.2.NC1a: Tổ chức dữ liệu thành mảng, truy cập vào dữ liệu để lấy thông tin.

6.1.NC1a: Xác định nhu cầu và giải quyết vấn đề kỹ thuật.]

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

a) Mục tiêu: HS thực hiện làm bài tập Vận dụng để nắm vững kiến thức.

b) Nội dung: HS vận dụng kiến thức đã học và hiểu biết của bản thân để làm bài tập Vận dụng trang 93 SGK.

c) Sản phẩm: Câu trả lời nội dung Vận dụng.

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

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

- GV yêu cầu HS hoàn thành bài tập phần Vận dụng trang 93 SGK.

Bài 1. Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.

Bài 2. Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết chương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.

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

- HS tự tìm hiểu, đưa ra ý kiến.

- GV điều hành, quan sát, hỗ trợ.

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

- HS trình bày kết quả.

Kết quả:

Bài 1.

1        def LinerSearch(A,K):

2                 for i in range(len(A)):

3                           if A[i] == K:

4                                     return i

5                 return -1

6                                     

7        A = ["Hà", "Bình", "Oanh", "An", "Việt"]

8        ten = input("Nhập tên học sinh cần tìm: ")

9        if LinearSearch(A,ten) >= 0:

10                print("Lớp có bạn",ten)

11      else                                 

12               print("Lớp không có bạn",ten)

Bài 2. 

1        def BinarySearch(A,K):

2                 left = 0

3                 right = len(A) - 1

4                 while left <= right:

5                           mid = (left + right)//2

6                                     if A[mid] == K:

7                                              return mid

8                                     elif A[mid] < K:

9                                              left = mid + 1

10                                   else:

11                                            right = mid -1

12               return -1 

13                                  

14      A = ["An", "Bình", "Hà", "Oanh", "Việt"]

15      ten = input("Nhập tên học sinh cần tìm: ")

16      if BinarySearch(A,ten) >= 0:

17                print("Lớp có bạn",ten)

18      else                                 

19               print("Lớp không có bạn",ten)

Bước 4: Đánh giá kết quả thực hiện

- GV nhận xét, đánh giá, đưa ra một vài ý mà HS còn thiếu, chốt đáp án.

- GV tổng kết tiết học.

[5.2.NC1a: HS viết chương trình máy tính để thực hiện yêu cầu.

1.2.NC1a: Tổ chức dữ liệu thành mảng, truy cập vào dữ liệu để lấy thông tin.

6.1.NC1a: Xác định nhu cầu và giải quyết vấn đề kỹ thuật.]

…………………………………………..

…………………………………………..

…………………………………………..