Kênh giáo viên » Giáo án chuyên đề Tin học 12 - Định hướng khoa học máy tính cánh diều

Giáo án chuyên đề Khoa học máy tính 12 cánh diều Bài 1: Kiểu dữ liệu hàng đợi

Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 12 - Khoa học máy tính bộ sách Cánh diều Bài 1: Kiểu dữ liệu hàng đợi. Bộ giáo án giúp giáo viên hướng dẫn học sinh mở rộng kiến thức, phát triển năng lực, nâng cao khả năng định hướng nghề nghiệp cho các em sau này. Thao tác tải về rất đơn giản, tài liệu file word có thể chỉnh sửa dễ dàng. Mời quý thầy cô tham khảo bài soạn.

Xem: => Giáo án Tin học 12 - Định hướng khoa học máy tính cánh diều

Hướng dẫn tải giáo án

Xem toàn bộ: Giáo án chuyên đề Khoa học máy tính 12 cánh diều đủ cả năm

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: KIỂU DỮ LIỆU 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 được kiểu dữ liệu hàng đợi là kiểu dữ liệu tuyến tính.
Mô tả được khái niệm hàng đợi và cơ chế hoạt động của nó.
Biểu diễn được hàng đợi bằng mảng một chiều và viết được chương trình con thực hiện các phép toán cơ bản trên hàng đợi.
Nêu được một số ứng dụng của hàng đợi.

2. Năng lực

Năng lực chung:

Tự chủ và tự học: Chủ động, tích cực thực hiện công việc của cá nhân.
Giao tiếp và hợp tác: Phân tích được các công việc cần thực hiện để hoàn thành nhiệm vụ của nhóm trong các hoạt động nhóm.
Giải quyết vấn đề và sáng tạo: Nêu được nhiều ý tưởng mới trong học tập, suy nghĩ không theo lối mòn, tạo ra yếu tố mới dựa trên những ý tưởng khác nhau.

Năng lực Tin học:

Biểu diễn được kiểu dữ liệu hàng đợi bằng list trong Python.
Giải thích và viết được các chương trình con có sử dụng các hàm cơ bản của kiểu dữ liệu hàng đợi.

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:

Máy chiếu, máy tính, màn hình hiển thị, hoặc ti vi.
Phòng thực hành, các máy tính có kết nối internet.
SGK, SGV Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

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

Các dụng cụ học tập theo yêu cầu của GV; SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính – Cánh diều.

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 bước đầu hình dung và lấy được các ví dụ về dữ liệu hàng đợi.

b. Nội dung: GV sử dụng câu hỏi ở phần Khởi động SGK tr.5 để đặt vấn đề, HS nêu nhận xét về dữ liệu hàng đợ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:

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 suy nghĩ trả lời câu hỏi Khởi động SGK trang 5:

Một phòng máy thực hành có 50 máy tính nối mạng với một máy in duy nhất (Hình 1). Có nhiều người dùng trong phòng đều có nhu cầu in tệp dữ liệu của họ. Theo em, các tệp dữ liệu đó sẽ được in theo thứ tự thế nào và có hệ thống phải sắp xếp các tệp dữ liệu này như thế nào để làm được điều đó?

A computer room with computers

Description automatically generated

Hình 1. Một ví dụ về nhiều máy tính cùng kết nối đến một máy in

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 mời một số HS xung phong trả lời câu hỏi Khởi động tr.5 SGK.

Gợi ý trả lời:

Trong trường hợp này, để quản lý việc in tệp dữ liệu từ nhiều người dùng trên các máy tính khác nhau một cách hợp lý và hiệu quả, có thể áp dụng một hệ thống hàng đợi (queueing system) để điều phối và quản lý các yêu cầu in.

Cụ thể, là sử dụng cơ chế FIFO (First In, First Out) của hàng đợi, nghĩa là tệp dữ liệu sẽ được in ra theo thứ tự đến trước là được in ra trước. Điều này đảm bảo tính công bằng trong việc xử lý các yêu cầu in và tránh ưu tiên cho một người dùng nào đó.

Để triển khai hệ thống hàng đợi này, có thể sử dụng các phần mềm quản lý hàng đợi như CUPS (Common Unix Printing System) hoặc các giải pháp tương tự. CUPS là một hệ thống in thông dụng trên nhiều hệ điều hành Unix và tương thích với hầu hết các loại máy in.

Khi có yêu cầu in từ một máy tính trong phòng máy thực hành, phần mềm quản lý hàng đợi sẽ ghi nhận yêu cầu đó và đưa vào hàng đợi in. Sau đó, các yêu cầu in sẽ được xử lý theo thứ tự mà chúng đến, đảm bảo tính công bằng và hiệu quả trong việc chia sẻ nguồn lực in.

