//
you're reading...
Dùng cho cấp THCS, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Giáo trình chuyên Tin học 10, Đề huấn luyện theo tuần, Đề thi cấp tỉnh - Đồng Tháp, Đề thi HSG quốc gia VNOI, Đề thi Tin học quốc tế IOI

Chương trình THPT chuyên – Môn Tin học

Bộ Giáo dục và Đào tạo, số: 10803 /BGDĐT-GDTrH, V/v:Hướng dẫn thực hiện chương trình chuyên sâu các môn chuyên cấp THPT
Chương trình chuyên sâu môn Tin học


BỘ GIÁO DỤC VÀ ĐÀO TẠO
CHƯƠNG TRÌNH CHUYÊN SÂU THPT CHUYÊN – MÔN: TIN HỌC, Hà Nội, 12/2009


LỚP 10


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

1. Về kiến thức

– Mở rộng và nâng cao hệ thống kiến thức chuẩn, cơ bản của tin học lớp 10 THPT.
– Trang bị kiến thức cơ bản về một số thuật toán, giải thuật.
– Trang bị một số kiến thức cơ bản về ngôn ngữ lập trình.

2. Về kĩ năng

– Thực hiện được một số thuật toán cơ bản.
– Vận dụng dụng được một số thuật toán cơ bản để giải một số bài toán
– Bước đầu sử dụng được ngôn ngữ lập trình để cài đặt được một số thuật toán, biểu diễn dữ liệu.

3. Về thái độ

– Có tác phong suy nghĩ và làm việc hợp lý, khoa học và chính xác.
– Tự giác, tích cực trong học tập

II. KẾ HOẠCH DẠY HỌC

Tổng số tiết: 123 tiết, trong đó có 53 tiết dành cho nội dung chuyên sâu.
Học kì I: 61 tiết
Học kì II: 62 tiết

III. NỘI DUNG DẠY HỌC

3.1. Cấu trúc nội dung dạy học

– Nội dung môn Tin học cho các trường THPT, được qui định trong chương trình môn Tin học, lớp 10, ban hành kèm theo Quyết định số 16/2006/QĐ-BGDĐT ngày 05 tháng 5 năm2006 của Bộ trưởng Bộ Giáo dục và Đào tạo
Nội dung chuyên sâu: gồm 2 chủ đề mở rộng và chuyên sâu:
+ Ngôn ngữ lập trình:
+ Phân tích, thiết kế và cài đặt giải thuật

3.2. Nội dung chuyên sâu


Chuyên đề: NGÔN NGỮ LẬP TRÌNH


Dưới đây dùng Turbo Pascal để mô tả nội dung kiến thức, kĩ năng cần truyền đạt của chuyên đề Ngôn ngữ lập trình, tuy nhiên khi thực hiện có thể chọn sử dụng các ngôn ngữ lập trình khác như C++, Java,… để dạy học.
Số tiết: 20 tiết

1.Khái niệm chương trình và ngôn ngữ lập trình

Kiến thức này đã có trong sách giáo khoa, cần nhắc lại để đảm bảo tính hệ thống.

2. Các thành phần cơ sở của ngôn ngữ lập trình TP

Kiến thức
• Biết các khái niệm cơ bản: Bảng chữ cái, Tên, Tên chuẩn, Tên riêng (từ khoá), Hằng và Biến.
Kỹ năng
• Biết đặt tên đúng. – Nên minh hoạ bằng một đoạn chương trình đơn giản

3. Cấu trúc tổng quát của một chương trình TP

Kiến thức

• Biết các thành phần của một chương trình TP.
Kĩ năng
• Nhận biết được các thành phần của một chương trình không có chương trình con.Dùng một chương trình TP đơn giản để minh hoạ.

4 Dịch, thực hiện và hiệu chỉnh chương trình

Kiến thức
• Biết các bước: soạn thảo, dịch, thực hiện và hiệu chỉnh chương trình.
• Biết một số công cụ của môi trường TP.
Kĩ năng
• Bước đầu sử dụng được chương trình dịch để phát hiện lỗi.
• Bước đầu chỉnh sửa được chương trình dựa vào thông báo lỗi của Chương trình dịch và tính hợp lí của kết quả thu được.

Giới thiệu trên máy tính quá trình viết một chương trình hoàn chỉnh để học sinh biết các thao tác cơ bản.

5.Một số kiểu dữ liệu chuẩn: số nguyên, số thực, logic, ký tự, xâu

Kiến thức
• Với mỗi kiểu dữ liệu, biết được phạm vi giá trị, cách khai báo, các hàm chuẩn và các thủ tục chuẩn có thể dùng.
• Với mỗi biến có kiểu dữ liệu trên, biết cách nhận giá trị (từ bàn phím và dùng lệnh gán) và cách viết giá trị ra màn hình
Kĩ năng
• Biết chọn kiểu dữ liệu thích hợp cho các biến cần khai báo.
• Biết dùng một số hàm chuẩn và thủ tục chuẩn viết một số chương trình dùng các kiểu dữ liệu trên Với mỗi kiểu dữ liệu, cho học sinh làm quen dần từ các ví dụ đơn giản đến phức tạp

