Giáo án NLS chuyên đề Tin học 12 KHMT Bài 4: Kiểu dữ liệu hàng đợi

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

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

BÀI 4: 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ểu diễn được hàng đợi bằng mảng một chiều.
• Giải thích và viết được các chương trình con sử dụng các hàm cơ bản của kiểu dữ liệu hàng đợi.

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:

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

Năng lực số:

• 1.3.NC1a: Quản lý dữ liệu, thông tin và nội dung số (HS thực hiện thao tác vẽ sơ đồ biến đổi trạng thái hàng đợi hoặc gõ các đoạn mô tả trên máy tính để tổ chức, lưu trữ và truy xuất các phần tử của hàng đợi theo cơ chế FIFO).
• 2.1.NC1a: Tương tác thông qua công nghệ số (HS xem video được tạo bởi công cụ AI và trả lời câu hỏi, sử dụng máy tính cá nhân hoặc thiết bị di động có kết nối Internet để làm bài tập trắc nghiệm củng cố trên môi trường số).
• 5.3.NC1a: Sử dụng sáng tạo công nghệ số (HS sử dụng công cụ lập trình Python IDE trên máy tính cá nhân để tự gõ, gỡ lỗi và thực thi thành công chương trình thiết lập hàng đợi và các thao tác cơ bản với hàng đợi từ mảng T có độ dài cố định N).
• 3.4.NC1a: Lập trình (HS viết được các hàm Python sử dụng kiểu dữ liệu hàng đợi).
• 6.2.NC1a: Sử dụng trí tuệ nhân tạo (HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản).
• 1.1.NC1a: Duyệt, tìm kiếm và lọc dữ liệu, thông tin và nội dung số (HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV).

Năng lực AI:

• 12.A3.1: Trách nhiệm công dân trong xã hội có AI (HS thể hiện trách nhiệm học thuật số bằng việc tự tư duy thuật toán biến đổi hàng đợi, tự viết code Python và thực hiện kiểm chứng chéo kết quả, cam kết sử dụng AI có kiểm soát và không lạm dụng sao chép code đối phó).
• 12.C2.1: Các yêu cầu dành cho công cụ AI hỗ trợ các hoạt động học tập và xã hội (HS biết cách đặt prompt phù hợp để nhờ Chatbot AI hỗ trợ giải thích tri thức lập trình, gỡ lỗi cú pháp hoặc phân tích các cơ chế xử lý hàng đợi trong hệ thống thực tế (như cơ chế Buffer, Spooling)).

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

• SGK, KHBD Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Phòng thực hành máy tính cài đặt sẵn môi trường lập trình Python (IDLE, PyCharm, VS Code,…) và có kết nối Internet, máy trình chiếu.
• Học liệu số & Công cụ AI:
• Bộ câu hỏi trắc nghiệm trên phần mềm Quizizz/website kenhhoctap.edu.vn hoặc phiếu bài tập số.
• Video AI được tạo bằng các công cụ AI để khởi động bài học.
• Công cụ Chatbot AI (ChatGPT/Gemini).

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

• SGK Chuyên đề học tập Tin học 12 – Định hướng Khoa học máy tính.
• Vở ghi. 

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

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

a. Mục tiêu: Tạo hứng thú học tập cho HS.

b. Nội dung: HS thảo luận nhóm và trả lời các câu hỏi phần Khởi động SGK tr.16. 

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ác câu hỏi phần Khởi động SGK tr.16.

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 xem video AI được thiết kế để phục vụ bài dạy và trả lời câu hỏi xuất hiện trong video đó.

- GV chia lớp thành ba nhóm học tập và nêu câu hỏi Khởi động SGK tr.16 cho các nhóm thảo luận: 

Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python). Em hãy trả lời các câu hỏi sau:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?

b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vào và lấy ra?

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

- HS xem video và suy nghĩ câu trả lời.

- HS thảo luận theo nhóm và 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 lần lượt mời các nhóm báo cáo kết quả thảo luận.

Gợi ý trả lời:

a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp.

