PPCT Chuyên Tin 12

LỚP 12
I MỤC ĐÍCH
- Thống nhất trên phạm vi toàn quốc kế hoạch dạy học và nội dung dạy học môn Tin học cho trường THPT chuyên
- Thống nhất trên phạm vi toàn quốc nội dung bồi dưỡng học sinh giỏi môn Tin học cấp THPT.
Mục tiêu:
Về kiến thức:
- Tiếp tục mở rộng và nâng cao các nội dung các chuyên đề đã có ở lớp 10, 11 chuyên, môn Tin học trường THPT chuyên.
- Trang bị một số kiến thức về cấu trúc dữ liệu và thuật toán: Tính toán hình học; Độ phức tạp của bài toán; Các cấu trúc dữ liệu nâng cao; Các cách tiếp cận giải bài toán NP-khó; Các thuật toán tiến hóa.
Về kĩ năng:
- Vận dụng được các chiến lược thiết kế thuật toán để giải các bài toán cụ thể ở mức tương đối khó và khó.
- Thành thạo trong tổ chức dữ liệu, cài đặt thuật toán bằng ngôn ngữ lập trình bậc cao.
Thái độ:
- Có ý thức xây dựng các thuật toán tốt cho các bài toán cụ thể.
- Có ý thức rèn luyện kĩ năng lập trình chuyên nghiệp, giải các bài toán một cách hiệu quả .
II. KẾ HOẠCH DẠY HỌC
Ngoài 52,5 tiết của chương trình Tin học 12 THPT, có 35 tiết dành cho chuyên sâu.
III NỘI DUNG DẠY HỌC
3.1. Nội dung chung : Nội dung dạy học bao gồm 02 phần:
- Nội dung SGK Tin học 12 THPT;
- Các chuyên đề chuyên sâu.
3.2. Nội dung chuyên sâu
Nội dung chuyên sâu bao gồm các chuyên đề sau:
- Các chuyên đề bắt buộc:
Chuyên đề 1. Tính toán hình học , 12 tiết
Chuyên đề 2. Độ phức tạp của bài toán, 8 tiết
Chuyên đề 3. Các cấu trúc dữ liệu nâng cao, 10 tiết
- Các chuyên đề tự chọn bắt buộc:
Chuyên đề 4. Các cách tiếpcận giải bài toán NP-khó, 5 tiết
Chuyên đề 5. Các thuật toán tiến hóa, 5 tiết






IV. NỘI DUNG CÁC CHUYÊN ĐỀ CHUYÊN SÂU

Chuyên đề 1. TÍNH TOÁN HÌNH HỌC
Số tiết: 12
Mục đích:
Hiểu khái niệm về các đối tượng hình học cơ bản;
Nắm được thuật toán thực hiện các bài toán hình học cơ bản;
Nắm được thuật toán giải một số bài toán hình học cơ bản: Bài toán tìm bao lồi và bài toán tìm cặp điểm gần nhất;
Hiểu được ảnh hưởng của sai số làm tròn.
TT
 Nội dung
 Mức độ cần đạt
 Ghi chú

1.
Điểm, đoạn thẳng, giao các đoạn thẳng
Kiến thức:
- Nắm được các khái niêm: điểm, đoạn thẳng, tam giác, đa giác;
- Nắm được các thuật toán: xây dựng phương trình đường thẳng; tìm giao của hai đường thẳng; xác định góc giữa hai đường thẳng; xác định giao điểm của hai đoạn thẳng.
Kĩ năng:
- Xác định được kiểu dữ liệu dùng trong xử lí đa giác;
- Cài đặt được các hàm, thủ tục tương ứng.
- Tọa độ các điểm thuộc kiểu nguyên;
- Đa giác được mô tả như một mảng các điểm.

2.
Đường khép kín đơn
Kiến thức:
Biết cách vẽ đường khép kín đơn đi qua n điểm cho trước.
Kĩ năng:
Cài đặt được hàm tính góc.


3.
Điểm nằm trong đa giác
Kiến thức:
Biết được các vị trí khác nhau cần xử lí: điểm kết thúc trùng với đỉnh đa giác, đoạn kiểm tra trùng khớp với một cạnh của đa giác.
Kĩ năng:
- Tính diện tích của đa giác;
- Cài đặt được các thủ tục chuẩn.


4.
Bao lồi . Thuật toán bọc gói
Kiến thức:
- Hiểu được định nghĩa bao lồi và trường hợp tối thiểu bao lồi là một tam giác, tối đa là đa giác lồi gồm đúng n điểm;
- Hiểu được thuật toán bọc gói.
Kĩ năng:
Cài đặt được thuật toán bọc gói.


5.
Phương pháp quét Graham


Kiến thức:
- Biết sử dụng thủ tục tính góc để tạo đa giác qua n điểm;
- Nắm được các thuật toán tìm bao lồi dựa trên đa giác.
Kĩ năng:
Cài đặt được thuật toán quét Graham.


6
Tìm cặp điểm gần nhất
Kiến thức:
- Hiểu được bài toán tìm cặp điểm gần nhất;
- Hiểu được các thuật toán trực tiếp và thuật toán chia để trị.
Kĩ năng:
Cài đặt được các thuật toán.


7.
Một số minh họa




Chuyên đề 2: ĐỘ PHỨC