6. Tổ chức rẽ nhánh

Kiến thức
• Hiểu được các câu lệnh này dùng để thể hiện các tình huống phải biện luận khi giải các bài toán
• Biết cách viết đúng các lệnh về mặt cú pháp.
Kĩ năng
• Sử dụng được các lệnh để viết các đoạn chương trình có biện luận cấu trúc rẽ nhánh trong mô tả thuật toán của môt số bài toán đơn giản.
• Viết được các lệnh rẽ nhánh khuyết, rẽ nhánh đầy đủ và áp dụng để thể hiện được thuật toán của một số bài toán đơn giản. – Nên bắt đầu bằng việc sử dụng các thuật toán đã có trong sách giáo khoa lớp 10
– Cần xây dựng các bài thực hành và tổ chức thực hiện tại phòng máy để học sinh đạt được những kỹ năng theo yêu cầu
– Nhấn mạnh rằng khác với kiểu mảng, trong kiểu bản ghi, các trường có thể thuộc các kiểu dữ liệu khác nhau.

7. Tổ chức lặp

Kiến thức
• Hiểu nhu cầu của cấu trúc lặp trong biểu diễn thuật toán
• Hiểu cấu trúc lặp kiểm tra điều kiện trước, cấu trúc lặp với số lần định trước.
• Biết cách vận dụng đúng đắn từng loại cấu trúc lặp vào tình huống cụ thể.
Kĩ năng
• Mô tả được thuật toán của một số bài toán sử dụng lệnh lặp.
• Viết đúng các lệnh lặp kiểm tra điều kiện trước, lệnh lặp với số lần định trước
• Dùng để viết chương trình giải một số bài toán.

8. Kiểu mảng

Kiến thức
• Hiểu được cách dùng dữ liệu kiểu mảng một chiều và hai chiều.
• Biết cách khai báo mảng và ký hiệu các phần tử của mảng.
Kĩ năng
• Thực hiện được khai báo mảng, truy cập, tính toán các phần tử của mảng.
• Cài đặt được thuật toán của một số bài toán với kiểu dữ liệu mảng một chiều.

9. Kiểu bản ghi

Kiến thức
• Biết kiểu Bản ghi dùng để thể hiện một loạt đối tượng cùng có chung một số thuộc tính.
• Biết cách khai báo biến kiểu bản ghi.
• Biết truy cập trực tiếp các trường và truy cập bằng lệnh With … Do ….
Kỹ năng
Sử dụng được loại biến bản ghi một cách linh hoạt

10. Kiểu tập hợp

Kiến thức
• Biết cách khai báo dữ liệu kiểu tập hợp với các hạn chế so với tập hợp dùng trong Toán học
• Biết các hàm chuẩn và thủ tục chuẩn đối với kiểu tập hợp
Kỹ năng
Sử dụng được kiểu tập hợp thể hiện một số đối tượng trong một số bài toán

11 Tệp và xử lý tệp

Kiến thức
• Biết khái niệm tệp định kiểu và tệp văn bản và mục đích của các kiểu dữ liệu này để lưu giữ lâu dài các thông tin tạo lập được.
• Biết các lệnh khai báo tệp định kiểu và tệp văn bản.
• Biết các lệnh và một số hàm, thủ tục chuẩn khi làm việc với tệp: gán tên cho biến tệp, mở tệp, đọc thông tin từ tệp, ghi thông tin vào tệp, đóng tệp.
Kĩ năng
Biết các thao tác tệp, chủ yếu là tệp văn bản

12. Chương trình con

Kiến thức
• Biết sự cần thiết của việc tổ chức chương trình con khi viết chương trình-chia để trị.
• Biết sự phân loại chương trình con: thủ tục và hàm.
• Biết cấu trúc một chương trình con.
• Biết gọi một thủ tục, một hàm
Kĩ năng
Viết được các chương trình phức tạp bằng cách tổ chức các chương trình con.


Chuyên đề: PHÂN TÍCH, THIẾT KẾ VÀ CÀI ĐẶT THUẬT TOÁN


Số tiết: 33 tiết

1. Khái niệm bài toán và thuật toán

Có trong sách giáo khoa lớp 10, chỉ cần hệ thống lại

2. Phân tích thuật toán