b) Để thực hiện phép toán thêm vào và lấy ra khi cài đặt hàng đợi bằng mảng một chiều, cần có những thông tin sau:

+ front, head (đầu hàng đợi): Chỉ số này giữ vị trí của phần tử đầu tiên trong hàng đợi. Khi thực hiện phép toán lấy ra (dequeue), phần tử tại vị trí này sẽ được lấy ra và chỉ số front sẽ được cập nhật để trỏ đến phần tử tiếp theo.

+ back, rear, tail (cuối hàng đợi): Chỉ số này giữ vị trí của phần tử cuối cùng trong hàng đợi. Khi thực hiện phép toán thêm vào (enqueue), phần tử mới sẽ được thêm vào vị trí kế tiếp của chỉ số rear, và chỉ số rear sẽ được cập nhật để trỏ đến vị trí cuối mới của hàng đợi.

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á và kết luận.

[6.2.NC1a: HS sử dụng công cụ AI hoặc sản phẩm số do GV cung cấp để tiếp nhận thông tin, trả lời câu hỏi đơn giản.

2.1.NC1a: HS thực hiện các tương tác cơ bản với học liệu số (xem video, trả lời câu hỏi trên môi trường số).

1.1.NC1a: HS tiếp cận, khai thác được thông tin từ nguồn học liệu số dưới sự hướng dẫn của GV.]

- GV đánh giá kết quả của HS, dẫn dắt HS vào bài học mới: Tương tự như ngăn xếp, hàng đợi cũng có thể được biểu diễn bằng mảng một chiều. Vậy nếu dùng kiểu dữ liệu list của Python để mô tả hàng đợi thì các thao tác chính như enqueue() và dequeue() sẽ được thiết lập như thế nào? Để trả lời câu hỏi này, chúng ta sẽ cùng nhau tìm hiểu Bài 4: Kiểu dữ liệu hàng đợi.

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

Hoạt động 1. Dùng kiểu dữ liệu mảng để biểu diễn hàng đợi

a. Mục tiêu: HS biết và nắm được cách sử dụng kiểu dữ liệu list trong Python để mô tả hàng đợi thông qua sơ đồ hoặc mô tả bằng lời, chưa cần lập trình.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 1. Biểu diễn hàng đợi bằng mảng một chiều, 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: HS biểu diễn được hàng đợi bằng mảng một chiều.

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

…………………………………………..

…………………………………………..

…………………………………………..

Hoạt động 2. Tìm hiểu các hàm của kiểu dữ liệu hàng đợi

a. Mục tiêu: HS hiểu và thực hiện được việc cài đặt các hàm chính của kiểu dữ liệu hàng đợi bằng list của Python.

b. Nội dung: GV giao nhiệm vụ; HS tìm hiểu nội dung mục 2. Tìm hiểu các hàm của kiểu 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: Các hàm của kiểu dữ liệu hàng đợi.

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

* THÔNG TIN BỔ SUNG

Với cách thiết lập hàng đợi sử dụng list của Python như trong bài học này thì độ phức tạp thời gian của các hàm cơ bản được cho trong bảng sau:

Như vậy mô hình cài đặt này của hàng đợi không thoả mãn tất cả các điều kiện về thời gian của mô hình kiểu dữ liệu hàng đợi. Tất cả các hàm/thao tác cơ bản trên đều có độ phức tạp thời gian O(1), trừ lệnh dequeue(Q) có thời gian O(n).

Do vậy việc biểu diễn, cài đặt hàng đợi bằng list của Python theo cách đã mô tả trong bài học là chưa thật tối ưu.

3. HOẠT ĐỘNG LUYỆN TẬP

a. Mục tiêu: Giúp HS hệ thống lại kiến thức đã học.

b. Nội dung: GV giao nhiệm vụ cho HS, HS hoàn thành phiếu bài tập.

c. Sản phẩm học tập: Phiếu bài tập.

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

…………………………………………..

…………………………………………..

…………………………………………..

4. HOẠT ĐỘNG VẬN DỤNG

a. Mục tiêu: HS nắm chắc kiến thức về kiểu dữ liệu hàng đợi.

