LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai
công bố trong bất kỳ công trình nào khác.
TÁC GIẢ
Đặng Ngọc Tuấn
MỤC LỤC
LỜI CAM ĐOAN i
MỤC LỤC ii
DANH MỤC CÁC TỪ VIẾT TẮT v
DANH MỤC CÁC BẢNG vi
DANH MỤC CÁC HÌNH vii
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
Việc PCCT vào lớp 10 THPT tại tỉnh Quảng Bình là một vấn đề tuy cũ nhưng
chưa có phần mềm nên dẫn đến tốn nhiều thời gian và công sức, bên cạnh đó để
đảm bảo quy chế, quy định là vấn đề hết sức khó khăn. Vì PCCT tại tỉnh Quảng
Bình có những đặc thù riêng biệt: ngoài những quy định của Bộ GDĐT, tại tỉnh
Quảng Bình còn có thêm nhiều yêu cầu, ràng buộc, nên tất cả các khâu đều phải
làm thủ công, dẫn đến kết quả chưa tối ưu, còn vi phạm quy chế, quy định 1
2. Mục tiêu và nhiệm vụ nghiên cứu 2
2.1. Mục tiêu 2
2.2. Nhiệm vụ 3
3. Phương pháp nghiên cứu 3
3.1. Tư liệu 3
3.2. Phân tích 3
3.3. Thực nghiệm 3
4. Ý nghĩa khoa học và thực tiễn của đề tài 3
4.1. Về mặt lý thuyết 3
4.2. Về mặt thực tiễn 4
5. Nội dung của luận văn 4

2.3.10. Sơ đồ quan hệ giữa các bảng 64
2.4. TỔNG KẾT CHƯƠNG 2 65
CHƯƠNG 3 66
XÂY DỰNG CHƯƠNG TRÌNH VÀ THỬ NGHIỆM 66
3.1. THIẾT KẾ CHI TIẾT CÁC THUẬT TOÁN 66
3.1.1. Quản lý PCCT 66
3.1.2. Giải pháp chính cho bài toán PCCT 67
3.1.3. Kết hợp thuật toán cặp ghép và tham lam trong bài toán PCCT 68
3.1.4. Dữ liệu chính bài toán PCCT lớp 10 THPT 73
3.2.4. Thử nghiệm thực tế với dữ liệu kỳ thi tuyển sinh vào lớp 10 THPT.78
83
3.2.5. Đánh giá phần mềm 84
KẾT LUẬN 87
1. Kết quả đạt được 87
2. Hạn chế 88
3. Hướng phát triển 88
TÀI LIỆU THAM KHẢO 90
Phụ lục 1 92
QUYẾT ĐỊNH CÔNG NHẬN KẾT QUẢ HỘI THI SÁNG TẠO KỸ THUẬT
TỈNH QUẢNG BÌNH LẦN THỨ V (2012-2013) 92
Phụ lục 2 93
GIỚI THIỆU CHƯƠNG TRÌNH 93
1. YÊU CẦU HỆ THỐNG 93
2. CÁC GIAO DIỆN CỦA PHẦN MỀM PCCT 93
DANH MỤC CÁC TỪ VIẾT TẮT
THPT: Trung học phổ thông.
THCS: Trung học cơ sở.
GDĐT: Giáo dục và Đào tạo.
PCCT: Phân công coi thi.
HĐCT: HĐCT.

2.10.
Biểu đồ tuần tự Usecase “Phân công CTHĐ” 58
Hình 2.11. Biểu đồ hoạt động Usecase “Quản lý danh sách CTHĐ” 59
Hình 2.12. Biểu đồ hoạt động Usecase“Nhập trường CT đã coi thi” 59
Hình 2.13. Biểu đồ hoạt động Usecase “Phân công CTHĐ” 60
Hình 2.14. Biểu đồ trạng thái đối tượng GV 60
Hình 2.15. Sơ đồ quan hệ giữa các bảng. 65
Hình 3.1. Quy trình PCCT lớp 10 THPT. 66
Hình 3.2. Giải pháp cho bài toán PCCT. 69
Hình 3.3. Thuật toán cặp ghép PCCT. 70
Hình 3.4.
Sơ đồ ghép cặp GV có tổng số khoảng cách di chuyển
ngắn nhất.
71
Hình 3.5.
Thuật toán tham lam PCCT cho nhóm GV của 1 trường
có số GV nhỏ hơn 5.
72
Hình 3.6. Quy trình PCCT lớp 10 THPT bằng phần mềm. 76
Hình 3.7. Bảng thống kê số lượng GT theo từng hội đồng. 77
Hình 3.8. Phân công thủ công. 78
Hình 3.9. Danh sách HĐCT cho từng hội đồng. 82
Hình
3.10.
Danh sách CB, GV tham gia coi thi của từng trường. 82
1
MỞ ĐẦU
1. Lý do chọn đề tài
Việc PCCT vào lớp 10 THPT tại tỉnh Quảng Bình là một vấn đề tuy cũ
nhưng chưa có phần mềm nên dẫn đến tốn nhiều thời gian và công sức, bên

