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 cạnh đó để đảm bảo quy chế, quy định là vấn đề hết
sức khó khăn.
- Việc ứng dụng công nghệ thông tin vào công tác quản lý giáo
dục hiện nay rất phổ biến.
- Nếu như có phần mềm PCCT vào lớp 10 THPT sẽ tiết kiệm
được rất nhiều chi phí, thời gian và nhân lực. Ngoài ra, nó còn giúp
tăng độ chính xác hiệu quả và đảm bảo tính khách quan.
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.
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ý một cách tự động 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.
Xây dựng sản phẩm hoàn thiện sử dụng tại Sở GDĐT Quảng
Bình.
3. Phương pháp nghiên cứu
3.1. Tư liệu
2
Tổng hợp các tài liệu liên quan đến thuật toán, cũng như các
quy chế của Bộ GDĐT và quy định của Sở GDĐT Quảng Bình.
3.2. Phân tích

PCCT tuyển sinh vào lớp 10 THPT tại tỉnh Quảng Bình, chẳng hạn
GV một trường được chia ra nhiều nhóm và đi coi thi tại nhiều hội
đồng khác nhau, phân công sao cho tương ứng về số lượng, tránh
phân công một người nhiều việc tại nhiều hội đồng. CB, GV, nhân
viên của tất cả các đơn vị phải thực hiện nhiệm vụ coi thi theo quy
định trong bảng phân công, đảm bảo quy chế thi của Bộ GDĐT và
quy định của Sở GDĐT Quảng Bình. Vấn đề của bài toán là ngoài
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 còn 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 … tại mỗi Hội đồng.
4
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 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 được hiển thị đầy đủ, không thiếu sót,
không bị sai lệch, hệ thống các ràng buộc của bài toán phải logic,
trùng khớp với nhau, không chồng chéo và phải phù hợp với yêu cầu
đề ra. Phần kỹ thuật cũng vậy, phải xử lý tất cả những yêu cầu chung
cũng như những yêu cầu riêng biệt từ các đối tượng gửi đến, chúng
được xem như là thành phần ràng buộc của bài toán, bắt buộc vấn đề
phải thỏa mãn và đáp ứng hoàn toàn. Vì vậy, tôi sẽ phân tích bài toán
trên hai thành phần đó.
1.3.3. Dữ liệu bài toán

b. Chức năng tra cứu
c. Chức năng tính toán
d. Chức năng chiết xuất
1.3.6. Các yêu cầu phi chức năng
- Giao diện đồ họa gần gũi, dễ sử dụng.
- Dữ liệu dạng Excel có thể trực tiếp truy xuất bằng chương
trình khác.
1.4. CÁC CÔNG CỤ HỖ TRỢ HIỆN TẠI
1.5. MỘT SỐ THUẬT TOÁN SỬ DỤNG ĐỂ GIẢI QUYẾT BÀI
TOÁN PCCT
1.5.1. Giới thiệu
6
Chúng tôi đã chọn kết hợp thuật toán cặp ghép và thuật toán
tham lam giải quyết bài toán PCCT tuyển sinh vào lớp 10 THPT.
1.5.2. Thuật toán cặp ghép
a. Các khái niệm
Ta gọi những cạnh trọng số 0 của G là những 0_cạnh. Xét một
bộ ghép M chỉ gồm những 0_cạnh.
- Những đỉnh thuộc M gọi là những đỉnh đã ghép, những đỉnh
còn lại gọi là những đỉnh chưa ghép.
- Những 0_cạnh thuộc M gọi là những 0_cạnh đã ghép, những
0_cạnh còn lại là những 0_ cạnh chưa ghép.
- Nếu ta định hướng lại các 0_cạnh như sau: Những 0_cạnh
chưa ghép cho hướng từ tập X sang tập Y, những 0_cạnh đã ghép
cho hướng từ tập Y về tập X.
- Đường pha (Alternating Path) là một đường đi cơ bản xuất
phát từ một X_đỉnh chưa ghép đi theo các 0_cạnh đã định hướng ở
trên.
- Một đường mở (Augmenting Path) là một đường pha đi từ
một X đỉnh chưa ghép tới một Y đỉnh chưa ghép.

VisitedY, điều này vô lý.
Biến đổi đồ thị G như sau: Với
∀
x
∈
VisitedX, trừ Δ vào
trọng số những cạnh liên thuộc với x, Với
∀
y
∈
VisitedY, cộng Δ
vào trọng số những cạnh liên thuộc với y.
Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất
phát ở x* cho tới khi tìm ra đường mở.
Bước 3: Sau bước 2 thì mọi X_đỉnh đều được ghép, in kết quả
về bộ ghép tìm được.
Mô hình cài đặt của thuật toán Hungari có thể viết như sau:
<Khởi tạo: M := Ø…>;
for (x*
∈
X) do
begin
repeat
8
<Tìm đường mở xuất phát ở x*>;
if <Không tìm thấy đường mở> then <Biến đổi đồ thị G: Chọn
Δ := …>;
until <Tìm thấy đường mở>;
<Dọc theo đường mở, loại bỏ những cạnh đã ghép khỏi M và
thêm vào M những cạnh chưa ghép>;

bài toán theo kiểu metaheuristic để tìm kiếm lựa chọn tối ưu địa
phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục.
Tính chất lựa chọn tham lam
Chúng ta có thể lựa chọn giải pháp nào được cho là tốt nhất ở
thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực
hiện lựa chọn vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ
thuộc vào các lựa chọn trước đó. Nhưng nó không thể phụ thuộc vào
một lựa chọn nào trong tương lai hay phụ thuộc vào lời giải của các
bài toán con. Thuật toán tiến triển theo kiểu thực hiện các chọn lựa
theo một vòng lặp, cùng lúc đó thu nhỏ bài toán đã cho về một bài
toán con nhỏ hơn.
b. Thuật toán
Cấu trúc tổng quát của thuật toán
Thamlam(C:tập hợp các ứng cử viên)
//hàm trả về giải pháp tối ưu, gồm các ứng cử viên
Begin
S = Ø //S là giải pháp tối ưu
10
While ( C
≠
Ø và S chưa là giải pháp) do
X = chọn( C) // chọn x từ tập c theo tiêu chí của hàm chọn
C = C – {x}
If (S

{x} có triển vọng là giải pháp) then S:=S

{x}
Endif
Endwhile

12
2.3.1. Bảng Người dùng
2.3.2. Bảng GV
2.3.3. Bảng Hội đồng
2.3.4. Bảng Khoảng cách
2.3.5. Bảng Loại GV
2.3.6. Bảng Loại GT
2.3.7. Bảng Huyện
2.3.8. Bảng Phòng thi
2.3.9. Bảng Trường học
2.3.10. Sơ đồ quan hệ giữa các bảng
Hình 2.15. Sơ đồ quan hệ giữa các bảng
13
2.4. TỔNG KẾT CHƯƠNG 2
Trong chương này, tôi đã trình bày quá trình sử dụng ngôn
ngữ UML để phân tích và thiết kế CSDL cho hệ thống phần mềm.
Nội dung chính của 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.
14
CHƯƠNG 3
XÂY DỰNG CHƯƠNG TRÌNH VÀ THỬ NGHIỆM
3.1. THIẾT KẾ CHI TIẾT CÁC THUẬT TOÁN
3.1.1. Quản lý PCCT
Quy chế về việc PCCT THPT do Bộ Giáo dục và Đào tạo ban
hành chỉ nêu rõ các bước triển khai và yêu cầu chung từng bước. Tuy
nhiên, việc triển khai PCCT THPT tại mỗi tỉnh lại có từng đặc thù
khác nhau nên việc áp dụng quy chế của Bộ Giáo dục và Đào tạo
mỗi nơi một khác. Vì vậy, tại Việt Nam mỗi tỉnh lại có quy định

Đúng
Sai
Dùng thuật toán Cặp ghép để ghép từng cặp GV – Hội đồng để
phân công CTHĐ
Dùng thuật toán Cặp ghép để ghép từng GV – Hội đồng để
phân công Phó CTHĐ
Dùng thuật toán Cặp ghép để ghép từng GV – Hội đồng để
phân công TK Hội đồng
16
3.1.3. Kết hợp thuật toán cặp ghép và tham lam trong bài
toán PCCT
a. Thuật toán cặp ghép
Từ bảng danh sách GV, sau khi phân công CT, PCT và TK
Hội đồng, ta lọc những GV còn lại, đồng thời chúng ta kiểm tra các
ràng buộc nếu thỏa mãn ta dùng thuật toán cặp ghép PCCT cho
những GV này. Thuật toán được mô tả qua hình 3.3.
Hình 3.3. Thuật toán cặp ghép PCCT
Khởi tạo dữ liệu
Tìm đường mở có
trong số = min
Tìm
thấy
Mở rộng đường
mở
Hoàn
tất ?
Đúng
Sai
Kết thúc
Đúng

