TS Lương Hoài Nam đề xuất dùng thuật toán tuyển sinh

Trong một kỳ tuyển sinh đại học, cao đẳng, dù ở nước ta hay các nước khác, số lượng thí sinh luôn lớn, từ hàng chục nghìn đến hàng trăm nghìn, thậm chí hàng triệu. Trong thâm tâm, mỗi thí sinh có nhiều nguyện vọng đại học, mỗi nguyện vọng lại có mức độ ưu tiên khác nhau, kiểu như "Tôi ao ước nhất là được vào trường này để học ngành này, còn bét ra thì vào trường kia để học ngành kia". Có nguyện vọng cao nhất, có nguyện vọng thấp nhất và giữa chúng là các nguyện vọng khác.

Trong một kỳ tuyển sinh, số lượng trường tuyển sinh cho các ngành đào tạo cũng là một số lớn, với số lượng các cặp "trường - ngành" từ hàng trăm đến hàng nghìn, thậm chí đến hàng chục nghìn. Trường nào cũng muốn thu hút được học sinh giỏi cho các ngành đào tạo để có chất lượng đầu ra tốt và tạo được uy tín đào tạo đại học tốt.

Tuyển sinh đại học là một việc khó. Để làm tốt nó, phải sử dụng các thuật toán để biến nó từ khó trở nên dễ.

Trong lịch sử tuyển sinh đại học, nước ta từng sử dụng một thuật toán rất đơn giản nhưng khá được việc. Đó là cho phép mỗi thí sinh đăng ký duy nhất một ngành ở duy nhất một trường và xét chọn theo điểm từ trên xuống dưới, cho đến khi lấy đủ chỉ tiêu vào ngành đó của trường đó. Các thí sinh không được nhận vào trường duy nhất đó mặc nhiên trượt đại học. Thuật toán này dễ hiểu, dễ dùng, có thể làm bằng tay, không cần có phần mềm tuyển sinh. Excel đã là xa xỉ.

Nhưng thuật toán tuyển sinh đơn giản đó bất cập ở chỗ làm cho không ít thí sinh giỏi bị trượt đại học vì đăng ký thi vào cặp trường - ngành có mức cạnh tranh cao (mà thí sinh không thể biết trước). Trong khi đó, các học sinh yếu hơn lại đậu đại học vào các cặp trường - ngành có điều kiện tuyển sinh dễ hơn. Một số em giỏi hơn bị trượt đại học có thể vui vẻ vào học ở các trường - ngành tuyển sinh dễ hơn, nhưng thuật toán tuyển sinh áp dụng đã loại bỏ cơ hội của em ngay từ đầu.

Để giải quyết bất cập trên, hầu hết các nước đã cho phép thí sinh đăng ký nhiều nguyện vọng xét tuyển đại học trong một kỳ tuyển sinh. Việc tuyển sinh đại học trở nên phức tạp hơn nhiều và phải dùng thuật toán khác. Đó là thuật toán "Hôn nhân ổn định" (Stable Marriage) do Gale và Shapley (Mỹ) đưa ra vào năm 1962. Đối với cách tuyển sinh tập trung (Bộ Giáo dục chủ trì) và cách tuyển sinh phân tán (mỗi trường tự thực hiện), thuật toán này được sử dụng theo các cách khác nhau.

Ngày cuối nộp hồ xét tuyển đại học đợt 1 ở Đại học Kinh tế Quốc dân. Ảnh: Quỳnh Trang.

Trong trường hợp tuyển sinh tập trung, tôi xin mượn bảng tính Excel để mô tả một cách trực quan khả năng sử dụng thuật toán của Gale và Shapley, theo hình dung của tôi, như sau:

Ký hiệu một cặp "trường - ngành" là TxNy, trong đó T là mã trường, N là mã ngành. Trên một hàng của bảng Excel, điền tất cả cặp TxNy cho tất cả các trường, ngành tuyển sinh trong kỳ. Phía trên mỗi cặp TxNy, ghi tất cả điều kiện tuyển sinh vào cặp “trường - ngành” đó (khối thi, điểm thi tối thiểu của từng môn thi, tổng điểm thi tối thiểu của các môn thi, tổng số chỉ tiêu tuyển sinh…). Cho tất cả thí sinh cùng với kết quả thi của họ, tất cả nguyện vọng tuyển sinh của họ và thứ tự ưu tiên của mỗi nguyện vọng vào một “Đám mây thí sinh”. Kết thúc việc nhập thông tin đầu vào ở đây.

Chạy một bộ lệnh trên Nguyện vọng thứ nhất để “nhặt” từ Đám mây thí sinh vào mỗi một cột và tất cả các cột TxNy các thí sinh đạt điều kiện tuyển sinh, theo kết quả thi từ cao xuống thấp, cho đến khi mỗi cột đạt đủ chỉ tiêu tuyển sinh (hoặc cho đến khi không tìm được thêm thí sinh đạt điều kiện tuyển sinh theo Nguyện vọng thứ nhất nữa). Lập một Danh sách trúng tuyển sơ bộ cho mỗi cột TxNy, đồng thời, đánh đấu “Từ chối” tất cả các thí sinh khác có Nguyện vọng thứ nhất vào các cột.