b. Nội dung: GV hướng dẫn HS thực hiện các bài tập phần Vận dụng SGK tr.19.

c. Sản phẩm học tập: HS hoàn thành bài tập phần Vận dụng SGK tr.19.

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 hoạt động cá nhân, hoàn thành bài tập phần Vận dụng SGK trang 19.

Câu 1. Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.

Câu 2. Cho trước mảng T gồm N phần tử T[0], T[1], ..., T[N-1]. Hãy viết hàm thiết lập hàng đợi và các thao tác cơ bản với hàng đợi từ mảng T.

Gợi ý:

- Để thiết lập dữ liệu hàng đợi từ mảng T cho trước cần có thêm biến backIdx mô tả chỉ số của phần tử đuôi của hàng đợi. Ban đầu thiết lập backIdx = -1 tương ứng với hàng đợi rỗng.

- Cần viết thêm hàm isFullQueue(Q) kiểm tra xem hàng đợi đã đầy chưa. Hàm trả về True nếu hàng đợi Q đã đầy (backIdx = N-1), ngược lại trả về False.

- GV định hướng khai thác AI có trách nhiệm (Khi nào nên/không nên dùng AI): 

+ Yêu cầu HS tự tư duy giải pháp thuật toán và giải thích cơ chế dời dịch phần tử ra giấy trước.

+ Sau khi tự làm xong, HS được phép sử dụng Chatbot AI (ChatGPT/Gemini) làm trợ lý để tra cứu gỡ lỗi cú pháp lập trình hoặc giải thích cơ chế Spooling vật lý của hệ điều hành.

+ GV quán triệt: "AI là trợ lý lập trình rất mạnh nhưng chỉ nên dùng để tối ưu hóa code và gỡ lỗi; các em tuyệt đối không được chép nguyên văn code do AI giải hộ để nộp bài đối phó. Hãy thể hiện sự trung thực học thuật kỉ nguyên số".

- GV đặt câu hỏi mở rộng: "Hãy giải thích cơ chế quản lý tiến trình in ấn (Printer Spooling) của hệ điều hành máy tính sử dụng hàng đợi như thế nào". 

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

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

- HS thực hiện viết prompt hỏi AI gỡ lỗi chương trình nếu code gặp lỗi.

- GV quan sát và hỗ trợ khi HS cần.

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

- GV mời một số HS trình bày kết quả.

- HS quan sát bài làm của các bạn khác, nhận xét nhau.

Gợi ý đáp án:

Câu 1. Lệnh dequeue(Q) chính là phương thức Q.pop(0), hàm này tương đương với đoạn chương trình sau bao gồm một vòng lặp do vậy có độ phức tạp thời gian O(n).

Câu 2. 

…………………………………………..

…………………………………………..

…………………………………………..

Câu hỏi mở rộng: Hệ điều hành đưa các tài liệu cần in vào một Queue. Máy in sẽ dequeue tài liệu ở đầu hàng đợi để in trước, đảm bảo tính công bằng FIFO và không làm tắc nghẽn bộ nhớ CPU.

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

- GV chính xác hoá lại các nội dung trả lời của HS.

- GV chuẩn kiến thức và kết thúc tiết học.

[3.4.NC1a: HS viết được các hàm hàng đợi bằng ngôn ngữ lập trình Python.

5.3.NC1a: HS áp dụng công cụ Python IDE thiết kế, thực thi thành công chương trình thiết lập hàng đợi từ mảng T và các thao tác kiểm tra đầy/rỗng trên môi trường lập trình.

12.A3.1: HS thể hiện trách nhiệm học thuật số thông qua việc tự lập trình thuật toán mảng, sử dụng AI có kiểm soát để debug mã nguồn, rà soát tính chuẩn xác và cam kết không phụ thuộc hoàn toàn vào công cụ công nghệ.

12.C2.1: HS đặt câu lệnh (prompt) phù hợp cho Chatbot AI để tra cứu thông tin chuyên sâu giải thích bản chất ứng dụng hàng đợi trong hệ thống tin học thực tế.]

* HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 4.

- Xem trước nội dung Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi.