Giáo án chuyên đề Khoa học máy tính 12 kết nối Bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi

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

Ngày dạy:…/…/…

CHUYÊN ĐỀ 1: TÌM HIỂU MỘT VÀI KIỂU DỮ LIỆU TUYẾN TÍNH

BÀI 1: MÔ HÌNH DỮ LIỆU NGĂN XẾP VÀ HÀNG ĐỢI

(2 tiết)

I. MỤC TIÊU

1. Kiến thức

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

• Biết và mô tả được mô hình dữ liệu ngăn xếp và hàng đợi thông qua cơ chế hoạt động của các kiểu dữ liệu này.

2. Năng lực

Năng lực chung: 

• Năng lực giao tiếp và hợp tác: Biết lựa chọn hình thức làm việc nhóm với quy mô phù hợp với yêu cầu và thực hiện tốt nhiệm vụ.

• Năng lực tự chủ và tự học: Chủ động học tập, tìm hiểu nội dung bài học, biết lắng nghe và trả lời nội dung trong bài học.

• Giải quyết vấn đề và sáng tạo: Trả lời được các câu hỏi, giải quyết được các vấn đề với sự hỗ trợ của công nghệ thông tin và truyền thông.

Năng lực Tin học:

• Mô tả được mô hình dữ liệu ngăn xếp và hàng đợi thông qua cơ chế hoạt động của các kiểu dữ liệu này.

3. Phẩm chất

• Chăm chỉ: Tích cực tìm tòi và sáng tạo trong học tập.

• Trung thực: Thực hiện đúng phần việc của bản thân và hợp tác làm việc nhóm khi được giao nhiệm vụ. Có ý thức báo cáo kết quả một cách chính xác.

• Trách nhiệm: Hoàn thành các bài tập theo yêu cầu của GV thông qua hệ thống câu hỏi, phiếu học tập, thông qua 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:

• Tài liệu, máy tính, máy trình chiếu.

• SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

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

• Vở ghi, máy tính. 

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Kết nối tri thức với cuộc sống.

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

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

a. Mục tiêu: Tạo hứng thú cho HS, giúp HS làm quen với những hiện tượng, sự vật trong cuộc sống có liên quan đến mô hình ngăn xếp và hàng đợi.

b. Nội dung: HS quan sát các hình ảnh và trả lời câu hỏi. 

c. Sản phẩm học tập: Từ yêu cầu, HS vận dụng sự hiểu biết để trả lời câu hỏi GV đưa ra.

d. Tổ chức thực hiện: GV chia lớp thành 6 nhóm, mỗi nhóm thảo luận trong thời gian 2 phút và ghi kết quả trả lời ra giấy.

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

- GV dẫn dắt vào bài học, yêu cầu HS quan sát và trả lời câu hỏi Khởi động SGK trang 5: Em hãy quan sát các hình ảnh về đồ vật và hiện tượng trong thực tế trong Hình 1.1 và cho biết:

a) Trong chồng đĩa, đĩa nào được xếp vào sau cùng? Đĩa nào được lấy ra đầu tiên?

b) Ai sẽ là người được rút tiền trước tại cây ATM? Người xếp hàng cuối cùng sẽ được rút tiền khi nào?

Hình 1.1. Một số đồ vật và hiện tượng trong thực tế

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

- HS tiếp nhận, thực hiện nhiệm vụ.

- 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 thu kết quả trả lời của từng nhóm, cho HS quan sát kết quả các nhóm và nhận xét.

Gợi ý trả lời:

- Hình a: Đĩa nào cho vào trước thì sẽ lấy ra sau cùng, đĩa nào cho vào sau cùng sẽ lấy ra đầu tiên.

Đây là cơ chế hoạt động của mô hình dữ liệu ngăn xếp (stack).

- Hình b: Ai xếp hàng trước sẽ được rút tiền trước, ai xếp sau sẽ rút tiền sau theo đúng thứ tự. 

Đây là cơ chế hoạt động của mô hình hàng đợi (queue).

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

GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Ngăn xếp (Stack) và Hàng đợi (Queue) là hai trong số những cấu trúc dữ liệu cực kỳ quan trọng, được sử dụng thường xuyên trong thiết kế thuật toán. Về bản chất, ngăn xếp và hàng đợi cũng giống như mảng, chúng là một tập hợp các phần tử cùng kiểu dữ liệu, nhưng được lưu trữ có tính thứ tự. Để hiểu rõ hơn về hai loại mô hình dữ liệu này, chúng ta sẽ cùng nhau đến với Bài 1: Mô hình dữ liệu ngăn xếp và hàng đợi.

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

Hoạt động 1. Tìm hiểu mô hình dữ liệu ngăn xếp

a. Mục tiêu: HS hiểu được cơ chế hoạt động của ngăn xếp, các thao tác chính và ý nghĩa của các thao tác này.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Mô hình dữ liệu ngăn xếp, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Mô tả được mô hình dữ liệu ngăn xếp thông qua cơ chế hoạt động của nó.

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

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, trao đổi và thảo luận theo nhóm đôi tìm hiểu nội dung mục 1 SGK tr.5 – 6, trả lời các câu hỏi sau: + Mô hình dữ liệu ngăn xếp hoạt động theo cơ chế gì? + Em hãy nêu một ví dụ khác về ngăn xếp và mô tả cách hoạt động của ví dụ này. + Em hãy mô tả mô hình dữ liệu ngăn xếp. Hình 1.2. Mô hình ngăn xếp + Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất. - GV yêu cầu HS đọc hiểu Ví dụ 1, 2 tr.6 SGK. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.7 SGK: Câu 1. Muốn lấy ra phần tử nằm ở đáy của ngăn xếp thì phải làm như thế nào? Câu 2. Cho S là một ngăn xếp rỗng. Em hãy cho biết, khi thực hiện các lệnh sau thì S sẽ chứa những phần tử nào? push(S,1); push(S,5); pop(S); push(S,10). Bước 2: HS thực hiện nhiệm vụ học tập - HS tìm hiểu nội dung mục 1 SGK tr. 5 – 6 sau đó trao đổi, thảo luận trả lời các câu hỏi mà GV đưa ra. - GV quan sát, 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 các nhóm báo cáo kết quả thảo luận. Hướng dẫn trả lời câu hỏi Củng cố tr.7 SGK: Câu 1. Để lấy ra phần tử nằm ở đáy của ngăn xếp thì phải pop(S) tất cả các phần tử trong Stack. Câu 2. S sẽ chứa phần tử 1, 10. - 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 - Từ kết quả thảo luận của nhóm, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ. - GV chính xác hoá lại các nội dung kiến thức. - GV kết luận:  + Đặc điểm: Ngăn xếp (stack) thuộc kiểu dữ liệu tuyến tính có các hàm cơ bản: hàm push() để đưa dữ liệu vào và hàm pop() để lấy dữ liệu ra ở cùng một đầu là đỉnh của ngăn xếp. Một số hàm khác là isEmptyStack(), top(). + Cơ chế hoạt động: Ngăn xếp hoạt động theo cơ chế “vào sau, ra trước” (LIFO). - GV chuyển sang nội dung Thực hành làm quen với phần mềm GanttProject.

1. Mô hình dữ liệu ngăn xếp - Cơ chế hoạt động của mô hình dữ liệu ngăn xếp: “vào sau, ra trước” (LIFO – Last In, First Out). - Ví dụ khác về ngăn xếp: chức năng Undo khi soạn thảo văn bản. Mỗi khi thực hiện một thao tác mới, trạng thái hiện tại của văn bản được đưa vào đỉnh của ngăn xếp Undo. Khi yêu cầu Undo, trạng thái hiện tại được lấy ra từ đỉnh ngăn xếp và khôi phục lại. - Mô hình dữ liệu ngăn xếp được mô tả như sau: + Ngăn xếp là một dãy tuyến tính các phần tử dữ liệu. + Ngăn xếp có các thao tác đưa phần tử vào và lấy phần tử ra tại cùng một đầu của ngăn xếp. Thao tác đưa dữ liệu vào là push và lấy dữ liệu ra là pop. + Quy ước đầu dùng để đưa dữ liệu vào và lấy dữ liệu ra là đỉnh (top) của ngăn xếp. Đầu ngược lại là đáy (bottom) của ngăn xếp. + Mô hình dữ liệu ngăn xếp hoạt động theo cơ chế LIFO. - Các thao tác cơ bản trên dữ liệu ngăn xếp:

Hoạt động 2. Tìm hiểu mô hình dữ liệu hàng đợi

a. Mục tiêu: HS hiểu được cơ chế hoạt động, các thao tác cơ bản của hàng đợi và ý nghĩa của các thao tác này.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Mô hình dữ liệu hàng đợi, kết hợp với những hiểu biết về thực tiễn, thảo luận nhóm thực hiện nhiệm vụ.

c. Sản phẩm: Mô tả được mô hình dữ liệu hàng đợi thông qua cơ chế hoạt động của nó.

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

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, trao đổi và thảo luận theo nhóm đôi tìm hiểu nội dung mục 2 SGK tr.7 – 8, trả lời các câu hỏi sau: + Mô hình dữ liệu hàng đợi hoạt động theo cơ chế gì? + Em hãy nêu một ví dụ của mô hình hàng đợi và mô tả cách hoạt động của ví dụ này. + Em hãy mô tả mô hình dữ liệu hàng đợi. Hình 1.3. Mô hình hàng đợi + Hãy ghép nối các nội dung cột A với cột B để có kết quả đúng nhất. - GV yêu cầu HS đọc hiểu Ví dụ 1, 2 tr.8 SGK. - GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, trả lời câu hỏi Củng cố tr.8 SGK: …………….

2. Mô hình dữ liệu hàng đợi - Cơ chế hoạt động của mô hình dữ liệu hàng đợi: “vào trước, ra trước” (FIFO – First In, First Out). - Ví dụ của mô hình hàng đợi: máy in.  Máy in sẽ lưu trữ các nội dung in vào một hàng đợi, nội dung nào vào trước sẽ được in trước, nội dung nào vào sau được in sau. - Mô hình dữ liệu hàng đợi được mô tả như sau: ………………

--------------- Còn tiếp ---------------