Kiến thức
• Biết được cùng một bài toán có thể có nhiều thuật toán khác nhau, việc phân tích thuật toán giúp ta lựa chọn thuật toán thích hợp.
• Biết các yếu tố để đánh giá một thuật toán tốt.
Kỹ năng
Đánh giá được độ phức tạp của một số thuật toán cơ bản. Việc phân tích, đánh giá độ phức tạp của từng thuật toán được thực hiện khi học các thuật toán cụ thể.
Việc đánh giá độ phức tạp của thuật toán sẽ còn được củng cố khi giới thiệu đến các thuật toán cụ thể ở phần tiếp theo.

3. Một số thuật toán duyệt: tổ hợp, dãy nhị phân, hoán vị, phân chia số

Kiến thức
Biết các thuật toán duyệt tuần tự và duyệt đệ quy các tổ hợp, dãy nhị phân, hoán vị, phân chia số
Kỹ năng
Vận dụng được để giải một số bài toán và cài đặt được trên máy tính.

4. Một số thuật toán sắp xếp: sắp xếp đơn giản, QuickSort, MergeSort

Kiến thức
• Biết được tầm quan trọng của các thuật toán sắp xếp
• Biết ba thuật toán sắp xếp phổ biến: sắp xếp đơn giản, QuickSort, MergeSort
Kỹ năng
Vận dụng được để giải một số bài toán và cài đặt được trên máy tính.

5. Chia để trị

Kiến thức
• Biết được ý tưởng cơ bản của phương pháp giải bài toán bằng cách chia để trị là chuyển việc giải bài toán kích thước lớn về việc giải bài toán có kích thước nhỏ hơn.
• Biết một số thuật toán tiêu biểu: tìm kiếm nhị phân, luỹ thừa nhanh.
Kỹ năng
• Vận dụng được để giải một số bài toán khác và cài đặt được trên máy tính.

6. Chia để trị

Kiến thức
• Biết được ý tưởng cơ bản của phương pháp giải bài toán bằng cách chia để trị là chuyển việc giải bài toán kích thước lớn về việc giải các bài toán có kích thước nhỏ hơn
• Biết được một số thuật toán tiêu biểu: tìm kiếm nhị phân, luỹ thừa nhanh
Kỹ năng
• Vận dụng được để giải một số bài toán khác và cài đặt được trên máy tính.

7. Mô hình đồ thị không có và có trọng số, cây

Kiến thức
• Nắm được các khái niệm cơ bản liên quan đến mô hình đồ thị: đỉnh, cạnh/cung, đường đi, chu trình, tính liên thông, thành phần liên thông, cây khung, trọng số thông qua các ví dụ điển hình.
• Biết cách thể hiện đồ thị khi lập trình.
Kỹ năng
Cài đặt được các cách biểu diễn đồ thị

8. Bài toán tìm đường đi ngắn nhất

Kiến thức
Biết được hai thuật toán tiêu biểu: Floyd và Dijkstra
Kỹ năng
Vận dụng được để giải một số bài toán và cài đặt được trên máy tính.

9. Bài toán tìm cây khung nhỏ nhất

Kiến thức
Biết được hai thuật toán Prim và Kruskal
Kỹ năng
Vận dụng được để giải một số bài toán và cài đặt được trên máy tính.


IV. GIẢI THÍCH VÀ HƯỚNG DẪN THỰC HIỆN


1. Kế hoạch dạy học

Tổng số tiết cho lớp 10 chuyên là 123 tiết. Trong đó, có 70 tiết học theo chương trình, sách giáo khoa chung cho tất cả các lớp 10 THPT, 53 tiết còn lại được dành để dạy học các modul kiến thức của phần mở rộng và nâng cao. Việc phân chia cụ thể số tiết học cho mỗi phần mở rộng và nâng cao phụ thuộc vào điều kiện thực tế.
Do thời lượng môn Tin học chuyên ít, nên khi chọn chủ đề tự chọn các học sinh lớp 10 chuyên tin học cần chọn chủ đề Tin học để bổ sung thêm thời lượng cho môn học.

2. Nội dung dạy học

Nội dung các chuyên đề được xây dựng với các điều kiện về giáo viên, cơ sở vật chất được đảm bảo và khả năng tiếp thu của học sinh là khá tốt và dựa trên quan niệm:

– Lớp 10 cần học, làm các bài tập để tiếp thu các kiến thức cơ bản và rèn luyện một số kĩ năng phổ thông. Bước đầu trang bị một số kiến thức mở rộng về giải thuật, vận dụng để giải một số bài toán và cài đặt trên máy tính.

– Lớp 11 là lớp bản lề của cả khoá, cần đưa vào các vấn đề nâng cao, chuyên sâu, các bài tập khó hơn.

– Lớp 12 là lớp cuối cấp, học sinh chuẩn bị cho kì thi thi tốt nghiệp và đại học-cao đẳng, chương trình có giảm nhẹ, nhất là phần bài tập. Chủ yếu đưa vào các vấn đề để mở rộng tầm hiểu biết và tăng cường ứng dụng công nghệ.

