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

ộ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; 
- 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 
 47 
- 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. 
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; 
- 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 
 48 
- 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. 
nhau 
 49 
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: 
 50 
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. 
 51 
Chuyên đề 5: THUÂṬ 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âṭ 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âṭ 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âṭ 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, 
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 
- 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ý. 
 52 
 Vấn đề xác định điều kiện kết thúc 
xử lý. 
với những bài toán mẫu. 
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. 
 53 
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ế hoac̣h daỵ hoc̣ tổng thể cho 
cả 03 lớp để xây dưṇg kế hoac̣h daỵ hoc̣ thưc̣ tế . Thưc̣ chất nôị dung các chuyên đề của chương trình lớp 12 đa ̃đề 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ôṭ khó khăn là chương trình SGK Tin hoc̣ 12 và chương trình các chuyên đề chuyên sâu có sự khác biệt nhiều , viêc̣ daỵ hoc̣ xen 
kẽ hai nôị dung đó của cùng môṭ môn hoc̣ đòi hỏi GV phải tổ chức daỵ hoc̣ 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ươṇg cho các chuyên đề cũng chỉ mang tính chất tương đối , GV hoàn toàn chủ đôṇg để đưa ra các nôị 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. 
 54 
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ả hoc̣ tâp̣ của HS qua chương trínhGK Tin hoc̣ 11 và các chuyên đề chuyên 
sâu. 
Với chương trình SGK Tin hoc̣ 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êṇ viêc̣ đánh giá đôc̣ lâp̣, sau đó lấy tổng điểm theo môṭ tỷ lê ̣nào đó, chẳng haṇ 5 - 5.