MỤC LỤC
QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (BẢN SAO) 3
LỜI CAM ĐOAN 4
MỞ ĐẦU 1
1. Tính cấp thiết của đề tài 1
2. Mục tiêu nghiên cứu 2
3. Đối tượng và phạm vi nghiên cứu 3
4. Phương pháp nghiên cứu 3
5. Bố cục của đề tài 4
6. Tổng quan tài liệu tham khảo 4
CHƯƠNG 1 5
PHƯƠNG PHÁP NHÁNH CẬN 5
1.1. KỸ THUẬT ĐỆ QUY 5
1.1.1. Thuật toán quay lui 5
1.1.2. Giải bài toán bằng cách sử dụng Đệ quy quay lui 6
1.2. PHƯƠNG PHÁP NHÁNH CẬN 11
1.2.1. Bài toán tối ưu tổ hợp 11
1.2.2 Cách giải một bài toán bằng phương pháp nhánh cận 13
CHƯƠNG 2 16
CHƯƠNG TRÌNH CHUYÊN SÂU MÔN TIN HỌC TRƯỜNG THPT
CHUYÊN 16
2.1 CHƯƠNG TRÌNH CHUYÊN SÂU MÔN TIN HỌC KHỐI 10 16
2.1.1 Mục đích 16
2.1.2 Kế hoạch và nội dung dạy học 16
2.2 CHƯƠNG TRÌNH CHUYÊN SÂU MÔN TIN HỌC KHỐI 11 24
2.2.1 Mục đích 24
2.2.2 Kế hoạch và nội dung dạy học 25
2.3 CHƯƠNG TRÌNH CHUYÊN SÂU MÔN TIN HỌC KHỐI 12 35
2.3.1 Mục đích 35
2.3.2 Kế hoạch và nội dung dạy học 36
2.4 ĐỊNH HƯỚNG PHƯƠNG PHÁP DẠY HỌC CHUYÊN ĐỀ

MỞ ĐẦU
1. Tính cấp thiết của đề tài
Chương trình đào tạo và bồi dưỡng học sinh có năng khiếu Toán, Tin
học bậc Trung học phổ thông đã được thực hiện trong nhiều năm qua. Qua
những năm thực hiện nó như là một chu trình đặc biệt gắn với sự trưởng thành
và hoàn thiện một mô hình đào tạo đặc biệt. Đó là đào tạo mũi nhọn, đào tạo
các thế hệ học sinh có năng khiếu trong lĩnh vực Toán học, Tin học. Lớp lớp
các thế hệ thầy và trò đã dũng cảm đi lên, tìm tòi và sáng tạo để tiếp cận với
thế giới hiện đại, cập nhật thông tin và nghiên cứu các phương pháp. Gắn với
việc đổi mới phương pháp dạy và học của chương trình đào tạo chuyên,
ngành Giáo dục và Đào tạo đang tích cực đổi mới phương pháp dạy và học để
đào tạo những thế hệ học sinh giỏi có kết quả cao trong các kỳ thi học sinh
giỏi cấp Quốc gia và giành được nhiều huy chương trong các kỳ thi Olympic
quốc tế mà trong đó có kỳ thi Olympic Tin học.
Có thể nói, giáo dục mũi nhọn phổ thông đã thu được những thành tựu
rực rỡ, được Nhà nước đầu tư có hiệu quả, xã hội thừa nhận và bạn bè quốc tế
khâm phục. Các đội tuyển quốc gia tham dự các kỳ thi olympic quốc tế có bề
dày thành tích mang tính ổn định và có tính kế thừa. Đặc biệt, đội tuyển Tin
học quốc gia tham dự thi Olympic quốc tế đã đạt được nhiều thành tích nỗi
bật. Tuy ra đời muộn hơn hệ chuyên Toán nhưng hệ THPT chuyên Tin học đã
sớm khẳng định vị thế của mình, đang trên đà hoàn thiện và phát triển đúng
hướng.
Để nâng cao chất lượng đào tạo mũi nhọn khối chuyên Tin học trường
THPT Chuyên Quảng Bình các thầy cô giáo luôn luôn cố gắng đổi mới
phương pháp, xây dựng các chuyên đề dạy và học các thuật toán trong tin học
để nâng cao chất lượng cũng như hiệu quả giáo dục. Để giải quyết tốt bài toán
thì học sinh cần phải có một số kỹ thuật quan trọng trong việc tiếp cận bài
1
toán và tìm thuật toán. Có rất nhiều lớp thuật toán khác nhau như: Vét cạn;
Chia để trị; Quy hoạch động; Tham lam; Nhánh cận; Các thuật toán trên đồ

được bằng phương pháp nhánh cận. Các bài toán được cài đặt chương trình
bằng ngôn ngữ lập trình Free Pascal để minh họa quá trình thực hiện thuật
toán.
4. Phương pháp nghiên cứu
Bài toán đặt ra trong thực tế yêu cầu tìm ra một nghiệm thỏa mãn một số
điều kiện nào đó và nghiệm đó là tốt nhất theo một chỉ tiêu cụ thể, đó là lớp
bài toán tối ưu. Nghiên cứu lời giải các lớp bài toán tối ưu thuộc về lĩnh vực
quy hoạch toán học.
Tuy nhiên cũng cần phải nói rằng trong nhiều trường hợp chúng ta chưa
thể xây dựng một thuật toán nào thực sự hữu hiệu để giải bài toán tối ưu, mà
cho tới nay việc tìm nghiệm của chúng vẫn phải dựa trên mô hình liệt kê toàn
bộ các cấu hình có thể và đánh giá, tìm ra cấu hình tốt nhất. Việc tìm cấu hình
theo cách này còn có tên gọi là vét cạn. Chính nhờ kỹ thuật này cùng với sự
phát triển của máy tính điện tử mà nhiều bài toán khó đã tìm thấy lời giải.
Mô hình thuật toán quay lui là tìm kiếm trên một cây phân cấp. Nếu giả
thiết rằng mỗi nút nhánh của cây chỉ có 2 nút con thì cây có độ cao n sẽ có tới
2
n
nút lá, con số này lớn hơn rất nhiều lần so với kích thước dữ liệu đầu vào n.
Chính vì vậy mà nếu như ta có thao tác thừa trong việc chọn x
i
thì sẽ phải trả
giá rất lớn về chi phí thực thi thuật toán bởi quá trình tìm kiếm lòng vòng vô
nghĩa trong các bước chọn kế tiếp x
i + 1
, x
i + 2
, … Khi đó, một vấn đề đặt ra là
trong quá trình liệt kê lời giải ta cần tận dụng những thông tin đã tìm được để
3

1.1. KỸ THUẬT ĐỆ QUY
1.1.1. Thuật toán quay lui
Thuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Thuật toán
này làm việc theo cách:
- Mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử
- Mỗi phần tử được chọn bằng cách thử tất cả các khả năng.
Giả sử cấu hình hình cần liệt kê có dạng x
1
, x
2
, … x
n
, khi đó thuật toán
quay lui sẽ xét tất cả các giá trị x
1
có thể nhận, thử cho x
1
nhận lần lượt các
giá trị đó. Với mỗi giá trị thử gán cho x
1
, thuật toán sẽ xét tất cả các giá trị x
2
có thể nhận, lại thử cho x
2
nhận lần lượt các giá trị đó. Với mỗi giá trị thử gán
cho x
2
lại xét tiếp các khả năng chọn x
3
, cứ tiếp tục như vậy… Mỗi khi ta tìm