Không bắt buộc phải dạy hết toàn bộ các chủ đề cũng như tất cả các nội dung trong từng chủ đề, việc chọn chủ đề và nội dung trong từng chủ đề cần cân nhắc dựa trên điều kiện về giáo viên, cơ sở vật chất và khả năng tiếp thu của học sinh.

Tài liệu này thống nhất nội dung dạy học và định hướng việc xây dựng một chương trình cụ thể cho các lớp chuyên tin học trong trường THPT chuyên, các lớp chuyên tin học của khối phổ thông chuyên thuộc trường đại học. Các trường THPT không chuyên căn cứ vào nội dung quy định trong bản hướng dẫn này để bồi dưỡng học sinh giỏi tin học với thời lượng thích hợp.

Ngoài ra, chương trình này còn định hướng kế hoạch xây dựng đội ngũ, đào tạo, bồi dưỡng giáo viên cho các lớp chuyên tin học. Định hướng việc thu thập tài liệu tốt, phù hợp.

Số tiết đưa ra cho mỗi chủ đề chỉ mang tính gợi ý và tương đối. Tuỳ điều kiện cụ thể, giáo viên tự xác định số tiết của từng bài giảng.

3. Phương pháp và phương tiện dạy học

1) Về cơ bản việc dạy các chủ đề theo cách học sinh tự nghiên cứu dưới sự hướng dẫn, định hướng của giáo viên. Khuyến khích học sinh trao đổi, thảo luận (kể cả qua mạng Internet) về các nội dung học tập.

2) Hai chủ đề nên dạy song song một cách hợp lý sao cho luôn có các bài tập hay để lập trình.

3) Khi dạy mô đun 1, không nhất thiết dạy xong các kiểu dữ liệu mới dạy lệnh. Ví dụ, sau kiểu lô gic, có thể dạy luôn các tổ chức rẽ nhánh, tổ chức lặp.

4) Học sinh chuyên cần cài đặt các thuật toán trên máy tính và trao đổi, tham khảo học tập qua Internet, vì vậy các trường cần trang bị máy tính, Internet cho các lớp chuyên tin.

4. Đánh giá kết quả học tập của học sinh

1) Hiện tại ngôn ngữ lập trình Pascal là ngôn ngữ lập trình được dùng trong kì thi chọn học sinh giỏi quốc gia môn tin học (chương trình dịch có thể là Turbo Pascal hoặc Free Pascal). Tuy nhiên, để phù hợp với xu thế phát triển của ngôn ngữ lập trình, khuyến khích sử dụng các ngôn ngữ dùng cho lập trình chuyên nghiệp như C, Java… để dạy học.

2) Nội dung dạy học tin học chuyên còn định hướng cho các kì thi tuyển chọn học sinh giỏi tin học ở địa phương và quốc gia.

3) Việc đánh giá kết quả học tập của học sinh chuyên phải căn cứ vào mục tiêu dạy học (kiến thức, kĩ năng, yêu cầu về thái độ); việc biên soạn đề kiểm tra phải căn cứ vào nội dung được qui định trong chương trình môn Tin học THPT và chương trình mở rộng, chuyên sâu, chú trọng đánh giá kĩ năng thực hành, năng lực giải quyết vấn dề và năng lực sáng tạo của học sinh.

4) Cần sử dụng kết hợp các phương pháp đánh giá như đánh giá theo kết quả đầu ra, đánh giá theo quá trình. Đa dạng hoá các loại hình kiểm tra: viết, vấn đáp, thực hành trên máy, tự kiểm tra, học sinh kiểm tra nhau, đánh giá của các chuyên gia, đánh giá nhờ các website trên mạng,…


TÀI LIỆU THAM KHẢO


1) Sách giáo khoa Tin học lớp 10, 11, 12
2) Wirth, N., Programs = Algorithms + Data Structures (có bản dịch tiếng Việt: Chương trình = Thuật toán + Cấu trúc dữ liệu)
3) Sedgewick, R., Algorithms (Bản dịch tiếng Việt: Cẩm nang Thuật toán)
4) Ullman, J.D., Data structures and Algorithms.
5) Ley, J.B., Programming pearls (Bản dịch tiếng Việt : Những viên ngọc trong lập trình).
6) Courtin J. Kowarski I.
7) Nhập môn thuật toán và cấu trúc dữ liệu
8) Tạp chí thế giới Vi tính PCWORLD
9) L.Nyhoff, S. Leestma (Bản dịch tiếng Việt : Lập trình nâng cao bằng Passcal với các cấu trúc dữ liệu )
10) Một số sách bài tập lập trình của ĐHTH HN , ĐHBK HN,Viện KHGD
11) Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật.
12) Một số trang web:
http://olympiads.win.tue.nl/ioi: trang web của các kỳ thi Tin học quốc tế
http://www.ioicamp.net: trang web của các sinh viên và học sinh chuyên Tin Việt Nam do Đại học Quốc gia Hà Nội chủ trì


LỚP 11


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:

– Mở rộng và nâng cao hệ thống chuẩn, cơ bản của môn Tin học lớp 11 THPT
– Tiếp tục mở rộng và nâng cao các nội dung các chuyên đề đã có ở lớp 10 chuyên môn Tin học trường THPT chuyên.
– Trang bị một số chiến lược xây dựng thuật toán: Quy hoạch động, Lí thuyết trò chơi,…

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 11 THPT, có 35 tiết dành cho chuyên sâu.

III NỘI DUNG DẠY HỌC

3.1. Cấu trúc nội dung dạy học

– Nội dung môn Tin học cho các trường THPT, được qui định trong chương trình môn Tin học, lớp 11, ban hành kèm theo Quyết định số 16/2006/QĐ-BGDĐT ngày 05 tháng 5 năm2006 của Bộ trưởng Bộ Giáo dục và Đào tạo
– Nội dung chuyên sâu: gồm 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 đề chuyên sâu sau:
Chuyên đề 1. Thuật toán Quy hoạch động
Chuyên đề 2. Lý thuyết trò chơi
Chuyên đề 3. Duyệt toàn bộ nâng cao
Chuyên đề 4. Bài toán luồng cực đại trong mạng và ứng dụng
Chuyên đề 5. Bài toán lập lịch


Chuyên đề 1. THUẬT TOÁN QUY HOẠCH ĐỘNG ( Dynamic programming algorithm)


Số tiết: 15

1. Bài toán có thể giải bằng thuật toán QHĐ

Kiến thức:
• Biết nguyên lí tối ưu, đặc trưng các bài toán có thể giải bằng thuật toán QHĐ, đặc trưng chính của thuật toán QHĐ.
• Phân biệt sự giống và khác nhau căn bản giữa thuật toán QHĐ và Đệ quy
Kĩ năng:
Nhận biết được bài toán cụ thể có thể giải được bằng QHĐ hay không. Thông qua ví dụ để minh họa lí thuyết.

2. Thuật toán QHĐ

Kiến thức:
• Hiểu các bước cần thực hiện khi xây dựng thuật toán QHĐ
• Hiểu các khái niệm cơ bản: cở sở, bảng phương án, công thức truy hồi, các truy vết để tìm nghiệm.

Kĩ năng:
Xây dựng được thuật toán QHĐ để giải bài toán cụ thể. Các ví dụ ban đầu nên chọn bài toán dễ tìm thuật toán QHĐ để giải.

3. Một số bài toán thường gặp được giải bằng QHĐ

  1. – Bài toán dãy con đơn điệu tăng dài nhất;
  2. – Bài toán xâu con chung dài nhất;
  3. – Bài toán biến đổi xâu;
  4. – Bài toán cái túi;
  5. – Bài toán lũy thừa một số;
  6. – Bài toán nhân các ma trận;
  7. – Bài toán chia đa giác thành các tam giác;

Kiến thức:
Với mỗi bài toán cụ thể, hiểu cách xác định các khái niệm cơ bản của QHĐ.
Kĩ năng
Cài đặt được chương trình và thử nghiệm chương trình với các bộ dữ liệu khác nhau. – Nên yêu cầu HS hiểu thấu đáo cách xác định các khái niệm cơ bản trước khi cài đặt chương trình.
– GV có thể tùy chọn các bài toán cụ thể khác để thay thế cho các bài toán nêu ở cột bên.


Chuyên đề 2. LÝ THUYẾT TRÒ CHƠI


Số tiết: 15

1 Khái niệm bài toán trò chơi. Phân loại. Một số bài toán bài toán trò chơi kinh điển

Kiến thức:
• Hiểu khái niệm về trò chơi đối kháng và không đối kháng, đặc trưng của bài toán trò chơi, khái niệm chiến lược điều khiển, hàm mục tiêu;
• Biết các loại yêu cầu thường gặp đối với bài toán trò chơi,
• Biết các bài toán trò chơi kinh điển: cờ ca rô, trò chơi Nim, trò chơi trên băng giấy và trên bàn cờ, trò chơi nhận dạng cấu hình.
Kỹ năng:
Biết cách lập trình tìm nước đi hợp lệ, nước đi tối ưu cục bộ. Chưa yêu cầu tìm chiến lược tối ưu.

2 Trò chơi trên đồ thị