Hội đồng 4
Danh sách GV
18
c. Thuật toán tham lam
Sau khi áp dụng thuật toán cặp ghép phân công coi thi cho
những nhóm GV có khoảng cách di chuyển ngắn nhất, chúng ta áp
dụng thuật toán tham lam để giải quyết các GV còn lại, cho ra được
một danh sách coi thi thô của toàn trường được mô tả qua hình 3.5.
Hình 3.5 thể hiện việc ứng dụng thuật toán tham lam để phân
công coi cho những nhóm GV trong một trường có tổng GV nhỏ hơn
5. Lựa chọn tham lam trong trường hợp này là tập các GV trong một
trường có số lượng chưa xét nhỏ hơn 5, ta sắp xếp theo chiều giảm
dần của số lượng, đồng thời giải quyết tất cả các trường này và cho
ra được danh sách PCCT dưới dạng bảng.
Sau bước này ta có thể sử dụng các chức năng tinh chỉnh nhằm tạo ra
một danh sách coi thi tốt nhất dưới dạng bảng, tại đây ta sẽ xuất ra
tệp Excel.
3.2. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ
3.2.1. Phân công tự động hoàn toàn
Nếu không có lỗi dữ liệu đầu vào thì phần mềm sẽ tiến hành
PCCT cho toàn bộ các hội đồng trong thời gian một vài phút.
3.2.2.Tinh chỉnh dữ liệu của các GV tham gia
Do không thể tự động đánh giá các GV bị thay đổi dữ liệu này
là tốt lên hay xấu đi, yêu cầu bắt buộc phải có của một lệnh tinh
chỉnh dữ liệu là cho phép người dùng quan sát các thay đổi trước và
sau khi thực hiện lệnh tinh chỉnh của các GV trung gian. Người
PCCT quan sát và quyết định cuối cùng xem có thực hiện thao tác
tinh chỉnh đó không.
19
3.2.3. Cách thức tinh chỉnh thủ công PCCT lớp 10 THPT

20
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.
3.2.5. Đánh giá phần mềm
a. Cách đánh giá
Căn cứ vào các tiêu chí về ràng buộc bài toán chúng tối có
bảng đánh giá như sau:
TT Tiêu chí ràng buộc Kết quả
1
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
Đạt
2
Khoảng cách ngắn nhất (GV coi thi gần đơn vị
công tác nhất)
Đạt
3 Tỷ lệ GV THPT, THCS Đạt
4
CB, GV không đến những đơn vị mà năm trước
đã đến coi thi
Đạt
5 Không đổi chéo GV coi thi Đạt
6
GV coi thi không dạy cùng trường với CTHĐ coi
thi
Đạt
7 Số lượng GV trùng môn < ½ số lượng phòng thi Đạt
8
Hội đồng tới coi thi khác huyện với trường đang

Đã nghiên cứu, tìm hiểu bài toán một cách đầy đủ, toàn diện
về nội dung; đã phân tích, thiết kế hệ thống và xây dựng cơ sở dữ
liệu đáp ứng tốt các yêu cầu của bài toán.
Kết hợp thuật toán cặp ghép và thuật toán tham lam vào việc
giải quyết bài toán PCCT là khâu đột phá ban đầu cho việc Tin học
hóa toàn bộ việc PCCT tại tỉnh Quảng Bình và có thể ứng dụng cho
các đơn vị trên toàn quốc; cho ra được một sản phẩm PCCT tương
đối tốt với nhiều tính năng nổi trội:
Việc cập nhật, xử lý dữ liệu nhanh với tốc độ gần như tức thời.
Thông tin được thể hiện trên màn hình một cách hợp lý, cho phép
người dùng quan sát từng bước tác nghiệp.
Chương trình đã xử lý được các kỹ thuật đặc thù của việc
PCCT; Phần mềm xếp tự động hoàn toàn, dữ liệu đáp ứng hầu hết
các ràng buộc thông thường của việc PCCT.
Phần mềm đã đưa ra được công cụ tinh chỉnh hợp lý như xếp
tay, chuyển đổi công tác, nhiệm vụ của CT, PCT, TK và GT; Các
công cụ này hoàn toàn được thực hiện bằng các thao tác như chuột,
bàn phím rất đơn giản, thuận tiện với người dùng.
Toàn bộ các module của chương trình được viết bằng ngôn
ngữ C# có giao diện thân thiện với người dùng và toàn bộ hệ thống
thực đơn, giao diện là Tiếng Việt.
23
Phần mềm đã được kiểm nghiệm qua thực tế kỳ thi tuyển sinh
vào lớp 10 THPT năm học 2013-2014, đã được ban tổ chức hội thi
sáng tạo kỹ thuật tỉnh Quảng Bình lần thứ V (2012-2013) công nhận
đạt giải Ba theo Quyết định số 130/QĐ-HTSTKT ngày 15 tháng 10
năm 2013 của Ban tổ chức chức hội thi (Phụ lục 1).
2. Hạn chế
Phần mềm khi đưa vào áp dụng vào thực tế còn các tồn tại như
sau: