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

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

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

 - Ví dụ xếp 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

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 Câu hỏi vận dụ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 tiếp nhận và thực hiện nhiệm vụ theo đúng hướng dẫn để hoàn thành yêu cầu.  - 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

 - Nếu HS có vướng mắc trong quá trình thực hành, GV yêu cầu HS thảo luận, tìm giải pháp khắc phục.  - HS báo cáo, chia sẻ giải pháp tìm được.  - Hướng dẫn thực hiện câu hỏi vận dụ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.

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

 - HS thực hiện thảo luận theo cặp, đọc và tìm hiểu thông tin trong mục 3 SGk – tr.8,9 và trả lời các câu hỏi:  + Nêu tên một số hàm cơ bản trên hàng đợi và ý nghĩa của chúng?  + Mô tả cụ thể cách sử dụng các hàm cơ bản trong Python?

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 nhiệm vụ theo đúng hướng dẫn để hoàn thành yêu cầu.  - 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

 - Nếu HS có vướng mắc trong quá trình thực hành, GV yêu cầu HS thảo luận, tìm giải pháp khắc phục.  - HS báo cáo, chia sẻ giải pháp tìm được.

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.

3. Cài đặt hàng đợi

 - Các hàm cơ bản và ý nghĩa:  + createQueue: Khởi tạo hàng đợi rỗng.  + front(Q): Hàm trả về phần tử đang đứng đầu hàng đợi Q nhưng không lấy nó ra khỏi Q.  + enqueue(Q, data): Thêm phần tử data vào cuối hàng đợi Q.  + dequeue(Q): Lấy ra khỏi hàng đợi Q phần tử đang đứng đầu hàng đợi và trả về phần tử này.  + isEmptyQueue(Q): Hàm trả về True nếu hàng đợi Q đang rỗng, ngược lại trả về giá trị False.  - Mô tả cách sử dụng hàm trong Python:  + Hàm createQueue() trả về một danh sách rỗng để tạo hàng đợi rỗng (Hình 6).

Hình 6. Hàm khởi tạo hàng đợi rỗng

 + Hàm front(Q) thực hiện trả về phần tử đang đứng đầu hàng đợi Q nhưng không lấy nó ra khỏi Q (Hình 7).

Hình 7. Hàm trả về phần tử đầu hàng đợi

 + Hàm enqueue(Q, data) thêm data vào hàng đợi Q (Hình 8).

Hình 8. Hàm thêm một phần tử vào hàng đợi

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

 - GV chia lớp thành các nhóm tương ứng với các tổ trong lớp để thực hiện phần thực hành SGK-tr.10,11.

a) Đọc hàm dequeue(Q) ở Hình 9 và cho biết dấu ? cần được thay bằng gì?

b) Đọc chương trình ở hình 10 và cho biết hàng đợi queue sẽ chứa những phần tử nào và kết quả in trên màn hình là gì khi chạy chương trình.

c) Bổ sung 3 câu lệnh temp = dequeue(queue) giống nhau vào cuối đoạn chương trình ở hình 10 và cho biết kết quả in trên màn hình là gì khi chạy chương trình.

d) Viết hàm isEmptyQueue(Q) với tham số truyền vào là hàng đợi Q. Hàm trả về giá trị True nếu hàng đợi Q đang rỗng không chứa phần tử nào, ngược lại hàm trả về giá trị False.

e) Sửa lại chương trình thu được khi thực hiện xong câu c) như sau: thay mỗi câu lệnh temp = dequeue(queue) thành đoạn chương trình ở hình 11. Cho biết kết quả in trên màn hình là gì khi chạy chương trình.

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 nhiệm vụ theo đúng hướng dẫn để hoàn thành yêu cầu.  - 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

 - Nếu HS có vướng mắc trong quá trình thực hành, GV yêu cầu HS thảo luận, tìm giải pháp khắc phục.  - HS báo cáo, chia sẻ giải pháp tìm được.

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.

4. Thực hành

a) Trong hình 9:

 - Dấu ? cần được thay bằng 0.