Ví dụ:
NHIPHAN.INP NHIPHAN.OUT
3 000
001
010
011
100
101
110
111
6
Thuật toán:
Ta sẽ liệt kê các dãy này bằng cách thử dùng các giá trị {0, 1} gán
cho x
i
. Với mỗi giá trị gán cho x
i
lại thử các giá trị có thể gán cho x
i+1
, …
Sau đây là chương trình liệt kê các dãy nhị phân với quy định khuôn
dạng Input/Output theo yêu cầu của bài toán.
Chương trình:
Program Liet_ke_day_nhi_phan;
Const fi = 'NHIPHAN.INP';
fo = 'NHIPHAN.OUT';
Var N:Integer;
X:AnsiString;
f:Text;
Procedure Read_Data;

Bài toán liệt kê các tập con có K phần tử:
Cho tập A gồm các phần tử {1, 2, …, N} theo thứ tự tăng dần.
8
Yêu cầu: Hãy viết chương trình liệt kê tất cả các tập con có k phần tử
theo thứ tự tăng dần là tập con của tập A.
Dữ liệu vào: Cho trong file văn bản SUBSET.INP, có cấu trúc như sau:
- Dòng 1: Ghi hai số nguyên dương N và K. (2 ≤ N ≤ 100, 1 ≤ K < N).
Dữ liệu ra: Ghi ra file văn bản SUBSET.OUT theo cấu trúc sau:
- Trên mỗi dòng: Ghi một tập con có độ dài k tìm được, các phần tử cách
nhau một dấu cách.
Ví dụ:
SUBSET.INP SUBSET.OUT
5 3 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Thuật toán:
Bài toán liệt kê tập con K phần tử của tập S = {1,2,…,n} có thể quy về
bài toán liệt kê các dãy K phần tử x
1…N
, trong đó 1 ≤ x
1
< x
2

i
là x
i -1
+ 1.
9
Từ các nhận xét trên ta có giá trị cận dưới và cận trên của x
i

là:
x
i -1
+ 1 ≤ x
i
≤ n - k + i
(Giả thiết rằng có thêm một số x
0
= 0 khi xét công thức trên với i = 1)
Thuật toán quay lui sẽ xét tất cả các cách chọn x
1
từ 1 (= x
0
+1) đến n -
k + 1, với mỗi giá trị đó, xét tiếp tất cả các cách chọn x
2
từ x
1
+1 đến n - k +
2, … cứ như vậy khi chọn được đến x
k
thì ta có một cấu hình cần liệt kê.

Begin
X[i]:=j;
if i=K then
Write_Data
Else
Attemp(i+1);
End;
End;
BEGIN
Read_Data;
X[0]:=0;
Attemp(1);
Close(f);
END.
1.2. PHƯƠNG PHÁP NHÁNH CẬN
1.2.1. Bài toán tối ưu tổ hợp
Trong rất nhiều vấn đề ứng dụng thực tế của tổ hợp, các cấu hình của tổ
hợp còn được gán cho một giá trị bằng số đánh giá giá trị sử dụng của cấu
hình đối với mục đích sử dụng cụ thể nào đó.
11
Khi đó xuất hiện bài toán: Hãy lựa chọn trong số các cấu hình tổ hợp
chấp nhận được cấu hình có giá trị sử dụng tốt nhất. Các bài toán như vậy
chúng ta sẽ gọi là bài toán tối ưu tổ hợp.
Dưới dạng tổng quát bài toán tối ưu tổ hợp có thể phát biểu như sau:
Tìm cực tiểu (hay cực đại) của hàm
( )
min(max),f x
→
với điều kiện
x D

hợp đặt ra là: Trên cơ sở các thuật toán liệt kê tổ hợp ta tiến hành duyệt từng
phương án của bài toán, đối với mỗi phương án ta đều tính giá trị hàm mục
tiêu tại nó, sau đó so sánh giá trị hàm mục tiêu tại tất cả các phương án được
liệt kê để tìm ra phương án tối ưu. Phương pháp xây dựng theo nguyên tắc
như vậy có tên gọi là phương pháp duyệt toàn bộ. Duyệt toàn bộ là khó có thể
thực hiện được ngay cả trên những máy tính điện tử hiện đại nhất.
Ví dụ để liệt kê hết 15! = 1307674368000 hoán vị trên máy tính điện tử
với tốc độ tính toán 1 tỷ phép tính một giây, nếu để liệt kê một hoán vị cần
phải làm 100 phép tính, thì ta cần một khoảng thời gian là 130767 giây, lớn
hơn 36 giờ. Vì vậy cần phải có những biện pháp nhằm hạn chế việc tìm kiếm
thì mới có hy vọng giải được các bài toán tối ưu tổ hợp thực tế.
12
Tất nhiên để có thể đề ra những biện pháp như vậy cần phải nghiên cứu
kỹ tính chất của bài toán tối ưu tổ hợp cụ thể. Trong một số trường hợp cụ thể
ta có thể xây dựng những thuật toán hiệu quả để giải bài toán đặt ra. Tuy
nhiên phải nhấn mạnh rằng trong nhiều trường hợp (ví dụ bài toán người du
lịch, bài toán cái túi, bài toán đồ thị con đầy đủ cực đại) chúng ta chưa thể xây
dựng được phương pháp hữu hiệu nào khác ngoài phương pháp duyệt toàn bộ.
Khi đó, một vấn đề đặt ra là trong quá trình liệt kê lời giải ta cần tận dụng các
thông tin đã tìm được để loại bỏ những phương án chắc chắn không phải tối
ưu.
Trong phần tiếp theo ta sẽ xét một sơ đồ tìm như vậy để giải các bài toán
tối ưu tổ hợp với tên gọi là thuật toán nhánh cận.
1.2.2 Cách giải một bài toán bằng phương pháp nhánh cận
Ta sẽ mô tả tư tưởng của thuật toán trên mô hình bài toán tối ưu tổ hợp
tổng quát sau:
( )
{
}
min :

β
và
2
β
, Nếu
1
β
≤
2
β
thì bước tiếp theo sẽ
chọn nhánh D
1
để tiếp tục, ngược lại thì chọn nhánh D
2
.
Giả sử tại đây ta chọn nhánh D
1
tiếp tục phát triển thuật toán, thì lúc này
ta cũng phân nhánh D
1
thành hai nhánh D
11
và D
12
. Tiếp tục dùng hàm g để
tính cận dưới cho các nhánh D
11
và D
12

Thuật toán phân nhánh của phương pháp nhánh cận có thể minh họa
bằng sơ đồ sau:

1
β

2
β
11
β

12
β

21
β

22
β

111
β

112
β*
β
Ta xây dựng thuật toán nhánh cận bằng thủ tục đệ quy tổng quát như sau:

D
11
D
2
D
22
D
21
D
12
D
11
1
D
11
2
D
*
else
if
( )
1 2 k
, , ,g a a a
…
≤
f
then
Try(k+1)
End;
End;

2.1.1 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 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.
+ Mục tiêu 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.
+ Mục tiêu 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.
2.1.2 Kế hoạch và nội dung dạy học
Chương trình tin học lớp 10 chuyên tin gồm 123 tiết, trong đó có 70 tiết
dành cho nội dung cơ bản và 53 tiết dành cho nội dung chuyên sâu.
- Nội dung cơ bản 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
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 bao gồm hai chủ đề mở rộng và chuyên sâu:
Ngôn ngữ lập trình và Phân tích, thiết kế và cài đặt giải thuật.
+ Nội dung chuyên sâu Ngôn ngữ lập trình sử dụng ngôn ngữ lập trình
Free Pascal để mô tả nội dung kiến thức, kĩ năng cần truyền đạt, tuy nhiên khi

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.
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.
18
TT Nội dung (20 tiết) Mức độ cần đạt
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ể

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.
20
TT Nội dung (20 tiết) Mức độ cần đạ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