Cấu trúc đề thi HSG Tin học Tây ninh

SỞ GIÁO DỤC VÀ ĐÀO TẠO TÂY NINH
___________



CẤU TRÚC ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT VÒNG TỈNH
MÔN TIN HỌC
_______________

I. Nội dung kiến thức:
1. Thuật toán về lý thuyết số:
- Kiến thức: Hiểu và vận dụng các thuật toán:
+ Hệ đếm, ước số và bội số;
+ Kiểm tra tính nguyên tố, dãy số Fibonacci, dãy Catalan;
+ Hoán vị, tổ hợp, chỉnh hợp;
+ Xử lí số nguyên lớn.
- Kỹ năng:
+ Vận dụng được các thuật toán về lý thuyết số để giải các bài toán cụ thể.
+ Sử dụng ngôn ngữ lập trình bậc cao để biểu diễn dữ liệu và cài đặt các thuật toán liên quan đến lý thuyết số, kiểm thử chương trình.
2. Thuật toán sắp xếp và tìm kiếm:
- Kiến thức: Hiểu và vận dụng các thuật toán:
+ Thuật toán sắp xếp: bubble sort, quick sort.
+ Thuật toán tìm kiếm: tuần tự, nhị phân.
- Kỹ năng:
+ Vận dụng được các thuật toán về sắp xếp và tìm kiếm để giải các bài toán cụ thể.
+ 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, kiểm thử chương trình.
3. Thiết kế thuật toán:
- Kiến thức: Hiểu và vận dụng các thuật toán:
+ Duyệt toàn bộ và nâng cao. Phương pháp quay lui (Backtracking);
+ Nhánh và cận (Branch and Bound);
+ Phương pháp thử và sai (Try and error)
+ Phương pháp tham lam (Greedy);
+ Chia để trị (Devide and Conquer);
+ Phương pháp qui hoạch động (Dynamic programming): các lớp bài toán qui hoạch động cơ bản, công thức truy hồi, cách truy vết.
- 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ể.
+ 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, kiểm thử chương trình.
4. Các thuật toán về đồ thị (graph)
- Kiến thức: Hiểu và vận dụng các thuật toán:
+ Biểu diễn đồ thị trên máy tính: ma trận kề, danh sách kề;
+ Các thuật toán tìm kiếm trên đồ thị: DFS và BFS;
+ Tính liên thông của đồ thị vô hướng và có hướng, bao đóng của đồ thị, xác định thành phần liên thông mạnh trên đồ thị có hướng, thành phần song liên thông.
+ Đồ thị Euler và đồ thị Hamilton
+ Đường đi ngắn nhất: thuật toán Ford – Bellman, thuật toán Dijkstra, thuật toán Floyd
+ Cây khung nhỏ nhất: thuật toán Kruskal, thuật toán Prim.
- Kỹ năng:
+ Vận dụng được các thuật toán về đồ thị để giải các bài toán cụ thể.
+ 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, kiểm thử chương trình.
II. Tài liệu tham khảo:
1. Cấu trúc đề thi chọn học sinh giỏi quốc gia của Bộ Giáo dục và đào tạo năm 2010.
2. Chương trình chuyên sâu trường THPT chuyên môn Tin học của Bộ Giáo dục và đào tạo năm 2009.
3. Các đề thi chọn học sinh giỏi quốc gia từ năm 2011 đến nay.
4. Tài liệu giáo khoa chuyên tin của Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh Hoàng, Nguyễn Thanh Tùng, NXB Giáo dục Việt Nam.
III. Cấu trúc đề thi:
Đề thi ngày thứ nhất: gồm 3 bài, cụ thể như sau:
TT
Nội dung
Số điểm
Số câu hỏi
Ghi chú

1
- Bài toán bao gồm một trong các vấn đề về:
+ Lý thuyết số.
+ Sắp xếp, tìm kiếm.
- Độ khó ở mức trung bình về giải thuật, cấu trúc dữ liệu và cài đặt.
6
1-2


2
- Bài toán bao gồm một trong các vấn đề về:
+ Duyệt – nhánh cận
+ Thuật toán tham lam
- Độ khó ở mức trung bình về giải thuật, cấu trúc dữ liệu và cài đặt.
7
1


3
- Bài toán đồ thị, bao gồm một trong các vấn đề về:
+ Tìm kiếm DFS hoặc BFS
+ Thành phần liên thông
+ Đồ thị Hamilton
+ Cây khung nhỏ nhất.
- Độ khó ở mức khá về giải thuật, cấu trúc dữ liệu và cài đặt.
7
1
Nếu là bài toán đồ thị thì chỉ cài đặt với ma trận kề.


Đề thi ngày thứ hai: gồm 3 bài, cụ thể như sau:
TT
Nội dung
Số điểm
Số câu hỏi
Ghi chú

1