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

CHÀO MỪNG CÁC EM ĐẾN VỚI

BÀI HỌC NGÀY HÔM NAY!

KHỞI ĐỘNG

Một phòng 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à 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 đó?

Hệ thống hàng đợi

Cơ chế FIFO

•       Tài liệu nào đưa đến trước in trước.

•       Tài liệu nào đưa đến sau in sau.

Mục đích

•       Đảm bảo tính công bằng khi in tài liệu

Phần mềm ứng dụng

•       CUPS (Common Unix Printing System)

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

NỘI DUNG BÀI HỌC

PHẦN 1. MỘT SỐ VÍ DỤ VỀ HÀNG ĐỢI 
VÀ CƠ CHẾ HOẠT ĐỘNG

Tìm hiểu thông tin mục 1 trong SGK tr.6 và trả lời câu hỏi:

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

Mục đích: tạo ra hàng đợi để đảm bảo tính công bằng.

Cơ chế: vào trước ra trước – FIFO

Ứng dụng trong tin học:

Tin nhắn trên mạng được gửi cho người nhận không có kết nối Internet, nhờ cơ chế của hàng đợi, tin nhắn được chuyển đi đúng thứ tự.

PHẦN 2. 
KIỂU DỮ LIỆU HÀNG ĐỢI VÀ CÁC PHÉP TOÁN CƠ BẢN TRÊN HÀNG ĐỢI Em hãy đọc thông tin và trả lời câu hỏi sau đây:

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?

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

Phép toán lấy ra: dequeue

 Thực hiện ở đầu front

Phép toán thêm vào: enqueue

 Thực hiện ở đầu back

• 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ư sau:
• Quan sát Hình 3a và cho biết mỗi số nguyên được lưu như thế nào?

Số 10 lưu ở Q[Front]

Front = 0

Số 3 lưu ở

Q[Front + 1]

Số 9 lưu ở Q[Back]

Back = 7

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?

Ø  Nếu tiến hành lấy ra, số 10 sẽ bị lấy đầu tiên, vì đứng đầu hàng đợi:

Ø  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ị:

Trả lời câu hỏi củng cố:

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.

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

Trả lời câu hỏi củng cố:

Em hãy:

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.

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.

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

Cần 2 biến Front và Back để lưu lần lượt các 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ị.

Các phần tử từ Q[0]  Q[Front – 1] không dùng để lưu giá trị mới thêm vào

Ví dụ

Bảng có thể lưu được tối đa 4 phần tử (thao tác lấy giá trị tại Q[0] =1)

Chỉ dùng các phần tử Q[1], Q[2], Q[3] để lưu hàng đợi.

PHẦN 3. 
CÀI ĐẶT HÀNG ĐỢI