- HS khác lắng nghe, nhận xét và bổ sung.

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: Hôm nay chúng ta sẽ tìm hiểu về một khái niệm quan trọng trong lập trình - đó là 'kiểu dữ liệu hàng đợi'. Hãy cùng tìm hiểu cách mà kiểu dữ liệu này giúp chúng ta quản lý và xử lý các yêu cầu một cách hiệu quả, thông qua việc áp dụng nguyên tắc 'First In, First Out'. Điều này sẽ giúp các em hiểu rõ hơn về cách thức hoạt động của hệ thống hàng đợi và áp dụng nó vào các bài toán thực tế - Bài 1: Kiểu dữ liệu hàng đợi.

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

Hoạt động 1. Tìm hiểu một số ví dụ về hàng đợi và cơ chế hoạt động

a. Mục tiêu: HS nêu được một số ví dụ về hàng đợi trong thực tế cùng với cơ chế hoạt động của chúng.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Một số ví dụ về hàng đợi và cơ chế hoạt động, 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: Trình bày được một số ví dụ về hàng đợi, cơ chế hoạt động và ứng dụng của hàng đợi trong tin học.

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 cho HS thảo luận theo bàn, đọc và tìm hiểu nội dung trong mục 1 SGK tr.6 để trả lời các câu hỏi sau:

+ Nêu các ví dụ về xếp hàng đợi đến lượt?

+ Mục đích của việc xếp hàng đợi là gì?

+ Cơ chế hoạt động của hàng đợi tuân theo quy tắc nào?

+ Nêu một số ứng dụng của hàng đợi trong Tin học?

- GV gọi lần lượt HS đứng tại chỗ trình bày câu trả lời cho mỗi câu hỏi trên.

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

- HS tìm hiểu nội dung phần a, mục 1 SGK tr.5 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.

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

1. Một số ví dụ về hàng đợi và cơ chế hoạt động

- Ví dụ về hàng đợi: xếp hàng đợi thanh toán ở siêu thị, ở quầy bán vé xem phim, được bác sĩ thăm khám,….

Hình 2. Ví dụ xếp hàng đợi thanh toán ở siêu thị

- Mục đích của việc tạo ra hàng đợi là để đảm bảo công bằng, tránh tình trạng người đến trước lại bị phục vụ sau và ngược lại.

- Cơ chế hoạt động tuân theo quy tắc vào trước ra trước hay còn gọi là FIFO.

- Ứng dụng của hàng đợi trong tin học như:
Khi sử dụng phần mềm nhắn tin trên mạng, tin nhắn gửi đi khi người nhận không kết nối Internet sẽ được xếp vào hàng đợi theo thứ tự gửi đi. Khi người nhận kết nối, tin nhắn sẽ được lấy ra từ hàng đợi và gửi đi, đảm bảo người nhận nhìn thấy các tin nhắn theo thứ tự chúng đã được gửi.

Top of Form

Hoạt động 2. Tìm hiểu kiểu dữ liệu hàng đợi và các phép toán cơ bản trên hàng đợi

a. Mục tiêu: HS mô tả được khái niệm hàng đợi và các phép toán cơ bản trên hàng đợi.

b. Nội dung: GV hướng dẫn HS thực hiện theo các hoạt động trong SGK để thực hiện các phép toán cơ bản trên hàng đợi.

c. Sản phẩm: Kết quả HS thực hiện các yêu cầu, gợi ý, dẫn dắt của GV để thực hiện các thao tác lấy ra, thêm vào trong hàng đợi.

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 cho HS đọc thông tin mục 2 SGK-tr.6 để trả lời câu hỏi:

+ Hàng đợi thuộc kiểu dữ liệu nào?

+ Các phép toán cơ bản trên hàng đợi gồm những phép toán nào?

- GV trình chiếu Hình 3a, 3b cho HS quan sát, kết hợp với đọc thông tin sách SGK để hiểu được cách biểu diễn hàng đợi.

+ Khi dùng mảng một chiều để lưu các phần tử của hàng đợi, ta sẽ lưu như ở Hình 3a.

Hình 3a. Hàng đợi chứa các phần tử là các số nguyên

Quan sát Hình 3a và cho biết mỗi số nguyên được lưu như thế nào?

+ Nếu tiến hành thực hiện một thao tác lấy ra thì số nào sẽ được đưa ra khỏi hàng đợi? Vì sao? Hàng đợi mới thu được sẽ bao gồm những phần tử nào và chỉ số của các phần tử này trong mảng thay đổi như thế nào?

- GV cho HS thảo luận nhóm 4, thực hiện Hoạt động 1 SGK tr.7:

Em hãy:

a) Cho biết những thao tác nào cần được thực hiện để có thể lấy số 6 ra khỏi
hàng đợi ở Hình 4a và vẽ hàng đợi biểu diễn bởi mảng một chiều tại thời điểm lấy xong số 6. Giá trị biến Front thay đổi thế nào so với trạng thái ban đầu ở Hình 4b.
b) Vẽ hàng đợi thu được khi tiếp tục thực hiện một thao tác thêm vào số 8. Giá trị biến Back thay đổi thế nào so với Hình 4b.
c) Tiếp tục thực hiện các thao tác lấy ra cho đến khi hàng đợi rỗng, và cho biết mối quan hệ giữa giá trị biến Front và Back khi hàng đợi rỗng.

- Thông qua phần biểu diễn một hàng đợi, GV đặt câu hỏi:

+ Khi biểu diễn hàng đợi thì cần những biến nào để lưu các chỉ số?

+ Việc thực hiện thao tác lấy ra, thêm vào trong hàng đợi có những nhược điểm nào?

- Để minh họa rõ hơn cho câu trả lời trên, GV trình chiếu Hình 5 là một ví dụ minh họa về biểu diễn hàng đợi bởi mảng một chiều, và giảng cho HS hiểu được ý nghĩa của ví dụ.

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 2 SGK tr.6 – 8 và trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp 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

- HS lần lượt trả lời các câu hỏi.

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

Hướng dẫn trả lời câu hỏi Hoạt động 1 SGK tr.7:

a) Thao tác cần thực hiện:

- Lần lượt lấy ra số 3 và tăng giá trị biến Front = 2; Lấy ra số 5 và tăng giá trị biến Front = 3; Lấy ra số 6 và tăng giá trị biến Front = 4.

- Hàng đợi:

- Giá trị biến Front tăng lên 3 đơn vị so với Hình 4b.

b) – Hàng đợi khi thêm vào số 8:

- Giá trị biến Back tăng lên 1 đơn vị so với Hình 4b.

c) Tiếp tục thực hiện lấy ra cho đến khi hàng đợi rỗng thì không còn phần tử nào nên không có giá trị của biến Front và Back.

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.

2. Kiểu dữ liệu hàng đợi và các phép toán cơ bản trên hàng đợi

- Hàng đợi thuộc kiểu dữ liệu tuyến tính.

- Các phép toán cơ bản:

+ enqueue: Phép toán thêm vào, thực hiện chỉ ở một phía gọi là phía cuối (Back hay Rear).

+ dequeue: Phép toán lấy ra, chỉ thực hiện ở phía còn lại gọi là phía đầu (Front hay Head).

Hình 3b. Biểu diễn hàng đợi ở Hình 3a bởi mảng một chiều

- Mô phỏng một hàng đợi gồm 8 số nguyên lần lượt là 10, 3, 5, 6, -7, 12, 4, 9, trong đó 10 đứng đầu hàng đợi, số 9 đứng cuối hàng đợi.

- Số 10 lưu ở Q[Front] với Front = 0; Số 3 lưu ở Q[Front+1],…và số 9 lưu ở Q[Back].

+ Nếu tiến hành thực hiện thao tác lấy ra thì số 10 sẽ được lấy ra đầu tiên; Vì số 10 đứng đầu hàng đợi.

+ Hàng đợi mới chỉ còn 7 số nguyên như Hình 4a.

Hình 4a. Hàng đợi thu được từ Hình 3a sau khi thực hiện một thao tác lấy ra

- Sau khi lấy số 10 ra, mảng một chiều Q sẽ tăng giá trị biến Front lên 1 đơn vị (Hình 4b).

Hình 4b. Biểu diễn hàng đợi ở Hình 4a bởi mảng một chiều

- Khi biểu diễn hàng đợi bởi mảng một chiều (Q) ta cần hai biến Front và Back để lưu lần lượt chỉ số trong mảng.

- Nếu lấy ra, cần tăng giá trị biến Front lên 1 đơn vị; nếu thêm vào, cần tăng giá trị biến Back lên 1 đơn vị.

- Nhược điểm: Các phần tử từ Q[0] đến Q[Front-1] không được dùng để lưu những phần tử mới được thêm vào hàng đợi.

- Ví dụ minh họa: Mảng Q lưu trữ ba phần tử của hàng đợi theo thứ tự từ đầu đến cuối Q[0]=1; Q[1]=5; Q[2]=9, với Front = 0, Back = 2.

+ Khi lấy ra, biến Front tăng lên 1 đơn vị.

+ Khi thêm vào số 7, biến Back được tăng lên 1 đơn vị như trong Hình 5.

Hình 5. Một ví dụ minh họa về biểu diễn hàng đợi bởi mảng một chiều

Hoạt động 3. Cài đặt hàng đợi

a. Mục tiêu: HS nhận biết được một số hàm và ý nghĩa của chúng trong hàng đợi.

b. Nội dung: GV hướng dẫn HS thực hiện theo các hoạt động trong SGK để biết sử dụng các hàm khi cài đặt hàng đợi.

c. Sản phẩm: Kết quả HS thực hiện các yêu cầu, gợi ý, dẫn dắt của GV để sử dụng được các hàm createQueue(); front(Q); enqueue(Q, data); dequeue(Q); isEmptyQueue(Q).

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

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

Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II