Kiến thức:
• Biết cách xây dựng mô hình toán học trên cơ sở lý thuyết đồ thị;
• Phân biệt hai loại mô hình: dạng cây và dạng có chu trình tương ứng với các trường hợp tài nguyên hữu hạn và tài nguyên vô hạn;
• Giới thiệu hàm Grandi và ứng dụng.
Kỹ năng:
• Biết cách xây dựng mô hình toán học và cách tổ chức dữ liệu cho một số bài toán trò chơi kinh điển;
• Tìm được tập đỉnh thắng, thua, hoà;
• Lập trình tổ chức chơi giữa người và máy, xây dựng được mô hình trí tuệ nhân tạo đơn giản;
• Biết cách kiểm tra tính chuẩn mực của dữ liệu vào. Chỉ sử dụng các khái niệm cơ bản của lý thuyết đồ thị: đỉnh, cung có hướng và vô hướng, trọng số.

3 Kỹ thuật bảng phương án.

Kiến thức:
• Giới thiệu khái niệm bảng phương án và kỹ thuật dữ liệu hoá chiến lược điều khiể; xác định vai trò bảng phương án trong các bài toán trò chơi nói riêng và trong các bài toán điều khiển nói chung;
• Trình bày các loại bảng phương án và cách khởi tạo, lưu trữ, khai thác ứng dụng;
• Xác định quan hệ giữa bảng phương án và quy hoạch động trong một số mô hình trò chơi.
Kỹ năng:
• Biết cách ứng dụng bảng phương án trong hai chế độ:
– + Chế độ bảng phương án ngoài,
– + Chế độ bảng phương án trong,
• Lập trình xây dựng được bảng phương án cho một số trò chơi kinh điển đã giới thiệu;
• Sử dụng bảng phương án để tìm chiến lược điều khiển tối ưu;
• Biết cách ứng dụng bảng phương án giải quyết một số bài toán có lô gíc phức tạp. Không đi sâu vào lý thuyết bảng phương án, chỉ lưu ý những yếu tố, tính chất cơ bản phải có của bảng phương án.

4 Trò chơi và trí tuệ nhân tạo

Kiến thức:
• Giới thiệu về suy diễn, biểu diễn các suy diễn, khái niệm lập trình lôgic và ứng dụng trong các bài toán trò chơi;
• Giới thiệu một số phương pháp nâng cao hiệu quả chương trình bằng kỹ thuật lập trình nhiều giai đoạn.
Kỹ năng:
Biết cách dùng máy tính để hỗ trợ việc xây dựng một chương trình hiệu quả và đơn giản. Cho học sinh thấy mối quan hệ giữa bài toán trò chơi và trí tuệ nhân tạo, biết rõ vai trò vị trí của kỹ thuật lập trình trò chơi trong tin học nói chung.


Chuyên đề 3. DUYỆT TOÀN BỘ NÂNG CAO


Số tiết: 5

1. Chiến lược giải toán bằng cách duyệt toàn bộ. Phương pháp quay lui

Kiến thức:
• Biết nguyên lí cơ bản của phương pháp quay lui là liệt kê và thử tất cả các khả năng xây dựng nghiệm có thể cho bài toán.
• Hiểu được lược đồ tổng quát của một thuật toán quay lui.
Kĩ năng:
• Nhận biết được vectơ nghiệm và từng thành phần của vecto nghiệm;
• Biết được tập điều kiện để một vectơ đã chọn là nghiệm;
• Nhận biết được tập các ứng cử viên được chọn làm thành phần thứ i của vectơ nghiệm. Thông qua ví dụ để minh họa lí thuyết.

2.Một số bài toán thường gặp được giải bằng duyệt toàn bộ

– Bài toán liệt kê các dãy nhị phân độ dài n;
– Bài toán liệt kê tập con k phần tử;
– Bài toán xếp 8 quân hậu;
– Bài toán mã đi tuần.
Kiến thức:
Hiểu cách xác định các bước xây dựng vectơ ứng cử viên và kiểm tra để tìm nghiệm của mỗi bài toán cụ thể.
Kĩ năng:
Cài đặt được chương trình và thử nghiệm chương trình với các bộ dữ liệu khác nhau. – Nên yêu cầu HS hiểu thấu đáo cách xác định các khái niệm cơ bản trước khi cài đặt chương trình.
– GV có thể tùy chọn các bài toán cụ thể khác để thay thế cho các bài toán nêu ở cột bên.
– GV nên phân tích những thuận lợi và hạn chế của phương pháp duyệt toàn bộ so với những phương pháp khác. Có thể chọn một vài ví dụ có thể áp dụng hai phương pháp khác nhau để so sánh được (chẳng hạn những bài toán sinh tuần tự đã học ở lớp 10).


Chuyên đề 4. BÀI TOÁN LUỒNG CỰC ĐẠI TRONG MẠNG VÀ ỨNG DỤNG


Số tiết: 5

1. Biểu diễn đồ thị, duyệt đồ thị

