Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 13: Kĩ thuật duyệt quay lui

Giáo án Chuyên đề Tin học 11 Kết nối tri thức Bài 13: Kĩ thuật duyệt quay lui

Xem thử

Chỉ từ 200k mua trọn bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 Kết nối tri thức chuẩn kiến thức, trình bày đẹp mắt, dễ dàng chỉnh sửa:

• B1: gửi phí vào tk: 1133836868 - CT TNHH DAU TU VA DV GD VIETJACK - Ngân hàng MB (QR)
• B2: Nhắn tin tới Zalo VietJack Official - nhấn vào đây để thông báo và nhận giáo án

I. MỤC TIÊU

1. Về kiến thức

Sau bài học này, HS sẽ:

- Biết và trình bày được ý tưởng của kĩ thuật quay lui thông qua một số ví dụ đơn giản.

- Nhận ra được mối liên quan giữa thiết kế thuật toán theo kĩ thuật quay lui và kĩ thuật đệ quy.

- Thực hiện được chương trình sinh tất cả các xâu nhị phân bằng kĩ thuật quay lui.

2. 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 giải quyết vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

3. Phẩm chất:

- Hình thành ý thức 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ụ.

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

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

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

- SGK, SGV, Giáo án;

- Máy tính đã cài đặt Python và máy chiếu;

- Sơ đồ một trò chơi mê cung trên giấy.

- Phần mềm mô phỏng trò chơi mê cung cho phép HS tự chơi trên máy tính.

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

- SGK, vở ghi.

- Kiến thức Python.

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 mê cung cùng lịch sử hình thành thuật toán vét cạn quay lui.

- Kích thích sự tò mò cho người học.

b. Nội dung: GV cho các nhóm HS trao đổi để nhận ra các tính chất chung nhất của các hiện tượng và đưa ra lời giải của bài toán này.

c. Sản phẩm học tập: HS dựa vào kiến thức và hiểu biết cá nhân để đưa ra câu trả lời.

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

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

- GV yêu cầu HS đọc nội dung mở đầu, quan sát hình ảnh

Chúng ta đã biết từ bài học trước, thiết lập các thuật toán duyệt sẽ phụ thuộc hoàn toàn vào mô hình và cấu trúc của miền dữ liệu cần tìm kiếm. Từ lâu các nhà khoa học đã nhìn thấy rất nhiều bài toán khó không tìm được cách duyệt hữu hiệu, điển hình nhất là bài toán tìm đường đi trong mê cung.Bài toán tìm đường đi trong mê cung lần đầu tiên được đưa ra trong cuốn sách Récréations Mathématiques của tác giả Édouard Lucas năm 1882 tại Pháp. Cũng trong cuốn sách đó Lucas đã đưa ra phác thảo đầu tiên của một phương pháp giải bài toán tìm đường đi trong mê cung mà bây giờ chúng ta gọi là thuật toán duyệt quay lui, hay đơn giản là thuật toán quay lui (backtracking).

Trong trò chơi mê cung (xem hình) em cần tìm một đường đi xuất phát từ lối vào và ra khỏi mê cung tại lối ra. Em có đề xuất gì để giải bài toán này.

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.

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

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

- Các HS khác nhận xét, nêu ý kiến khác (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, đánh giá, tuyên dương câu trả lời của HS.

- GV dẫn dắt vào nội dung bài mới: Bài 13. Kĩ thuật duyệt quay lui.

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

Hoạt động 1. Tìm hiểu ý tưởng của thuật toán quay lui

a. Mục tiêu: HS biết được ý tưởng ban đầu của thuật toán quay lui dựa trên mô hình bài toán mê cung.

b. Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 1 SGK, đọc thông tin mục 1, thảo luận nhóm và xây dựng kiến thức mới.

c. Sản phẩm học tập: HS nêu được ý tưởng ban đầu của thuật toán quay lui.

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 chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 1 SGK trang 56: Đọc, trao đổi và thảo luận về ý tưởng thuật toán quay lui của bài toán tìm đường đi trong mê cung.   - GV yêu cầu HS thử phác thảo và trao đổi về ý tưởng của thuật toán tìm đường đi bằng vét cạn, quay lui với bài toán mê cung. - GV đưa ra sơ đồ giải mã của thuật toán này. + HS trao đổi tìm hiểu sơ đồ. + HS trình bày, giải thích. - GV chốt kiến thức. - GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr57) để củng cố kiến thức: + Câu 1: Khi đã thực hiện hết các bước lặp tại dòng 2 ở trên thì hàm có dừng không? + Câu 2: Lệnh gọi hàm chính của chương trình trên là gì?

1. Kĩ thuật duyệt quay lui Hoạt động 1 Ý tưởng của thuật toán duyệt quay lui là luôn tìm cách đi tiếp theo. Xuất phát từ vị trí gốc, thuật toán sẽ gọi hàm tìm bước đi tiếp theo. Nếu thực hiện được một bước đi thì gọi lại hàm để tìm bước đi tiếp theo. Nếu không tìm thấy đường đi thì cần "quay lui" về vị trí trước đó để tìm đường đi khác. Thuật toán sẽ sử dụng kĩ thuật đệ quy khi gọi hàm cho bước đi tiếp theo. Sơ đồ mã giả của thuật toán quy lui Giải thích Hàm có chức năng tim bước đi tiếp theo xuất phát từ <vị trí> hiện thời. + Nếu vị trí hiện thời là đích thì thông báo tìm thấy nghiệm tại dòng 3 và dừng chương trình. Dòng 5 sẽ tìm tất cả các phương án có thể đi tiếp. + Nếu tìm thấy một phương án đi khả thi tại dòng 6 thì thực hiện ngay bước đi này tại dòng 7 để cập nhật thông tin vào <vị trí> mới. Sau gọi đệ quy lại hàm gốc để đi tiếp tại dòng 9. + Nếu không thể đi tiếp (lệnh gọi đệ quy dòng 9 không thể thực hiện) thì quay lui tại dòng 10, xoá thông tin bước vừa đi để quay lại vòng lặp 5.

................................

................................

................................

Trên đây tóm tắt một số nội dung miễn phí trong bộ Kế hoạch bài dạy (KHBD) hay Giáo án Chuyên đề Tin học 11 mới nhất, để mua tài liệu đầy đủ, Thầy/Cô vui lòng xem thử:

Xem thử

Xem thêm các bài soạn Giáo án Chuyên đề Tin học lớp 11 Kết nối tri thức hay, chuẩn khác:

• Giáo án Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

• Giáo án Chuyên đề Tin học 11 Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

• Giáo án Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui

• Giáo án Chuyên đề Tin học 11 Bài 15: Bài toán xếp hậu

• Giáo án Chuyên đề Tin học 11 Bài 16: Thực hành thiết kế thuật tóan theo kĩ thuật quay lui

---