b) Trong chương trình ở Hình 10:

Phân tích chương trình và kết quả

Hàng đợi queue:

 + Ban đầu, hàng đợi rỗng (chưa chứa phần tử nào).  + Sau khi thực hiện lệnh enqueue(queue, 2), phần tử 2 được thêm vào cuối hàng đợi.  + Sau khi thực hiện lệnh enqueue(queue, 4), phần tử 4 được thêm vào cuối hàng đợi.  + Sau khi thực hiện lệnh enqueue(queue, 6), phần tử 6 được thêm vào cuối hàng đợi.  + Sau khi thực hiện lệnh temp = dequeue(queue), phần tử 2 (phần tử đầu tiên) được lấy ra khỏi hàng đợi và gán cho biến temp.  + Lệnh print("Phần tử đang đứng đầu hàng đợi = ", front(queue)) trả về phần tử 4 (phần tử đầu tiên) nhưng không lấy phần tử này ra khỏi hàng đợi.

Kết quả in trên màn hình:

 + Phần tử đang đứng đầu hàng đợi = 4.

Hàng đợi sau khi chạy chương trình:

 + Hàng đợi còn lại phần tử 4 và 6.

c)

 + Kết quả in trên màn hình:

d)

def isEmptyQueue(Q):

  if len(Q) == 0:

    return True

  else:

    return False

e) Chương trình sau khi sửa:

 - Kết quả sau khi chạy chương trình:

Phần tử 2 đã được lấy ra khỏi hàng đợi

Phần tử đang đứng đầu hàng đợi =  4

Phần tử 4 đã được lấy ra khỏi hàng đợi

Phần tử 6 đã được lấy ra khỏi hàng đợi

Hàng đợi rỗng, không thực hiện được thao tác dequeue

Trường THPT:………………………………………….

Lớp:……………………………………………………...

Họ và tên:……………………………………………….

PHIẾU BÀI TẬP CHUYÊN ĐỀ TIN HỌC 12 – ĐỊNH HƯỚNG KHOA HỌC MÁY TÍNH – CÁNH DIỀU

BÀI 1: KIỂU DỮ LIỆU HÀNG ĐỢI

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Trong cơ chế hoạt động của hàng đợi, phần tử nào được xử lý đầu tiên?

A. Phần tử ở giữa hàng đợi.

B. Phần tử được thêm vào hàng đợi sau cùng.

C. Phần tử ở đầu hàng đợi.

D. Phần tử được thêm vào hàng đợi đầu tiên.

Câu 2. Một ví dụ cụ thể về việc sử dụng hàng đợi là gì?

A. Sắp xếp danh sách từ điển.

B. Tìm kiếm trong mảng không tuần tự.

C. In các tệp từ một thư mục.

D. Dịch vụ hàng đợi điện tử tại ngân hàng.

Câu 3. Kiểu dữ liệu nào phù hợp để biểu diễn một hàng đợi trong Python?

A. List.

B. Tuple.

C. Set.

D. Dictionary.

Câu 4. Phép toán nào không thực hiện được trên hàng đợi?

A. Thêm phần tử vào cuối hàng đợi.

B. Xóa phần tử ở đầu hàng đợi.

C. Truy cập phần tử ở vị trí bất kỳ trong hàng đợi.

D. Sắp xếp các phần tử trong hàng đợi.

Câu 5. Cho ví dụ về một chương trình hàng đợi như sau:

Trong chương trình trên, hàm nào trong lớp Queue được sử dụng để lấy ra phần tử khỏi hàng đợi?

A. enqueue.

B. dequeue.

C. is_empty.

D. size.

Câu 6. Hàm nào sau đây dùng để thêm phần tử vào cuối hàng đợi?

A. front(Q, data).

B. dequeue (Q, data).

C. enqueue(Q, data).

D. add(Q, data).

Câu 7. Hàm nào sau đây được sử dụng để lấy ra phần tử đang đứng đầu hàng đợi?

A. enqueue(Q).

B. dequeue(Q).

C. remove(Q).

D. shift(Q).