Chạy một bộ lệnh trên Nguyện vọng thứ hai của Những người bị từ chối ở Nguyện vọng thứ nhất theo cách tương tự như trên và điều chỉnh Danh sách trúng tuyển sơ bộ ở mỗi cột trên cơ sở Danh sách trúng tuyển sơ bộ được lập theo Nguyện vọng thứ nhất và các thí sinh mới đạt điều kiện tuyển sinh theo Nguyện vọng thứ hai, xếp theo kết quả thi của các thí sinh từ cao xuống thấp, cho đến khi mỗi cột đạt đủ chỉ tiêu tuyển sinh (hoặc cho đến khi không tìm được thêm thí sinh đạt điều kiện tuyển sinh theo Nguyện vọng thứ hai trong số Những người bị từ chối ở Nguyện vọng thứ nhất).

Tiếp tục làm tương tự theo Nguyện vọng thứ ba, Nguyện vọng thứ tư,… và kết thúc ở nguyện Nguyện vọng thứ “n”. Đó là khi mà mỗi một thí sinh hoặc là đã nằm ở các Danh sách trúng tuyển sơ bộ, hoặc đã bị tất cả các cặp TxNy, mà thí sinh đó đăng ký đánh dấu “Từ chối”. Sau bước thứ “n”, các Danh sách trúng tuyển sơ bộ ở các cột sẽ trở thành các Danh sách trúng tuyển chính thức. Tất cả các thí sinh còn lại trong Đám mây thí sinh là những thí sinh trượt đại học trong kỳ tuyển sinh.

Để kiểm tra tính chính xác của việc tuyển sinh, cần “chạy” chương trình nhiều lần và đối chiếu kết quả giữa các lần. Về nguyên tắc, kết quả tuyển sinh trong tất cả các lần thực hiện phải tuyệt đối giống nhau. Mặc dù vậy, khi sử dụng thuật toán tuyển sinh này, vẫn có thể phát sinh một số trường hợp ngoại lệ, cần sự cân nhắc và can thiệp của con người.

Trong trường hợp tuyển sinh phân tán (các trường tự tuyển sinh, Bộ Giáo dục không can thiệp), việc áp dụng thuật toán này phức tạp hơn. Lý do là mỗi trường biết việc thí sinh đăng ký vào một hoặc một số cặp TxNy của trường mình, nhưng lại không biết thí sinh còn đăng ký tuyển sinh vào những trường khác, cũng không biết mức độ ưu tiên của từng nguyện vọng của thí sinh. Việc tuyển sinh trong trường hợp đó không thể kết thúc ngay trong một đợt, mà phải qua nhiều đợt.

Tôi xin sử dụng ngôn ngữ mô tả rất sinh động và thú vị của GS Vũ Hà Văn trong bài viết “Lấy người mình yêu và… không bỏ được”: “Trong bước thứ nhất, mỗi anh chàng sẽ ngỏ lời với cô gái mà anh ta thích nhất. Tất nhiên, cô nào sáng giá sẽ có nhiều cây si. Mỗi cô gái sẽ trả lời một cách lửng lơ “Để tớ xem!”, với anh chàng sáng giá nhất trong những cây si, và đá đít thẳng thừng những chàng còn lại. Sau bước này, nàng coi như có hẹn ước với cây si cao nhất đó, và chàng cũng coi như có hẹn ước với nàng.

Trong những vòng tiếp theo, mỗi chàng trai chưa có hẹn ước sẽ ngỏ lời với cô gái mà anh ta thích nhất vẫn còn nằm trong danh sách những cô chưa đá đít anh ấy. Anh chàng sẽ không quan tâm là cô gái đó đã có hẹn ước hay chưa. (Chiến thuật mặt dày này được ứng dụng tương đối hiệu quả sau khi thuật toán “bố mẹ đặt đâu con ngồi đấy” trở nên lỗi thời trong một số năm gần đây.) Về phần các cô gái, nếu được một anh chàng mới ngỏ lời, nàng sẽ cân nhắc so sánh với cây si hiện có (nếu có), và sẽ giữ lại cây cao điểm hơn”.

Chúng ta có thể thay các chàng bằng các thí sinh, còn các nàng bằng các trường đại học. Tất nhiên, trong trường hợp tuyển sinh phân tán, các trường đại học còn sử dụng các phương pháp tuyển sinh khác. Do trường toàn quyền quyết định việc tuyển sinh, họ hoàn toàn có thể xét và xác nhận kết quả tuyển sinh với từng thí sinh đăng ký vào trường mình, mà không quá phụ thuộc vào thuật toán tuyển sinh như trong trường hợp tuyển sinh tập trung.

TS Lương Hoài Nam