Kênh giáo viên » Giáo án chuyên đề Tin học 11 Định hướng khoa học máy tính kết nối tri thức

Giáo án chuyên đề Khoa học máy tính 11 kết nối Bài 9: Sắp xếp trộn (P2)

Giáo án giảng dạy theo sách Chuyên đề học tập Tin học 11 - Định hướng Khoa học máy tính bộ sách kết nối tri thức Bài 9: Sắp xếp trộn (P2). 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 demo.

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

Xem toàn bộ: Giáo án chuyên đề Tin học 11 Khoa học máy tính kết nối tri thức đủ cả năm

Hoạt động 3. Tìm hiểu đánh giá thuật toán sắp xếp trộn

Mục tiêu: HS biết được tính ưu việt của sắp xếp trộn.
Nội dung: GV yêu cầu HS tìm hiểu Hoạt động 3 SGK trang 43, đọc thông tin mục 3, thảo luận nhóm và xây dựng kiến thức mới.
Sản phẩm học tập: HS đánh giá được độ phức tạp thời gian của sắp xếp trộn và trả lời được các Câu hỏi củng cố kiến thức SGK trang 45.
Tổ chức hoạt động:

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 chia lớp thành các nhóm, yêu cầu thảo luận để hoàn thành Hoạt động 3 SGK trang 43:

Phân tích, trao đổi, thảo luận để tính độ phức tạp thời gian của thuật toán sắp xếp trộn.

- GV phân tích và làm rõ cho HS hiểu được ý nghĩa quan trọng của sắp xếp trộn là có thời gian chạy chỉ là O(nlogn), nhanh hơn hẳn các thuật toán sắp xếp đã biết, đều có thời gian chạy O(n²).

- GV kết luận về đánh giá thuật toán sắp xếp trộn.

- GV cho HS thảo luận cặp đôi, trả lời Câu hỏi (SGK – tr44) để củng cố kiến thức:

+ Câu 1: Tính thời gian chạy của thuật toán sắp xếp trộn nếu A = [3,1].

+ Câu 2: Mô tả thực hiện các bước của sắp xếp trộn với dãy A = [5, 1, 7, 4]. Trường hợp này T(4) sẽ được tính như thế nào?

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

- Các nhóm HS tìm hiểu đánh giá độ phức tạp của sắp xếp trộn trong SGK.

- HS thảo luận nhóm, hoàn thành bài tập phần Câu hỏi.

- GV theo dõi, hỗ trợ HS trong quá trình học tập.

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 trình bày kết quả thảo luận của nhóm mình.

- Đại diện các nhóm xung phong trả lời Câu hỏi (SGK – tr43)

Câu 1: Tính thời gian chạy thuật toán sắp xếp trộn với A = [3, 1]. Chúng ta sẽ phân tích và tính theo số đơn vị thời gian.

- Kiểm tra tại dòng 2, mất 1 đơn vị thời gian.

- Thực hiện lệnh tại dòng 5, mất 1 đơn vị thời gian.

- Các dòng 5, 6 mỗi dòng chỉ mất 1 đơn vị thời gian do B và C đều là mảng 1 phần tử.

- Dòng 8 sẽ mất 2 đơn vị thời gian.

Do vậy tổng cộng mất 6 đơn vị thời gian.

Câu 2: Các bước thực hiện sắp xếp trộn với A = [5, 1, 7, 4] như sau:

Bước 1: Dòng 5, tính k = 2.

Bước 2: Tính B = [5,1]

Bước 3: Tính C = [4,7]

Bước 4: Trộn B, C và trả về dãy [1,4,5,7]

Thời gian chạy tính như sau:

- Kiểm tra tại dòng lệnh 1, mất 1 đơn vị thời gian.

- (1) tốn 1 đơn vị thời gian.

- (2), (3) mỗi bước mất 6 đơn vị thời gian (xem câu 1).

- (4) tốn 4 đơn vị thời gian.

Tổng cộng sẽ mất 2 + 12 + 4 = 18 đơn vị thời gian.

- Các HS còn lại nhận xét, bổ sung (nếu có).

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

- GV nhận xét, bổ sung, tuyên dương ghi điểm các nhóm làm tốt.

- GV tổng kết lại nội dung.

- GV chuyển sang nội dung luyện tập.

3. Đánh giá thuật toán sắp xếp trộn

- Hoạt động 3

Phân tích: Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.

Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.

Trường hợp tổng quát:

- Tại bước chia, cần O(1) thời gian để thực hiện.

- Các dòng 6,7 sẽ mất 2T(n/2) thời gian.

- Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).

Tổng kết lại chúng ta có các công thức sau tính thời gian T(n).

T(1) = 1

T(n) = 2T(n/2) + O(n), n > 1

Không mất tổng quát, giả sử tồn tại hằng số C > 0 sao cho:

T(n) = 2T(n/2) + Cn, n > 1

Các công thức (1), (2) được gọi là công thức truy hồi để tính độ phức tạp thời gian T(n) của thuật toán sắp xếp trộn.

Người ta tính được: T(n) = O(nlogn).

*Kết luận

- Thuật toán sắp xếp trộn sử dụng kĩ thuật chia để trị có độ phức tạp thời gian O(nlogn), bậc thời gian này là tốt hơn hẳn các thuật toán sắp xếp mà chúng ta đã biết (sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt).

HOẠT ĐỘNG LUYỆN TẬP
Mục tiêu: HS vận dụng kiến thức, hoàn thành bài tập phần Luyện tập.
Nội dung: GV giao nhiệm vụ, HS thảo luận.
Sản phẩm học tập: HS áp dụng kiến thức về sắp xếp trộn để giải các bài toán.
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 thảo luận nhóm đôi, hoàn thành các bài tập:

Bài 1: Viết chương trình thực hiện công việc sau:

- Dữ liệu được nhập từ tệp văn bản Data.inp bao gồm hai dòng, mỗi dòng là một dãy các số nguyên đã được sắp xếp theo thứ tự tăng dần, các số cách nhau bởi dấu cách. Hai dãy này có thể không bằng nhau về kích thước.

- Chương trình sẽ thực hiện trộn hai dãy trên và đưa kết quả dãy được trộn ra tệp Data.out theo một hàng ngang.

Bài 2: Viết lại chương trình hoàn chỉnh thực hiện sắp xếp trộn với dãy A cho trước trên một tệp văn bản. Kết quả đưa ra màn hình.

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

- HS thảo luận, viết chương trình giải bài toán.

- GV hướng dẫn, theo dõi, 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 đại diện của 1 nhóm lên bảng thực hiện trên máy và chạy thử chương trình.

- HS khác quan sát, nhận xét, sửa bài (nếu có).

Kết quả:

Bài 1: Chương trình như sau:

Bài 2: Chương trình có thể như sau:

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

- GV nhận xét, tuyên dương.

HOẠT ĐỘNG VẬN DỤNG
Mục tiêu: HS vận dụng kiến thức, liên hệ với thực tế để giải quyết vấn đề.
Nội dung: GV tổ chức cho HS làm bài tập phần Vận dụng SGK trang44.
Sản phẩm học tập: HS viết và chạy thử chương trình.
Tổ chức thực hiện:

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

- GV nêu yêu cầu bài toán:

Bài 1: Viết chương trình hoàn chỉnh nhập dãy số bất kì từ tệp văn bản, sau đó tiến hành sắp xếp dãy số này theo hai cách khác nhau, cách 1 là một trong các thuật toán sắp xếp đã biết, cách 2 là sắp xếp trộn. Đo thời gian chạy thực sự của hai cách trên, so sánh và kết luận về ưu điểm của sắp xếp trộn.

Bài 2: Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước, cụ thể như sau.

- Thủ tục trộn sẽ có dạng sau: merge(A,left,mid,right). Thủ tục này sẽ trộn hai phân đoạn của dãy A là A[left], ...., A[mid] và A[mid + 1]..... A[right]. Hai phân đoạn này phải được sắp xếp đúng trước đó.

- Thuật toán chính có dạng mergeSoft(A, left, right) như sau:

- Lệnh gọi hàm đệ quy là:

mergeSort(A, 0, len(A) – 1)

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

- HS thảo luận, viết chương trình giải bài toán.

- GV hướng dẫn, theo dõi, 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 đại diện của 1 nhóm lên bảng thực hiện trên máy và chạy thử chương trình.

- HS khác quan sát, nhận xét, sửa bài (nếu có).

Kết quả:

Bài 1: Chương trình sau sẽ so sánh sắp xếp chèn với sắp xếp trộn.

Bài 2: Sắp xếp trộn tại chỗ.