Kiến thức:
Hiểu các khái niệm:
– Ma trận trọng số
– Danh sách kề
– Thuật toán duyệt BFS và DFS
Kĩ năng:
• Lập đúng ma trận kề
• Cài đặt được các thuật toán BFS và DFS Trước khi cài đặt thuật toán có thể yêu cầu HS mô phỏng thuật toán bằng ví dụ đơn giản, cụ thể.

2. Bài toán luồng cực đại

Kiến thức:
Hiểu các khái niệm:
– Mạng và luồng trong mạng
– Bài toán luồng cực đại trong mạng
Kĩ năng:
Nhận biết được bài toán thực tế có thể đưa về bài toán luồng cực đại trong mạng.
3 Lát cắt. Đường tăng luồng. Định lý Ford – Fulkerson Kiến thức:
Hiểu các nội dung:
– Lát cắt và đường tăng luồng
– Định lý về luồng cực đại và lát cắt hẹp nhất
Kĩ năng:
Vận dụng được định lí trong các bài toán cụ thể

4. Thuật toán Ford – Fulkerson tìm luồng cực đại trong mạng

Kiến thức:
Hiểu các nội dung:
– Mô tả thuật toán
– Về hiệu quả của thuật toán
– Thuật toán cải biên của Edmond-Karp
Kĩ năng:
Cài đặt tốt chương trình cho thuật toán

5. Một số bài toán luồng tổng quát

Kiến thức:
Hiểu các nội dung:
– Mạng với nhiều điểm phát và điểm thu
– Bài toán với khả năng thông qua của các cung và các đỉnh
– Mạng trong đó khả năng thông qua của mỗi cung bị chặn hai phía.
Kĩ năng:
Nhận biết được các vấn đề thực tế tương ứng với các luồng tổng quát

6. Một số ứng dụng

Kiến thức:
Hiểu một số bài toán:
– Bài toán ghép cặp trên đồ thị hai phía
– Bài toán về hệ thống đại diện chung.
– Bài toán lập lịch
Kĩ năng:
Cài đặt được chương trình cho các thuật toán giải các bài toán


Chuyên đề 5. BÀI TOÁN LẬP LỊCH


Số tiết: 5

1. Giới thiệu bài toán lập lịch

1.1. Các thành phần của bài toán lập lịch

Kiến thức:
Hiểu các khái niệm về:
Công việc: Trình tự thực hiện, Ngắt quãng, Thời điểm sẵn sàng, Thời gian xử lý, Thời điểm hoàn thành, Thời gian trôi, Thời gian chờ đợi, Thời hạn hoàn thành, Thời gian lệch, Khoảng trễ, Độ trễ, Đúng hạn.

Môi trường máy: Máy, Máy đơn, Máy song song, Xưởng công việc (Job Shop), Xưởng dây chuyền (Flow Shop), Xưởng mở (Open Shop).

Hàm mục tiêu: Thời điểm hoàn thành lịch (Makespan), Tổng (có trọng số) thời gian xử lý (Total (Weighted) Completion Time), Thời gian trôi trung bình (có trọng số) ((Weighted) Mean Flow Time), Thời gian chờ đợi trung bình (Mean Waiting Time), Khoảng trễ (Lateness), Độ trễ, Đúng hạn, Tiêu chuẩn tổng quát, Qui dẫn giữa các bài toán lập lịch.

1.2. Ký pháp Graham

Kiến thức:
Hiểu biết các khái niệm:
– Trường mô tả môi trường máy
– Trường mô tả các ràng buộc và thuộc tính của công việc
– Trường mô tả tiêu chuẩn tối ưu

2. Một số phương pháp giải cơ bản

2.1. Giải thuật tham lam

Kiến thức:
Hiểu biết các thuật toán:

  1. – Thời gian xử lý lớn nhất (Longest Processing Time, viết tắt là LPT)
  2. – Thời gian xử lý nhỏ nhất (Shortest Processing Time, viết tắt là SPT)
  3. – Thời gian xử lý có trọng số nhỏ nhất (Weighted Shortest Processing Time – WSPT)
  4. – Thời hạn hoàn thành sớm nhất (Earliest Due Date- EDD)
  5. – Thời gian lệch nhỏ nhất (Minimum Slack Time – MST)
  6. – Lập luận hoán đổi
  7. – Các ví dụ ứng dụng: Bài toán 1| | Cj . Bài toán 1||Lmax. Bài toán 1|rj, pmtn|Lmax. Bài toán 1|rj, pmtn|Cj. Bài toán 1|prec|hmax – Thuật toán Lawler. Thuật toán Johnson giải bài toán F2||Cmax

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên

2.2. Qui hoạch động

Kiến thức:
Hiểu biết các thuật toán:

  1. – Bài toán lập lịch cực đại lợi nhuận 1| | wi(1-Ui)
  2. – Thuật toán Moore

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên

2.3. Qui về bài toán tối ưu trên đồ thị