thực hiện được và cho ra kết quả tương đối tốt, nhưng phải mất nhiều thời
gian và ít nhất phải có kinh nghiệm xếp GT nếu không muốn có sai sót xảy ra,
chẳng hạn như: chỗ này thừa người, chỗ khác lại thiếu, sai chức danh, sai địa
điểm,
Ngoài các ràng buộc trên, việc giải quyết chế độ cho một số CB GV một
cách khác nhau, một số người phải coi thi gần vì lí do phải chăm sóc người
ốm, thai nghén hoặc con nhỏ, nên việc xếp coi thi cũng có nhiều điểm khác so
với các đơn vị khác. Chính vì lý do này, đề tài nghiên cứu các thuật toán và áp
dụng nó để làm sao thỏa mãn một cách tốt nhất các nhu cầu cần thiết, hợp lý
của GV.
Xuất phát từ những lý do trên, tôi đã chọn đề tài “Nghiên cứu xây dựng
hệ thống hỗ trợ PCCT tuyển sinh vào lớp 10 THPT tại tỉnh Quảng Bình”
ứng dụng tại Sở GDĐT Quảng Bình, có giải pháp và chương trình, sản phẩm
cụ thể làm đề tài luận văn tốt nghiệp thạc sĩ của mình. Chương trình được xây
dựng và ứng dụng sẽ giúp hoàn thiện hơn kiến thức được học và có ý nghĩa
khoa học, thực tiễn cao.
2. Mục tiêu và nhiệm vụ nghiên cứu
2.1. Mục tiêu
Hoàn thành sản phẩm là một chương trình PCCT tuyển sinh vào lớp 10
THPT tại tỉnh Quảng Bình.
3
Tiếp tục phát triển ứng dụng chương trình PCCT tuyển sinh vào lớp 10
THPT trên toàn quốc.
2.2. Nhiệm vụ
Phân tích các đặc thù chung và riêng biệt, đề ra giải pháp hợp lý trong
việc xây dựng và triển khai hệ thống.
Nghiên cứu kết hợp các thuật toán để giải quyết bài toán PCCT tuyển
sinh vào lớp 10 THPT.
Phân tích, đánh giá và đề ra giải pháp PCCT một cách tự động và chính
xác.

chương trình này là trình bày các Usecase và các luồng thao tác của các
Usecase đó. Ngoài ra, chương này còn trình bày thiết kế các bảng dữ liệu từ
các đối tượng tham gia trong hệ thống và mối quan hệ giữa các bảng.
Chương 3. Xây dựng chương trình và thử nghiệm
Triển khai một chương trình máy tính cài đặt phần mềm PCCT được thể
hiện chi tiết; thử nghiệm và đánh giá các kết quả đạt được thông qua việc áp
dụng thuật toán cặp ghép và tham lam, tự động hóa bài toán PCCT tuyển sinh
và các chức năng tinh chỉnh thủ công, nhằm tạo ra một bảng PCCT tuyển sinh
tinh về chất, áp dụng tốt cho Sở GDĐT Quảng Bình và các Sở GDĐT trên
toàn quốc.
5
CHƯƠNG 1
BÀI TOÁN PCCT TUYỂN SINH VÀO LỚP 10 THPT TẠI
TỈNH QUẢNG BÌNH
1.1. GIỚI THIỆU
Như chúng ta đã biết, những năm gần đây tại các tỉnh thành trên cả nước
và ở tỉnh Quảng Bình nói riêng luôn tổ chức các kỳ thi tuyển sinh vào lớp 10
THPT. Để chuẩn bị và tổ chức kỳ thi tuyển sinh vào lớp 10 THPT, các Sở
GDĐT các tỉnh thành nói chung và tỉnh Quảng Bình nói riêng luôn ra Quyết
định thành lập các HĐCT. Tuy nhiên, việc ra Quyết định thành lập các HĐCT
là một công việc rất phức tạp, gặp nhiều khó khăn và tốn nhiều thời gian. Một
trong số khó khăn lớn nhất đó là bài toán phân công GT cho các HĐCT, đây
là sản phẩm chính là cơ sở để lãnh đạo ra Quyết định thành lập các HĐCT.
Bài toán PCCT tuyển sinh vào lớp 10 THPT tại tỉnh Quảng Bình tuy cũ,
nhưng chưa có phần mềm giải quyết nên phải làm thủ công. Bài toán này
không chỉ được đo bằng độ phức tạp của vấn đề, mà còn ở tính thực tiễn, khả
năng áp dụng rất cao trên thực tế. Bất cứ một Sở GDĐT nào, bài toán phân
công GT cho các HĐCT là một việc làm quan trọng và luôn có sự quan tâm
của lãnh đạo Sở, CB, GV, nhân viên toàn ngành và xã hội. Chính vì lẽ đó bài
toán PCCT tuyển sinh vào lớp 10 THPT trở thành một trong những vấn đề

phức tạp ở các ràng buộc GV chồng chéo lên nhau mà còn giữa các HĐCT
này với các hội đồng khác, giữa GV trường này với GV trường khác, giữa GV
và CT các hội đồng thi. Qui mô của các HĐCT rất đa dạng với những yêu cầu
7
đặc biệt khác nhau: số lượng thí sinh, số phòng thi, số lượng GT, lãnh đạo hội
đồng, địa điểm đặt hội đồng, điều kiện kinh tế xã hội …
Từ những vấn đề khó khăn trên trong việc giải quyết bài toán PCCT
tuyển sinh vào lớp 10 THPT tại tỉnh Quảng Bình trước đây chủ yếu phải phân
công bằng tay, tức là phải làm thủ công; việc phân công GT bằng tay vừa khó
vừa dễ, với công cụ sử dụng chủ yếu là:
- Máy vi tính, phần mềm Word, Excel, thước, tẩy, bút chì, giấy trắng.
- Dùng phương pháp cắt, dán thủ công danh sách GV theo số lượng theo
từng hội đồng.
- Luôn phải đề phòng khỏi bị phân công một GV coi thi tại nhiều hội
đồng, GV hai trường coi thi chéo nhau, trùng địa điểm coi thi năm trước và
năm sau, tỉ lệ GV bộ môn không đảm bảo đúng yêu cầu.
- Phải tư duy liền mạch nếu không quên ngay.
- Kinh nghiệm nhiều năm được tích lũy.
- Phải mất rất nhiều thời gian và công sức.
Từ đó có thể đưa ra bản danh sách phân công GT coi thi tại các HĐCT
tương đối dùng được, sau đó phải qua rà soát, kiểm tra, tinh chỉnh và cuối
cùng cho ra được một sản phẩm tương đối tốt, áp dụng được trong thực tế
nhưng phải mất rất nhiều thời gian và công sức. Nhất là người làm công việc
phân công GT phải có kinh nghiệm, hiểu rõ về qui trình và qui chế nghiệp vụ
tổ chức các kỳ thi; qui mô kỳ thi và qui mô các HĐCT, nắm nhiều vấn đề liên
quan khác.
1.2.2. Dùng phần mềm để PCCT tuyển sinh vào lớp 10 THPT
Hiện nay có một số phần mềm dùng để PCCT của một số tỉnh, hay một
số tổ chức khác nhưng hiệu quả không cao, không đáp ứng được yêu cầu của
Sở GDĐT Quảng Bình. Chỉ mới thực hiện theo Quy chế của Bộ GDĐT, chưa

việc thực hiện đúng, chính xác, còn phải tốt hơn, nhanh hơn và hiệu quả hơn
công việc phân công bằng tay mà chúng ta vẫn phải làm. Sở GDĐT Quảng
Bình có nhiều đặc trưng riêng như địa hình khó khăn, khoảng cách giữa các
HĐCT với nhau dài. Ngoài ra việc PCCT tại mỗi hội đồng phải đảm bảo các
yêu cầu tương đương nhau về: Độ tuổi trung bình của các hội đồng, giới tính
(tỷ lệ nam nữ), khoảng cách ngắn nhất (GV coi thi gần đơn vị công tác nhất);
tỷ lệ GV THPT, THCS (điều động hết GV THPT, còn lại điều động GV -
THCS, tỷ lệ GV tương đương nhau); CB, GV không đến những đơn vị mà
năm trước đã đến coi thi, không đổi chéo GV coi thi giữa các trường (Ví dụ:
Trường THPT Minh Hóa đến coi thi trường THPT Tuyên Hóa thì GV trường
THPT Tuyên Hóa không đến coi thi tại trường THPT Minh Hóa và ngược
lại). GV không coi thi tại các hội đồng đặt trên huyện, thị, thành phố nơi công
tác. GV không coi thi tại Hội đồng mà CTHĐ là Lãnh đạo đơn vị mình đang
công tác…
Thông thường, công việc này được làm bằng tay, tất nhiên chúng ta luôn
thực hiện được và cho ra kết quả tương đối tốt, nhưng phải mất nhiều thời
gian và ít nhất phải có kinh nghiệm xếp GT nếu không muốn có sai sót xảy ra,
chẳng hạn như: chỗ này thừa người, chỗ khác lại thiếu, sai chức danh, sai địa
điểm,
Ngoài các ràng buộc trên, việc giải quyết chế độ cho một số CB GV một
cách khác nhau, một số người phải coi thi gần vì lí do phải chăm sóc người
ốm, thai nghén hoặc con nhỏ, nên việc xếp coi thi cũng có nhiều điểm khác so
với các đơn vị khác. Chính vì lý do này, đề tài nghiên cứu các thuật toán và áp
dụng nó để làm sao thỏa mãn một cách tốt nhất các nhu cầu của GV.
1.3.2. Phát biểu bài toán
Ngay khi vấn đề được đặt ra, chúng ta đã thấy bài toán phải được giải
quyết trên hai nền tảng cơ bản: nghiệp vụ và kỹ thuật. Để tạo ra những sản
10
phẩm phù hợp với thực tiễn, nhu cầu của ngành, của bài toán PCCT tuyển
sinh vào lớp 10 THPT tại tỉnh Quảng Bình, yêu cầu dữ liệu của bài toán phải

+ Danh sách CB, GV đoàn thanh tra.
+ Danh sách CB, GV làm nhiệm vụ ra đề, in sao đề.
+ Danh sách các thành viên làm nhiệm vụ bảo vệ, y tế, phục vụ kỳ thi
của từng HĐCT.
+ Quyết định thành lập các HĐCT năm trước.
+ Danh sách phân công nhiệm vụ tại các hội đồng thi năm trước.
+ Danh sách điều động CB, GV của từng đơn vị năm trước.
+ Bảng yêu cầu ràng buộc của từng HĐCT.
+ Bảng yêu cầu ràng buộc của CB, GV các trường coi thi.
+ Bảng khoảng cách giữa các HĐCT.
a. Các đối tượng sử dụng
Các đối tượng chính yếu xung quanh mô hình phân công GT coi thi tại
các HĐCT chính là thành phần đầy đủ tính năng của chương trình trong bài
toán. Tất cả được liệt kê như sau:
- CB, GV.
- Trường học.
- HĐCT.
- Phòng thi.
- Môn thi.
- Huyện thị.
- Khoảng cách giữa các hội đồng.
12
b. Mối quan hệ giữa các đối tượng
Dựa trên Quyết định thành lập các HĐCT, thể hiện rõ thông tin các đối
tượng liên quan nhau ở tại thời điểm tổ chức kỳ thi. Hay nói cách khác Quyết
định thành lập HĐCT là phần thể hiện mối quan hệ của các đối tượng: HĐCT,
CB, GV, nhân viên làm nhiệm vụ coi thi. Sau này HĐCT đặt tại một điểm cụ
thể với số lượng phòng thi cụ thể tương ứng số lượng thí sinh dự thi cụ thể, gây
phát sinh mới, tạo quan hệ thứ hai giữa GT làm nhiệm vụ thi và phòng thi. Đó
là mối quan hệ cơ sở.

Đối tượng Trường học
Đối tượng trường học được hiểu là một trường THPT hoặc trường THCS
và THPT hoặc có thể là đơn vị Phòng GDĐT. Mỗi đơn vị có số lượng CB,
GV, nhân viên đề nghị làm nhiệm vụ coi thi khác nhau, do đó cần phải có các
thông tin cần thiết về các đơn vị cụ thể để làm dữ liệu ràng buộc cho bài toán.
+ Tên đơn vị.
+ Mã đơn vị.
+ Địa chỉ.
+ Mã huyện, thị/thành phố nơi đơn vị đóng.
Đối tượng CB, GV, nhân viên
Mỗi CB, GV, nhân viên có một hồ sơ cá nhân riêng, do đó phải nhập đầy
đủ các thông tin cần thiết theo mẫu của bài toán.
+ Họ và tên.
+ Ngày sinh.
+ Giới tính.
+ Môn dạy.
+ Chức vụ.
14
+ Mã đơn vị công tác.
+ Mã Loại GT.
+ Mã Nhóm GT.
+ Số năm tham gia giảng dạy.
+ Mã đề nghị làm nhiệm vụ tại HĐCT.
+ Mã đề nghị làm nhiệm vụ tại hội đồng chấm thi.
+ Có người thân thi tại.
+ Lý do xin nghỉ coi thi, chấm thi.
Đối tượng HĐCT
Trong quá trình tổ chức kỳ thi theo một quy định chung nào đó mà các
HĐCT phải xảy ra cùng một thời điểm. Các HĐCT phải có đầy đủ thông tin
cần thiết, các thông tin này cần được nhập vào làm dữ liệu ràng buộc cho bài

+ Ghi chú.
Đối tượng Loại GT
Mỗi CB, GV, nhân viên khi nhận nhiệm vụ tại mỗi Hội đồng đều giữ
những chức vụ khác nhau: CTHĐ, Phó CTHĐ, TK, GT … Vì vậy, đối tượng
này cần lưu thông tin về:
+ Mã Loại GT.
+ Tên Loại GT.
Đối tượng Loại GV
Mỗi CB, GV được đề nghị PCCT đều giữ một vai trò nào đó tại đơn vị
mình công tác như: Hiệu trưởng, phó hiệu trưởng, Tổ trưởng, GV, CB phòng
sở Vì vậy, đối tượng này cần lưu thông tin về:
+ Mã Loại GV.
+ Tên Loại GV.
16
Đối tượng Nhóm GT
GV mỗi đơn vị được phân công theo nhóm tới các Hội đồng để coi thi.
Vì vậy, có rất nhiều Nhóm GT được chia và PCCT. Các thông tin cụ thể của
đối tượng này:
+ Mã Nhóm GT.
+ Tên Nhóm GT.
+ Mã đơn vị.
+ Mã hội đồng đến coi thi.
Đối tượng Khoảng cách giữa các HĐCT.
Mỗi lần tổ chức thi, có rất nhiều HĐCT. Mỗi hội đồng đều được đặt tại
các đơn vị trường học. Trong ràng buộc của bài toán có một ràng buộc rất
quan trọng đó là phân công GV coi thi sao cho khoảng cách là tối ưu nhất.
+ Mã Khoảng cách.
+ Mã đơn vị.
+ Mã Hội đồng.
+ Khoảng cách.

phòng thi là những người không dạy môn đang thi.
1.3.5. Các yêu cầu chức năng
a. Chức năng lưu trữ
Tất cả các thông tin của đối tượng được phép lưu trữ dưới dạng dữ liệu
cụ thể như sau:
+ GV (Họ và tên, ngày sinh, giới tính, môn dạy, năm vào ngành, đơn vị
công tác, chức vụ).
18
+ HĐCT (Tên hội đồng, địa điểm đặt hội đồng, qui mô hội đồng, số
lượng phòng thi, số lượng thí sinh, số lượng CB; GV; nhân viên làm nhiệm vụ
coi thi).
+ Danh sách lãnh đạo HĐCT (Họ và tên, ngày sinh, đơn vị, chức vụ,
chức vụ hội đồng, tên hội đồng, địa chỉ đặt hội đồng ).
+ Danh sách GT tại HĐCT (Họ và tên, ngày sinh, giới tính, môn dạy,
năm vào ngành, đơn vị công tác, chức vụ, HĐCT).
+ Bảng mã phân công GT (Tên hội đồng, mã hội đồng, số lượng phòng
thi, số lượng GT cần, mã CT, mã đơn vị n, số lượng GT m, mã đơn vị dp n, số
lượng GT dp m).
+ Bảng mã hội đồng (Tên hội đồng, địa điểm, mã hội đồng, qui mô hội
đồng).
+ Khoảng cách giữa HĐCT và đơn vị công tác.
b. Chức năng tra cứu
Ngoài thông tin các đối tượng được lưu trữ, chương trình còn thể hiện
những bảng kết quả thực thi, trong quá trình phân công GT coi thi tuyển sinh
vào lớp 10 THPT tại tỉnh Quảng Bình gồm các tra cứu sau:
+ Danh sách HĐCT.
+ Danh sách GV làm nhiệm vụ coi thi tại các hội đồng thi.
+ Danh sách Lãnh đạo HĐCT tại các hội đồng thi.
+ Qui mô các HĐCT.
+ Thống kê độ tuổi trung bình của từng hội đồng thi.