Chương trình chuyên sâu môn Tin học Lớp 10

ng của các cấu trúc dữ liệu vào việc cài đặt hiệu quả một số thuật toán điển hình. TT Nội dung Mức độ cần đạt Ghi chú 1. Mô hình cây trong tổ chức dữ liệu Kiến thức: - Hiểu khái niệm kiểu dữ liệu trừu tượng cây và một số khái niệm trong mô hình cây (chiều cao, gốc, nút lá, bậc của nút, bậc của cây); - Biết một số ứng dụng của cách tổ chức dữ liệu theo mô hình cây (cây thư mục; biểu diễn không gian lời giải bài toán trong lý thuyết trò chơi; cây phân tích cú pháp của các văn phạm như biểu thức, các câu lệnh trong một chương trình; ứng dụng trong tổ chức dữ liệu ở bộ nhớ trong và bộ nhớ ngoài cho các bài toán tìm kiếm;...). Thông qua ví dụ để minh họa lí thuyết. 2. Cây nhị phân và ứng dụng Kiến thức: - Hiểu khái niệm cấu trúc dữ liệu cây nhị phân; - Hiểu khái niệm cây nhị phân tìm kiếm và các ứng dụng của nó; - Hiểu khái niệm cây biểu thức và ứng dụng. Kĩ năng: Cài đặt được các thuật toán và thử nghiệm chương trình với các bộ dữ liệu khác nhau. - Yêu cầu HS hiểu thấu đáo các khái niệm, các cấu trúc dữ liệu và các phép toán với chúng. - GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau. 3. Mã Huffman Kiến thức: - Biết khái niệm mã hoá và ứng dụng; - Nắm được khái niệm mã Huffman và thuật toán xây dựng. Kĩ năng: Cài đặt được chương trình mã hoá và giải mã theo mã Huffman và thử nghiệm chương trình với các bộ dữ liệu khác nhau. - Yêu cầu HS hiểu thấu đáo nội dung bài toán mã hoá và cách tổ chức dữ liệu cây để xây dựng mã và giải mã. - GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau . 4. Cấu trúc dữ liệu đống và ứng dụng Kiến thức: - Biết cấu trúc dữ liệu đống và các phép toán với cấu trúc dữ liệu đống; - Hiểu được ứng dụng của cấu trúc dữ liệu đống vào xây dựng thuật toán sắp xếp vun đống (Heap Sort); - Hiểu được ứng dụng của cấu trúc dữ liệu đống trong việc tổ chức hàng đợi có ưu tiên; - Hiểu được ứng dụng hàng đợi ưu tiên vào việc cài đặt các thuật toán Prim, Dijkstra. Kĩ năng: Cài đặt được chương trình thực hiện các thuật toán và thử nghiệm chương trình với các bộ dữ liệu khác nhau. - Yêu cầu HS hiểu thấu đáo các khái niệm, các cách tổ chức dữ liệu bằng việc sử dụng nhiều minh họa, mô phỏng trước khi trình bày thuật toán cài đặt chương trình. - GV nên hướng dẫn cho HS phân tích so sánh các cách cài đặt khác nhau Chuyên đề 4: CÁC CÁCH TIẾP CẬN GIẢI BÀI TOÁN NP-KHÓ Số tiết: 5 Mục đích: Nắm được phát biểu của một số bài toán NP-khó điển hình; Nắm được khái niệm thuật toán gần đúng đảm bảo chất lượng lời giải; Nắm được một số thuật toán gần đúng để giải các bài toán NP-khó điển hình; Nắm được một số thuật toán ngẫu nhiên. 1 Một số bài toán NP-khó điển hình Kiến thức: Phát biểu được một số bài toán NP-khó điển hình: Bài toán cái túi, Bài toán người du lịch, Bài toán phủ đỉnh, Bài toán đóng thùng, Bài toán phủ tập. 2 Các thuật toán gần đúng đảm bảo chất lượng lời giải Kiến thức: - Hiểu khái niệm thuật toán gần đúng đảm bảo chất lượng lời giải, khái niệm sơ đồ xấp xỉ thời gian đa thức; - Nắm được một số thụât toán gần đúng để giải các bài toán NP-khó đã giới thiệu. Kĩ năng: Cài đặt được các thuật toán đã trình bày. 3 Cách tiếp cận ngẫu nhiên để giải các bài toán NP-khó Kiến thức: - Biết kỹ thuật phát triển thuật toán ngẫu nhiên; - Hiểu thụât toán tạo số ngẫu nhiên và các thuật toán sinh ngẫu nhiên các cấu hình tổ hợp cơ bản. Kĩ năng: - Biết vận dụng để xây dựng thuật toán ngẫu nhiên giải các bài toán đã trình bày; - Cài đặt được các thuật toán đã xét. Chuyên đề 5: THUẬT TOÁN TIẾN HÓA Số tiết: 5 Mục đích: Nắm được bản chất của thuật toán tiến hoá; Nắm được sơ đồ tổng quát của thuật toán; Nắm được một số thuật toán tiến hoá để giải một số bài toán điển hình. Stt Nội dung Yêu cầu cần đạt Ghi chú 1 Các khái niệm cơ bản: Định nghĩa thuật toán tiến hóa (di truyền) Lai giống, Đột biến, Phạm vi ứng dụng . Kiến thức: - Hiểu được bản chất của thuật toán tiến hóa, nguyên lý hoạt động của thuật toán; - Làm quen với các khái niệm cơ bản của thuật toán, phương pháp tìm kiếm lời giải gần đúng; - Xác định được lĩnh vực cho phép áp dụng có hiệu quả thuật toán tiến hóa. GV cần liên hệ với các kiến thức sinh học tương ứng, nêu các ví dụ về chọn lọc tự nhiên và kỹ thuật lai ghép chọn lọc định hướng (công nghệ gen). 2 Các khâu xử lý cơ bản: Khởi tạo trạng thái đầu của quần thể, Chọn cá thể để phát triển, Phát triển quần thể thông qua lai giống hoặc đột biến, Đánh giá các cá thể trong quần thể, Xác lập thế hệ mới, Vấn đề xác định điều kiện kết thúc xử lý. Kiến thức: - Nắm được các bước cần thực hiện khi tổ chức giải bài toán theo thuật toán di truyền; - Xác định được sơ đồ tổng quát của thuật toán, đặc điểm của từng khâu xử lý. Kỹ năng: Xác định được cấu trúc dữ liệu và cài đặt các phép xử lý cơ bản của thuật toán ứng với những bài toán mẫu. - GV liên hệ với sơ đồ tổng quát của thuật toán “Tìm kiếm quay lui” và xác định các nét tương đồng giữa hai loại thuật toán trong việc mô tả sơ đồ chung. - Cần chuẩn bị nhiều ví dụ minh họa cho từng khâu xử lý. 3 Các lớp bài toán ứng dụng thuật toán di truyền: Bài toán lập lịch, Bài toán trò chơi, Tính gần đúng, Tối ưu hóa quá trình xử lý truy vấn trong hệ QTCSDL, Các bài toán phỏng sinh học. Kiến thức: Biết cụ thể hóa được các khâu xử lý nêu ở mục 2 đối với mỗi loại bài toán. Kỹ năng: Triển khai được thuật toán áp dụng với một số bài toán mẫu. Không nhất thiết phải xét một cách chi tiết tất cả các lớp bài toán đã nêu. GV có thể chỉ đi sâu vào một vài loại bài toán trong số đã liệt kê và dừng lại chi tiết ở một bài toán cụ thể, thuộc một lớp cụ thể. 4 Chương trình minh họa áp dụng trên một số bài toán đơn giản. Kiến thức: - Biết cách so sánh kết quả giải bài toán (các bài toán) bằng các phương pháp khác đã học trước đây để thấy ưu nhược điểm của thuật toán di truyền; - Xác định được phạm vi ứng dụng của thuật toán. Kỹ năng: Rèn luyện kỹ thuật cài đặt: Nắm vững sơ đồ điều khiển chung, Biết cách triển khai các khâu xử lý cơ bản cho một hoặc một vài bài toán cụ thể, GV nên chuẩn bị các chương trình giải bằng các phương pháp khác để tiến hành so sánh đánh giá hiệu quả thuật toán. V. GIẢI THÍCH VÀ HƯỚNG DẪN THỰC HIỆN 5.1. Kế hoạch dạy học - Triển khai dạy học ở lớp 12 một mặt đảm bảo hoàn thành chương trình SGK tin học 12 THPT, mặt khác cần kế thừa, phát triển và nâng cao một cách hệ thống các chuyên đề chuyên sâu đã học ở lớp 10, lớp 11. Do vậy, mỗi trường có thể chủ động điều chỉnh kế hoạch dạy học cho phù hợp. - Việc phân chia các chuyên đề chuyên sâu cho các lớp 10, 11, 12 chỉ mang tính tương đối. GV nên có kế hoạch dạy học tổng thể cho cả 03 lớp để xây dựng kế hoạch dạy học thực tế. Thực chất nội dung các chuyên đề của chương trình lớp 12 đã đề cập trong chương trình lớp 10 và 11. Điều này phù hợp với truyền thống bồi dưỡng học sinh giỏi của các trường, thường tập trung chính vào lớp 10 và 11. - Một khó khăn là chương trình SGK Tin học 12 và chương trình các chuyên đề chuyên sâu có sự khác biệt nhiều, việc dạy học xen kẽ hai nội dung đó của cùng một môn học đòi hỏi GV phải tổ chức dạy học hợp lí. 5.2. Nội dung dạy học chuyên sâu - Các chuyên đề bao gồm chuyên đề bắt buộc (chuyên đề 1, 2 và 3) và chuyên đề tự chọn (chọn một trong hai chuyên đề 4 hoặc 5). Việc chọn chuyên đề tự chọn nào do giáo viên mỗi trường quyết định, các chuyên đề đề xuất cũng chỉ mang tính định hướng, GV có thể bổ sung các chuyên đề khác phù hợp hơn đối với trình độ HS của mình và quỹ thời gian. - Việc phân bổ thời lượng cho các chuyên đề cũng chỉ mang tính chất tương đối, GV hoàn toàn chủ động để đưa ra các nội dung và thời gian tương ứng thích hợp cho HS của mình. - Khả năng vận dụng lí thuyết để làm bài tập là rất quan trọng, cần đặc biệt chú trọng. Kĩ năng cài đặt chương trình thành thạo, giải các bài toán cụ thể là yêu cầu bắt buộc, tính hoàn thiện việc giải bài toán bằng máy tính là một đòi hỏi cao. Cần hình thành kĩ năng lựa chọn và xây dựng các thuật toán hiệu quả để giải các bài toán cụ thể. - Ngoài ra, để có một lời giải tốt cho máy tính cần cung cấp, rèn luyện kĩ năng tổ chức tốt dữ liệu cho mỗi bài toán cụ thể và kĩ năng đánh giá, kiểm thử chương trình. 5.3. Phương pháp và phương tiện dạy học Tương tự như đối với chương trình lớp 10, 11 đối với chương trình lớp 12 cũng cần quan tâm tới các đặc trưng sau: - HS chuyên là đối tượng có khả năng tự học rất cao, cần trình bày kiến thức theo dạng gợi mở, phát huy tính độc lập, sáng tạo, tìm lời giải hay. - Tạo dựng môi trường tốt để HS có điều kiện trao đổi học tập lẫn nhau, đánh giá, nhận xét các lời giải của nhau, tạo các bộ test đặc thù để kiểm định chất lượng chương trình của bạn, chia xẻ đề bài hay, lời giải tốt mà các em sưu tầm được. - Đối với HS chuyên tin cần đảm bảo mỗi HS/01 máy và cung cấp đủ môi trường lập trình đầy đủ và hiện đại. Trên Internet, nguồn tài liệu rất phong phú, nhiều kì thi trực tuyến rất bổ ích, cần tạo dựng môi trường đủ tốt để HS có thể khai thác Internet một cách thuận lợi. 5.4. Kiểm tra, đánh giá Tính hoàn thiện trong việc vận dụng kiến thức và kĩ năng để giải quyết các bài tập là yêu cầu rất cao. Tuy nhiên không nên chỉ đánh giá kết quả học tập của học sinh thông qua test chương trình giải các các bài toán, mà có thể dưới nhiều hình thức khác để phát hiện khả năng nổi trội cũng như những khiếm khuyết của mỗi HS để có giải pháp kịp thời. Với chương trình lớp 11, có thể kết hợp đánh giá kết quả học tập của HS qua chương trínhGK Tin học 11 và các chuyên đề chuyên sâu. Với chương trình SGK Tin học 12 và các chuyên đề chuyên có sự khác biệt, nên việc đánh giá kết hợp là khó thực hiện. Vì vậy có thể thực hiện việc đánh giá độc lập, sau đó lấy tổng điểm theo một tỷ lệ nào đó, chẳng hạn 5 - 5.