Kiến thức:
Hiểu biết các nội dung:

  1. – Bài toán lập lịch thi công (PERT).
  2. – Qui dẫn bài toán R||Cj về bài toán ghép cặp trên đồ thị hai phía

Kĩ năng:
Cài đặt chương trình cho các thuật toán trên

2.4. Thuật toán nhánh cận

Kiến thức:
Hiểu biết các nội dung:

  1. – Sơ đồ chung của thuật toán nhánh cận
  2. – Ví dụ áp dụng: Bài toán 1|ri|Lmax.

Kĩ năng:
Cài đặt bảng chương trình cho các thuật toán trên


IV. GIẢI THÍCH VÀ HƯỚNG DẪN THỰC HIỆN


4.1. Kế hoạch dạy học

Triển khai dạy học ở lớp 11 một mặt đảm bảo hoàn thành chương trình SGK tin học 11 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. 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.
Chẳng hạn, chủ đề 1 chuyên sâu ở lớp 10 đã có học về TP Pascal nên quỹ thời gian dành cho Tin học 11 nên dùng để nâng cao kiến thức về lập trình, ngôn ngữ lập trình bậc cao và kĩ thuật lập trình trong môi trường 32 bit. Khuyến khích việc học và sử dụng C++, Java,…

4.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 và chuyên đề 2) và chuyên đề tự chọn (chọn một trong ba chuyên đề 3, 4, 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.

– 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.

4.3. Phương pháp và phương tiện dạy học

– Học sinh 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 để học sinh 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 học sinh chuyên tin cần đảm bảo mỗi em có 1 máy và cung cấp 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 để học sinh có thể khai thác Internet một cách thuận lợi.

4.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 học sinh để có giải pháp kịp thời.


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:

  1. Chuyên đề 1. Tính toán hình học , 12 tiết
  2. Chuyên đề 2. Độ phức tạp của bài toán, 8 tiết
  3. 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:

  1. Chuyên đề 4. Các cách tiếpcận giải bài toán NP-khó, 5 tiết
  2. 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.

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 TẠP CỦA BÀI TOÁN


Số tiết: 8
Mục đích:
• Hiểu được khái niệm độ phức tạp tính toán của bài toán;
• Nắm được một số kỹ thuật phân tích độ phức tạp tính toán của bài toán;
• Nắm được khái niệm qui dẫn giữa các bài toán;
• Có kiến thức nhập môn về các bài toán NP-đầy đủ, NP-khó;
• Nắm được danh sách một số bài toán NP-đầy đủ, NP-khó.

1. Độ phức tạp của bài toán

Kiến thức:
– Hiểu khái niệm bài toán tính toán;
– Hiểu khái niệm độ phức tạp tính toán của bài toán.
Kĩ năng:
Phân biệt được mức độ phức tạp của các bài toán.

2. Phân tích độ phức tạp tính toán của bài toán

Kiến thức:
– Nắm được ý nghĩa của việc đánh giá cận trên, đánh giá cận dưới của bài toán;
– Hiểu được các kĩ thuật đánh giá cận dưới cho độ phức tạp của bài toán nhờ sử dụng mô hình tính toán cây quyết định và lập luận phản biện;
– Hiểu được khái niệm qui dẫn và ứng dụng để so sánh mức độ khó của các bài toán.
Kĩ năng:
Phân tích được độ phức tạp của một số bài toán cụ thể.

3. Nhập môn NP-đầy đủ

Kiến thức:
– Biết khái niệm bài toán dạng quyết định;
– Biết khái niệm bằng chứng ngắn gọn dễ kiểm tra;
– Hiểu được định nghĩa lớp bài toán NP và co-NP, lớp bài toán NP-đầy đủ và NP-khó;
– Biết danh mục một số bài toán NP-khó.
Kĩ năng:
Nhận dạng được các bài toán NP-khó.


Chuyên đề 3. CÁC CẤU TRÚC DỮ LIỆU NÂNG CAO


Số tiết: 10

Mục đích:
• Hiểu khái niệm kiểu dữ liệu trừu tượng cây;
• Nắm được các ứng dụng của cây;
• Biết cách tổ chức dữ liệu dạng cây;
• Nắm được một số cấu trúc dữ liệu và thuật toán xử lý;
• Nắm được một số ứng dụ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.

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:

  1. • Bài toán cái túi,
  2. • Bài toán người du lịch,
  3. • Bài toán phủ đỉnh,
  4. • Bài toán đóng thùng,
  5. • 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.

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:

  1. • Bài toán lập lịch,
  2. • Bài toán trò chơi,
  3. • Tính gần đúng,
  4. • Tối ưu hóa quá trình xử lý truy vấn trong hệ QTCSDL,
  5. • 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.

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2015
M T W T F S S
« Sep   Nov »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: