Giáo án Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản
Giáo án Bài 21: Các thuật toán sắp xếp đơn giản sách Tin học 11 - Định hướng Khoa học máy tính kết nối tri thức. Được thiết kế theo công văn 5512, chi tiết, đầy đủ. Giáo án là bản word, có thể tải về và dễ dàng chỉnh sửa. Bộ giáo án có đầy đủ các bài trong học kì 1 + học kì 2 của KHMT 11 kết nối tri thức. Kéo xuống dưới để tham khảo chi tiết.
Xem: => Giáo án tin học 11 theo định hướng khoa học máy tính kết nối tri thức
Xem video về mẫu Giáo án Khoa học máy tính 11 kết nối Bài 21: Các thuật toán sắp xếp đơn giản
Các tài liệu bổ trợ khác
Xem toàn bộ: Giáo án khoa học máy tính 11 kết nối tri thức đủ cả năm
Ngày soạn: .../.../...
Ngày dạy: .../.../...
BÀI 21: CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
- MỤC TIÊU:
- Kiến thức:
Học xong bài này, HS đạt các yêu cầu sau:
- Biết và thực hiện được một số thuật toán sắp xếp đơn giản.
- Năng lực
Năng lực chung:
- Tự chủ và tự học: biết lắng nghe, tự giác học tập và hoàn thành nhiệm vụ; tích cực tham gia các hoạt động học tập trong lớp.
- Giao tiếp và hợp tác: có thói quen trao đổi, giúp đỡ nhau trong học tập; biết cùng nhau hoàn thành nhiệm vụ học tập theo sự hướng dẫn của GV.
- Giải quyết vấn đề và sáng tạo: ứng dụng các kiến thức đã học vào thực tế, phát triển khả năng giải quyết vấn đề có tính tích hợp liên môn giữa Tin học với các môn học khác.
Năng lực riêng:
- Biết và thực hiện được một số thuật toán sắp xếp đơn giản.
- Thực hiện được các thuật toán và chương sắp xếp đơn giản như sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.
- Phẩm chất
- Trách nhiệm, tính cẩn thận khi làm việc nhóm, phẩm chất làm việc chăm chỉ, chuyên cần để hoàn thành một nhiệm vụ.
- THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
- Đối với giáo viên
- SGK, tài liệu giảng dạy, giáo án PPT.
- Máy tính, máy chiếu.
- Đối với học sinh:
- SGK, SBT Tin học 11, vở ghi chép.
- Tài liệu, thiết bị có liên quan đến nội dung bài học.
III. TIẾN TRÌNH DẠY HỌC
- HOẠT ĐỘNG KHỞI ĐỘNG
- a) Mục tiêu: HS biết được về bài toán sắp xếp các phần tử của một danh sách theo thứ tự (tăng dần hoặc giảm dần) và ý nghĩa của việc sắp xếp trong bài toán tìm kiếm.
- b) Nội dung: GV tổ chức trả lời câu hỏi ở phần Mở đầu, thông qua đó làm quen với các thuật toán sắp xếp đơn giản.
- c) Sản phẩm: Dựa vào kiến thức của bản thân, HS thực hiện yêu cầu GV đưa ra.
- d) Tổ chức thực hiện:
Bước 1: GV chuyển giao nhiệm vụ:
- GV dẫn dắt, đặt vấn đề cho HS: Bài học trước cho em thấy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn so với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. Bài toán sắp xếp cơ bản có dạng như sau:
Cho dãy A gồm n phần tử:
A[0], A[1],…, A[n-1] (1)
Cần sắp xếp dãy theo thứ tự tăng dần:
A[0] ≤ A[1] ≤ … ≤ A[n-1] (2)
- GV đặt câu hỏi yêu cầu HS trả lời: Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.
Bước 2: HS thực hiện nhiệm vụ học tập: HS lắng nghe, suy nghĩ câu trả lời.
Bước 3: Báo cáo kết quả hoạt động, thảo luận:
- GV gọi đại diện một số HS trả lời.
- HS khác nhận xét, bổ sung.
Bước 4: Đánh giá kết quả thực hiện:
- GV nhận xét câu trả lời của HS. Trên cơ sở đó, GV dẫn dắt HS vào bài học mới: Bài 21: Các thuật toán sắp xếp đơn giản.
- HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC
Hoạt động 1: Tìm hiểu về thuật toán sắp xếp chèn
- a) Mục tiêu: Giúp HS hiểu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chèn.
- b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được ý tưởng của thuật toán sắp xếp chèn.
- c) Sản phẩm: HS nêu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chèn.
- d) Tổ chức thực hiện:
HOẠT ĐỘNG CỦA GV VÀ HS | SẢN PHẨM DỰ KIẾN |
Bước 1: GV chuyển giao nhiệm vụ: - GV đặt vấn đề theo Hoạt động 1 trang 99 SGK: Quan sát sơ đồ mô phỏng, trao đổi, thảo luận về ý tưởng chính của thuật toán sắp xếp chèn. - GV chiếu sơ đồ các bước thực hiện thuật toán sắp xếp chèn (hình 21.1) cho HS quan sát. - GV yêu cầu HS quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau: + So sánh số bước lặp với độ dài của dãy số ban đầu. + Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ số bước lặp? + Khi kết thúc lặp ta thu được kết quả gì? - Trên cơ sở kiến thức vừa nêu, GV yêu cầu HS nêu ý tưởng chính của thuật toán sắp xếp chèn. - GV giới thiệu hai cách mô tả thuật toán sắp xếp chèn trên thực tế. - Dựa vào ví dụ vừa nêu ở Hoạt động 1, GV yêu cầu HS trả lời câu hỏi củng cố trang 100 SGK: + Câu 1: Mô phỏng chi tiết các bước lặp sắp xếp chèn dãy A = [5, 0, 4, 2, 3]. + Câu 2: Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào? Bước 2: HS thực hiện nhiệm vụ học tập: - HS thảo luận nhóm, đọc SGK và trả lời câu hỏi. Bước 3: Báo cáo kết quả hoạt động, thảo luận: - Đại diện nhóm HS trình bày. *Câu hỏi củng cố trang 100 SGK: + Câu 1: Mô tả thuật toán sắp xếp chèn với dãy [5, 0, 4, 2, 3] có thể như sau: Bước 1. Chèn phần tử 0 vào trước 5, dãy thu được: [0, 5, 4, 2, 3] Bước 2. Chèn phần tử 4 vào trước 5, thu được: [0, 4, 5, 2, 3] Bước 3. Chèn phần tử 2 vào trước 4, thu được: [0, 2, 4, 5, 3]. Bước 4. Chèn phần tử 3 vào trước 4, thu được: [0, 2, 3, 4, 5]. + Câu 2: Nếu dãy ban đầu đã được sắp xếp đúng thì tại mỗi bước duyệt không cần thực hiện thao tác "chèn" nữa vì A[i] đã ở đúng vị trí rồi. Do vậy, thuật toán sắp xếp chèn sẽ không thực hiện bất cứ thao tác gì trên dãy đã cho. - Các nhóm khác nhận xét, bổ sung cho nhóm bạn. Bước 4: Đánh giá kết quả thực hiện: - GV nhận xét, đánh giá kết quả thảo luận của HS. | 1. Thuật toán sắp xếp chèn - Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt. - Thuật toán sắp xếp chèn có thể mô tả bằng hàm InsertSort(A) như sau: 1 deft InsertionSort(A): 2 n = len(A) 3 for i in range(1,n): 4 value = A[i] 5 j = i – 1 6 while j >= 0 and A[j] > value: 7 A[j+1] = A[j] 8 j = j – 1 9 A[j+1] = value
|
Hoạt động 2: Tìm hiểu về thuật toán sắp xếp chọn
- a) Mục tiêu: Giúp HS hiểu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chọn.
- b) Nội dung: GV tổ chức cho HS thực hiện theo các hoạt động trong SGK và nêu được ý tưởng của thuật toán sắp xếp chọn.
- c) Sản phẩm: HS nêu được ý tưởng và các bước thực hiện của thuật toán sắp xếp chọn.
- d) Tổ chức thực hiện:
Trên chỉ là 1 phần của giáo án. Giáo án khi tải về có đầy đủ nội dung của bài. Đủ nội dung của học kì I + học kì II
Hệ thống có đầy đủ các tài liệu:
- Giáo án word (350k)
- Giáo án Powerpoint (400k)
- Trắc nghiệm theo cấu trúc mới (200k)
- Đề thi cấu trúc mới: ma trận, đáp án, thang điểm..(200k)
- Phiếu trắc nghiệm câu trả lời ngắn (200k)
- Trắc nghiệm đúng sai (250k)
- Lý thuyết bài học và kiến thức trọng tâm (200k)
- File word giải bài tập sgk (150k)
- Phiếu bài tập để học sinh luyện kiến thức (200k)
Nâng cấp lên VIP đê tải tất cả ở tài liệu trên
- Phí nâng cấp VIP: 800k
=> Chỉ gửi 450k. Tải về dùng thực tế. Nếu hài lòng, 1 ngày sau mới gửi phí còn lại
Cách nâng cấp:
- Bước 1: Chuyển phí vào STK: 1214136868686 - cty Fidutech - MB(QR)
- Bước 2: Nhắn tin tới Zalo Fidutech - nhấn vào đây để thông báo và nhận tài liệu
Xem toàn bộ: Giáo án khoa học máy tính 11 kết nối tri thức đủ cả năm
ĐẦY ĐỦ GIÁO ÁN CÁC BỘ SÁCH KHÁC
GIÁO ÁN WORD LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN POWERPOINT LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN CHUYÊN ĐỀ LỚP 11 KẾT NỐI TRI THỨC
GIÁO ÁN DẠY THÊM 11 KẾT NỐI TRI THỨC
CÁCH ĐẶT MUA:
Liên hệ Zalo: Fidutech - nhấn vào đây