Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 1.3: Ứng dụng của hàng đợi

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 làm việc độc lập và trả lời các câu hỏi:

+ Cơ chế hoạt động của hàng đợi là gì? 

+ Hàng đợi có thể được ứng dụng vào những lĩnh vực nào? Trong mỗi lĩnh vực đó, hàng đợi được sử dụng để làm gì?

+ Em hãy nêu một số ứng dụng phổ biến của hàng đợi trong lĩnh vực Công nghệ thông tin.

-  GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Làm SGK tr.15:

Câu 1. Theo em, hàng đợi có những ứng dụng nào?

Câu 2. Hàng đợi máy in được sử dụng như thế nào?

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.14 – 15 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 Làm SGK tr.15:

Câu 1. Một số ứng dụng của hàng đợi:

+ Quản lí các nhiệm vụ cần thực hiện.

+ Sắp xếp thứ tự in tài liệu.

+ Sắp xếp thứ tự phục vụ các yêu cầu từ máy khách gửi tới máy chủ Email hay web.

Câu 2.Hàng đợi máy in hoạt động theo cơ chế FIFO. Tài liệu nào được gửi tới máy in trước sẽ được in trước.

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

- Từ nội dung trả lời của HS, 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 chốt kiến thức theo hoạt động Ghi nhớ:

• Hàng đợi với cơ chế vào trước ra trước được ứng dụng để giải quyết một số vấn đề trong các lĩnh vực công nghệ thông tin, kinh doanh,... 

• Trong lĩnh vực Công nghệ thông tin, hàng đợi được sử dụng để giải quyết các vấn đề như sắp xếp lịch, phân bố tài nguyên của máy tính, thứ tự gửi email, in tài liệu,...

1. Một số ứng dụng của hàng đợi

- Hàng đợi hoạt động theo cơ chế FIFO (First In, First Out) – vào trước ra trước.

- Hàng đợi được ứng dụng để giải quyết một số vấn đề trong các lĩnh vực Công nghệ thông tin, dịch vụ, kinh doanh,... 

Ví dụ: 

+ Trong lĩnh vực Công nghệ thông tin, hàng đợi được sử dụng để giải quyết các vấn đề như phân bố tài nguyên của hệ điều hành, thứ tự gửi email, in tài liệu. 

+ Trong kinh doanh, hàng đợi được sử dụng để sắp xếp thứ tự xử lí đơn hàng, chăm sóc khách hàng. 

…

- Một số ứng dụng phổ biến của hàng đợi trong lĩnh vực Công nghệ thông tin:

+ Sắp xếp lịch trình: 

• Sử dụng hàng đợi để quản lí các nhiệm vụ cần thực hiện. 

• Một trong những cách tiếp cận đơn giản là "đến trước, phục vụ trước" (FCFS – First Come, First Served). Nghĩa là các nhiệm vụ theo thứ tự yêu cầu được thêm vào cuối hàng đợi với thao tác enqueue và lấy ra khỏi hàng đợi để thực hiện với thao tác dequeue. 

Ví dụ:

Hình 1a. Thứ tự thực hiện các quá trình

Hình 1b. Hàng đợi công việc chứa các

quá trình cần thực hiện

Hình 1. Cơ chế "Đến trước - Phục vụ trước" dùng hàng đợi để thực hiện các quá trình

+ Hàng đợi máy in: 

• Được sử dụng để quản lí thứ tự xử lí lệnh in. 

• Các tài liệu cần in được enqueue vào hàng đợi và được dequeue để thực hiện in theo cơ chế FIFO

Ví dụ:

Hình 2. Minh hoạ hàng đợi máy in

+ Máy chủ email hay web: 

• Sử dụng hàng đợi để quản lí các yêu cầu đến từ máy khách, nhằm đảm bảo xử lí các yêu cầu theo thứ tự thích hợp (chẳng hạn như yêu cầu nào đến trước sẽ được phục vụ trước). 

• Các yêu cầu được enqueue vào hàng đợi và được dequeue để xử lí theo cơ chế FIFO. 

Ví dụ:

Hình 3. Minh hoạ hàng đợi yêu cầu

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 kĩ minh hoạ trò chơi Hot Potato và yêu cầu của Nhiệm vụ SGK tr.16 và thực hành cá nhân theo hướng dẫn.

Trò chơi Hot Potato: Các người chơi đứng thành vòng tròn và lần lượt chuyển củ khoai cho người bên cạnh theo chiều kim đồng hồ trên nền nhạc. Khi nhạc dừng, lượt chơi dừng tạm thời, người nào đang giữ củ khoai sẽ bị loại và giao lại cho người bên cạnh theo chiều kim đồng hồ. Để đơn giản hoá quy định, người chơi có thể quy ước sau m lần chuyển củ khoai thì lượt chơi ngừng tạm thời. Trò chơi tiếp tục cho đến khi chỉ còn lại một người, gọi là người chiến thắng.

Hình 4 minh hoạ trò chơi Hot Potato với 5 người chơi, bắt đầu từ An.

Hình 4. Minh hoạ trò chơi Hot Potato với 5 người chơi

Yêu cầu: Hãy viết chương trình in ra màn hình tên người chiến thắng với danh sách n (n ≥ 1) người chơi và số nguyên dương m (m > 0) được nhập từ bàn phím. Chạy chương trình với số người chơi n = 5.

Hướng dẫn:

Mã giả trò chơi Hot Potato:

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

- HS tiếp nhận và thực hiện theo đúng hướng dẫn để hoàn thành Nhiệm vụ.

- Trong quá trình HS thực hành, GV quan sát, hỗ trợ, giải đáp các vướng mắc của HS.

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

- HS chạy chương trình và báo cáo kết quả cho GV.

- GV kiểm tra kết quả thực hành 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, kiểm tra kết quả thực hiện Nhiệm vụ của HS.

- Nhiệm vụ thực hành được gọi là hoàn thành khi HS hiểu rõ ứng dụng của hàng đợi và chạy được chương trình trò chơi Hot Potato.

2. THỰC HÀNH 

Nhiệm vụ. Trò chơi Hot Potato

- Input: Danh sách 5 người chơi: ['An', 'Trung', 'Quang', 'Nga', 'Han'] và m = 2.

- Output: Tên của người chiến thắng là "Nga".

* Mã nguồn tham khảo: