Các bài khác
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 1 Bên trong máy tính
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 2 Khám phá thế giới thiết bị số thông minh
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 3 Khái quát về hệ điều hành
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 4 Thực hành với các thiết bị số
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề A Bài 5 Phần mềm ứng dụng và dịch vụ phần mềm
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 1 Lưu trữ trực tuyến
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 2 Thực hành một số tính năng hữu ích của máy tìm kiếm
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 3 Thực hành một số tính năng nâng cao của mạng xã hội
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề C Bài 4 Thực hành một số tính năng hữu ích của dịch vụ thư điện tử
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề D Bài Phòng tránh lừa đảo và ứng xử văn hoá trên mạng
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 1 Bài toán quản lí và cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 2 Bảng và khoá chính trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 3 Quan hệ giữa các bảng và khoá ngoài trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 4 Các biểu mẫu cho xem và cập nhật dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 5 Truy vấn trong cơ sở dữ liệu quan hệ
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 6 Truy vấn trong cơ sở dữ liệu quan hệ (tiếp theo)
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 7 Các loại kiến trúc của hệ cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F Bài 8 Bảo vệ an toàn của hệ cơ sở dữ liệu và bảo mật thông tin trong cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề G Bài Nghề quản trị cơ sở dữ liệu
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 1 Kiểu mảng và cấu trúc mảng
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 2 Mảng hai chiều
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 3 Thực hành về tệp, mảng và danh sách
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 4 Làm mịn dần từng bước từ thuật toán đến chương trình máy tính
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 5 Đánh giá thuật toán
- Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 6 Kiểm thử và sửa lỗi chương trình
Khoa học máy tính 11 cánh diều: Tải giáo án Chủ đề F(CS) Bài 7 Lập trình giải bài toán tìm kiếm
Mẫu giáo án chủ đề F(CS) Bài 7 Lập trình giải bài toán tìm kiếm - khoa học máy tính 11 cánh diều. Giáo án được biên soạn chi chủ đề. Có thể tải về tham khảo. Cách tải nhanh chóng, dễ dàng. Ngoài ra, hệ thống có đủ các chủ đề khác trong chương trình khoa học máy tính 11 cánh diều
Nội dung giáo án
Ngày soạn:…/…/…
Ngày dạy:…/…/…
BÀI 7. LẬP TRÌNH GIẢI BÀI TOÁN TÌM KIẾM
- MỤC TIÊU
- Về kiến thức
Sau bài học này, HS sẽ:
- Phát biểu được bài toán tìm kiếm.
- Viết được chương trình cho một số thuật toán tìm kiếm.
- Vận dụng được quy tắc thực hành xác định độ phức tạp của một vài thuật toán tìm kiếm đơn giản.
- Năng lực
Năng lực chung:
- Năng lực tự chủ: Biết lựa chọn các nguồn tài liệu học tập phù hợp.
- Năng lực giải quyết vấn đề và sáng tạo: Xác định và tìm hiểu được các thông tin liên quan đến vấn đề, đề xuất giải pháp giải quyết vấn đề trong bài học.
- Năng lực giao tiếp và hợp tác: Thực hiện tốt nhiệm vụ trong hoạt động nhóm.
Năng lực tin học:
- Hình thành, phát triển năng lực tin học giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.
- Ứng dụng công nghệ thông tin và truyền thông trong học và tự học.
- Khả năng tư duy logic và mô hình hóa.
- Phẩm chất
- Hình thành ý thức trách nhiệm, tính cẩn thận, chăm chỉ trong học tập và công việc.
- Có ý thức vận dụng kiến thức, kĩ năng đã học ở nhà trường vào thực tiễn.
- THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
- Đối với giáo viên
- SGK, SGV, Giáo án;
- Máy tính và máy chiếu;
- Tài liệu hướng dẫn sử dụng máy tính (tivi, điện thoại,...) (nếu có).
- Đối với học sinh: SGK, SBT, vở ghi.
III. TIẾN TRÌNH DẠY HỌC
- HOẠT ĐỘNG KHỞI ĐỘNG
- Mục tiêu: Tạo tâm thế vui vẻ, hứng khởi cho HS trước khi vào bài học mới; kích thích sự tò mò cho người học.
- Nội dung: GV cho HS liên hệ thực tế, dùng những hiểu biết của bản thân để trả lời câu hỏi.
- Sản phẩm học tập: Câu trả lời của HS theo ý kiến cá nhân.
- Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ học tập
- GV đặt câu hỏi: Khi mới tạo một tài khoản người dùng, em được yêu cầu nhập tên người dùng “user name”. Có trường hợp em phải nhập lại tên khác vì tên vừa nhập đã có người sử dụng rồi. Theo em, máy tính làm gì ngay sau khi nhận được yêu cầu tạo mới một tài khoản? Hãy phát biểu thành một bài toán.
Bước 2: HS thực hiện nhiệm vụ học tập
- HS lắng nghe, suy nghĩ và đưa ra câu trả lời dựa trên những hiểu biết của bản thân.
Bước 3: Báo cáo kết quả hoạt động và thảo luận
- GV mời 2 - 3 HS trả lời câu hỏi.
Gợi ý:
+ Máy tính bắt đầu tìm kiếm dữ liệu và tiến hành xử lí thông tin ngay sau khi nhận.
+ Bài toán: Cho tên người dùng “user name” và danh sách tài khoản, hãy tìm kiếm trong danh sách những người đã sử dụng tên này.
- GV ghi nhận tất cả các câu trả lời của HS.
Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập
- GV nhận xét, đánh giá, dẫn dắt vào nội dung bài mới: Thế nào là bài toán tìm kiếm? Làm thế nào để thiết kế thuật toán tìm kiếm bằng hàm Python? Chúng ta hãy cùng vào - Bài 6. Kiểm thử và sửa lỗi chương trình.
- HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Bài toán tìm kiếm
- Mục tiêu: Phát biểu được bài toán tìm kiếm.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 1 SGK trang 117 - 118; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Khái niệm bài toán tìm kiếm và tìm kiếm tuần tự bằng hàm của Python.
- 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 Nhiệm vụ 1. Bài toán tìm kiếm - GV yêu cầu dựa vào hiểu biết của bản thân: Nêu ví dụ một số bài toán tìm kiếm trong thực tế. (Yêu cầu HS phát biểu rõ ràng từng bài toán theo mẫu phát biểu bài toán tìm kiếm cụ thể mà phần khởi động đã đưa ra). - Trên cơ sở các ví dụ vừa nêu, GV yêu cầu HS đọc mục 1a tr.117 SGK: Trình bày bài toán tìm kiếm theo nghĩa chung nhất. Nhiệm vụ 2. Tìm kiếm tuần tự bằng hàm của Python - GV chiếu minh họa kết quả chạy máy với ví dụ và giải thích: Với mảng a = [1, 2, 3, 4, 5, 6] như hình bên, câu lệnh print(a.index(3, 1, 4)) sẽ in ra màn hình kết quả là 2, cho biết vị trí của phần tử 3 trong đoạn [1, 4] ở mảng a. - Từ ví dụ vừa nêu, GV yêu cầu HS đọc hiểu thông tin mục 1b tr.117 - 118 và trả lời: Trình bày phương thức tìm kiếm tuần tự hằng hàm của Python. Bước 2: HS thực hiện nhiệm vụ học tập - HS đọc và tìm hiểu thông tin mục 1 SGK trang 117, thực hiện nhiệm vụ được giao. - GV hướng dẫn, theo dõi, hỗ trợ HS khi cần. Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS giơ tay trả lờ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ận xét câu trả lời của HS. - GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở. |
1. Bài toán tìm kiếm a) Khái niệm bài toán tìm kiếm - Theo nghĩa chung nhất, bài toán tìm kiếm là: Cho một yêu cầu tìm kiếm và một tập hợp dữ liệu là phạm vi tìm kiếm. Hãy tìm mục (các mục) dữ liệu đáp ứng yêu cầu tìm kiếm đã cho hoặc khẳng định không có mục dữ liệu nào đáp ứng yêu cầu đó. Ví dụ: + Cho mã cuốn sách, hãy tìm cuốn sách trong kho sách của thư viện. + Tìm một tên người trong danh sách khám bệnh… b) Tìm kiếm tuần tự bằng hàm của Python - Phương thức index thực hiện tìm kiếm theo cách tuần tự cho dãy xâu kí tự, mảng hoặc danh sách. - Các trường hợp trả về khi dùng index + Nếu xuất hiện nhiều lần thì đưa ra chỉ số của lần xuất hiện đầu tiên. Ví dụ: a = [1, 3, 3, 4, 3, 5, 6] print(a.index(3)) + Báo lỗi “valueError” nếu không tìm thấy. Ví dụ: a = [1, 2, 3, 4, 5, 6] print(a.index(5, 1, 4)) + Phương thức index có hai tham số tùy chọn: lo, hi để hạn chế thực hiện tìm kiếm chỉ trong đoạn con của dãy số, bắt đầu từ chỉ số lo (lowest) và kết thúc ở hi (highest). Cú pháp: dãy_số.index(giá_trị, lo, hi)
|
Hoạt động 2: Thuật toán tìm kiếm tuần tự
- Mục tiêu:
- Viết được chương trình cho một số thuật toán tìm kiếm.
- Vận dụng được quy tắc thực hành xác định độ phức tạp của một vài thuật toán tìm kiếm đơn giản.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 2 SGK trang 118; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Thuật toán tìm kiếm tuần tự.
- 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 yêu cầu HS đọc hiểu thông tin mục 2 tr.118, quan sát Hình 1 và Hình 2, thảo luận cặp đôi trả lời câu hỏi: Vận dụng kiến thức đã học ở bài trước, hãy xác định độ phức tạp thời gian của thuật toán trong để tìm kiếm tuần tự một số x. Bước 2: HS thực hiện nhiệm vụ học tập - HS đọc hiểu thông tin mục 2 SGK trang 118 và thực hiện nhiệm vụ. - GV theo dõi, hỗ trợ HS trong quá trình học tập. Bước 3: Báo cáo kết quả hoạt động và thảo luận - HS giơ tay trả lời câu hỏi: Độ phức tạp thời gian của thuật toán tìm kiếm tuần tự là O(n). - Các HS còn lại nhận xét, bổ sung (nếu có). Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập - GV nhận xét kết quả trả lời của HS. - GV tổng quát kiến thức và yêu cầu HS ghi chép đầy đủ vào vở. |
2. Thuật toán tìm kiếm tuần tự - Thực hiện tìm kiếm tuần tự bằng phép lặp duyệt từ đầu dãy số với điều kiện dừng khi “tìm thấy” hoặc “đã xét hết dãy số”. Chi tiết dần từng bước thuật toán tìm kiếm tuần tự Từ mô tả liệt kê các bước của thuật toán tìm kiếm tuần tự chuyển thành mã giả |
Hoạt động 3: Thuật toán tìm kiếm nhị phân
- Mục tiêu:
- Viết được chương trình cho một số thuật toán tìm kiếm.
- Vận dụng được quy tắc thực hành xác định độ phức tạp của một vài thuật toán tìm kiếm đơn giản.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin mục 3 SGK trang 119 – 120; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Thuật toán tìm kiếm nhị phân.
- 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 yêu cầu HS đọc hiểu thông tin mục 3 tr.119 - 120, quan sát Hình 3, 4 trả lời câu hỏi Hoạt động: Dựa trên mô tả thuật toán tìm kiếm nhị phân cho ở Hình 3, em hãy nêu tóm tắt ý tưởng của thuật toán này. Bước 2: HS thực hiện nhiệm vụ học tập - HS đọc và tìm hiểu nhiệm vụ mục 3 SGK trang 119 - 120, thực hiện các nhiệm vụ được giao. - GV hướng dẫn, theo dõi, hỗ trợ HS khi 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 một số nhóm trình bày kết quả thảo luận: Ý tưởng của thuật toán tìm kiếm nhị phân: + So sánh x với phần tử chính giữa mảng A (nếu x là phần tử giữa thì dừng) + Nếu không: xác định xem x có thể thuộc nửa trái hay nửa phải của A. + Lặp lại 2 bước trên với nửa đã được xác định. - GV mời HS nhóm 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ận xét kết quả thảo luận của HS, thái độ làm việc của HS trong nhóm. - GV kết luận và yêu cầu HS ghi chép đầy đủ vào vở. |
3. Thuật toán tìm kiếm nhị phân - Nếu dãy số đã sắp xếp theo thứ tự thì có thể áp dụng thuật toán tìm kiếm nhị phân. - Phép lặp lại thực hiện tìm kiếm nhị phân chia đôi dãy số tại điểm “giữa” có chỉ số (lo + hi)//2, bỏ bớt nửa dãy cho đến khi “tìm thấy” hoặc hết dãy.
|
Hoạt động 4: Thực hành lập trình giải bài toán tìm kiếm
- Mục tiêu: Thực hành lập trình giải bài toán tìm kiếm.
- Nội dung: GV giao nhiệm vụ, HS đọc hiểu thông tin nhiệm vụ mục 4 SGK trang 120; thực hiện các nhiệm vụ GV giao.
- Sản phẩm học tập: Thực hành lập trình giải bài toán tìm kiếm..
- Tổ chức hoạt động:
Thông tin tải tải liệu
Nhận xét
Đánh giá trung bình
Chi tiết
Kho tài liệu Tin học 11 cánh diều
Giáo án lớp 11 cánh diều chương trình mới bản chuẩn
1. Giáo án ban tự nhiên
- Giáo án toán 11 cánh diều chuẩn nhất
- Giáo án vật lí 11 cánh diều chuẩn nhất
- Giáo án sinh học 11 cánh diều chuẩn nhất
- Giáo án hoá học 11 cánh diều chuẩn nhất
- Giáo án tiếng anh 11 cánh diều chuẩn nhất
2. Giáo án ban xã hội
- Giáo án ngữ văn 11 cánh diều chuẩn nhất
- Giáo án lịch sử 11 cánh diều chuẩn nhất
- Giáo án Địa lí 11 cánh diều chuẩn nhất
- Giáo án kinh tế pháp luật 11 cánh diều chuẩn nhất
3. Giáo án các môn khác
Giáo án tin học cánh diều bản chuẩn, đầy đủ
Tin học cánh diều THPT
- Giáo án Tin học 10 Cánh diều chuẩn nhất
- Giáo án Tin học 11 Cánh diều chuẩn nhất
- Giáo án Tin học 12 Cánh diều chuẩn nhất
Tin học cánh diều THCS
- Giáo án Tin học 6 Cánh diều chuẩn nhất
- Giáo án Tin học 7 Cánh diều chuẩn nhất
- Giáo án Tin học 8 Cánh diều chuẩn nhất
- Giáo án Tin học 9 Cánh diều chuẩn nhất